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?
