Space Shuttle Example Original Space Shuttle launch aborted 20 minutes before scheduled launch Shuttle has five computers CS162 Operating Systems and Systems Programming Lecture 4 Four run the Primary Avionics Software System PASS PASS Asynchronous and real time Runs all of the control systems Results synchronized and compared every 3 to 4 ms Synchronization Atomic operations Locks Semaphores BFS The Fifth computer is the Backup Flight System BFS stays synchronized in case it is needed Written by completely different team than PASS Countdown aborted because BFS disagreed with PASS January 31 2011 Ion Stoica http inst eecs berkeley edu cs162 A 1 67 chance that PASS was out of sync one cycle Bug due to modifications in initialization code of PASS A delayed init request placed into timer queue As a result timer queue not empty at expected time to force use of hardware clock Bug not found during extensive simulation 31 1 11 Another Concurrent Program Example Synchronization Hardware Support for Synchronization Higher level Synchronization Abstractions One tries to increment a shared counter The other tries to decrement the counter Thread A i 0 while i 10 i i 1 printf A wins Thread B i 0 while i 10 i i 1 printf B wins Semaphores monitors and condition variables Programming paradigms for concurrent programs Assume that memory loads and stores are atomic but incrementing and decrementing are not atomic Who wins 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 31 1 11 Ion Stoica CS162 UCB Spring 2011 Lec 4 2 Goals for Today Two threads A and B compete with each other Ion Stoica CS162 UCB Spring 2011 Note Some slides and or pictures in the following are adapted from slides 2005 Silberschatz Galvin and Gagne Gagne Many slides generated by Kubiatowicz 31 1 11 Lec 4 3 Page 1 Ion Stoica CS162 UCB Spring 2011 Lec 4 4 Motivation Too much milk Definitions Great thing about OS s analogy between problems in OS and problems in real life Synchronization using atomic operations to ensure cooperation between threads Help you understand real life problems better But computers are much stupider than people For now only loads and stores are atomic We ll show its hard to build anything useful with only reads and writes Example People need to coordinate Time 3 00 3 05 3 10 3 15 3 20 3 25 3 30 31 1 11 Person A Look in Fridge Out of milk Leave for store Arrive at store Buy milk Arrive home put milk away Person B Mutual Exclusion ensuring that only one thread does a particular thing at a time One thread excludes the other while doing its task Look in Fridge Out of milk Leave for store Arrive at store Buy milk Arrive home put milk away Ion Stoica CS162 UCB Spring 2011 Critical Section piece of code that only one thread can execute at once Critical section is the result of mutual exclusion Critical section and mutual exclusion are two ways of describing the same thing 31 1 11 Lec 4 5 Lock prevents someone from doing something Need to be careful about correctness of concurrent programs since non deterministic Lock before entering critical section and before accessing shared data Unlock when leaving after accessing shared data Wait if locked Always write down behavior first Impulse is to start coding first then when it doesn t work pull hair out Instead think first then code Important idea all synchronization involves waiting For example fix the milk problem by putting a key on the refrigerator What are the correctness properties for the Too much milk problem Lock it and take key if you are going to go buy milk Fixes too much roommate angry if only wants orange juice Never more than one person buys Someone buys if needed Restrict ourselves to use only atomic load and store operations as building blocks Of Course We don t know how to make a lock yet Ion Stoica CS162 UCB Spring 2011 Lec 4 6 Too Much Milk Correctness Properties More Definitions 31 1 11 Ion Stoica CS162 UCB Spring 2011 31 1 11 Lec 4 7 Page 2 Ion Stoica CS162 UCB Spring 2011 Lec 4 8 Too Much Milk Solution 1 Too Much Milk Solution 1 Still too much milk but only occasionally Use a note to avoid buying too much milk Thread A if noMilk if noNote Leave a note before buying kind of lock Remove note after buying kind of unlock Don t buy if note wait if noMilk if noNote leave Note buy milk remove note Suppose a computer tries this remember only memory read write are atomic if noMilk if noNote leave Note buy milk remove note Makes it really hard to debug Must work despite what the thread dispatcher does Ion Stoica CS162 UCB Spring 2011 31 1 11 Lec 4 9 Too Much Milk Solution 1 Lec 4 10 How about labeled notes Let s try to fix this by placing note first Now we can leave note before checking Another try at previous solution Algorithm looks like this leave Note if noMilk if noNote buy milk remove note What happens here Well with human probably nothing bad With computer no one ever buys milk Ion Stoica CS162 UCB Spring 2011 Ion Stoica CS162 UCB Spring 2011 Too Much Milk Solution 2 Clearly the Note is not quite blocking enough 31 1 11 leave Note buy milk Thread can get context switched after checking milk and note but before buying milk Solution makes problem worse since fails intermittently Result 31 1 11 Thread B Thread A leave note A if noNote B if noMilk buy Milk remove note A Thread B leave note B if noNote A if noMilk buy Milk remove note B Does this work 31 1 11 Lec 4 11 Page 3 Ion Stoica CS162 UCB Spring 2011 Lec 4 12 Too Much Milk Solution 2 problem Too Much Milk Solution 2 Possible for neither thread to buy milk Thread A Thread B leave note A leave note B if noNote A if noMilk buy Milk if noNote B if noMilk buy Milk remove note B Really insidious I m not getting milk You re getting milk This kind of lockup is called starvation Unlikely that this would happen but will at worse possible time 31 1 11 Ion Stoica CS162 UCB Spring 2011 31 1 11 Lec 4 13 Review Too Much Milk Solution 3 Our solution protects a single Critical Section piece of code for each thread 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 Does this work Yes Both can guarantee that Code would have to be slightly different for each thread It is safe to buy or Other
View Full Document
Unlocking...