A software approach to mutual exclusion is Lamport's bakery algorithm [LAMP74], so cal...

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
  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. Describe the algorithm in words.

b. Show that this algorithm avoids deadlock.

c. Show that it enforces mutual exclusion.