Review Synchronization problem with Threads One thread per transaction each running CS162 Operating Systems and Systems Programming Lecture 6 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 Mutual Exclusion Semaphores Monitors and Condition Variables Thread 1 load r1 acct balance Thread 2 load r1 acct balance add r1 amount2 store r1 acct balance February 11 2008 Prof Anthony D Joseph http inst eecs berkeley edu cs162 add r1 amount1 store 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 middle 2 11 08 Review Too Much Milk Solution 3 Here is a possible two note solution Thread A leave note A while note B X do nothing if noMilk buy milk remove note A Our solution protects a single Critical Section piece of code for each thread Thread B leave note B if noNote A Y if noMilk buy milk remove note B 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 It is safe to buy or Other will buy ok to quit While A is waiting it is consuming CPU time This is called busy waiting At X There s a better way if no note B safe for A to buy otherwise wait to find out what will happen Have hardware provide better higher level primitives than atomic load and store Build even higher level programming abstractions on this new hardware support At Y if no note A safe for B to buy Otherwise A is either buying or waiting for B to quit Joseph CS162 UCB Spring 2008 Lec 6 2 Review Solution 3 discussion Does this work Yes Both can guarantee that 2 11 08 Joseph CS162 UCB Spring 2008 Lec 6 3 2 11 08 Page 1 Joseph CS162 UCB Spring 2008 Lec 6 4 Goals for Today High Level Picture The abstraction of threads is good Hardware Support for Synchronization Higher level Synchronization Abstractions Maintains sequential execution model Allows simple parallelism to overlap I O and computation Semaphores monitors and condition variables Unfortunately still too complicated to access state shared between threads Programming paradigms for concurrent programs 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 paradigms Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne Gagne Many slides generated from my lecture notes by Kubiatowicz 2 11 08 Joseph CS162 UCB Spring 2008 2 11 08 Lec 6 5 Review Too Much Milk Solution 4 Suppose we have some sort of implementation of a lock more in a moment 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 sleep if 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 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 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 Skip the test since you always need more ice cream Joseph CS162 UCB Spring 2008 Lec 6 6 How to implement Locks 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 2 11 08 Joseph CS162 UCB Spring 2008 Lec 6 7 2 11 08 Page 2 Joseph CS162 UCB Spring 2008 Lec 6 8 Na ve use of Interrupt Enable Disable How can we build multi instruction atomic operations Better Implementation of Locks by Disabling Interrupts Key idea maintain a lock variable and impose mutual exclusion only during operations on that variable 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 int value FREE Avoiding internal events although virtual memory tricky Preventing external events by disabling interrupts Acquire Release disable interrupts disable interrupts 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 else Enable interrupts value FREE else value BUSY enable interrupts enable 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 2 11 08 Reactor about to meltdown Help Joseph CS162 UCB Spring 2008 2 11 08 Lec 6 9 New Lock Implementation Discussion Why do we need to disable interrupts at all What about re enabling ints when going to sleep Enable Position Enable Position Enable Position Acquire disable interrupts if value BUSY put thread on wait queue Go to sleep else value BUSY enable interrupts Before Putting thread on the wait queue Release can check the queue and not wake up thread After putting the thread on the wait queue Note unlike previous solution the critical section inside Acquire is very short Release puts the thread on the ready queue but the thread still thinks it needs to go to sleep Misses wakeup and still holds lock deadlock User of lock can take as long as they like in their own critical section doesn t impact global machine behavior Critical interrupts taken in time Joseph CS162 UCB Spring 2008 Lec 6 10 Interrupt re enable in going to sleep Avoid interruption between checking and setting lock value Otherwise two
View Full Document
Unlocking...