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 uses only atomic memory read and write operations.

Development

The algorithm evolved through four increasingly robust attempts.

1. Alternation

while (turn != i) { /* wait */ }
/* --- Critical Section --- */
turn = j;

Strict Alternation

A single turn variable enforces strict alternation. If one process terminates or is slower, the other is blocked indefinitely. Fails bounded waiting.

2. Status Flag

while (flag[j]) { /* wait */ }
flag[i] = true;
/* --- Critical Section --- */
flag[i] = false;

Race Condition

Checking then setting flag[i] is not atomic. Both processes may pass the check simultaneously, violating mutual exclusion.

3. Immediate Interest

flag[i] = true;
while (flag[j]) { /* wait */ }
/* --- Critical Section --- */
flag[i] = false;

Deadlock

If both set their flags simultaneously, both wait forever. Violates progress.

4. Yielding

flag[i] = true;
while (flag[j]) {
    flag[i] = false;
    /* wait */
    flag[i] = true;
}
/* --- Critical Section --- */
flag[i] = false;

Livelock

Both processes may continuously yield to each other in perfect synchrony. Active but not progressing — violates progress.

Final Algorithm

Combines flag[] (intent) with turn (tie-breaker):

flag[i] = true;
while (flag[j]) {
    if (turn == j) {
        flag[i] = false;
        while (turn == j) { /* wait */ }
        flag[i] = true;
    }
}
/* --- Critical Section --- */
turn = j;
flag[i] = false;

Two Mechanisms

flag[] expresses intent to enter; turn resolves conflicts when both processes are interested simultaneously.