Another software approach to mutual exclusion is Lamport's bakery algorithm, 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