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, *choosing*[*i*] is true if P_{i} is choosing a
number. The number that P_{i} will use to enter the critical section is in
*number*[*i*]; it is 0 if P_{i} is not trying to enter its
critical section.

*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 P_{i} (line 5);
however, that does not always happen. Afterwards, P_{i} indicates it is done
(line 6).

*lines 7-12*: Now we select which process goes into the critical section. Pi
waits until it has the lowest number of all the processes waiting to enter the
critical section. If two processes have the same number, the one with the
smaller name - the value of the subscript - goes in; the notation "(a,b) <
(c,d)" means true if a < c or if both a = c and b < d (lines 9-10). Note
that if a process is not trying to enter the critical section, its number is 0.
Also, if a process is choosing a number when P_{i} tries to look at it, P_{i} waits
until it has done so before looking (line 8).

*line 14*: Now P_{i} is no longer interested in entering its critical section, so it
sets *number*[*i*] to 0.

Why does Lamport's Bakery algorithm used a variable called
*choosing* (see the algorithm, lines 1, 4, 6, and 8)? It is very
instructive to see what happens if you leave it out. This gives an example of
mutual exclusion being violated if you don't put *choosing* in.
But first, the algorithm (with the lines involving *choosing*
commented out) so you can see what the modification was:

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 ; *) 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;

Suppose we have two processes just beginning; call them *p*_{0} and *p*_{1}. Both reach line 5 at the same time. Now, we'll assume both read ` number[0]` and

The reason for choosing is to prevent the **while** loop in lines 9-11 from being entered when process *j* is setting its ` number[j]`. Note that if the loop is entered and then process

Send email to cs150@csif.cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562