Chapter 5: Process Synchronization PDF

Chapter 5: Process Synchronization Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 5: Process Synchronization Background The Critical-Section Problem Peterson’s So...

Chapter 5: Process Synchronization Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 5: Process Synchronization Background The Critical-Section Problem Peterson’s Solution Synchronization Hardware Mutex Locks Semaphores Classic Problems of Synchronization Monitors Synchronization Examples Alternative Approaches Operating System Concepts – 9th Edition 5.2 Silberschatz, Galvin and Gagne ©2013  Objectives To present the concept of process synchronization. To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data To present both software and hardware solutions of the critical- section problem To examine several classical process-synchronization problems To explore several tools that are used to solve process synchronization problems Operating System Concepts – 9th Edition 5.3 Silberschatz, Galvin and Gagne ©2013  Background Processes can execute concurrently  May be interrupted at any time, partially completing execution Concurrent access to shared data may result in data inconsistency Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes Illustration of the problem: Suppose that we wanted to provide a solution to the consumer- producer problem that fills all the buffers. We can do so by having an integer counter that keeps track of the number of full buffers. Initially, counter 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. Operating System Concepts – 9th Edition 5.4 Silberschatz, Galvin and Gagne ©2013  Producer while (true) { while (counter == BUFFER_SIZE) ; buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; counter++; } Operating System Concepts – 9th Edition 5.5 Silberschatz, Galvin and Gagne ©2013  Consumer while (true) { while (counter == 0) ; next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; } Operating System Concepts – 9th Edition 5.6 Silberschatz, Galvin and Gagne ©2013  Race Condition Race Condition: The situation where several processes access and manipulate shared data concurrently, the final value of the data depends on which process finishes last.  Critical Section: A piece of code in a cooperating process in which the process may updates shared data (variable, file, database, etc.).  Critical Section Problem: Serialize executions of critical sections in cooperating processes Operating System Concepts – 9th Edition 5.7 Silberschatz, Galvin and Gagne ©2013  Race Condition counter++ could be implemented as register1 = counter register1 = register1 + 1 counter = register1 counter-- could be implemented as register2 = counter register2 = register2 - 1 counter = register2 Consider this execution interleaving with “count = 5” initially: S0: producer execute register1 = counter {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = counter {register2 = 5} S3: consumer execute register2 = register2 – 1 {register2 = 4} S4: producer execute counter = register1 {counter = 6 } S5: consumer execute counter = register2 {counter = 4} Operating System Concepts – 9th Edition 5.8 Silberschatz, Galvin and Gagne ©2013  Critical Section Problem Consider system of n processes {p0, p1, … pn-1} Each process has critical section segment of code  Process may be changing common variables, updating table, writing file, etc  When one process in critical section, no other may be in its critical section Critical section problem is to design protocol to solve this Each process must ask permission to enter critical section in entry section, may follow critical section with exit section, then remainder section Operating System Concepts – 9th Edition 5.9 Silberschatz, Galvin and Gagne ©2013  Solution to Critical-Section Problem 1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections 2. 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 indefinitely 3. 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 processes Operating System Concepts – 9th Edition 5.10 Silberschatz, Galvin and Gagne ©2013  Critical Section General structure of process Pi Operating System Concepts – 9th Edition 5.11 Silberschatz, Galvin and Gagne ©2013  Possible Solutions  2-Process Critical Section Problem  N-Process Critical Section Problem  Only 2 processes, P0 and P1  Processes may share some common variables to synchronize their actions.  Shared variables:  int s; initially s = 0 or 1  s = i  Pi can enter its critical section Operating System Concepts – 9th Edition 5.12 Silberschatz, Galvin and Gagne ©2013  Algorithm 1 Process Pi do { Process Pj //i=0, j=1 while (s != i); while (s!= j); critical section critical section s = i; s = j; remainder section } while (true); remainder section Does not satisfy the progress condition Operating System Concepts – 9th Edition 5.13 Silberschatz, Galvin and Gagne ©2013  Algorithm 2 do { flag[i] = true; //i=0 while (flag[j]); critical section flag[i] = false; remainder section } while (true); # P2 Process flag P0 P1 flag[J] = true; //j=1 F F while (flag[I]); critical section flag[j] = false; Operating System Concepts – 9th Edition 5.14 Silberschatz, Galvin and Gagne ©2013  Peterson’s Solution Good algorithmic description of solving the problem Two process solution Assume that the load and store machine-language instructions are atomic; that is, cannot be interrupted The two processes share two variables:  int s;  Boolean flag The variable turn indicates whose turn it is to enter the critical section The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is ready! Operating System Concepts – 9th Edition 5.15 Silberschatz, Galvin and Gagne ©2013  Algorithm for Process Pi do { flag[i] = true; s = j; while (flag[j] && s = = j); critical section flag[i] = false; remainder section } while (true); flag[J] = true; flag F F s = I; while (flag[i] && turn = = i); critical section flag[j] = false; Rem sec Operating System Concepts – 9th Edition 5.16 Silberschatz, Galvin and Gagne ©2013  Peterson’s Solution (Cont.) Provable that the three CS requirement are met: 1. Mutual exclusion is preserved Pi enters CS only if: either flag[j] = false or s = i 2. Progress requirement is satisfied 3. Bounded-waiting requirement is met Operating System Concepts – 9th Edition 5.17 Silberschatz, Galvin and Gagne ©2013  Semaphore Synchronization tool that provides more sophisticated ways (than Mutex locks) for process to synchronize their activities. Semaphore S – integer variable Can only be accessed via two indivisible (atomic) operations  wait() and signal()  Originally called P() and V() Definition of the wait() operation wait(S) { while (S