# Question: A software approach to mutual exclusion is Lamport s bakery algorithm

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.

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.

**View Solution:**## Answer to relevant Questions

Now consider a version of the bakery algorithm without the variable choosing. Then we have 1 int number[n]; 2 while (true) { 3 number[i] = 1 + getmax(number[], n); 4 for (int j = 0; j < n; j++){ 5 while ((number[j]! ...It should be possible to implement general semaphores using binary semaphores. We can use the operations semWaitB and semSignalB and two binary semaphores, delay and mutex. Consider the following: void semWait(semaphore ...Suppose the following two processes, foo and bar, are executed concurrently and share the semaphore variables S and R (each initialized to 1) and the integer variable x (initialized to 0). a. Can the concurrent execution of ...Show that the four conditions of deadlock apply to Figure. In the THE multiprogramming system, a page can make the following state transitions: 1. Empty S input buffer ........ (Input production) 2. Input buffer S processing area ...... (Input consumption) 3. Processing ...Post your question