Dekker,s algorithm -First Attempt var turn: 0.1; PROCESS O PROCESS 1 while turn#o do nothing while turn# 1 do nothing i <critical section> <critical section> turn: =0 turn: =1 Processes must strictly alternate in their use of their critical sections PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm —First Attempt PROCESS 1 … while turn ≠ 1 do {nothing}; <critical section> turn:=0; … var turn:0..1; PROCESS 0 … while turn≠0 do {nothing}; <critical section>; turn:=1; … Processes must strictly alternate in their use of their critical sections
Dekker's Algorithm-Second Attempt . o fig5.3: a two-lgloo solution for mutual exclusion (P199) 4 Each process may examine the others board but cannot alter it o When a process wishes to enter its critical section, it periodically checks the others board until it finds FALSE written on it, indicating that the other process is not in its critical section. PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –Second Attempt ❖ Fig5.3:A two-Igloo solution for mutual exclusion (P199) ❖ Each process may examine the other’s board but cannot alter it. ❖ When a process wishes to enter its critical section, it periodically checks the other’s board until it finds “FALSE” written on it, indicating that the other process is not in its critical section
Dekker's Algorithm-Second Attempt ☆ If false, writes“true” on its own board and enter. After finish. alter its board to show“ false” If true, busy waiting PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –Second Attempt ❖ If false, writes “true” on its own board and enter. After finish, alter its board to show “false” ❖ If true，busy waiting
Dekker's Algorithm-Second Attempt var flag array [o.1] of boolean: false PROCESS O PROCESS 1 while flag do nothingi while flaglo do nothing flag[0: true; flag: =trues <critical section> <critical section flag[0: false; flag1]: = false; ROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –Second Attempt PROCESS 1 … while flag[0] do {nothing}; flag[1]:=true; <critical section>; flag[1]:=false; … var flag : array [0..1] of boolean :false ; PROCESS 0 … while flag[1] do {nothing}; flag[0]:=true; <critical section>; flag[0]:=false; …
Dekker's Algorithm-Second Attempt ☆ Analysis Cannot guarantee mutual exclusion: PO: flag1=false; do while flag; Pl: flagl0false; do while flag 0l; PO: flaglo=true; <critical section>; P1: flagll=true; <critical section>; 7) PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –Second Attempt ❖ Analysis Cannot guarantee mutual exclusion: P0： flag[1]=false; do while flag[1]; P1：flag[0]=false; do while flag[0]; P0：flag[0]=true; <critical section>; P1：flag[1]=true; <critical section>;