CS162 Operating Systems and Systems Programming Lecture 7 Mutual Exclusion Semaphores Monitors and Condition Variables September 21 2005 Prof John Kubiatowicz http inst eecs berkeley edu cs162 Review A Concurrent Program Example Two threads A and B compete with each other One tries to increment a shared counter The other tries to decrement the counter Thread A Thread B i 0 i 0 while i 10 while i 10 i i 1 i i 1 printf A wins printf B wins Assume that memory loads and stores are atomic but incrementing and decrementing are not atomic Who wins Could be either Is it guaranteed that someone wins Why or why not What it both threads have their own CPU running at same speed Is it guaranteed that it goes on forever 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 2 Review Hand Simulating Multiprocessor Example Inner loop looks like this Thread AThread B r1 0 load r1 M i r1 0 load r1 M i r1 1 add r1 r1 1 r1 1 sub r1 r1 1 M i 1 store r1 M i M i 1 store r1 M i Hand Simulation And we re off A gets off to an early start B says hmph better go fast and tries really hard A goes ahead and writes 1 B goes and writes 1 A says HUH I could have sworn I put a 1 there Could this happen on a uniprocessor Yes Unlikely but if you depending on it not happening it will and your system will break 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 3 Review Too Much Milk Solution 3 Here is a possible two note solution Thread A Thread B leave note A while note B do nothing buy milk if noMilk buy milk remove note B remove note A leave note B if noNote A if noMilk Does this work Yes Both can guarantee that It is safe to buy or Other will buy ok to quit At A if no note B safe for A to buy otherwise wait to find out what will happen At B if no note A safe for B to buy Otherwise A is either buying or waiting for B to quit 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 4 Goals for Today Hardware Support for Synchronization Higher level Synchronization Abstractions Semaphores monitors and condition variables Programming paradigms for concurrent programs Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 5 Gagne High 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 paradigms 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 6 Where are we going with synchronization Program s Higherlevel API Hardwar e Shared Programs Locks Semaphores Load Store Monitors Disable Ints Comp Swap Send Receive Test Set We are going to implement various higher level synchronization primitives using atomic operations Everything is pretty painful if only atomic primitives are load and store Need to provide primitives useful at user level 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 7 How 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 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 task to sleep How do you handle the interface between the hardware and scheduler 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 8 Na ve use of Interrupt Enable Disable 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 9 21 05 Reactor about to meltdown Kubiatowicz CS162 UCBHelp Fall 2005 Lec 7 9 Better Implementation of Locks by Disabling Interrupts Key idea maintain a lock variable and impose mutual exclusion only during operations on that variable int value FREE Acquire Release disable interrupts disable interrupts if value BUSY if anyone on wait queue 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 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 10 New 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 Acquire disable interrupts if value BUSY put thread on wait queue Go to sleep Enable interrupts else value BUSY enable interrupts Critical Section Note unlike previous solution the critical section inside Acquire is very short User of lock can take as long as they like in their own critical section doesn t impact global machine behavior 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 11 Critical interrupts taken in time Interrupt re enable in going to sleep 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 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 Want to put it after sleep But how 9 21 05 Kubiatowicz CS162 UCB Fall 2005 Lec 7 12 Administrivia First Design Document due Monday 9 26 Subsequently need to schedule design review with TA through web form Note that Much of the design document grade
View Full Document
Unlocking...