CS162 Operating Systems and Systems Programming Lecture 8 Readers Writers Language Support for Synchronization September 26 2005 Prof John Kubiatowicz http inst eecs berkeley edu cs162 Review Implementation of Locks by Disabling Interrupts Key idea maintain a lock variable and impose mutual exclusion only during operations on that variable int value FREE Acquire Release disable interrupts disable interrupts if value BUSY if anyone on wait queue take thread off wait queue put thread on wait queue Place on ready queue Go to sleep else Enable interrupts value FREE else value BUSY enable interrupts enable interrupts 9 26 05 Kubiatowicz CS162 UCB Fall 2005 Lec 8 2 Review 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 interrupts Thread AThread B contex disable ints t s w itch sleep sleep return enable ints t contex disable int sleep switch sleep return enable ints 9 26 05 Kubiatowicz CS162 UCB Fall 2005 Lec 8 3 Review 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 int guard 0 int value FREE Acquire Release Short busy wait time Short busy wait time while test set guard while test set guard if anyone on wait queue if value BUSY take thread off wait queue put thread on wait queue Place on ready queue go to sleep guard 0 else else value FREE value BUSY guard 0 guard 0 Note sleep has to be sure to reset the guard variable Why 9 26 05 can t weKubiatowicz do it just before CS162 UCB or Fall just 2005 after the sleep Lec 8 4 Goals for Today Continue with Synchronization Abstractions Semaphores monitors and condition variables Readers Writers problem and solutoin Language Support for Synchronization Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and 9 26 05 Kubiatowicz CS162 UCB Fall 2005 Lec 8 5 Gagne Recall 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 2 Value 0 Value 1 9 26 05 Kubiatowicz CS162 UCB Fall 2005 Lec 8 6 Producer consumer with a bounded buffer Producer Buffer Consumer 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 empty 9 26 05 Kubiatowicz CS162 UCB Fall 2005 Lec 8 7 Correctness 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 8 9 26 05 Kubiatowicz CS162 UCB Fall 2005 Full Solution to Bounded Buffer Coke Machine Semaphore fullBuffer 0 Initially no coke Semaphore emptyBuffers numBuffers Initially num empty slots Semaphore mutex 1 No one using machine Producer item emptyBuffers P mutex P Enqueue item mutex V fullBuffers V Consumer fullBuffers P mutex P item Dequeue mutex V emptyBuffers V return item 9 26 05 Wait until space Wait until machine free Tell consumers there is more coke Check if there s a coke Wait until machine free tell producer need more Kubiatowicz CS162 UCB Fall 2005 Lec 8 9 Discussion 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 9 26 05 Kubiatowicz CS162 UCB Fall 2005 Lec 8 10 Administrivia First design document due today Has to be in by 11 59pm Good luck Future rule no slip days on first design document Need to get design reviews in on time Since we didn t tell you about this until today you can use up to one slip day on today s assignment Design reviews Everyone must attend 2 points off for one missing person 1 additional point off for each additional missing person No exceptions unless you have talked with us in advance and we have OK d your reasoning Note taker Um Someone came up to me last week about being a note taker but didn t send me email 9 26 05 Kubiatowicz CS162 UCB Fall 2005 Lec 8 11 Use of compare swap for queues compare swap address reg1 reg2 68000 if reg1 M address M address reg2 return success else return failure Here is an atomic add to linked list function addToQueue object do repeat until no conflict ld r1 M root Get ptr to current head st r1 M object Save link in new object until compare swap root r1 object root next next next 9 26 05 New Object Kubiatowicz CS162 UCB Fall 2005 Lec 8 12 Motivation for Monitors and Condition Variables Semaphores are a huge step up but They are confusing because they are dual purpose Both mutual exclusion and scheduling constraints Example the fact that flipping of P s in bounded buffer gives deadlock is not immediately obvious Cleaner idea Use locks for mutual exclusion and condition variables for scheduling constraints Definition Monitor a lock and zero or more condition variables for managing concurrent access to shared data Use of Monitors is a programming paradigm Some languages like Java
View Full Document
Unlocking...