CS 162 Operating Systems and Systems Programming Professor Anthony D Joseph 9 1 2 Spring 2003 Constraints 1 Readers can access database when no writers Condition okToRead 2 Writers can access database when no readers or writers okToWrite Lecture 9 Readers Writers and Language Support for Synchronization 9 0 Main points 3 Only one thread manipulates state variables at a time 9 1 3 Review definition of monitors and condition variables Illustrate use of monitors and condition variables by solving readers writers problem Language support can make thread programming easier Threads are a fundamental OS abstraction but be careful about how you use them Summarize concurrency section Condition Solution Basic structure of solution Reader wait until no writers access database check out wake up waiting writer Writer 9 1 Readers Writers 9 1 1 wait until no readers or writers access database Motivation check out wake up waiting readers or writer Shared database for example bank balances or airline seats State variables Two classes of users Readers never modify database Writers read and modify database Using a single lock on the database would be overly restrictive Want many readers at same time only one writer at same time of active readers AR 0 of active writers AW 0 of waiting readers WR 0 of waiting writers WW 0 Condition okToRead NIL Condition okToWrite NIL Lock lock FREE CS 162 Spring 2003 Lecture 9 1 13 CS 162 Spring 2003 Lecture 9 2 13 Code Writer Reader first check self into system check in lock Acquire lock Acquire while AW WW 0 symmetrical while AW AR 0 check if safe to read check if safe to write if any readers or if any writers wait writers wait WR okToRead Wait lock WW WR okToWrite Wait lock WW AR lock Release AW lock Release Access DB Access DB check self out of system check out lock Acquire lock Acquire AR if AR 0 WW 0 if no other readers still AW active wake up writer if WW 0 give priority to other writers okToWrite Signal lock okToWrite Signal lock else if WR 0 lock Release okToRead Broadcast lock lock Release Questions 1 Can readers starve 2 Why does checkRead need a while CS 162 Spring 2003 Lecture 9 3 13 CS 162 Spring 2003 Lecture 9 4 13 9 2 Comparison between semaphores and monitors In other words P V are commutative result is the same no matter what order they occur Condition variables are not commutative That s why they must be in a critical section need to access state variables to do their job Illustrate the differences by considering can we build monitors out of semaphores After all semaphores provide atomic operations and queuing Does this fix the problem Does this work Wait semaphore P Signal if semaphore queue is not empty Signal semaphore V semaphore V Condition variables only work inside of a lock If you try to use semaphores inside of a lock you have to watch for deadlock For one it is not legal to look at contents of semaphore queue But there is also a race condition signaler can slip in after lock is released and before wait Then waiter never wakes up Does this work Wait Lock lock Program needs to release lock and go to sleep atomically lock Release semaphore P Is it possible to implement condition variables using semaphores Yes but exercise left to the reader lock Acquire 9 3 Summary of Monitors Signal Monitors represent the logic of the program wait if necessary signal if change something so waiter might need to wake up Condition variables have no history but semaphores do have history lock semaphore V while need to wait What if thread signals and no one is waiting No op What if thread later waits Thread waits wait unlock do something so no need to wait What if thread V s and no one is waiting Increment What if thread later does P Decrement and continue CS 162 Spring 2003 Lecture 9 lock signal unlock 5 13 CS 162 Spring 2003 Lecture 9 6 13 9 4 Language support for thread synchronization The problem with requiring the programmer to specify both lock acquire and release statements is that he might forget to put a release everywhere it is needed 9 4 1 Languages like C This is not too bad in a language like C just make sure you know all the code paths out of a critical section int Rtn lock acquire if exception lock release return errReturnCode lock release return OK Watch out for setjmp longjmp Might happen in called procedure 9 4 2 Languages like C Languages that support exceptions like C are more problematic void Rtn lock acquire DoFoo lock release void DoFoo if exception throw errException CS 162 Spring 2003 Lecture 9 7 13 CS 162 Spring 2003 Lecture 9 8 13 Rtn needs to catch the exception release the lock and then re throw the exception void Rtn Java also has synchronized statements lock acquire synchronized object try DoFoo Every Java object has an associated lock Any Java object can be used to control access to a synchronized block of code The synchronizing object s lock is acquired on entry and released on exit even if exit is by means of a thrown exception catch C syntax for catching any exception lock release synchronized object throw C syntax for re throwing an exception DoFoo lock release void DoFoo 9 4 3 Java Java has explicit support for threads and thread synchronization throw errException Bank account example class Account How to wait in a synchronized method or code block private int balance object constructor void wait long timeout void wait long timeout int nanoseconds void wait public Account int initialBalance How to signal in a synchronized method or code block balance initialBalance void notify wakes up the longest waiting waiter void notifyAll like broadcast wakes up all waiters public synchronized int getBalance return balance public synchronized void deposit int amount balance amount Each Account object has an associated lock which gets automatically acquired and released on entry and exit from each synchronized method CS 162 Spring 2003 Lecture 9 9 13 CS 162 Spring 2003 Lecture 9 10 13 Notes Only one condition variable per lock Condition variables can wait for a bounded length of time This is useful for handling exception cases where something has failed For example 9 6 Cautionary Tale OS 2 Illustrates why an abstraction doesn t always work the way you want it to t1 time now Microsoft OS 2 around 1988 initially a spectacular failure Since then IBM while ATMRequest has completely re written it from scratch wait LONG TIME t2 time now Used threads for everything window systems communication between if t2 t1 LONG TIME CheckIfMachineBroken
View Full Document
Unlocking...