Dekker's Algorithm for Process Synchronization

Dekker's algorithm holds a notable place in computer science history as the first ever software solution to the critical section problem for two processes. Proposed by Th. J. Dekker in 1965, it did not arrive in its final form right away.

It went through five versions, each one fixing something the previous version got wrong. Understanding all five versions gives you a clear picture of why the final solution is designed the way it is.

Version 1: Taking Strict Turns

The first attempt used a single variable called thread_no to decide whose turn it was. If thread_no was 1, Thread 1 could enter. If it was 2, Thread 2 could enter. After finishing, each thread handed the turn to the other.

cpp

std::atomic<int> thread_no{1};

void thread1() {
    for (int i = 0; i < ITERATIONS; ++i) {
        while (thread_no.load() != 1) std::this_thread::yield();
        // --- Critical Section ---
        std::cout << "Thread 1 in critical section" << std::endl;
        thread_no.store(2);    // Hand turn to Thread 2
    }
}

void thread2() {
    for (int i = 0; i < ITERATIONS; ++i) {
        while (thread_no.load() != 2) std::this_thread::yield();
        // --- Critical Section ---
        std::cout << "Thread 2 in critical section" << std::endl;
        thread_no.store(1);    // Hand turn to Thread 1
    }
}

Flaw: Lockstep Synchronization

The two threads are chained in a strict alternating pattern. If Thread 1 finishes all its work and stops running, Thread 2 gets stuck waiting forever for a turn that will never come because Thread 1 is no longer around to hand it back. This violates the Progress requirement.

Version 2: Using Flags Instead

To fix the lockstep issue, Version 2 switched to two separate boolean flags, one per thread. Each thread checks the other's flag before entering and sets its own flag once it is clear to go in.

cpp

std::atomic<bool> th1{false};
std::atomic<bool> th2{false};

void thread1() {
    for (int i = 0; i < ITERATIONS; ++i) {
        while (th2.load()) std::this_thread::yield();  // Wait if other is in
        th1.store(true);                                // THEN set my flag
        // --- Critical Section ---
        th1.store(false);                               // Done
    }
}

Flaw: Mutual Exclusion Violated

If both threads check each other's flag at the same moment and both see false, they both set their own flags to true and both enter the critical section simultaneously. The problem is that the check and the flag-set are two separate operations with a gap between them.

Version 3: Setting the Flag Earlier

Version 3 tried to fix the mutual exclusion issue by having each thread set its own flag BEFORE checking the other thread's flag, rather than after.

cpp

std::atomic<bool> th1{false};
std::atomic<bool> th2{false};

void thread1() {
    for (int i = 0; i < ITERATIONS; ++i) {
        th1.store(true);                                // Set flag FIRST
        while (th2.load()) std::this_thread::yield();   // THEN check other
        // --- Critical Section ---
        th1.store(false);
    }
}

Flaw: Deadlock

If both threads set their flags to true at the same time, each one sees the other's flag as true and both end up waiting forever. Each is blocking the other with no way out. This is a textbook deadlock.

Version 4: Random Backoff

Version 4 addressed deadlock by having each thread temporarily lower its flag for a short random period when it detects a conflict, then try again.

cpp

std::atomic<bool> th1{false};
std::atomic<bool> th2{false};

void thread1() {
    for (int i = 0; i < ITERATIONS; ++i) {
        th1.store(true);
        while (th2.load()) {
            th1.store(false);       // Back off
            pause_random();         // Wait a random time
            th1.store(true);        // Try again
        }
        // --- Critical Section ---
        th1.store(false);
    }
}

Flaw: No Bounded Waiting Guarantee

Deadlock is mostly avoided, but the randomness introduces unpredictability. There is no guarantee about how long a thread might wait before getting in. In the worst case, both threads could keep backing off and retrying in sync indefinitely (called a livelock). This violates Bounded Waiting.

Version 5: The Complete Solution

The fifth and final version introduced a favoured variable to break ties deterministically. When both threads want in at the same time, the one that is not favoured steps back and waits until the favoured thread finishes. After finishing, a thread passes the favour to the other one.

cpp

#include <iostream>
#include <thread>
#include <atomic>
#include <chrono>

std::atomic<bool> want1{false};
std::atomic<bool> want2{false};
std::atomic<int> favoured{1};
const int ITERATIONS = 10;

void thread1() {
    for (int i = 0; i < ITERATIONS; ++i) {
        want1.store(true);                    // I want in
        while (want2.load()) {                // Does the other want in too?
            if (favoured.load() == 2) {       // Am I NOT favoured?
                want1.store(false);           // Back off
                while (favoured.load() == 2) {
                    std::this_thread::yield(); // Wait for my turn
                }
                want1.store(true);            // Try again
            }
        }
        // --- Critical Section ---
        std::cout << "Thread 1 in critical section" << std::endl;
        // --- Exit Section ---
        favoured.store(2);                    // Hand favour to Thread 2
        want1.store(false);                   // I'm done
    }
}

void thread2() {
    for (int i = 0; i < ITERATIONS; ++i) {
        want2.store(true);
        while (want1.load()) {
            if (favoured.load() == 1) {
                want2.store(false);
                while (favoured.load() == 1) {
                    std::this_thread::yield();
                }
                want2.store(true);
            }
        }
        std::cout << "Thread 2 in critical section" << std::endl;
        favoured.store(1);
        want2.store(false);
    }
}

int main() {
    std::thread t1(thread1);
    std::thread t2(thread2);
    t1.join();
    t2.join();
    std::cout << "Both threads completed." << std::endl;
    return 0;
}

Output:

text

Thread 1 in critical section
Thread 2 in critical section
Thread 1 in critical section
Thread 2 in critical section
...
Both threads completed.

Why Version 5 Works

Requirement	How Version 5 Satisfies It
Mutual Exclusion	Only one thread proceeds when both want in. The unfavoured thread backs off entirely until the favoured one finishes.
Progress	The favoured variable always resolves the conflict deterministically. No stalling or randomness involved.
Bounded Waiting	Once a thread finishes and hands favour to the other, that other thread cannot be skipped more than once.

The Evolution at a Glance

Version	Approach	What It Fixed	What It Broke
V1	Single turn variable	Basic mutual exclusion	Lockstep (no progress if one stops)
V2	Flags, check then set	Removed lockstep	Mutual exclusion violated (race in gap)
V3	Flags, set then check	Restored mutual exclusion	Deadlock (both flags up, both wait)
V4	Random backoff	Broke deadlock	No bounded waiting (livelock possible)
V5	Favoured variable	Deterministic tie-breaking	Nothing. All three requirements satisfied.

The journey through all five versions shows something useful: getting synchronization right is harder than it looks. Each version fixed one thing and broke something else, until the fifth version finally got all three conditions right at the same time. For two processes, this remains one of the cleanest pure software solutions ever designed.

Dekker's Algorithm for Process Synchronization
Version 1: Taking Strict Turns
Version 2: Using Flags Instead
Version 3: Setting the Flag Earlier
Version 4: Random Backoff
Version 5: The Complete Solution
Why Version 5 Works
The Evolution at a Glance