Slide 1Synchronization ConstructsIntroducing MonitorsCritical Section: MonitorsRemember Condition VariablesCoke Machine – Example MonitorSlide 7Hoare Monitors: SemanticsHansen (Mesa) Monitors: SemanticsTradeoffProblems with Monitors Nested Monitor CallsMore Monitor Headaches The priority inversion problemOther Interesting TopicsSemaphoresImportant properties of SemaphoresSlide 16Using Semaphores for Mutual ExclusionCoke Machine ExampleRevisiting Coke Machine ExampleImplementing SemaphoresSlide 21The Problem with SemaphoresComparing Semaphores and MonitorsSummary1Semaphores and Monitors: High-level Synchronization Constructs2Synchronization ConstructsSynchronizationCoordinating execution of multiple threads that share data structuresPast few lectures: Locks: provide mutual exclusionCondition variables: provide conditional synchronizationToday: Historical perspectiveMonitorsAlternate high-level language constructsSemaphoresIntroduced by Dijkstra in 1960sMain synchronization primitives in early operating systems3Separate the concerns of mutual exclusion and conditional synchronizationWhat is a monitor?One lock, andZero or more condition variables for managing concurrent access to shared dataGeneral approach:Collect related shared data into an object/moduleDefine methods for accessing the shared dataMonitors first introduced as programming language constructCalling a method defined in the monitor automatically acquires the lockExamples: Mesa, Java (synchronized methods)Monitors also define a programming conventionCan be used in any language (C, C++, … )Introducing Monitors4Critical Section: MonitorsBasic idea:Restrict programming model Permit access to shared variables only within a critical sectionGeneral program structureEntry section“Lock” before entering critical sectionWait if already lockedKey point: synchronization may involve waitCritical section codeExit section“Unlock” when leaving the critical sectionObject-oriented programming styleAssociate a lock with each shared objectMethods that access shared object are critical sectionsAcquire/release locks when entering/exiting a method that defines a critical section5Remember Condition VariablesLocksProvide mutual exclusionSupport two methodsLock::Acquire() – wait until lock is free, then grab itLock::Release() – release the lock, waking up a waiter, if anyCondition variablesSupport conditional synchronizationThree operationsWait(): Release lock; wait for the condition to become true; reacquire lock upon return (Java wait())Signal(): Wake up a waiter, if any (Java notify())Broadcast(): Wake up all the waiters (Java notifyAll())Two semantics for implementation of wait() and signal()Hoare monitor semanticsHansen (Mesa) monitor semantics6Coke Machine – Example MonitorClass CokeMachine{ … Lock lock; int count = 0; Condition notFull, notEmpty;}Class CokeMachine{ … Lock lock; int count = 0; Condition notFull, notEmpty;}CokeMachine::Deposit(){ lockacquire(); while (count == n) {notFull.wait(&lock); } Add coke to the machine; count++; notEmpty.signal(); lockrelease();}CokeMachine::Deposit(){ lockacquire(); while (count == n) {notFull.wait(&lock); } Add coke to the machine; count++; notEmpty.signal(); lockrelease();}CokeMachine::Remove(){ lockacquire(); while (count == 0) {notEmpty.wait(&lock); } Remove coke from to the machine; count--; notFull.signal(); lockrelease();}CokeMachine::Remove(){ lockacquire(); while (count == 0) {notEmpty.wait(&lock); } Remove coke from to the machine; count--; notFull.signal(); lockrelease();}Does the order of aquire/while(){wait} matter?Order of release/signalmatter?7Every monitor function should start with what?A. waitB. signalC. lock acquireD. lock releaseE. signalAll8Hoare Monitors: SemanticsHoare monitor semantics:Assume thread T1 is waiting on condition xAssume thread T2 is in the monitorAssume thread T2 calls x.signalT2 gives up monitor, T2 blocks!T1 takes over monitor, runsT1 gives up monitorT2 takes over monitor, resumesExamplefn1(…)…x.wait // T1 blocks// T1 resumesLockrelease();fn4(…)…x.signal // T2 blocksT2 resumes9Hansen (Mesa) Monitors: SemanticsHansen monitor semantics:Assume thread T1 waiting on condition xAssume thread T2 is in the monitorAssume thread T2 calls x.signal; wake up T1 T2 continues, finishesWhen T1 get a chance to run,T1 takes over monitor, runsT1 finishes, gives up monitorExample:fn1(…)…x.wait // T1 blocks// T1 resumes// T1 finishesfn4(…)…x.signal // T2 continues// T2 finishes10TradeofHoareClaims:Cleaner, good for proofsWhen a condition variable is signaled, it does not changeUsed in most textbooks…butInefficient implementationNot modular – correctness depends on correct use and implementation of signalHansenSignal is only a hint that the condition may be trueNeed to check condition again before proceedingCan lead to synchronization bugsUsed by most systems (e.g., Java)Benefits:Efficient implementationCondition guaranteed to be true once you are out of while !CokeMachine::Deposit(){ lockacquire(); if (count == n) {notFull.wait(&lock); } Add coke to the machine; count++; notEmpty.signal(); lockrelease();}CokeMachine::Deposit(){ lockacquire(); if (count == n) {notFull.wait(&lock); } Add coke to the machine; count++; notEmpty.signal(); lockrelease();}CokeMachine::Deposit(){ lockacquire(); while (count == n) {notFull.wait(&lock); } Add coke to the machine; count++; notEmpty.signal(); lockrelease();}CokeMachine::Deposit(){ lockacquire(); while (count == n) {notFull.wait(&lock); } Add coke to the machine; count++; notEmpty.signal(); lockrelease();}11Problems with MonitorsNested Monitor CallsWhat happens when one monitor calls into another?What happens to CokeMachine::lock if thread sleeps in CokeTruck::Unload?What happens if truck unloader wants a coke?CokeMachine::Deposit(){ lockacquire(); while (count == n) {notFull.wait(&lock); } truck->unload(); Add coke to the machine; count++; notEmpty.signal(); lockrelease();}CokeMachine::Deposit(){ lockacquire(); while (count == n) {notFull.wait(&lock); }