Page 1CS162Operating Systems andSystems ProgrammingLecture 6Mutual Exclusion, Semaphores, Monitors, and Condition VariablesFebruary 11, 2008Prof. Anthony D. Josephhttp://inst.eecs.berkeley.edu/~cs162Lec 6.22/11/08 Joseph CS162 ©UCB Spring 2008Review: Synchronization problem with Threads• One thread per transaction, each running:Deposit(acctId, amount) {acct = GetAccount(actId); /* May use disk I/O */acct->balance += amount;StoreAccount(acct); /* Involves disk I/O */}• Unfortunately, shared state can get corrupted:Thread 1 Thread 2load r1, acct->balanceload r1, acct->balanceadd r1, amount2store r1, acct->balanceadd r1, amount1store r1, acct->balance• Atomic Operation: an operation that always runs to completion or not at all– It is indivisible: it cannot be stopped in the middle and state cannot be modified by someone else in the middleLec 6.32/11/08 Joseph CS162 ©UCB Spring 2008Review: Too Much Milk Solution #3• Here is a possible two-note solution:Thread A Thread Bleave note A; leave note B;while (note B) {\\X if (noNote A) {\\Ydo nothing; if (noMilk) {} buy milk;if (noMilk) { }buy milk; }} remove note B;remove note A;• Does this work? Yes. Both can guarantee that: – It is safe to buy, or– Other will buy, ok to quit• At X: – if no note B, safe for A to buy, – otherwise wait to find out what will happen• At Y: – if no note A, safe for B to buy– Otherwise, A is either buying or waiting for B to quitLec 6.42/11/08 Joseph CS162 ©UCB Spring 2008Review: Solution #3 discussion• Our solution protects a single ―Critical-Section‖ piece of code for each thread:if (noMilk) {buy milk;}• Solution #3 works, but it’s really unsatisfactory– Really complex – even for this simple an example» Hard to convince yourself that this really works– A’s code is different from B’s – what if lots of threads?» Code would have to be slightly different for each thread– While A is waiting, it is consuming CPU time» This is called ―busy-waiting‖• There’s a better way– Have hardware provide better (higher-level) primitives than atomic load and store– Build even higher-level programming abstractions on this new hardware supportPage 2Lec 6.52/11/08 Joseph CS162 ©UCB Spring 2008Goals for Today• Hardware Support for Synchronization• Higher-level Synchronization Abstractions– Semaphores, monitors, and condition variables• Programming paradigms for concurrent programsNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne Note: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne. Many slides generated from my lecture notes by Kubiatowicz.Lec 6.62/11/08 Joseph CS162 ©UCB Spring 2008High-Level Picture• The abstraction of threads is good:– Maintains sequential execution model – Allows simple parallelism to overlap I/O and computation• Unfortunately, still too complicated to access state shared between threads – Consider ―too much milk‖ example– Implementing a concurrent program with only loads and stores would be tricky and error-prone• Today, we’ll implement higher-level operations on top of atomic operations provided by hardware– Develop a ―synchronization toolbox‖– Explore some common programming paradigmsLec 6.72/11/08 Joseph CS162 ©UCB Spring 2008Review: Too Much Milk: Solution #4• Suppose we have some sort of implementation of a lock (more in a moment). – Lock.Acquire() – wait until lock is free, then grab– Lock.Release() – Unlock, waking up anyone waiting– These must be atomic operations – if two threads are waiting for the lock and both see it’s free, only one succeeds to grab the lock• Then, our milk problem is easy:milklock.Acquire();if (nomilk)buy milk;milklock.Release();• Once again, section of code between Acquire() and Release() called a ―Critical Section‖• Of course, you can make this even simpler: suppose you are out of ice cream instead of milk– Skip the test since you always need more ice cream.Lec 6.82/11/08 Joseph CS162 ©UCB Spring 2008How to implement Locks?• Lock: prevents someone from doing something– Lock before entering critical section and before accessing shared data– Unlock when leaving, after accessing shared data– Wait if locked» Important idea: all synchronization involves waiting» Should sleepif waiting for a long time• Atomic Load/Store: get solution like Milk #3– Looked at this last lecture– Pretty complex and error prone• Hardware Lock instruction– Is this a good idea?– Complexity?» Done in the Intel 432» Each feature makes hardware more complex and slow– What about putting a task to sleep?» How do you handle the interface between the hardware and scheduler?Page 3Lec 6.92/11/08 Joseph CS162 ©UCB Spring 2008• How can we build multi-instruction atomic operations?– Recall: dispatcher gets control in two ways. » Internal: Thread does something to relinquish the CPU» External: Interrupts cause dispatcher to take CPU– On a uniprocessor, can avoid context-switching by:» Avoiding internal events (although virtual memory tricky)» Preventing external events by disabling interrupts• Consequently, naïve Implementation of locks:LockAcquire { disable Ints; }LockRelease { enable Ints; }• Problems with this approach:– Can’t let user do this! Consider following:LockAcquire();While(TRUE) {;}– Real-Time system—no guarantees on timing! » Critical Sections might be arbitrarily long– What happens with I/O or other important events?» ―Reactor about to meltdown. Help?‖Naïve use of Interrupt Enable/DisableLec 6.102/11/08 Joseph CS162 ©UCB Spring 2008Better 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 6.112/11/08 Joseph CS162 ©UCB Spring 2008New Lock Implementation: Discussion• Why do we need to disable interrupts at all?– Avoid interruption between checking and setting lock value– Otherwise two threads could think that they both have lock• Note: unlike previous
View Full Document
Unlocking...