Bakery Algorithm

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 number[j], j) < (number[i],i) do
10.             (* nothing *);
11.   end;
12.   (* critical section *)
13.   number[i] := 0; 
14.   (* remainder section *)
15. until false;

lines 1–2: Here, choosing[i] is true if process i is choosing a number. The number that process i will use to enter the critical section is in number[i]; it is 0 if process 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 process i (line 5); however, that does not always happen. Afterwards, process i indicates it is done (line 6).

lines 8–11: Now we select which process goes into the critical section. Process i 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 index — 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 process i tries to look at it, process i waits until it has done so before looking (line 8).

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

UC Davis sigil
Matt Bishop
Office: 2209 Watershed Sciences
Phone: +1 (530) 752-8060
ECS 150, Operating Systems
Version of April 17, 2022 at 9:30PM

You can also obtain a PDF version of this.

Valid HTML 4.01 Transitional Built with BBEdit Built on a Macintosh