1Semaphores and Monitors: High-level Synchronization ConstructsA Historical Perspective2Synchronization ConstructsSynchronization Coordinating execution of multiple threads that share datastructuresPast few lectures: Locks: provide mutual exclusion Condition variables: provide conditional synchronizationToday: Historical perspective Semaphores Introduced by Dijkstra in 1960s Main synchronization primitives in early operating systems Monitors Alternate high-level language constructs3SemaphoresAn abstract data typeA non-negative integer variable with two atomic operationsWe assume that a semaphore is fair No thread t that is blocked on a P() operation remains blocked if the V()operation on the semaphore is invoked infinitely often In practice, FIFO is mostly used, transforming the set into a queue.SemaphoreP() (Passeren; wait)Atomically: If sem > 0, then decrement sem by 1Otherwise “wait” until sem > 0SemaphoreV() (Vrijgeven; signal)Atomically: Increment sem by 14Important properties of SemaphoresSemaphores are non-negative integersThe only operations you can use to change the value of asemaphore are P() and V() (except for the initial setup) P() can block, but V() never blocksSemaphores are used both forMutual exclusion, andConditional synchronizationTwo types of semaphores Binary semaphores: Can either be 0 or 1 General/Counting semaphores: Can take any non-negative value Binary semaphores are as expressive as general semaphores(given one can implement the other)5Using Semaphores for Mutual ExclusionUse a binary semaphore for mutual exclusionUsing Semaphores for producer-consumer with boundedbufferSemaphore = new Semaphore(1);SemaphoreP(); Critical Section;SemaphoreV();Semaphore mutex;Semaphore fullBuffers;Semaphore emptyBuffers;Use a separatesemaphore foreach constraint6Revisiting Coke Machine ExampleClass CokeMachine{ … Semaphore new mutex(1); Semaphores new fullBuffers(0); Semaphores new emptyBuffers(numBuffers);}CokeMachine::Deposit(){ emptyBuffersP(); mutexP(); Add coke to the machine; mutexV(); fullBuffersV();}CokeMachine::Remove(){ fullBuffersP(); mutexP(); Remove coke from to the machine; mutexV(); emptyBuffersV();}7Comparing codeCokeMachine::Deposit(){ lockacquire(); while (count == n) {notFull.wait(&lock); } Add coke to the machine; count++; notEmpty.signal(); lockrelease();}CokeMachine::Deposit(){ emptyBuffersP(); mutexP(); Add coke to the machine; mutexV(); fullBuffersV();}CokeMachine::Deposit(){ mutexP(); emptyBuffersP(); Add coke to the machine; fullBuffersV(); mutexV();}Does the order of P matter? V?8Implementing SemaphoresSemaphore::P() { Disable interrupts; if (value == 0) { Put TCB on wait queue for semaphore; Switch(); // dispatch a ready thread } else {value--;} Enable interrupts;}Semaphore::V() { Disable interrupts; if wait queue is not empty { Move a waiting thread to ready queue; } else {value++;} Enable interrupts;}9Implementing SemaphoresSemaphore::P() { Disable interrupts; while (value == 0) { Put TCB on wait queue for semaphore; Switch(); // dispatch a ready thread } value--; Enable interrupts;}Semaphore::V() { Disable interrupts; if wait queue is not empty { Move a waiting thread to ready queue; } value++; Enable interrupts;}10The Problem with SemaphoresCokeMachine::Deposit(){ emptyBuffersP(); mutexP(); Add coke to the machine; mutexV(); fullBuffersV();}CokeMachine::Remove(){ fullBuffersP(); mutexP(); Remove coke from to the machine; mutexV(); emptyBuffersV();}Semaphores are used for dual purpose Mutual exclusion Conditional synchronizationDifficult to read/develop codeWaiting for condition is independent of mutual exclusion Programmer needs to be clever about using semaphores11Separate the concerns of mutual exclusion and conditionalsynchronizationWhat is a monitor? One lock, and Zero or more condition variables for managing concurrent access toshared dataGeneral approach: Collect related shared data into an object/module Define methods for accessing the shared dataMonitors were first introduced as a 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 Monitors12Locks and Condition Variables – RecapLocks 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 Signal(): Wake up a waiter, if any Broadcast(): Wake up all the waiters Two semantics for the implementation of wait() and signal() Hoare monitor semantics Hansen monitor semantics13Coke Machine ExampleClass 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::Remove(){ lockacquire(); while (count == 0) {notEmpty.wait(&lock); } Remove coke from to the machine; count--; notFull.signal(); lockrelease();}14Hoare 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 resumes15Hansen 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