Lamport’s bakery algorithm [LAMP74] is a software approach to mutual exclusion t

Question

Lamport’s bakery algorithm [LAMP74] is a software approach to mutual exclusion that supports an arbitrary number of processes (unlike Peterson’s solution, which supports only two processes). Lamport’s algorithm is called the “bakery algorithm” because it is based on a practice in bakeries, delicatessens, and other shops: Every customer is given a numbered ticket on arrival, allowing each customer to be served in turn.

The pseudocode for Lamport’s algorithm is as follows:

choosing[n];

number[n];

(true)

choosing[i] = true;

number[i] = 1 + getmax(number[], n);

choosing[i] = false;

(int j = 0; j < n; j++)

(choosing[j]) { };

((number[j]!= 0)

   && (number[j], j) < (number[i], i)) { };

/* critical section */

number[i] = 0;

/* remainder section */

The arrays choosing and number are initialized by default to false and 0, respectively. The ith element of each array may be read and written by process i , but other processes may only read it. The notation (a, b) < (c, d) is defined as:

(a < c) || ((a = c) && (b < d))

Explain Lamport’s algorithm in words.

[LAMP74] Lamport, L. “A New Solution to Dijkstra’s Concurrent Programming Problem.” Communications of the ACM, August 1974.

Explanation / Answer

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.

Algorithm

Let us give some line numbers and detailed structure for the algorithm provided.

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;

Please find the following comments for the individual line numbers for the alogorithm above.

lines 1-2: Here, choosing[i] is true if Pi is choosing a number. The number that Pi will use to enter the critical section is in number[i]; it is 0 if Pi 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 Pi (line 5); however, that does not always happen. Afterwards, Pi 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 Pi tries to look at it, Pi waits until it has done so before looking (line 8).

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

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.