ReviewOutlineWhat’s wrong with this picture?SemaphoresSemaphore OperationsP(s)V(s)Mutual exclusion with semaphoresQuestions, Questions...Binary SemaphoreBinary SemaphoresImportant properties of Semaphores -IImportant Properties of Semaphores- IIClassic Problems: Producer-Consumer IProducer Consumer IIProducer Consumer IIIProducer Consumer IVBeyond SemaphoresMonitors (late 60’s, early 70’s)LocksExample: Producer ConsumerHouston, we have a problem…Condition VariablesProducer Consumer, againA dilemmaHoare MonitorsExample: Hoare MonitorsPer Brinch Hansen’s MonitorsExample: Hansen MonitorsTradeoffClassic Problems 2: Readers-WritersTowards a solutionStructure of the solutionThe proceduresSemaphores and Monitors - ISemaphores and Monitors-IIA few matters of styleExample: JavaReview•The Critical Section problem•Peterson’s Algorithm•Implementing Atomicity•Busy waiting•BlockingOutline•Semaphores–what they are–how they are used•Monitors–what they are–how they are usedWhat’s wrong with this picture?Our solutions to CS have two unappealing features:–They are mistifying and unclear–They use busy waitingSemaphoresA semaphore consists of:•A variable s•A thread set T•A function P (Passeren; wait)•A function V (Vrijgeven; signal)syntax example: Semaphore s(5);Semaphore OperationsInitialization(val){s = val ; T = P(s)s--;if(s < 0){add caller thread to T;block;}This code executes atomically.V(s)s++;if(s  0){Remove a thread t from T;Unblock(t);}This code executes atomically.Mutual exclusion with semaphoresThread T0while (!terminate) {<entry0>CS<exit0>NCS0}Thread T1while (!terminate) {<entry1>CS<exit1>NCS1}P(s); P(s);V(s); V(s);init: s = 1Questions, Questions...•What if we have n threads instead of 2?•What if we want to allow at most k threads in the CS?Binary SemaphoreTwo types:•Counting semaphores–s takes any values•Binary semaphores–s takes only 0 or 1Binary SemaphoresP(s)if (s == 0){Add caller thread to T;Block;}elses--;V(s)if (T != ){ Remove a thread t from T; Unblock(t);}else if (s == 0)s = 1;Important properties of Semaphores -I•Semaphores are non-negative integers•The only operations you can use to change the value of a semaphore are P() and V() (except for the initial setup)•Semaphores have two uses–Mutual exclusion: you know all about it–Synchronization: how do we make sure that T1 completes execution before T2 starts?Important Propertiesof Semaphores- II•We assume that a semaphore is fair:No thread t that is blocked because of a P(s) operation remains blocked if s is V’d infinitely oftenDoes this guarantee bounded waiting?•In practice, FIFO is mostly used, transforming the set into a queue. •V(s) never blocks.•Binary semaphores are as expressive as general semaphores (given one can implement the other)–But they are different: {s = 0} V(s) V(s) P(s) P(s) VS{s = 0} Vb(s) Vb(s) Pb(s) Pb(s)Classic Problems: Producer-Consumer I•Producer adds items to a shared buffer•Consumer takes them out•Buffer avoids producers and consumers to proceed in lock step•Buffer is finiteExamples:–cpp|cc|as–coke machine–ready queue in a multithreaded multiprocessor–….Producer Consumer II•Two types of constraint:–Mutual Exclusion•Only one thread can manipulate the buffer at any one time–Condition Synchronization•Consumer must wait if buffer is empty•Producer must wait if buffer is full•Are these safety or liveness properties?Producer Consumer III•Use a separate semaphore for each constraintSemaphore mutex; // protects the shared bufferSemaphore fullSlots; // counts full slots: if 0, no // cokeSemaphore emptySlots; // counts empty slots: if 0, // nowhere to put more cokeProducer Consumer IVSemaphore new mutex (1);Semaphore new emptySlots(numSlots);Semaphore new fullSlots(0);Producer() {P(emptySlots);P(mutex);put 1 coke in the machineV(mutex);V(fullSlots);}Consumer() {P(fullSlots);P(mutex);take a coke outV(mutex);V(emptySlots);}Is the order of Ps important? Is the order of Vs important?Beyond Semaphores•Semaphores huge step forward (immagine having to do producer consumer with Peterson’s algorithm…)•BUT…Semaphores are used both for mutex and condition synchronization–hard to read code–hard to get code rightMonitors (late 60’s, early 70’s)•A programming language construct, much like what we call today objects•Consists of:–General purpose variables–Methods–Initialization code (constructor)–Condition variables•Can implement a monitor-like style of programming without without the language construct, using a combination of locks and condition variablesLocksA lock provides mutual exclusion to shared data:Lock::Acquire() – wait until lock is free, then grab itLock::Release() – unlock; wake up anyone waiting in AcquireRules:–Always acquire before accessing a shared data structure–Always release after finishing with shared data structure–Lock is initially freeExample: Producer ConsumeraddToBuff() {lock.Acquire(); // lock before using shared dataput item on buffer, if there is spacelock.Release();}removeFromBuff() {lock.Acquire(); // lock before using shared dataif something on buffer, remove itlock.Release();return item;}Houston, we have a problem…•How do we change removeFromBuff so that it check if there is something in the buffer before trying to remove it?•Logically, want to suspend thread inside the critical section•What is the problem?•Solution: suspend and atomically release lockCondition VariablesA queue of threads waiting for something inside the critical section (why does it not violate safety?)Condition variables have two operations:–Wait()•Calling thread blocks, releases lock (gives up monitor)•Wait on a queue until someone signals variable–Signal()•Unblock someone who was waiting on the variable–Broadcast()•Unblock all waiting on the variableProducer Consumer, againaddToBuff() {lock.Acquire(); // lock before using shared dataput item on buffercondition.signal();lock.Release();}removeFromBuff() {lock.Acquire(); // lock before using shared datawhile nothing on buffer {condition.wait(&lock)}remove item from bufferlock.Release();return item;}A dilemma•What happens to a thread that signals on a condition variable while in the middle of a critical section?Hoare Monitors•Assume thread Q waiting on condition x•Assume thread P is in the monitor•Assume thread P calls x.signal•P gives up monitor,