1Lecture 4SynchronizationOctober 7, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapter 7 (Process Synchronization)Programming Assignment #1• Due Sunday, October 19, midnight3SynchronizationSynchronize: to (arrange events to) happen at same timeProcess synchronization• when one process has to wait for another• points in each process occur “at the same time”Uses of synchronization• avoid race conditions• wait for resources to become available4Example of a Race ConditionThe Credit/Debit ProblemProcess P0Credit (a) int a;{ int b; b = ReadBalance (); b = b + a; WriteBalance (b); PrintReceipt (b);}Process P1Debit (a) int a;{ int b; b = ReadBalance (); b = b - a; WriteBalance (b); PrintReceipt (b);}criticalsections5To Avoid Race ConditionsIdentify critical sections• sections of code executed by multiple processes• must run atomically with respect to each otherEnforce mutual exclusion• only one process active in a critical sectionProcess 0------------------------critical---section-----------------------Process 1------------------------critical---section-----------------------6Four Rules for Mutual Exclusion1. No two processes inside critical sections at same time2. No process outside a critical section may block others3. No process may wait forever to enter critical section4. No assumptions about speeds or number of CPU’s7How to Achieve Mutual Exclusion?Surround critical section with entry/exit codeEntry code should act as a barrier• if another process is in their critical section, block• otherwise, allow process to proceedExit code should act to release other entry barriers< entry code >< critical section >< exit code >< entry code >< critical section >< exit code >8Possible Solution: Software Lock?Lock indicates whether any process is in critical sectionRace condition in while loop (breaks Rule 1)P0while ( lock == CLOSED );lock = CLOSED;< critical section >lock = OPEN;P1while ( lock == CLOSED );lock = CLOSED;< critical section >lock = OPEN;shared int lock = OPEN;9Possible Solution: Take Turns?Alternate which process can enter critical sectionPrevents entry even if OK to enter (breaks Rule 2)P0while ( turn != P0 );< critical section >turn = P1;P1while ( turn != P1 );< critical section >turn = P0;shared int turn = P0;10Possible Solution: State Intention?Each process states it wants to enter critical sectionRace condition: prevents entry forever (breaks Rule 3)P0flag[P0] = TRUE;while ( flag[P1] );< critical section >flag[P0] = FALSE;P1flag[P1] = TRUE;while ( flag[P0] );< critical section >flag[P1] = FALSE;shared boolean flag[2] = {FALSE, FALSE};11Peterson’s SolutionIf there is competition, take turns; otherwise, enterWorks! Extends to n processes. Problem: busy-waitingP0flag[P0] = TRUE;turn = P1;while ( flag[P1] && turn == P1 );< critical section >flag[P0] = FALSE;P1flag[P1] = TRUE;turn = P0;while ( flag[P0] && turn == P0 );< critical section >flag[P1] = FALSE;int turn;shared boolean flag[2] = {FALSE, FALSE};12What about Turning Off Interrupts?By turning off interrupts, context-switching can’t occurToo restrictive: locks out all processes, even those not incritical section (breaks Rule 2)Doesn’t work on a multiprocessor (breaks Rule 4)P0InterruptsOff ();< critical section >InterruptsOn ();P1InterruptsOff ();< critical section >InterruptsOn ();13Hardware 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 valueSimple, works for n processes (but still busy-waits!)P0while ( tset (lock) == 1 );< critical section >lock = 0;P1while ( tset (lock) == 1 );< critical section >lock = 0;shared int lock = 0;14SemaphoresSemaphore: integer variable used for synchronization• has integer value• list of waiting processesWorks like a gate• If value > 0, gate is open, and value indicatesnumber of processes that can enter• Otherwise, gate is closed, possibly with waitingprocesses15Semaphore OperationsSemaphore s = n /* declare and initialize */Wait (s)if s is zero, block process (and associate with s)decrement s (note: occurs after process unblocks)Signal (s)increment sif any blocked processes, unblock one of themNo other operations permitted (e.g., can’t test value)16Mutual Exclusion with SemaphoresUse a “mutex” semaphore initialized to 1Allows only one process to enter critical sectionSimple, works for n processes, no busy-waiting (really?)P0Wait (mutex);< critical section >Signal (mutex);P1Wait (mutex);< critical section >Signal (mutex);sem mutex = 117Synchronization with SemaphoresUse a “synch” semaphore initialized to 0Allows a process to wait for another before proceedingSemaphores provide pure synchronization• no way for a process to tell it blocked• i.e., no information transferP0< to be done before P1 >Signal (synch);P1Wait (synch);< to be done after P0 >sem synch = 0;18Atomicity of Semaphore OperationsWait (sem) and Signal (sem) are atomic operations• their bodies are critical sectionsMutual exclusion achieved using a lower-level mechanism• test-and-set locks• turning off interrupts (on a uniprocessor)Therefore, problems such as busy-waiting still exist• but at a “lower-level”• for brief (and known) periods of
View Full Document
Unlocking...