1CSC 4103 - Operating SystemsFall 2009Tevfik Ko!arLouisiana State UniversitySeptember 17th, 2009Lecture - VIIIProcess Synchronization - I2Roadmap• Process Synchronization• Race Conditions• Critical-Section Problem– Solutions to Critical Section– Different Implementations3Background• Concurrent access to shared data may result in data inconsistency• Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes• Consider consumer-producer problem: – Initially, count is set to 0– It is incremented by the producer after it produces a new buffer – and is decremented by the consumer after it consumes a buffer.4Producer: while (true){ /* produce an item and put in nextProduced while (count == BUFFER_SIZE) ; // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; count++; } while (1) { while (count == 0) ; // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; } /* consume the item in nextConsumedConsumer: Shared Variables: count=0, buffer[]Race Condition!Race condition: The situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last. !To prevent race conditions, concurrent processes must be synchronized. – Ensure that only one process at a time is manipulating the variable counter. ! The statements •counter++; •counter--; must be performed atomically. ! Atomic operation means an operation without interruption.56Race Condition• count++ could be implemented as register1 = count register1 = register1 + 1 count = register1• count-- could be implemented as register2 = count register2 = register2 - 1 count = register2• Consider this execution interleaving with “count = 5” initially: S0: producer execute register1 = count {register1 = 5}S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = count {register2 = 5} S3: consumer execute register2 = register2 - 1 {register2 = 4} S4: producer execute count = register1 {count = 6 } S5: consumer execute count = register2 {count = 4}Race Condition7char chin, chout;//sharedvoid echo(){ do { chin = getchar(); chout = chin; putchar(chout); } while (...);}Achar chin, chout; //sharedvoid echo(){ do { chin = getchar(); chout = chin; putchar(chout); } while (...);}B> ./echoHello world!Hello world!Single-threaded echo Multithreaded echo (lucky)> ./echoHello world!Hello world!123456luckyCPUscheduling!"Significant race conditions in I/O & variable sharingRace Condition8char chin, chout;//sharedvoid echo(){ do { chin = getchar(); chout = chin; putchar(chout); } while (...);}A> ./echoHello world!Hello world!Single-threaded echochar chin, chout; //sharedvoid echo(){ do { chin = getchar(); chout = chin; putchar(chout); } while (...);}B"Significant race conditions in I/O & variable sharing156234unluckyCPUscheduling!Multithreaded echo (unlucky)> ./echoHello world!ee....Race Condition9void echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}Bvoid echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}A> ./echoHello world!Hello world!Single-threaded echo"Significant race conditions in I/O & variable sharing156234unluckyCPUscheduling!Multithreaded echo (unlucky)> ./echoHello world!eH....Race Condition10"Significant race conditions in I/O & variable sharing#in this case, replacing the global variables with local variables did not solve the problem#we actually had two race conditions here:$one race condition in the shared variables and the order of value assignment$another race condition in the shared output stream: which thread is going to write to output first (this race persisted even after making the variables local to each thread)==> generally, problematic race conditions may occur whenever resources and/or data are shared (by processes unaware of each other or processes indirectly aware of each other)11Critical Section/Region• Critical section/region: segment of code in which the process may be changing shared data (eg. common variables)• No two processes should be executing in their critical sections at the same time --> prevents race conditions• Critical section problem: design a protocol that the processes use to cooperateCritical Section12"The “indivisible” execution blocks are critical regions#a critical region is a section of code that may be executed by only one process or thread at a timeBAcommon critical regionBAA’s critical regionB’s critical region#although it is not necessarily the same region of memory or section of program in both processes==> but physically different or not, what matters is that these regions cannot be interleaved or executed in parallel (pseudo or real)13Solution to Critical-Section ProblemA solution to the critical-section problem must satisfy the following requirements:1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely14Solution to Critical-Section Problem3. Bounded Waiting - A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted!Assume that each process executes at a nonzero speed !No assumption concerning relative speed of the N processesCritical Section15 enter critical region? exit critical region enter critical region? exit critical region#critical regions can be protected from concurrent access by padding them with entrance and exit gates (we’ll see how later): a thread must try to check in, then it must check out "We need mutual exclusion from critical regionsvoid echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}BAvoid echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while