COS 318: Operating SystemsSemaphores, Monitors and Condition Variables2Today’s Topics!Semaphores!Monitors!Mesa-style monitors!Programming idiom!BarriersBounded Buffer Problem3Producer ConsumerBounded Buffer with Sleep and Wakeupproducer() { while (1) { produce an item if (count == N) sleep; count = count + 1; if (count == 1) wakeup(consumer); }}consumer() { while (1) { if (count == 0) sleep(); take an item from buffer count = count – 1; if (count == N-1) wakeup(producer); consume the item }}Bounded Buffer with Sleep and Wakeup!What if consumer is descheduled after reading count?!Lost wakeup problem!Problem: access and test of count not atomicproducer() { while (1) { produce an item if (count == N) sleep; count = count + 1; if (count == 1) wakeup(consumer); }}consumer() { while (1) { if (count == 0) sleep(); take an item from buffer count = count – 1; if (count == N-1) wakeup(producer); consume the item }}6Semaphores (Dijkstra, 1965)!Keep count of number of wakeups saved!Initialization"Initialize a value atomically!P (or Down or Wait) definition"Atomic operation"Wait for semaphore to become positive and then decrementP(s){ P(s){ while (s <= 0) if (--s < 0) ; block(s); s--; }}!V (or Up or Signal) definition"Atomic operation"Increment semaphore by 1V(s){ V(s){ s++; if (++s <= 0)} unblock(s) }Bounded Buffer with Semaphores!Initialization: emptyCount = N; fullCount = 0!Are P(mutex)and V(mutex) necessary?producer() { while (1) { produce an item P(emptyCount); P(mutex); put the item in buffer V(mutex); V(fullCount); }}consumer() { while (1) { P(fullCount); P(mutex); take an item from buffer V(mutex); V(emptyCount); consume the item }}8Interrupted Thread…Interrupt…Use Semaphores for Interrupt HandlingInterrupt handler...V(s);...Device managerwhile (1) { P(s); Acquire(m); ... deal with interrupt ... Release(m);}Init(s,0);Is Mutual Exclusion Enough?producer() { while (1) { produce an item P(mutex); put the item in buffer V(mutex); }}consumer() { while (1) { P(mutex); take an item from buffer V(mutex); consume the item }}Uses of Semaphores in this Example!Event sequencing"Don’t consume if buffer empty, wait for something to be added!Mutual exclusion"Avoid race conditions on shared variables10Bounded Buffer with Semaphores (again)producer() { while (1) { produce an item P(emptyCount); P(mutex); put the item in buffer V(mutex); V(fullCount); }}consumer() { while (1) { P(fullCount); P(mutex); take an item from buffer V(mutex); V(emptyCount); consume the item }}Does Order Matter?producer() { while (1) { produce an item P(mutex); P(emptyCount); put the item in buffer V(mutex); V(fullCount); }}consumer() { while (1) { P(fullCount); P(mutex); take an item from buffer V(mutex); V(emptyCount); consume the item }}Monitor: Hide Mutual Exclusion!Brinch-Hansen (73), Hoare (74)!Procedures are mutually exclusive"Enforced by monitor (by compiler)Shareddata...Queue of waiting processestrying to enter the monitorprocedures!What about blocking and sequencing?Condition Variables in A Monitor!Wait( condition )"Block on “condition”!Signal( condition )"Wakeup a blocked process on “condition”Shareddata...Entry queueproceduresxyQueues associatedwith x, y conditions!Look like semaphores, but are not!They don’t “count”, or accumulat signals!Like sleep/wakeup, but with mutual exclusion at monitor levelProducer-Consumer with Monitorsmonitor ProdCons condition full, empty; procedure Enter; begin if (buffer is full) wait(full); put item into buffer; if (only one item) signal(empty); end; procedure Remove; begin if (buffer is empty) wait(empty); remove an item; if (buffer was full) signal(full); end;procedure Producerbegin while true do begin produce an item ProdCons.Enter(); end;end;procedure Consumerbegin while true do begin ProdCons.Remove(); consume an item; end;end;16What happens after a signal?!Run the signaled thread immediately and suspend the current one (Hoare)"If the signaler has other work to do, life is complex"It is difficult to make sure there is nothing to do, because the signal implementation is not aware of how it is used"It is easy to prove things!Exit the monitor (Hansen)"Signal must be the last statement of a monitor procedure!Continues its execution (Mesa)"Easy to implement"But, the condition may not be true when the awaken process actually gets a chance to runMesa Style “Monitor” (Birrell’s Paper)!Associate a condition variable with a mutex!Wait( mutex, condition )"Atomically unlock the mutex and enqueue on the condition variable (block the thread)"Re-lock the lock when it is awoken!Signal( condition )"No-op if there is no thread blocked on the condition variable"Wake up at least one if there are threads blocked!Broadcast( condition )"Wake up all waiting threads!Original Mesa paper"B. Lampson and D. Redell. Experience with processes and monitors in Mesa. Comm. ACM 23, 2 (feb 1980), pp 106-117.18Consumer-Producer with Mesa-Style Monitorstatic count = 0;static Cond full, empty;static Mutex lock;Enter(Item item) { Acquire(lock); if (count==N) Wait(lock, full); insert item into buffer count++; if (count==1) Signal(empty); Release(lock);}Remove(Item item) { Acquire(lock); if (!count) Wait(lock, empty); remove item from buffer count--; if (count==N-1) Signal(full); Release(lock);}Any issues with this?19Consumer-Producer with Mesa-Style Monitorstatic count = 0;static Cond full, empty;static Mutex lock;Enter(Item item) { Acquire(lock); while (count==N) Wait(lock, full); insert item into buffer count++; if (count==1) Signal(empty); Release(lock);}Remove(Item item) { Acquire(lock); while (!count) Wait(lock, empty); remove item from buffer count--; if (count==N-1) Signal(full); Release(lock);}20The Programming Idiom!Waiting for a resourceAcquire( mutex );while ( no resource ) wait( mutex, cond );...(use the resource)... Release( mutex);!Make a resource availableAcquire( mutex );...(make resource available)...Signal( cond );/* or Broadcast( cond );Release( mutex);21Condition Variables Primitives!Wait( mutex, cond )"Enter the critical section (min busy wait) "Release mutex"Put my