Dekker's Algorithm

This Screenshot is taken from William Stalling's Operating Systems book. My doubt is that Bounded wait is not satisfied by this solution.

For example: P0 and P1 both want to enter critical section and set their flags to true.

flag[0] = true

flag[ 1] = true

Both p0 and p1 enter while loop, p0 wins the race process P1 sets its flag to false

now flag[ 1]= false

Process P0 goes into Critical Section, comes out, sets turn = 1 and flag[0]=false.

Now actual problem starts from here:

Process P1 comes out of infinite while loop and before i could set flag[ 1] to True from False, it gets preempted.

Now Process P0 can go any number of times in Critical section because Flag[ 1] is False.

Conclusion: Process P1 tried to get access to critical section but because of bad solution it did set its flag to False to give path to Po and now stuck for infinite time.

hence B.W is not satisfied!


2 Answers 2


When P1 runs again, it set its flag to True. Your scenario assumes P0 is executed continuously, while P1 never gets a chance to execute its code. This also happens in the simple case where there is only one process running, but obviously this does not contradict bounded waiting.

An implicit assumption when talking about protocols for mutual exclusion is that all of the processes involved will eventually run and execute their current command (otherwise it is meaningless to talk about properties such as bounded waiting or starvation freedom).


Yes, it ensures bounded waiting. In the example you have given even if p0 enters twice in a row, p1 will be able to enter in it the after p0's second entry.

Normally you will see only 1 entry to the other process is allowed for binary critical solution problem. But here 2 entries are allowed.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.