Synchronization Peterson’s Solution.pptx

Synchronization problems in Peterson's Solution

1. Peterson’s Solution

2. Critical Section Problem Consider system of n processes {p , p 1 , … p n-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 Especially challenging with preemptive kernels

3. Critical Section General structure of process p i is

4. Solution to Critical-Section Problem 1. Mutual Exclusion - If process P i 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 - After a process has made a request to enter it’s CS, there is a bound on the number of times that the other processes are allowed to enter their CS otherwise the process will suffer from starvation Of course also no deadlock (no cycles)

5. Peterson’s solutions: Algorithm 1 Process Pi: repeat while(turn!=i){}; CS turn:=j; RS forever An execution view of Algorithm 1 Process P0: Process P1: repeat repeat while(turn!=0); while(turn!=1); CS CS turn:=1; turn:=0; RS RS forever forever

6. Algorithm 1 (cont.) The shared variable turn is initialized (to 0 or 1) before executing any Pi Pi’s critical section is executed iff turn = i Pi is busy waiting if Pj is in CS: mutual exclusion is satisfied Progress requirement is not satisfied since it requires strict alternation of CSs If a process requires its CS more often then the other, it cannot get it.

7. Algorithm 2 Flag[i]=flag[j]=false Process Pi: repeat flag[i]:=true; while(flag[j]); CS flag[i]:=false; RS forever Flag[i]=flag[j]=false Process Pj : repeat flag[j]:=true; while(flag[i]); CS flag[j]:=false; RS forever

8. Keep 1 Bool variable for each process: flag[0] and flag[1] Pi signals that it is ready to enter it’s CS by: flag[i]:=true Mutual Exclusion is satisfied but not the progress requirement If we have the sequence: T0: flag[0]:=true T1: flag[1]:=true Both process will wait forever to enter their CS: we have a deadlock

9. Algorithm 3 (Peterson’s algorithm) Process Pi: repeat flag[i]:=true; // want in turn:=j; // let the other in while (flag[j ]&turn=j){}; CS flag[i]:=false; // do not want in RS forever

10. Initialization: flag[0]:=flag[1]:=false turn:= 0 or 1 Willingness to enter CS specified by flag[i]:=true If both processes attempt to enter their CS simultaneously, only one turn value will last Exit section: specifies that Pi is unwilling to enter CS Execution view of Algorithm 3 Process P0: Process P1: repeat repeat flag[0]:=true; flag[1]:=true; turn:= 1; turn:= 0; while(flag[1]&turn=1){}; while(flag[0]&turn=0){}; CS CS flag[0]:=false; flag[1]:=false; RS RS forever forever

11. Synchronization Hardware Many systems provide hardware support for critical section code Uniprocessors – could disable interrupts Currently running code would execute without preemption mutual exclusion is preserved but efficiency of execution is degraded The reason is that while in CS, we cannot interleave execution with other processes that are in RS Generally too inefficient on multiprocessor systems Operating systems using this not broadly scalable Modern machines provide special atomic hardware instructions Atomic = non- interruptable mutual exclusion is not preserved Either test memory word and set value Or swap contents of two memory words

12. Hardware solutions: interrupt disabling/enabling Process Pi: repeat disable interrupts critical section enable interrupts remainder section forever

13. do { acquire lock critical section release lock remainder section } while (TRUE); Solution to Critical-section Problem Using Locks

14. TestAndSet Instruction Definition: boolean TestAndSet (boolean *target) { boolean rv = *target; *target = TRUE; return rv: }

15. Solution using TestAndSet Shared boolean variable lock, initialized to FALSE Solution: do { while ( TestAndSet (&lock )) ; // do nothing // critical section lock = FALSE; // remainder section } while (TRUE);

16. Swap Instruction Definition: void Swap (boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp: }

17. Solution using Swap Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key Solution: do { key = TRUE; while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section } while (TRUE);

18. Bounded-waiting Mutual Exclusion with TestandSet() do { waiting[i] = TRUE; key = TRUE; while (waiting[i] && key) key = TestAndSet(&lock); waiting[i] = FALSE; // critical section j = (i + 1) % n; while ((j != i) && !waiting[j]) j = (j + 1) % n; if (j == i) lock = FALSE; else waiting[j] = FALSE; // remainder section } while (TRUE);