4
$\begingroup$

I'm studying the bakery algorithm.

do { 
     choosing[i] = true; 
     number[i] = max(number[0], number[1], …, number [n – 1])+1; 
     choosing[i] = false; 
     for (j = 0; j < n; j++) { 
         while (choosing[j]); // 
         while ((number[j]!= 0) && (number[j],j)<(number[i],i))); 
     } 
     critical section 
     number[i] = 0; 
     remainder section 
} while (1); 

Please help me know what exactly this choosing doing here. I checked this for all conditions that I could generate to understand its use. But it doesn't seem to be making any difference. Please help me with a case.

$\endgroup$
10
$\begingroup$

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)) {}.

$\endgroup$
  • $\begingroup$ @gilles I have doubt as follows let say thread one arrive first and got its token (at that time token of thread 2 is zero), now thread 1 got preempted and thread 2 is generating it token now it will generate token (it will consider token value of thread 1) and further thread 1 start it execution again , now it will consider new token value of thread so it is fine (correct me here if i am wrong) $\endgroup$ – sunil Jul 20 '18 at 21:24
  • $\begingroup$ choosing[] will make sure that in while loop comparison of token should happen with updated values of tokens and if any thread is preparing to get the token then another thread need to wait in while loop and once we have updated value we can continue while loop comparison $\endgroup$ – sunil Jul 20 '18 at 21:25
  • $\begingroup$ Can I understand your k.tmpX as value stored in register of thread k? $\endgroup$ – Bit_hcAlgorithm Dec 25 '18 at 3:28
  • $\begingroup$ @ptr_user7813604 yes $\endgroup$ – Gilles 'SO- stop being evil' Dec 25 '18 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.