6.1 The first known correct software solution to the critical

-section problem for two processes was developed by Dekker. The two processes, P0 and P1 , share the following variables:

boolean flag[2]; /* initially false */

int turn;

The structure of process Pi (i == 0 or 1) is shown in Figure 6.25; the other process is Pj ( j == 1 or 0). Prove that the algorithm satisfies all three requirements for the critical-section problem.

Answer: This algorithm satisfies the three conditions of mutual exclusion.

(1) Mutual exclusion is ensured through the use of the flag and turn variables. If both processes set their flag to true, only one will succeed. Namely, the process whose turn it is. The waiting process can only enter its critical section when the other process updates the value of turn.

(2) Progress is provided, again through the flag and turnvariables. This algorithm does not provide strict alternation. Rather, if a process wishes to access their critical section, it can set their flag variable to true and enter their critical section. It only sets turn to the value of the other process upon exiting its critical section. If this process wishes to enter its critical section again - before the other process - it repeats the process of entering its critical section and setting turn to the other process upon exiting.

(3) Bounded waiting is preserved through the use of the TTturn variable. Assume two processes wish to enter their respective critical sections. They both set their value of flag to true, however only the thread whose turn it is can proceed, the other thread waits. If bounded waiting were not preserved, it would therefore be possible that the waiting process would have to wait indefinitely while the first process repeatedly entered - and exited - its critical section. However, Dekker’s algorithm has a process set the value of turn to the other process, thereby ensuring that the other process will enter its critical section next.