choosing[i] is true while number[i] is being updated to be larger than all the other values in the number array — the new ticket value that the thread is taking. In the body of the for loop, the code first waits for choosing[j] to be false, which indicates that thread number j has chosen its ticket for this round. If thread j goes on executing while thread i hasn't entered the critical section yet, then number[i] won't change, so:
- If thread
j is still in the same round and hasn't finished the critical section yet, then number[j] is the result of a max computation which may or may not have taken the current value of number[i] into account, depending on the interleaving of the execution of threads i and j.
- If thread
j is in the remainder section then number[j] is 0.
- If thread
j has begun a new round then its number[j] is the result of a max computation that took the current value of number[i] into account, thus number[j] > number[i].
In the first case, threads i and j are running their for loop concurrently; only one of them will win the (number[j],j)<(number[i],i) comparison and proceed into the critical section, and the other will wait for the winner's number value to become acceptable again. In the second case, thread j is not competing for the critical section. In the third case, thread j has a higher number and will wait in its own for loop while thread i hasn't reset its number[i] value.
The choosing array works around the lack of atomicity in the computation of number[] values. If it was removed, then you could have two threads computing the same value concurrently and each finding that it had the smaller value at the point of testing. This could happen with as little as two threads (I use the notation k.tmpX to designate local storage of the thread k):
initially: number[1] = number[2] = 0
thread 1 thread 2
//choosing[1]=true
1.tmp1 = number[1]
1.tmp2 = number[2]
//choosing[2]=true
2.tmp1 = number[1]
2.tmp2 = number[2]
number[2] = max(2.tmp1,2.tmp2)+1 = 1
//choosing[2]=false
//while (choosing[1]) {}
while (number[1]≠0 &&
(number[1],1)<(number[2],2)) {}
critical section ...
number[1] = max(1.tmp1,1.tmp2)+1 = 1
//choosing[1]=false
//while (choosing[2]) {}
while (number[2]≠0 &&
(number[2],2)<(number[1],1)) {}
critical section ...
critical section ...
The two threads computed the same ticket number. The bakery algorithm uses the thread number to determine the priority in this case. However, thread 2 decided to the critical thread while thread 1 was still preparing, whereas thread 1 saw the new ticket number of thread 2 when deciding whether to enter the critical section but had computed its own ticket number based on thread 2's old ticket number. So thread 1 incorrectly entered the critical section.
The choosing array solves this problem by preventing thread 2 from entering the critical section. Since thread 1 is computing its ticket number at the time thread 2 is preparing to enter the critical section, thread 2 will block on while (choosing[1]) {}, after which it will see the updated value of number[1] and allow thread 1 to enter the critical section first, while thread 2 waits on while (number[1]≠0 && (number[1],1)<(number[2],2)) {}.
