CS162 Operating Systems and Systems Programming Lecture 7 Readers Writers Language Support for Synchronization February 13 2008 Prof Anthony D Joseph http inst eecs berkeley edu cs162 Review Semaphores Definition a Semaphore has a non negative integer value and supports the following two operations Only time can set integer directly is at initialization time 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 2 13 08 Joseph CS162 UCB Spring 2008 Lec 7 2 Review Full Solution to Bounded Buffer 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 2 13 08 Wait until space Wait until buffer free Tell consumers there is more coke Check if there s a coke Wait until machine free tell producer need more Joseph CS162 UCB Spring 2008 Lec 7 3 Review Discussion about Solution Is order of P s important Yes Can cause deadlock Is order of V s important No except for scheduling efficiency What if we have 2 producers or 2 consumers Nothing changes 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 2 13 08 Joseph CS162 UCB Spring 2008 Lec 7 4 Review Monitors and Condition Variables 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 provide monitors in the language The lock provides mutual exclusion to shared data Always acquire before accessing shared data structure Always release after finishing with shared data Lock initially free 2 13 08 Joseph CS162 UCB Spring 2008 Lec 7 5 Goals for Today Continue with Synchronization Abstractions Monitors and condition variables Readers Writers problem and solution Language Support for Synchronization An Overview of ACID properties in a DBMS Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and 2 13 08 Josephgenerated CS162 UCB Spring Lec 7 6 Gagne Many slides Gagne from2008 my lecture notes Simple Monitor Example version 1 Here is an infinite synchronized queue Lock lock Queue queue AddToQueue item lock Acquire queue enqueue item lock Release Lock shared data Add item Release Lock RemoveFromQueue lock Acquire item queue dequeue lock Release return item 2 13 08 Lock shared data Get next item or null Release Lock Might return null Joseph CS162 UCB Spring 2008 Lec 7 7 Condition Variables How do we change the RemoveFromQueue routine to wait until something is on the queue Could do this by keeping a count of the number of things on the queue with semaphores but error prone Condition Variable a queue of threads waiting for something inside a critical section Key idea allow sleeping inside critical section by atomically releasing lock at time we go to sleep Contrast to semaphores Can t wait inside critical section Operations Wait lock Atomically release lock and go to sleep Re acquire lock later before returning Signal Wake up one waiter if any Broadcast Wake up all waiters Rule Must hold lock when doing condition variable ops In Birrell paper he says can perform signal outside of CS162 UCB Spring 2008 lock IGNOREJoseph HIM this is only an optimization Lec 7 8 2 13 08 Complete Monitor Example with condition variable Here is an infinite synchronized queue Lock lock Condition dataready Queue queue AddToQueue item lock Acquire queue enqueue item dataready signal lock Release Get Lock Add item Signal any waiters Release Lock RemoveFromQueue lock Acquire Get Lock while queue isEmpty dataready wait lock If nothing sleep item queue dequeue Get next item lock Release Release Lock return item 2 13 08 Joseph CS162 UCB Spring 2008 Lec 7 9 Mesa vs Hoare monitors Need to be careful about precise definition of signal and wait Consider a piece of our dequeue code while queue isEmpty dataready wait lock If nothing sleep item queue dequeue Get next item Why didn t we do this if queue isEmpty dataready wait lock If nothing sleep item queue dequeue Get next item Answer depends on the type of scheduling Hoare style most textbooks Signaler gives lock CPU to waiter waiter runs immediately Waiter gives up lock processor back to signaler when it exits critical section or if it waits again Mesa style Nachos most real operating systems Signaler keeps lock and processor Waiter placed on ready queue with no special priority Practically need to check condition again after wait 2 13 08 Joseph CS162 UCB Spring 2008 Lec 7 10 Administrivia First design document due tomorrow by 11 59pm Use the newsgroup for questions search Google groups Design reviews Everyone must attend no exceptions 2 points off for one missing person 1 additional point off for each additional missing person Penalty for arriving late arrive 5 10 mins early Sign up link to be posted pages What we expect in document review Architecture correctness constraints algorithms pseudocode NO CODE Important testing strategy and test case types Midterm I in two weeks Wed 2 27 TBA 6 7 30 Closed book no notes no calculators PDAs Topics Everything up to 2 20 Sunday 2 24 review session 2 13 08 Joseph CS162 UCB Spring 2008 Lec 7 11 Readers Writers Problem W R R R Motivation Consider a shared database Two classes of users Readers never modify database Writers read and modify database Is using a single lock on the whole database sufficient 2 13 08 Like to have many readers at the same time Only one writer at a time Joseph CS162 UCB Spring 2008 Lec 7 12 Basic Readers Writers Solution Correctness Constraints Readers can access database when no writers Writers can access database when no readers or writers Only one thread manipulates state variables at a time Basic structure of a solution Reader Wait until no writers Access data base Check out wake up a waiting writer Writer Wait until no active readers or writers Access database Check out wake up waiting readers or writer State
View Full Document
Unlocking...