Before We Begin CSE 120 Principles of Operating Systems Read Chapter 7 Process Synchronization Lecture 4 Programming Assignment 1 Synchronization Due Sunday October 19 midnight October 7 2003 Prof Joe Pasquale Department of Computer Science and Engineering University of California San Diego 2003 by Joseph Pasquale 2 1 Synchronization Example of a Race Condition Synchronize to arrange events to happen at same time Process synchronization when one process has to wait for another points in each process occur at the same time The Credit Debit Problem Process P0 Process P1 Credit a int a int b Debit a int a int b Uses of synchronization b ReadBalance b b a WriteBalance b avoid race conditions wait for resources to become available 3 PrintReceipt b critical sections b ReadBalance b b a WriteBalance b PrintReceipt b 4 To Avoid Race Conditions Four Rules for Mutual Exclusion Identify critical sections 1 No two processes inside critical sections at same time sections of code executed by multiple processes 2 No process outside a critical section may block others must run atomically with respect to each other Process 0 critical section Enforce mutual exclusion 3 No process may wait forever to enter critical section Process 1 critical section only one process active in a critical section 4 No assumptions about speeds or number of CPU s 5 How to Achieve Mutual Exclusion Possible Solution Software Lock Lock indicates whether any process is in critical section Surround critical section with entry exit code entry code critical section exit code 6 entry code critical section exit code shared int lock OPEN P0 P1 lock CLOSED lock CLOSED while lock CLOSED Entry code should act as a barrier if another process is in their critical section block otherwise allow process to proceed critical section lock OPEN while lock CLOSED critical section lock OPEN Race condition in while loop breaks Rule 1 Exit code should act to release other entry barriers 7 8 Possible Solution Take Turns Possible Solution State Intention Each process states it wants to enter critical section Alternate which process can enter critical section shared int turn P0 shared boolean flag 2 FALSE FALSE P0 P1 P0 P1 critical section critical section while flag P1 while flag P0 while turn P0 while turn P1 turn P1 flag P0 TRUE turn P0 critical section flag P0 FALSE Prevents entry even if OK to enter breaks Rule 2 flag P1 TRUE critical section flag P1 FALSE Race condition prevents entry forever breaks Rule 3 9 Peterson s Solution What about Turning Off Interrupts If there is competition take turns otherwise enter By turning off interrupts context switching can t occur int turn shared boolean flag 2 FALSE FALSE P0 P1 turn P1 turn P0 flag P0 TRUE while flag P1 turn P1 critical section flag P0 FALSE 10 P0 P1 critical section critical section InterruptsOff flag P1 TRUE InterruptsOn while flag P0 turn P0 critical section flag P1 FALSE Works Extends to n processes Problem busy waiting 11 InterruptsOff InterruptsOn Too restrictive locks out all processes even those not in critical section breaks Rule 2 Doesn t work on a multiprocessor breaks Rule 4 12 Hardware Solution Test Set Instr TSET mem simultaneously test mem and set it to 1 reg mem mem 1 set cond code atomically C func tset lock sets lock to 1 returns orig value shared int lock 0 P0 P1 critical section critical section while tset lock 1 lock 0 Semaphores Semaphore integer variable used for synchronization has integer value list of waiting processes Works like a gate If value 0 gate is open and value indicates number of processes that can enter while tset lock 1 Otherwise gate is closed possibly with waiting processes lock 0 Simple works for n processes but still busy waits 13 Semaphore Operations Semaphore s n 14 Mutual Exclusion with Semaphores declare and initialize Use a mutex semaphore initialized to 1 Wait s sem mutex 1 if s is zero block process and associate with s decrement s note occurs after process unblocks P0 P1 critical section critical section Wait mutex Signal s Signal mutex increment s if any blocked processes unblock one of them Wait mutex Signal mutex Allows only one process to enter critical section No other operations permitted e g can t test value Simple works for n processes no busy waiting really 15 16 Synchronization with Semaphores Wait sem and Signal sem are atomic operations Use a synch semaphore initialized to 0 sem synch 0 P0 to be done before P1 Signal synch Atomicity of Semaphore Operations their bodies are critical sections P1 Mutual exclusion achieved using a lower level mechanism Wait synch to be done after P0 Allows a process to wait for another before proceeding Semaphores provide pure synchronization test and set locks turning off interrupts on a uniprocessor Therefore problems such as busy waiting still exist no way for a process to tell it blocked but at a lower level i e no information transfer for brief and known periods of time 17 18
View Full Document
Unlocking...