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.