1
$\begingroup$

I'm currently studying the Bakery Algorithm. I understand it for what it is but now I want to switch it up a bit.

If we changed the < in the 2nd while() loop to ≤ what exactly would happen?

My take: I don't think it'll cause starvation but I think I'm wrong.

Thanks for taking the time to read. 

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
    number[i] = 0; 
    remainder section
} while(1);
Improve this question
$\endgroup$
2
  • $\begingroup$ You could answer your own question by editing the TLA encoding of the algorithm (and proof). See [github.com/tlaplus/Examples] $\endgroup$
    – Kai
    Mar 19, 2018 at 10:24
  • $\begingroup$ And to save you some time, investigate what happens when j reaches i. After your change, it's impossible for process i to leave that loop. It may pay off to study the original formulation of the bakery algorithm rather than your butchered one. $\endgroup$
    – Kai
    Mar 19, 2018 at 10:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.