This algorithm solves the critical section problem for n processes using a Test and Set instruction (called TaS here). This instruction does the following function atomically:
function TaS(var Lock: boolean): boolean; begin TaS := Lock; Lock := true; end;
1 var waiting: shared array [0..n-1] of boolean; 2 Lock: shared boolean; 3 j: 0..n-1; 4 key: boolean; ... 5 repeat (* process Pi *) 6 waiting[i] := true; 7 key := true; 8 while waiting[i] and key do 9 key := TaS(Lock); 10 waiting[i] := false; 11 (* critical section goes here *) 12 j := i + 1 mod n; 13 while (j <> i) and not waiting[j] do 14 j := j + 1 mod n; 15 if j = i then 16 Lock := false 17 else 18 waiting[j] := false; 19 until false;
lines 1-2: These are global to all processes, and are all initialized to false.
lines 3-4: These are local to each process Pi and are uninitialized.
lines 5-10: This is the entry section. Basically, waiting[i] is true as long as Pi is trying to get into its critical section; if any other process is in that section, then Lock will also be true, and Pi will loop in lines 8-9. Once Pi can go on, it is no longer waiting for permission to enter, and sets waiting[i] to false (line 10); it then proceeds into the critical section. Note that Lock is set to true by the TaS instruction in line 9 that returns false.
lines 12-18: This is the exit section. When Pi leaves the critical section, it must choose which other waiting process may enter next. It starts with the process with the next higher index (line 12). It checks each process to see if that process is waiting for access (lines 13-14); if no-one is, it simply releases the lock (by setting Lock to false; lines 15-16). However, if some other process Pj is waiting for entry, Pi simply shanges waiting[j] to false to allow Pj to enter the critical section (lines 17-18).
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562