Pseudocode
| //flag is boolean array; and turn is an integer flag = false flag = false turn = 0 // or 1 | |
| P0: flag = true; while (flag == true) { if (turn ≠ 0) { flag = false; while (turn ≠ 0) { // busy wait } flag = true; } } // critical section ... turn = 1; flag = false; // remainder section | P1: flag = true; while (flag == true) { if (turn ≠ 1) { flag = false; while (turn ≠ 1) { // busy wait } flag = true; } } // critical section ... turn = 0; flag = false; // remainder section |
Processes indicate an intention to enter the critical section which is tested by the outer while loop. If the other process has not flagged intent, the critical section can be entered safely irrespective of the current turn. Mutual exclusion will still be guaranteed as neither process can become critical before setting their flag (implying at least one process will enter the while loop). This also guarantees progress as waiting will not occur on a process which has withdrawn intent to become critical. Alternatively, if the other process's variable was set the while loop is entered and the turn variable will establish who is permitted to become critical. Processes without priority will withdraw their intention to enter the critical section until they are given priority again (the inner while loop). Processes with priority will break from the while loop and enter their critical section.
Dekker's algorithm guarantees mutual exclusion, freedom from deadlock, and freedom from starvation. Let us see why the last property holds. Suppose p0 is stuck inside the "while flag" loop forever. There is freedom from deadlock, so eventually p1 will proceed to its critical section and set turn = 0 (and the value of turn will remain unchanged as long as p0 doesn't progress). Eventually p0 will break out of the inner "while turn ≠ 0" loop (if it was ever stuck on it). After that it will set flag := true and settle down to waiting for flag to become false (since turn = 0, it will never do the actions in the while loop). The next time p1 tries to enter its critical section, it will be forced to execute the actions in its "while flag" loop. In particular, it will eventually set flag = false and get stuck in the "while turn ≠ 1" loop (since turn remains 0). The next time control passes to p0, it will exit the "while flag" loop and enter its critical section.
If the algorithm were modified by performing the actions in the "while flag" loop without checking if turn = 0, then there is a possibility of starvation. Thus all the steps in the algorithm are necessary.
Read more about this topic: Dekker's Algorithm