CS162 Operating Systems and Systems Programming Lecture 8 Readers-Writers Language Support for SynchronizationReview: Implementation of Locks by Disabling InterruptsReview: How to Re-enable After Sleep()?Review: Locks using test&setGoals for TodayRecall: SemaphoresProducer-consumer with a bounded bufferCorrectness constraints for solutionFull Solution to Bounded Buffer (Coke Machine)Discussion about SolutionAdministriviaUse of compare&swap for queuesMotivation for Monitors and Condition VariablesSimple Monitor Example (version 1)Condition VariablesComplete Monitor Example (with condition variable)Mesa vs. Hoare monitorsReaders/Writers ProblemBasic Readers/Writers SolutionCode for a ReaderCode for a WriterSimulation of Readers/Writers solutionSimulation(2)Simulation(3)QuestionsCan we construct Monitors from Semaphores?Construction of Monitors from Semaphores (con’t)Monitor ConclusionC-Language Support for SynchronizationC++ Language Support for SynchronizationC++ Language Support for Synchronization (con’t)Java Language Support for SynchronizationJava Language Support for Synchronization (con’t)Java Language Support for Synchronization (con’t 2)SummaryCS162Operating Systems andSystems ProgrammingLecture 8Readers-WritersLanguage Support for SynchronizationSeptember 26, 2005Prof. John Kubiatowiczhttp://inst.eecs.berkeley.edu/~cs162Lec 8.29/26/05 Kubiatowicz CS162 ©UCB Fall 2005Review: Implementation of Locks by Disabling Interrupts•Key idea: maintain a lock variable and impose mutual exclusion only during operations on that variableint value = FREE;Acquire() {disable interrupts;if (value == BUSY) {put thread on wait queue;Go to sleep();// Enable interrupts?} else {value = BUSY;}enable interrupts;}Release() {disable interrupts;if (anyone on wait queue) {take thread off wait queuePlace on ready queue;} else {value = FREE;}enable interrupts;}Lec 8.39/26/05 Kubiatowicz CS162 ©UCB Fall 2005Review: How to Re-enable After Sleep()?•In Nachos, since ints are disabled when you call sleep:–Responsibility of the next thread to re-enable ints–When the sleeping thread wakes up, returns to acquire and re-enables interruptsThread AThread B..disable intssleepsleep returnenable ints...disable intsleepsleep returnenable ints..contextswitchcontextswitchLec 8.49/26/05 Kubiatowicz CS162 ©UCB Fall 2005Review: Locks using test&set•Can we build test&set locks without busy-waiting?–Can’t entirely, but can minimize!–Idea: only busy-wait to atomically check lock value•Note: sleep has to be sure to reset the guard variable–Why can’t we do it just before or just after the sleep?Release() {// Short busy-wait timewhile (test&set(guard));if anyone on wait queue {take thread off wait queuePlace on ready queue;} else {value = FREE;}guard = 0;int guard = 0;int value = FREE;Acquire() {// Short busy-wait timewhile (test&set(guard));if (value == BUSY) {put thread on wait queue;go to sleep() & guard = 0;} else {value = BUSY;guard = 0;}}Lec 8.59/26/05 Kubiatowicz CS162 ©UCB Fall 2005Goals for Today•Continue with Synchronization Abstractions–Semaphores, monitors, and condition variables•Readers-Writers problem and solutoin•Language Support for SynchronizationNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and GagneLec 8.69/26/05 Kubiatowicz CS162 ©UCB Fall 2005Value=2Value=1Value=0Recall: Semaphores•Definition: a Semaphore has a non-negative integer value and supports the following two operations:–P(): an atomic operation that waits for semaphore to become positive, then decrements it by 1 »Think of this as the wait() operation–V(): an atomic operation that increments the semaphore by 1, waking up a waiting P, if any»This of this as the signal() operation–Only time can set integer directly is at initialization time•Semaphore from railway analogy–Here is a semaphore initialized to 2 for resource control:Value=1Value=0Value=0Lec 8.79/26/05 Kubiatowicz CS162 ©UCB Fall 2005Producer-consumer with a bounded buffer•Problem Definition–Producer puts things into a shared buffer–Consumer takes them out–Need synchronization to coordinate producer/consumer•Don’t want producer and consumer to have to work in lockstep, so put a fixed-size buffer between them–Need to synchronize access to this buffer–Producer needs to wait if buffer is full–Consumer needs to wait if buffer is empty•Example 1: GCC compiler–cpp | cc1 | cc2 | as | ld•Example 2: Coke machine–Producer can put limited number of cokes in machine–Consumer can’t take cokes out if machine is emptyProducer ConsumerBufferLec 8.89/26/05 Kubiatowicz CS162 ©UCB Fall 2005Correctness constraints for solution•Correctness Constraints:–Consumer must wait for producer to fill buffers, if none full (scheduling constraint)–Producer must wait for consumer to empty buffers, if all full (scheduling constraint)–Only one thread can manipulate buffer queue at a time (mutual exclusion)•Remember why we need mutual exclusion–Because computers are stupid–Imagine if in real life: the delivery person is filling the machine and somebody comes up and tries to stick their money into the machine•General rule of thumb: Use a separate semaphore for each constraint–Semaphore fullBuffers; // consumer’s constraint–Semaphore emptyBuffers;// producer’s constraint–Semaphore mutex; // mutual exclusionLec 8.99/26/05 Kubiatowicz CS162 ©UCB Fall 2005Full Solution to Bounded Buffer (Coke Machine)Semaphore fullBuffer = 0; // Initially, no cokeSemaphore emptyBuffers = numBuffers;// Initially, num empty slotsSemaphore mutex = 1; // No one using machineProducer(item) {emptyBuffers.P(); // Wait until spacemutex.P(); // Wait until machine freeEnqueue(item);mutex.V();fullBuffers.V(); // Tell consumers there is// more coke}Consumer() {fullBuffers.P(); // Check if there’s a cokemutex.P(); // Wait until machine freeitem = Dequeue();mutex.V();emptyBuffers.V(); // tell producer need morereturn item;}Lec 8.109/26/05 Kubiatowicz CS162 ©UCB Fall 2005Discussion about Solution•Why asymmetry?–Producer does: emptyBuffer.P(), fullBuffer.V()–Consumer does: fullBuffer.P(), emptyBuffer.V()•Is order of P’s important?–Yes! Can cause deadlock•Is order of V’s important?–No, except that it might affect scheduling efficiency•What if we have 2 producers or 2 consumers?–Do we need to change anything?Lec 8.119/26/05 Kubiatowicz CS162 ©UCB Fall
View Full Document
Unlocking...