COS 318: Operating Systems Semaphores, Monitors and Condition Variables Kai Li Computer Science Department Princeton University (http://www.cs.princeton.edu/courses/cos318/)2 Today’s Topics  Semaphores  Monitors  Mesa-style monitors  Programming idiom  Barriers3 Semaphores (Dijkstra, 1965)  Initialization  Initialize a value atomically  P (or Down or Wait) definition  Atomic operation  Wait for semaphore to become positive and then decrement P(s){ while (s <= 0) ; s--; }  V (or Up or Signal) definition  Atomic operation  Increment semaphore by 1 V(s){ 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 } }5 Example: Interrupt Handler  A device thread works with an interrupt handler  What to do with shared data?  What if “m” is held by another thread or by itself? Device thread ... Acquire(m); ... Release(m); ... Interrupt handler ... Acquire(m); ... Release(m); ... ?6 Interrupted Thread … Interrupt … Use Semaphore to Signal Interrupt handler ... V(s); ... Device thread while (1) { P(s); Acquire(m); ... deal with interrupt ... Release(m); } Init(s,0);Semaphores Are Not Always Convenient  It is a consumer and producer problem  Dequeue(q) should block until q is not empty  Semaphores are difficult to use: orders are important Enqueue(q, item) { Acquire(mutex); put item into q; Release(mutex); } Dequeue(q) { Acquire(mutex); take an item from q; Release(mutex); return item; }  A shared queue has Enqueue and Dequeue:Monitor: Hide Mutual Exclusion  Brinch-Hansen (73), Hoare (74)  Procedures are mutual exclusive Shared data ... Queue of waiting processes trying to enter the monitor proceduresCondition Variables in A Monitor  Wait( condition )  Block on “condition”  Signal( condition )  Wakeup a blocked process on “condition” Shared data ... Entry queue procedures x y Queues associated with x, y conditionsProducer-Consumer with Monitors monitor 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 Producer begin while true do begin produce an item ProdCons.Enter(); end; end; procedure Consumer begin while true do begin ProdCons.Remove(); consume an item; end; end;11 Options of the Signaler  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 enqueued on the condition variable (block the thread)  Re-lock the lock when it is awaken  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.13 Consumer-Producer with Mesa-Style Monitor static 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?14 Consumer-Producer with Mesa-Style Monitor static 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); }15 The Programming Idiom  Waiting for a resource Acquire( mutex ); while ( no resource ) wait( mutex, cond ); ... (use the resource) ... Release( mutex);  Make a resource available Acquire( mutex ); ... (make resource available) ... Signal( cond ); /* or Broadcast( cond ); Release( mutex);Revisit the Motivation Example  Does this work? Enqueue(Queue q, Item item) { Acquire(lock); insert an item to q; Signal(Empty); Release(lock); } Item GetItem(Queue q) { Item item; Acquire( lock ); while ( q is empty ) Wait( lock, Empty); remove an item; Release( lock ); return item; }17 Condition Variables Primitives  Wait( mutex, cond )  Enter the critical section (min busy wait)  Release mutex  Put my TCB to cond’s queue  Call scheduler  Exit the critical section . . . (blocked)  Waking up: • Acquire mutex • Resume  Signal( cond )  Enter the critical section (min busy wait)  Wake up a TCB in cond’s queue  Exit the critical sectionMore on Mesa-Style Monitor  Signaler continues execution  Waiters simply put on ready queue, with no special priority  Must reevaluate the condition  No constraints on when the waiting thread/process must run after a “signal”  Simple to introduce a broadcast: wake up all  No constrains on signaler  Can execute