Lamports bakery algorithm [LAMP74] is a software approach to mutual exclusion that supports an arbitrary number of processes (unlike Petersons solution, which supports only two processes). Lamports 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 Lamports 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 i^th 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 Lamports algorithm in words.

[LAMP74] Lamport, L. A New Solution to Dijkstras Concurrent Programming Problem. Communications of the ACM, August 1974.