CS 162 Spring 2003 Lecture 9 1/13 CS 162 Operating Systems and Systems Programming Professor: Anthony D. Joseph Spring 2003 Lecture 9: Readers-Writers and Language Support for Synchronization 9.0 Main points: 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 9.1 Readers/Writers 9.1.1 Motivation Shared database (for example, bank balances, or airline seats) 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 CS 162 Spring 2003 Lecture 9 2/13 9.1.2 Constraints 1. Readers can access database when no writers (Condition okToRead) 2. Writers can access database when no readers or writers (Condition okToWrite) 3. Only one thread manipulates state variables at a time. 9.1.3 Solution Basic structure of solution Reader wait until no writers access database check out – wake up waiting writer Writer wait until no readers or writers access database check out – wake up waiting readers or writer State variables: # 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 = FREECS 162 Spring 2003 Lecture 9 3/13 Code: Reader() { // first check self into system lock.Acquire(); while ((AW + WW) > 0) { // check if safe to read // if any writers, wait WR++; okToRead.Wait(&lock); WR--; } AR++; lock.Release(); Access DB // check self out of system lock.Acquire(); AR--; if (AR == 0 && WW > 0) //if no other readers still // active, wake up writer okToWrite.Signal(&lock); lock.Release(); } CS 162 Spring 2003 Lecture 9 4/13 Writer() { // symmetrical // check in lock.Acquire(); while ((AW + AR) > 0) { // check if safe to write // if any readers or // writers, wait WW++; okToWrite->Wait(&lock); WW--; } AW++; lock.Release(); Access DB // check out lock.Acquire(); AW--; if (WW > 0) // give priority to other writers okToWrite->Signal(&lock); else if (WR > 0) okToRead->Broadcast(&lock); lock.Release(); } Questions: 1. Can readers starve? 2. Why does checkRead need a while?CS 162 Spring 2003 Lecture 9 5/13 9.2 Comparison between semaphores and monitors Illustrate the differences by considering: can we build monitors out of semaphores? After all, semaphores provide atomic operations and queuing. Does this work? Wait() { semaphore->P(); } Signal() { 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. Does this work? Wait(Lock *lock) { lock->Release(); semaphore->P(); lock->Acquire(); } Signal() { semaphore->V(); } Condition variables have no history, but semaphores do have history. What if thread signals and no one is waiting? No op. What if thread later waits? Thread waits. 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 6/13 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. Does this fix the problem? Signal() { if semaphore queue is not empty semaphore->V(); } 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! Program needs to release lock and go to sleep atomically. Is it possible to implement condition variables using semaphores? Yes, but exercise left to the reader! 9.3 Summary of Monitors Monitors represent the logic of the program – wait if necessary, signal if change something so waiter might need to wake up. lock while (need to wait) { wait(); } unlock do something so no need to wait lock signal(); unlockCS 162 Spring 2003 Lecture 9 7/13 CS 162 Spring 2003 Lecture 9 8/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 9/13 Rtn() needs to catch the exception, release the lock, and then re-throw the exception: void Rtn() { lock.acquire(); try { … DoFoo(); … } catch (…) { // C++ syntax for catching any exception. lock.release(); throw; // C++ syntax for re-throwing an exception. } lock.release(); } 9.4.3 Java Java has explicit support for threads and thread synchronization. Bank account example: class Account { private int balance; // object constructor public Account (int initialBalance) { balance = initialBalance; } 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 10/13 Java also has synchronized statements: synchronized (object) { … } 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: synchronized (object) { … DoFoo(); … } void DoFoo() { … throw errException; … } How to wait in a synchronized method or code block: • void wait(long
View Full Document
Unlocking...