Question

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]! = 0) && (number[j],j) < (number[i],i)) { };
6 }
7 /* critical section */;
8 number [i] = 0;
9 /* remainder */;
10 }
Does this version violate mutual exclusion? Explain why or why not.

Answer 1

Suppose we have two processes just beginning; call them p0 and p1. Both reach line 3 at the same time. Now, we'll assume both read number[0] and number[1] before either addition takes place. Let p1 complete the line, assigning 1 to number[1], but p0 block before the assignment. Then p1 gets through the while loop at line 5 and enters the critical section. While in the critical section, it blocks; p0 unblocks, and assigns 1 to number[0] at line 3. It proceeds to the while loop at line 5. When it goes through that loop for j = 1, the first condition on line 5 is true. Further, the second condition on line 5 is false, so p0 enters the critical section. Now p0 and p1 are both in the critical section, violating mutual exclusion. The reason for choosing is to prevent the while loop in line 5 from being entered when process j is setting its number[j]. Note that if the loop is entered and then process j reaches line 3, one of two situations arises. Either number[j] has the value 0 when the first test is executed, in which case process i moves on to the next process, or number[j] has a non-zero value, in which case at some point number[j] will be greater than number[i] (since process i finished executing statement 3 before process j began). Either way, process i will enter the critical section before process j, and when process j reaches the while loop, it will loop at least until process i leaves the critical section.

Either way, process i will enter the critical section before process j, and when process j reaches the while loop, it will loop at least until process i leaves the critical section.