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?


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.