More on Semaphores, and Classic Synchronization ProblemsAnnouncementsFrom last time...SemaphoresSlide 5Slide 6Slide 7Slide 8Slide 9DeadlockSlide 11Slide 12Slide 13Classic Synchronization ProblemsBounded Buffer Producer/Consumer ProblemSlide 16Slide 17Slide 18Slide 19Slide 20The Readers/Writers ProblemSlide 22Slide 23More on Semaphores, and Classic Synchronization ProblemsCSCI 3753 Operating SystemsSpring 2005Prof. Rick HanAnnouncements•HW #3 is due Friday Feb. 25, a week+ from now•PA #2 is coming, assigned about next Tuesday•Midterm is tentatively Thursday March 10•Read chapters 8 and 9From last time...•We introduced critical sections, atomic locks, and semaphores•A semaphore S is an integer variable–initialize S to some value Sinit = n–P(S) operates atomically on S to decrement S, but only if S>0. Otherwise, the process calling P(S) relinquishes control.– V(S) atomically increments S•A binary semaphore, a.k.a. mutex lock, can be used to provide mutual exclusion on critical sections–Sinit = 1–value of semaphore varies only between 0 and 1Semaphores•Usage example #1: mutual exclusion Semaphore S = 1; // initial value of semaphore is 1 int counter; // assume counter is set correctly somewhere in codeProcess P1:P(S); // execute critical section counter++;V(S);Process P2:P(S); // execute critical section counter--;V(S);•Both processes atomically P() and V() the semaphore S, which enables mutual exclusion on critical section code, in this case protecting access to the shared variable counterSemaphores•Usage example #2: enforcing order of access between two processes–Suppose there are two processes P1 and P2, where P1 contains code C1 and P2 contains code C2–Want to ensure that code C1 executes before code C2–Use semaphores to synchronize the order of execution of the two processesSemaphore S=0; // initial value of semaphore = 0Process P2:wait(S); // P() the semaphoreC2; // execute C2Process P1:C1; // execute C1signal(S); // V() the semaphoreSemaphores•In the previous example #2, there are two cases:1. if P1 executes first, then •C1 will execute first, then P1 will V() the semaphore, increasing its value to 1•Later, when P2 executes, it will call wait(S), which will decrement the semaphore to 0 followed by execution of C2•Thus C1 executes before C22. If P2 executes first, then •P2 will block on the semaphore, which is equal to 0, so that C2 will not be executed yet•Later, when P1 executes, it will run through C1, then V() the semaphore•This awakens P2, which then executes C2•Thus C1 executes before C2Semaphores•Let’s revisit the following intuitive implementation of semaphores that uses only disabling and reenabling of interrupts–Note that a process that blocks on this kind of semaphore will spin in a busy wait while() loop - this type of semaphore is called a spinlock•Figure 8.25 in the text illustrates a semaphore implemented using a TestandSet instruction that also exhibits spinlock behaviorV(S) { disableInt(); S++; enableInt()}P(S) { disableInterrupts(); while(S==0) { enableInt(); disableInt(); } S--; enableInt()}Semaphores•Spinlock implementations of semaphores can occupy the CPU unnecessarily•Instead, sleep the process until it needs to be woken up by a V()/signal()V(semaphore *S) { S->value++; if (S->value<=0) { remove a process P from S->list; wakeup(P); }}P(semaphore *S) { S->value--; if (S->value<0) { add this process to S->list; block(); }}where we have defined the following structure for a semaphoretypedef struct { int value; struct process *list;} semaphore;Semaphores•In the previous slide’s redefinition of a semaphore, we are departing from the classic definition of a semaphore–Now, the semaphore’s value is allowed to be negative, because the decrement occurs before the test in P()–The absolute value of the semaphore’s negative amount can now be used to indicate the number of processes blocked on the semaphore–Processes now yield the CPU if the semaphore’s value is negative, rather than busy wait–If more than one process is blocked on a semaphore, then use a FIFO queue to select the next process to wake up when a semaphore is V’ed•Why is LIFO to be avoided?Deadlock•Semaphores provide synchronization, but can introduce more complicated higher level problems like deadlock–two processes deadlock when each wants a resource that has been locked by the other process–e.g. P1 wants resource R2 locked by process P2 with semaphore S2, while P2 wants resource R1 locked by process P1 with semaphore S1DeadlockSemaphore Q= 1; // binary semaphore as a mutex lockSemaphore S = 1; // binary semaphore as a mutex lockProcess P1:P(S);P(Q);modify R1 and R2;V(S);V(Q);Process P2:P(Q);P(S);modify R1 and R2;V(Q);V(S);(1)(3)(4)Deadlock!(2)If statements (1) through (4) are executed in that order, then P1 and P2 will be deadlocked after statement (4) - verify this for yourself by stepping thru the semaphore valuesDeadlock•In the previous example, –Each process will sleep on the other process’s semaphore–the V() signalling statements will never get executed, so there is no way to wake up the two processes from within those two processes–there is no rule prohibiting an application programmer from P()’ing Q before S, or vice versa - the application programmer won’t have enough information to decide on the proper order–in general, with N processes sharing N semaphores, the potential for deadlock growsDeadlock•Other examples:–A programmer mistakenly follows a P() with a second P() instead of a V(), e.g.P(mutex) critical sectionP(mutex) <---- this causes a deadlock, should have been a V()–A programmer forgets and omits the P(mutex) or V(mutex). Can cause deadlock if V(mutex) is omitted. Can violate mutual exclusion if P(mutex) is omitted.–A programmer reverses the order of P() and V(), e.g.V(mutex) critical section <---- this violates mutual exclusion, but is not anP(mutex) example of deadlockClassic Synchronization Problems•Bounded Buffer Producer-Consumer Problem•Readers-Writers Problem–First Readers Problem•Dining Philosophers Problem•These are not just abstract problems–They are representative of several classes of synchronization problems commonly encountered when trying to synchronize access to shared resources