Question

A software approach to mutual exclusion is Lamport’s bakery algorithm [LAMP74], so called because it is based on the practice in bakeries and other shops in which every customer receives a numbered ticket on arrival, allowing each to be served in turn. The algorithm is as follows:

boolean choosing[n];

int number[n];

while (true) {

choosing[i] = true;

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

choosing[i] = false;

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

while (choosing[j]) { };

while ((number[j] != 0) && (number[j],j) < (number[i],i)) { };

}

/* critical section */;

number [i] = 0;

/* remainder */;

}

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

(a < c) or (a = c and b < d)

a. Describe the algorithm in words.

b. Show that this algorithm avoids deadlock.

c. Show that it enforces mutual exclusion.

Answer 1

a.      

When a process wishes to enter its critical section, it is assigned a ticket number. The ticket number assigned is calculated by adding one to the largest of the ticket numbers currently held by the processes waiting to enter their critical section and the process already in its critical section. The process with the smallest ticket number has the highest precedence for entering its critical section. In case more than one process receives the same ticket number, the process with the smallest numerical name enters its critical section. When a process exits its critical section, it resets its ticket number to zero.

 

b.      

If each process is assigned a unique process number, then there is a unique, strict ordering of processes at all times. Therefore, deadlock cannot occur. 

 

c.      

To demonstrate mutual exclusion, we first need to prove the following lemma: if Pi is in its critical section, and Pk has calculated its number[k] and is attempting to enter its critical section, then the following relationship holds: 

 

( number[i], i ) < ( number[k], k )

 

 

To prove the lemma, define the following times:

 

Tw1 Pi reads choosing[k] for the last time, for j = k, in its first wait, so we have choosing[k] = false at Tw1.

Tw2 Pi begins its final execution, for j = k, of the second while loop. We therefore have Tw1 < Tw2.

Tk1 Pk enters the beginning of the repeat loop.

Tk2 Pk finishes calculating number[k].

Tk3 Pk sets choosing[k] to false. We have Tk1 < Tk2 < Tk3.

 

 

Since at Tw1, choosing[k] = false, we have either Tw1 < Tk1 or Tk3 < Tw1. In the first case, we have number[i] < number[k], since Pi was assigned its number prior to Pk; this satisfies the condition of the lemma.

 

 

In the second case, we have Tk2 < Tk3 < Tw1 < Tw2, and therefore Tk2 < Tw2. This means that at Tw2, Pi has read the current value of number[k]. Moreover, as Tw2 is the moment at which the final execution of the second while for j = k takes place, we have (number[i], i) < ( number[k], k), which completes the proof of the lemma.

 

 

It is now easy to show the mutual exclusion is enforced. Assume that Pi is in its critical section and Pk is attempting to enter its critical section. Pk will be unable to enter its critical section, as it will find number[i] ≠ 0 and (number[i], i) < (number[k], k).

It is now easy to show the mutual exclusion is enforced. Assume that Pi is in its critical section and Pk is attempting to enter its critical section.