Dekker's Algorithm

operating-systems concurrency

Definition

Dekker's Algorithm

Dekker’s algorithm is the first known correct software solution to the mutual exclusion problem for two processes. It ensures that no two processes enter their critical sections simultaneously using only atomic memory read and write operations.

Development

The algorithm was developed through a series of increasingly robust attempts:

1. Alternation (Turn Variable)

Uses a single variable turn.

• Logic: Process $i$ only enters if turn == i.
• Problem: Strictly enforces alternation. If one process terminates or is much slower, the other is blocked indefinitely.

while turn ≠ i do nothing;
// --- Critical Section ---
turn := j;

2. Status Flag

Uses a boolean array flag[0..1].

• Logic: Check if the other is interested before setting own flag.
• Problem: Does not guarantee mutual exclusion (Race Condition on the check).

while flag[j] do nothing;
flag[i] := true;
// --- Critical Section ---
flag[i] := false;

3. Immediate Interest

• Logic: Set own flag to true before checking the other.
• Problem: Deadlock occurs if both set their flags at the same time.

flag[i] := true;
while flag[j] do nothing;
// --- Critical Section ---
flag[i] := false;

4. Yielding (Livelock)

• Logic: If the other is interested, temporarily set own flag to false and try again.
• Problem: Can lead to a livelock (or “After-you” situation). This occurs if both processes set their flags simultaneously and then continuously yield to each other in perfect synchrony. Both processes remain active (consuming CPU cycles), but neither ever enters the critical section, failing the Progress requirement.

flag[i] := true;
while flag[j] do
begin
    flag[i] := false;
    // Wait for a short time
    flag[i] := true;
end;
// --- Critical Section ---
flag[i] := false;

Final Algorithm

The final version combines the flag array (intent) and the turn variable (tie-breaker) to ensure both mutual exclusion and progress.

flag[i] := true;
while flag[j] do
begin
    if turn = j then
    begin
        flag[i] := false;
        while turn = j do nothing; // Wait for turn
        flag[i] := true;
    end;
end;
 
// --- Critical Section ---
turn := j;
flag[i] := false;

Visual Representation