3
$\begingroup$

i'm reading an old exam and one question was: Which property of the Bakery algorithm is violated with the following change?

- mutual exclusion
- deadlock freedom
- starvation freedom

Algorithm: (i is the number of a thread)

choosing: array[0..n-1] of boolean (init false);
number: array[0..n-1]

loop forever:
1:  choosing[i]<-true;
2:  number[i]<-1+max(number);
3:  choosing[i] <-false;
4:  for all j in {0,..,n-1} with j!=i do
5:     await(choosing[j]=false)
6:     await((number[j]=0) or (number[j],j)>>(number[i],i))
7:  critical section
8:  numbe[i]<-0;

Change: Replace Line 6 with await((number[j]=0) or (number[j]>number[i]))

I think the deadlock freedom is violated because it is possible that two threads get the same value for number[i]. If two threads have the same number no one will pass the new 6. line. Is that correct? And if deadlock freedom is violated, is starvation freedom automatically violated too?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.