DOC PREVIEW
Duke CPS 110 - Monitors and Semaphores

This preview shows page 1-2-22-23 out of 23 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Monitors and SemaphoresAnnotated Condition Variable ExampleThe Roots of Condition Variables: MonitorsHoare SemanticsMesa SemanticsFrom Monitors to Mx/Cv PairsMutual Exclusion in JavaWait/Notify in JavaSemaphoresSemaphores as MutexesPing-Pong with SemaphoresPing-Pong with One Semaphore?Slide 13Another Example With Dual SemaphoresBasic BarrierHow About This? (#1)How About This? (#2)How About This? (#3)How About This? (#4)Basic Producer/ConsumerA Bounded ResourceA Bounded Resource with a Counting SemaphoreSpin-Yield: Just Say NoMonitors and SemaphoresMonitors and SemaphoresAnnotated Condition Variable ExampleAnnotated Condition Variable ExampleCondition *cv;Lock* cvMx;int waiter = 0;void await() {cvMx->Lock();waiter = waiter + 1; /* “I’m sleeping” */cv->Wait(cvMx); /* sleep */cvMx->Unlock();}void awake() {cvMx->Lock();if (waiter)cv->Signal(cvMx);waiter = waiter - 1;CvMx->Unlock();}Must hold lock when calling Wait. Wait atomically reacquires lock before returning.Wait atomically releases lock and sleeps until next Signal. Association with lock/mutex allows threads to safely manage state related to the sleep/wakeup coordination (e.g., waiters count).The Roots of Condition Variables: MonitorsThe Roots of Condition Variables: MonitorsA monitor is a “magic” module (a collection of procedures and state) with serialized execution and integrated wait/signal primitives.P1()P2()P3()P4()statereadyto enterblockedwait()At most one thread may be active in a given monitor at any time.(exit)(enter)A thread may wait in the monitor, allowing another thread to enter.A thread in the monitor may signal a waiting thread, causing it to return from its wait and reenter the monitor.signal()CVs are easier to understand if we think about them in terms of the original monitor formulation.[Brinch Hansen 1973, C.A.R. Hoare 1974]Hoare SemanticsHoare SemanticsP1()P2()P3()P4()statereadyto enterwaitingwait()(exit)(enter)Hoare semantics: the signaled thread immediately takes over the monitor, and the signaler is suspended.signal()(Hoare)Hoare semantics allow the signaled thread to assume that the state has not changed since the signal that woke it up.Suppose purple signals, and a waiting blue is selected to wake up.suspendedsignal()(Hoare)The signaler does not continue in the monitor until the signaled thread exits or waits again.Mesa SemanticsMesa SemanticsP1()P2()P3()P4()statereadyto (re)enterwaitingwait()(exit)(enter)Mesa semantics: the signaled thread transitions back to the ready state (Nachos, Topaz, Java).signal()(Mesa)BUT: the signaled thread must examine the monitor state again after the wait, as the state may have changed since the signal.Suppose again that purple signals blue in the original example.There is no suspended state: the signaler continues until it exits the monitor or waits. The signaled thread contends with other ready threads to (re)enter the monitor and return from wait. Mesa semantics are easier to understand and implement...Loop before you leap!From Monitors to Mx/Cv PairsFrom Monitors to Mx/Cv PairsMutexes and condition variables (as in Nachos) are based on the monitors concept, but they are more flexible.•A monitor is “just like” a module whose state includes a mutex and a condition variable.The difference is syntactic; the basic semantics (and implementation) are the same for mutex/CV and monitors.•It’s “just as if” the module’s methods Acquire the mutex on entry and Release the mutex before returning.•But with mutexes, the critical regions within the methods can be defined at a finer grain, to allow more concurrency.•With condition variables, the module methods may wait and signal on multiple independent conditions.Mutual Exclusion in JavaMutual Exclusion in JavaMutexes and condition variables are built in to every Java object.•no explicit classes for mutuxes and condition variablesEvery object is/has a “monitor”.•At most one thread may “own” any given object’s monitor.•A thread becomes the owner of an object’s monitor byexecuting a method declared as synchronizedsome methods may choose not to enforce mutual exclusion (unsynchronized)by executing the body of a synchronized statement or blocksynchronized construct specifies which object to acquiresupports finer-grained locking than “pure monitors” allowexactly identical to the Modula-2 “LOCK(m) DO” construct in BirrellWait/Notify in JavaWait/Notify in Javapublic class Object { void notify(); /* signal */ void notifyAll(); /* broadcast */ void wait(); void wait(long timeout);}public class PingPong (extends Object) { public synchronized void PingPong() {while(true) { notify(); wait();} }}Every Java object may be treated as a condition variable for threads using its monitor.A thread must own an object’s monitor to call wait/notify, else the method raises an IllegalMonitorStateException.Wait(*) waits until the timeout elapses or another thread notifies, then it waits some more until it can re-obtain ownership of the monitor: Mesa semantics.Loop before you leap!SemaphoresSemaphoresSemaphores handle all of your synchronization needs with one elegant but confusing abstraction.•controls allocation of a resource with multiple instances•a non-negative integer with special operations and propertiesinitialize to arbitrary value with Init operation“souped up” increment (Up or V) and decrement (Down or P)•atomic sleep/wakeup behavior implicit in P and VP does an atomic sleep, if the semaphore value is zero.P means “probe”; it cannot decrement until the semaphore is positive.V does an atomic wakeup.num(P) <= num(V) + initSemaphores as MutexesSemaphores as Mutexessemapohore->Init(1);void Lock::Acquire(){semaphore->Down();}void Lock::Release(){semaphore->Up();}Semaphores must be initialized with a value representing the number of free resources: mutexes are a single-use resource.Down() to acquire a resource; blocks ifno resource is available.Up() to release a resource; wakes up one waiter, if any.Mutexes are often called binary semaphores.However, “real” mutexes have additional constraints on their use.Up and Down are atomic.Ping-Pong with SemaphoresPing-Pong with SemaphoresvoidPingPong() { while(not done) { blue->P(); Compute(); purple->V();}}voidPingPong() { while(not done) { purple->P(); Compute(); blue->V(); }}blue->Init(0);purple->Init(1);Ping-Pong with One Semaphore?Ping-Pong with One Semaphore?voidPingPong() {


View Full Document

Duke CPS 110 - Monitors and Semaphores

Download Monitors and Semaphores
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Monitors and Semaphores and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Monitors and Semaphores 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?