●●● ●●●● 6. Process synchronization 9989 ●●●0 Objectives ●●●● 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 o introduce the concept of an atomic transaction and describe mechanisms to ensure atomicity
2 6. Process synchronization ⚫ Objectives ⚫ 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 introduce the concept of an atomic transaction and describe mechanisms to ensure atomicity
●●● ●●●● 6. Process synchronization 9988 ●●●● e 6.1 Background ●●●● o 6.2 The Critical-Section Problem °6.3 Peterson’sSo|uton 6.4 Synchronization Hardware 6.5 Semaphores o 6.6 Classic Problems of synchronization ●67 Monitors e 6.8 Synchronization Examples o 6.9 Atomic transactions
3 6. Process synchronization ⚫ 6.1 Background ⚫ 6.2 The Critical-Section Problem ⚫ 6.3 Peterson’s Solution ⚫ 6.4 Synchronization Hardware ⚫ 6.5 Semaphores ⚫ 6.6 Classic Problems of Synchronization ⚫ 6.7 Monitors ⚫ 6.8 Synchronization Examples ⚫ 6.9 Atomic Transactions
●●● ●●●● 6.1 Background ●●●●● ●●●● ●●0●● ●●●0 o Concurrent access to shared data may result in data inconsistency o A example: bounded buffer problem with shared data o Producer while(true)( produce an item in nextProduced * while(count== BUFFER SIZE); /do nothing buffer [in]= nextProduced; in=(in+1)% BUFFER SIZE count++
4 6.1 Background ⚫ Concurrent access to shared data may result in data inconsistency ⚫ A example: bounded buffer problem with shared data ⚫ Producer while (true) { /* produce an item in nextProduced */ while (count == BUFFER_SIZE); // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; count++; }
●●● ●●●● 6.1 Background ●●●●● ●●●● ●●0●● ●●●● Consumer ●●●● while(true)t while(count==0); //do nothing nextConsumed= buffer[out] out=out+ 1)% BUFFER SIZE count--, /* consume the item in nextconsumed*/ o The statements /* count=5*/ count++e l/Producer count-- ∥/ Consumer
5 6.1 Background ⚫ Consumer while (true) { while (count == 0); // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /* consume the item in nextConsumed*/ } ⚫ The statements /* count=5 */ count++; //Producer count--; // Consumer
●●● ●●●● 6.1 Background ●●●●● ●●●● ●●0●● ●●●● o count++ could be implemented as ●●●● register1 count register1 register1+ 1 count= register1 o count--could be implemented as register2= count register2 register2 -1 count= register2 Remember that the contents of the register will be saved and restored by the interrupt
6 6.1 Background ⚫ count++ could be implemented as register1 = count register1 = register1 + 1 count = register1 ⚫ count-- could be implemented as register2 = count register2 = register2 - 1 count = register2 Remember that the contents of the register will be saved and restored by the interrupt
●●● ●●●● 6.1 Background ●●●●● ●●●● ●●0●● ●●●0 ● f both the producer and consumer attempt to。 update the buffer concurrently, the assembly language statements may get interleaved One such interleaving is TO: producer execute register1=count [register1= 5] T1: producer execute register1= register1+1 register1= 6] T2: consumer execute register2=count Register= 5) T3: consumer execute register2= register2 -1 register2=41 T4: consumer execute count= register2 Icount=4] T5: producer execute count= registert Icount=61 The value of count may be either 4 or 6, where the correct result should be 5
7 6.1 Background ⚫ If both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved ⚫ One such interleaving is T0: producer execute register1 = count {register1 = 5} T1: producer execute register1 = register1 + 1 {register1 = 6} T2: consumer execute register2 = count {register2 = 5} T3: consumer execute register2 = register2 - 1 {register2 = 4} T4: consumer execute count = register2 {count = 4} T5: producer execute count = register1 {count = 6 } ⚫ The value of count may be either 4 or 6, where the correct result should be 5
●●● ●●●● 6.1 Background ●●●●● ●●●● ●●0●● ●●●0 Race condition(竟争状态读写的交错情形)°° The situation where several processes access and manipulate shared data concurrent o The final value of the shared data depends upon which process finishes last Solution---Synchronized Concurrent process must be synchronized To prevent race conditions and maintain data consistency requires mechanisms to ensure the orderly execution of cooperating processes ( serialization在临界区串行化) How
8 6.1 Background ⚫ 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. ⚫ Solution---Synchronized ⚫ Concurrent process must be synchronized ⚫ To prevent race conditions and maintain data consistency requires mechanisms to ensure the orderly execution of cooperating processes (serialization 在临界区串行化) ⚫ How ？
●●● ●●●● 6. Process synchronization 9988 ●●●● e 6.1 Background ●●●● o 6.2 The Critical-Section Problem °6.3 Peterson’sSo|uton 6.4 Synchronization Hardware 6.5 Semaphores o 6.6 Classic Problems of synchronization ●67 Monitors e 6.8 Synchronization Examples o 6.9 Atomic transactions
9 6. Process synchronization ⚫ 6.1 Background ⚫ 6.2 The Critical-Section Problem ⚫ 6.3 Peterson’s Solution ⚫ 6.4 Synchronization Hardware ⚫ 6.5 Semaphores ⚫ 6.6 Classic Problems of Synchronization ⚫ 6.7 Monitors ⚫ 6.8 Synchronization Examples ⚫ 6.9 Atomic Transactions
●●● ●●●● 6.2 The Critical-Section Problem :: ●●●● ° Critica| section ●●●● The n processes compete to use some shared data(临界资源) o Changing common variables o updating a table writing a file o Each process has a code segment, called critical section, in which the shared data is accessed
10 6.2 The Critical-Section Problem ⚫ Critical section ⚫ The n processes compete to use some shared data （临界资源） ⚫ Changing common variables ⚫ updating a table ⚫ writing a file ⚫ Each process has a code segment, called critical section, in which the shared data is accessed
●●● ●●●● 6.2 The Critical-Section Problem: ●●●0 e The critical section problem ●●●● o Be how to design a protocol that One process is executing in its critical section, no other process is to be allowed to execute in its critical section of accessing the same shared data No two processes are executing in their critical section at the same time
11 6.2 The Critical-Section Problem ⚫ The critical section problem ⚫ Be how to design a protocol that ⚫ One process is executing in its critical section, no other process is to be allowed to execute in its critical section of accessing the same shared data ⚫ No two processes are executing in their critical section at the same time