1Consider Dekkers algorithm written for an arbitrary number

1.Consider Dekker\'s algorithm, written for an arbitrary number of processes by changing the statement executed when leaving the critical section from

turn = 1 - i //i.e. P0 sets turn to 1 and P1 sets turn to 0

to

turn = (turn + 1) % n //n = number of processes

Evaluate the algorithm when the number of concurrently executing processes is greater than two, if the changes create any problem, give an example of executing sequence.

In the above question , how to i get an execution sequence that shows starvation ?

Solution

It doesn\'t work. mutual exclusion is enforced; but starvation and deadlock is possible if turn is set to a non-contending process. Let suppose we have three Processes P1,P2 and P3 . Lets say p1 is currently executing by acquiring the lock on Critical Section objects and meanwhile P3 has entered to request the Critical Section resources now P3 has to wait as P1 is currently using the resources. Lets say in the interim P2 also raises a request to access critical section resources or locked resources, but since P1 has already acquired them it also has to wait. P1 while exiting now as per the new exit flag setting conditon, sets the turn using the formula : turn = (turn + 1) % n and therefore turn now becomes 2 ( as per turn = (1+1 )%3 ) . Now when P3 tries to enter the critical section it has to wait as, as per the turn flag P2 can enter . Lets say if P2 has some dependency on P3 then this can end up in a deadlocked state as P2 is eliglible to enter and it depends on P3, which is waiting for it\'s turn and which can only be signaled by the depending process P2.

Case 2 when P2 was never willing to enter the critical section in that case P3 would have starved as only P2 can set turn flag for P3.