This algorithm solves the critical section problem for *n* processes in
software. The basic idea is that of a bakery; customers take numbers, and
whoever has the lowest number gets service next. Here, of course, “service”
means entry to the critical section.

1 var choosing: shared array[0..n-1] of boolean; 2 number: shared array[0..n-1] of integer; ... 3 repeat 4 choosing[i] := true; 5 number[i] := max(number[0],number[1],...,number[n-1]) + 1; 6 choosing[i] := false; 7 for j := 0 to n-1 do begin 8 while choosing[j] do (* nothing *); 9 while number[j] <> 0 and 10 (number[j], j) < (number[i],i) do 11 (* nothing *); 12 end; 13 (* critical section *) 14 number[i] := 0; 15 (* remainder section *) 16 until false;

* lines 1-2*:
Here,

* lines 4-6*:
These three lines first indicate that the process is choosing a
number (line 4), then try to assign a unique number to the process process

* lines 7-12*:
Now we select which process goes into the critical section. Process

* line 14*:
Now process

You can also obtain a PDF version of this. | Version of April 15, 2008 at 5:310 PM |