Dekker,s Algorithm -Third Attempt var flag: array [0.1 of boolean false PROCESS O PROCESS flag[o: true; flag: =true; while flaglll do nothingi; while flaglo do nothing; <critical section>; <critical section> flag[0: false; flag 1: = false; ROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –Third Attempt PROCESS 1 … flag[1]:=true; while flag[0] do {nothing}; <critical section> flag[1]:=false; … var flag : array [0..1] of boolean : false; PROCESS 0 … flag[0]:=true; while flag[1] do {nothing}; <critical section>; flag[0]:=false; …
Dekker,s Algorithm -Third Attempt ☆ analysis PO: set flago=true; Pl: set flagyl=true; PO: do: while flagll i; block; Pl: do: while flago]; block; >causing deadlock PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –Third Attempt ❖ Analysis P0：set flag[0]=true; P1：set flag[1]=true; P0：do: while flag[1]; block； P1：do: while flag[0]; block； =>causing deadlock
Dekkers Algorithm -Fourth Attempt PROCESS O PROCESS 1 flag[o: true; flag1: = true; while flagyl do while flagon do begin begin flag[o: false flag1: = false; <delay for a short time> <delay for a short time>; flag[o: true; flagll: =true; end; end <critical section>' <critical section> flag[0: false; flag: =false; PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –Fourth Attempt PROCESS 1 … flag[1]:=true; while flag[0] do begin flag[1] :=false; <delay for a short time>; flag[1]:=true; end; <critical section> flag[1]:=false; … PROCESS 0 … flag[0]:=true; while flag[1] do begin flag[0] :=false; <delay for a short time>; flag[0]:=true; end; <critical section>; flag[0]:=false; …
Dekkers Algorithm -Fourth Attempt ☆ Analysis PO: set flagyl=true; 1: set flag=true; PO: do, while flag1; Pl: do, while flag[0l; P0: set flag false; set flagl1 false; PO: set flagon=true; Pl: set flag 1=true;...... Repeat this sequence forever, both process cannot enter the critical section. (not deadlock PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –Fourth Attempt ❖ Analysis P0：set flag[0]=true; P1：set flag[1]=true; P0：do, while flag[1]; P1：do,while flag[0]; P0：set flag[0]=false; P1：set flag[1]=false; P0：set flag[0]=true; P1：set flag[1]=true; …… Repeat this sequence forever, both process cannot enter the critical section. (not deadlock)
Dekker's Algorithm -A Correct Solution Var flag: array 0.1 of boolean; turn: 0..1; Procedure po Procedure pl Begin Begin repeat repeat flago: true fagl: true; while flagll do if turn=l then while flaglo] do if turn=0 then begin begin flag[0: false; flag1: false while turn=l do nothing while turn=0 do nothing flago: true; fagl: true; en d end <criticalsection>: turn: =1 criticalsection> turn: flago: false; <remainder> flag1: false; <remainder> forever forever End: End PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Dekker’s Algorithm –A Correct Solution Procedure P0; Begin repeat flag[0]:=true; while flag[1] do if turn=1 then begin flag[0]:=false; while turn=1 do {nothing} flag[0]:=true; end <critical section>; turn:=1; flag[0]:=false; <remainder> forever End; Procedure P1; Begin repeat flag[1]:=true; while flag[0] do if turn=0 then begin flag[1]:=false; while turn=0 do {nothing} flag[1]:=true; end <critical section>; turn:=0; flag[1]:=false; <remainder> forever End; Var flag:array[0..1] of boolean; turn:0..1;