Synchronization - Os

Process Synchronization (Continued)

4-1

Bounded Buffer Problem • A classical problem for bounded buffers in operating systems and networking – Producer processes put data items into the buffer – Consumer processes get the data items from the buffer – Shared buffer with n slots to store at most n items – Variable in points to the first empty slot in the butter – Variable out points to the first valid item in the buffer Producer Process

Consumer Process

repeat produce an item in nextp; entry synchronization; buf f er[in] = nextp; in = in + 1 mod n; exit synchronization; remaining section; until false

repeat entry synchronization; nextc = buf f er[out]; out = out + 1 mod n; exit synchronization; consume the item nextc; remaining section; until false

Operating Systems

Process Synchronization (Continued)

Synchronization Required • critical section for operations on shared buffer and its pointers • consumer should be blocked when buffer is empty • producer should be blocked when buffer is full Critical Section • use a semaphore for the critical sections in both producer and consumer Semaphore *mutex = new Semaphore(‘‘mutex’’, 1);

Emptiness Control • Producers reduce the emptiness • Consumers increase the emptiness • There are n empty slots initially • Use a semaphore to block producers when emptiness is reduced to zero Operating Systems

4-2

Process Synchronization (Continued)

Semaphore *nEmpty = new Semaphore(‘‘nEmtpy’’, n);

Fullness Control • Producers increase the fullness • Consumers reduce the fullness • There are 0 full slots initially • Use a semaphore to block consumers when fullness is reduced to zero Semaphore *nFull = new Semaphore(‘‘nFull’’, 0);

Operating Systems

4-3

Process Synchronization (Continued)

4-4

Producer Process

Consumer Process

repeat produce an item in nextp; nEmpty->P(); mutex->P(); buf f er[in] = nextp; in = in + 1 mod n; mutex->V(); nFull->V(); remaining section; until false

repeat nFull->P(); mutex->P(); nextc = buf f er[out]; out = out + 1 mod n; mutex->V(); nEmpty->V(); consume the item nextc; remaining section; until false

Operating Systems

Process Synchronization (Continued)

4-5

The order of semaphore operations is important. • What may happen to the following code? Producer Process

Consumer Process

repeat produce an item in nextp; mutex->P(); nEmpty->P(); buf f er[in] = nextp; in = in + 1 mod n; nFull->V(); mutex->V(); remaining section; until false

repeat mutex->P(); nFull->P(); nextc = buf f er[out]; out = out + 1 mod n; nEmpty->V(); mutex->V(); consume the item nextc; remaining section; until false

Operating Systems

Process Synchronization (Continued)

4-6

• How about this? Producer Process

Consumer Process

repeat produce an item in nextp; nEmpty->P(); mutex->P(); buf f er[in] = nextp; in = in + 1 mod n; nFull->V(); mutex->V(); remaining section; until false

repeat nFull->P(); mutex->P(); nextc = buf f er[out]; out = out + 1 mod n; mutex->V(); nEmpty->V(); consume the item nextc; remaining section; until false

Operating Systems

Process Synchronization (Continued)

4-7

Deadlock • A deadlock is a situation where a set of processes are waiting indefinitely for the events which can only be caused by the processes the same set. • Deadlock is possible when processes uses semaphores for synchronization – two semaphores x and y both initialized to 1 – Two processes A and B

Operating Systems

Process A

Process B

x->P(); y->P(); . . . x->V(); y->V();

y->P(); x->P(); . . . y->V(); x->V();

Process Synchronization (Continued)

Dining Philosopher Problem • a round table with N dining philosophers • one chop-stick between neighboring philosophers • philosophers’ process for (;;) { thinking; pick up both left and right chopstick; eating; put down both left and right chopstick; }

Solution using semaphores • one semaphore with value 1 for each chop-stick • use P() for action of picking up (acquire) chop-stick • use V() for action of putting down (release) chop-stick Possible Deadlock Operating Systems

4-8

Process Synchronization (Continued)

Monitor • high-level ADT for concurrent processes • in conjunction with condition variables • used in modern languages such as Java So, what is a monitor? • A special abstract data type (ADT) whose function (method) invocations are guaranteed to be mutually exclusive. • With an implicit lock (semaphore) to control mutual exclusion

Operating Systems

4-9

Process Synchronization (Continued)

A monitor won’t be useful without condition variables • what if a process running a monitor function (method) cannot proceed? • Will it release the mutex lock before it goes to sleep? • How to wake it up when the condition becomes satisfied? • What its priority compared with the processes waiting at the mutex lock?

Operating Systems

4-10

Process Synchronization (Continued)

Condition Variable • an abstract data type to represent a condition • two operations (methods) – wait(): cause the calling process (thread) to block (wait) at this condition variable – signal(): if there is a process (thread) blocking(waiting) at this condition variable, wake it up; otherwise do nothing • can be implemented by – a semaphore to hold waiting processes and block the calling process, and – a counter to count the number of processes waiting at this condition variable. Semaphore *sem = new Semaphore(‘‘x’’, 0) int count = 0;

Operating Systems

4-11

Process Synchronization (Continued)

But, where does the process stay if it is woken up by another process calling signal() of the condition variable? • it can join the queue at mutex lock by calling mutex->P() (the approach taken by Java) or • it can be put into an internal queue of higher priority in another semaphore called next by calling next->P() What should be done when a process calls wait() of a condition variable x? • the process must pass its exclusiveness to other waiting processes by – releasing mutex lock by calling mutex->V() (as in Java) or – wake up a process waiting at next by calling next->V() • remember the deadlock problem in the bounded buffer problem using semaphore?

Operating Systems

4-12

Process Synchronization (Continued)

Two styles of Monitor • Consider that process P calls signal() of a condition variable and wakes up process Q. • Hoare style – Q continues immediately and P suspends itself by calling mutex->P() or next->P() – advantage: condition is guaranteed to be satisfied when Q resumes – can use if to check the condition (does not need to re-check the condition) – disadvantage: high context-switch overhead • Mesa style – P continues, and Q is moved to mutex or next and continues later – disadvantage: condition may not be satisfied when Q resumes – need while loop to check the condition again – advantage: more efficient

Operating Systems

4-13

Process Synchronization (Continued)

Implementation of Hoare Style Monitor • private data members Semaphore *mutex = new Semaphore(‘‘mt’’, 1); Semaphore *next = new Semaphore(‘‘nx’’, 0); int next-count = 0;

• implementation of condition variables – each condition variable has (1) a semaphore sem initialized with 0 and (2) a counter count initialized with 0. – wait() method count++; if (next-count > 0) next->V() else mutex->V(); sem->P(); count--;

Operating Systems

4-14

Process Synchronization (Continued)

– signal() method if (count > 0) { next-count++; sem->V(); next-P(); next-count--; }

• The code for every method of the monitor mutex->P(); ... body of function ... if next-count > 0 next->V() else mutex->V();

Operating Systems

4-15

Process Synchronization (Continued)

Monitor Bounded Buffer Monitor for Dining Philosophers (figure 6.19)

Operating Systems

4-16