A Correct Solution: Dekker's Algorithm

This is the first correct solution proposed for the two-process case. Originally developed by Dekker in a different context, it was applied to the critical section problem by Dijkstra.

CONCEPT:

                      Both the turn variable and the status flags are combined in a careful way. The entry protocol begins as in Algorithm 3; we (the requesting process) set our flag and then check our neighbor's flag. If that flag is also set, the turn variable is used. There is no progress problem now because we know the other process is in its CS or entry protocol. If the turn is ours we wait for the flag of the other process to clear. No process will wait indefinitely with its flag set. If the turn belongs to the other process we wait, but we clear our flag before waiting to avoid blocking the other process. When the turn is given to us we reset our flag and proceed.

INITIALIZATION:

 typedef char boolean;
 ...
 shared boolean flags[n -1];
 shared int turn;
 ...
 turn = i ;
 ...
 flags[i ] = FREE;
 ...
 flags[j ] = FREE;
 ...

ENTRY PROTOCOL

 (for Process i ):

 /* claim the resource */
 flags[i ] = BUSY;

 /* wait if the other process is using the resource */
 while (flags[j ] == BUSY) {

  /* if waiting for the resource, also wait our turn */
  if (turn != i ) {
  
   /* but release the resource while waiting */
   flags[i ] = FREE;
   while (turn != i ) {
   }
   flags[i ] = BUSY;
  }

 } 

EXIT PROTOCOL
 (for Process i ):

/* pass the turn on, and release the resource */ turn = j ; < flags[i ] = FREE;

ANALYSIS:

The mutual exclusion requirement is assured. No process will enter its CS without setting its flag. Every process checks the other flag after setting its own. If both are set, the turn variable is used to allow only one process to proceed.

The progress requirement is assured. The turn variable is only considered when both processes are using, or trying to use, the resource.

Deadlock is not possible. No process waits with its flag continuously set, and one process always has the turn. The process with the turn will (eventually) discover the other flag free and will proceed.

Finally, bounded waiting is assured. Suppose Process j exits its CS and re-enters immediately while Process i is waiting. Then the turn has been given to Process i , and the flag of Process i is set. Process j will clear its flag and wait, and Process i will proceed.