Historical First Solution - Dekker's Algorithm | OneNoughtOne

0/236

Operating SystemsDekker's Algorithm

Dekker's Algorithm

LevelIntermediate

Duration55 mins

TopicDekker's Algorithm

1 / 5

Historical First Solution

The Birth of Concurrent Programming Theory

In 1965, Dutch mathematician Theodorus Jozef Dekker achieved something remarkable: he constructed the first known correct software solution to the mutual exclusion problem for two processes. This achievement, now known as Dekker's Algorithm, marked a watershed moment in computer science—the point where concurrent programming transitioned from intuition and hope to rigorous mathematical foundation.

Before Dekker's work, programmers attempting to coordinate multiple processes had no proven methodology. They relied on hardware-specific tricks, disabled interrupts, or accepted occasional race conditions as inevitable. Dekker demonstrated that correct synchronization could be achieved through pure software—using only ordinary read and write operations on shared memory—without any special hardware support.

This page explores the historical context that gave rise to Dekker's Algorithm, why the problem was so fiendishly difficult, and how Dekker's elegant solution laid the groundwork for all subsequent developments in synchronization theory.

What You Will Learn

By the end of this page, you will understand the historical context of Dekker's Algorithm, why it represented a breakthrough in computer science, the sequence of failed attempts that preceded it, and how it established the theoretical foundation for concurrent programming. You will appreciate why this algorithm remains studied today despite being superseded by simpler solutions.

The Synchronization Crisis of the 1960s

To appreciate Dekker's contribution, we must understand the landscape of computing in the early 1960s. This was an era when multiprogramming was emerging as a practical necessity, yet the theoretical foundations for safe concurrent execution did not exist.

The Hardware Context:

Early computers were single-program systems—load a program, execute it to completion, load the next. But as hardware became more expensive per cycle, idle time during I/O operations became unconscionable waste. The solution was multiprogramming: keep multiple programs in memory and switch between them, allowing one to execute while another waits for I/O.

This immediately created coordination problems. Multiple programs sharing memory could interfere with each other. Multiple programs accessing the same I/O device could corrupt data. The operating system itself needed to access shared data structures safely while user programs ran.

The Intellectual Crisis:

More troubling than the practical problems was the intellectual crisis. Programmers discovered that concurrent programs exhibited non-deterministic behavior—the same program with the same inputs could produce different outputs on different runs. Bugs appeared and disappeared seemingly at random. Debugging became nearly impossible because the act of debugging (which changes timing) could make bugs vanish.

The Heisenbug Phenomenon

Concurrent programming bugs that disappear when you try to observe them came to be known as 'Heisenbugs' (after Heisenberg's uncertainty principle). Before formal synchronization theory, programmers had no way to reason about these bugs systematically—they could only hope their testing was sufficient, which it never was.

The Mutual Exclusion Problem:

At the heart of these difficulties lay what Dijkstra would later formalize as the mutual exclusion problem: how can multiple processes coordinate to ensure that only one at a time executes a critical section of code that accesses shared resources?

This sounds simple. In practice, it proved extraordinarily subtle. Consider::

Processes can be interrupted at any point
Memory operations may not complete in the order written
No process can know what another process is "about to do"
Testing cannot prove absence of bugs, only their presence

The challenge was to construct a proof-based solution—one that could be mathematically demonstrated correct, not merely tested until bugs stopped appearing.

The State of Synchronization Before Dekker
Approach	Mechanism	Problems
Disable Interrupts	Turn off all interrupts during critical sections	Only works on single-processor; user code shouldn't have this privilege; I/O starvation
Lock Variables	Set a flag before entering critical section	Race condition: two processes can see flag unset simultaneously
Strict Alternation	Alternate turns between processes	Progress violation: if one process is slow, other must wait even for empty critical section
Hardware Locks	Use dedicated locking hardware	Not universally available; expensive; still required correct software algorithms
Hope and Testing	Test extensively and hope bugs are found	Race conditions may occur once per million executions—catastrophic in production

The Graveyard of Failed Solutions

Before Dekker's success, numerous attempts at solving mutual exclusion failed in subtle ways. Understanding these failures illuminates why Dekker's solution was such an achievement and provides essential intuition for synchronization algorithm design.

Attempt 1: The Single Lock Variable

The most obvious approach uses a single shared variable to indicate whether the critical section is occupied:

failed_attempt_1.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// INCORRECT: Single lock variable approach
// This approach seems intuitive but is fundamentally flawed
 
int lock = 0;  // 0 = unlocked, 1 = locked
 
void process_i() {
    while (1) {
        // Entry section - wait for lock to be free
        while (lock == 1) {
            // Busy wait - spin until lock is released
        }
        
        // CRITICAL RACE CONDITION HERE!
        // Between checking (lock == 0) and setting (lock = 1),
        // another process can also see lock == 0 and enter!
        
        lock = 1;  // Take the lock
        
        // === CRITICAL SECTION ===
        // Access shared resources here
        // Both processes may be here simultaneously!
        // === END CRITICAL SECTION ===
        
        lock = 0;  // Release the lock
        
        // Remainder section
    }
}
 
/*
 * FAILURE SCENARIO:
 * 
 * Time    Process A              Process B
 * ----    ---------              ---------
 * t1      while(lock==1){}       
 * t2      // lock is 0, exit      
 * t3      // about to set lock    while(lock==1){}
 * t4                              // lock is 0, exit
 * t5      lock = 1               
 * t6                              lock = 1
 * t7      CRITICAL SECTION       CRITICAL SECTION
 *                                 
 * BOTH IN CRITICAL SECTION - MUTUAL EXCLUSION VIOLATED!
 */

The Check-Then-Act Anti-Pattern

This failure represents the 'check-then-act' anti-pattern: the decision to enter (check) and the claim of occupancy (act) are separate operations. During the gap between them, any number of other processes can also check and decide to enter. No matter how small this gap, in a concurrent system it WILL be exploited eventually.

Attempt 2: Claiming Before Checking

To fix the race condition, perhaps we should claim the lock before checking if it's available:

failed_attempt_2.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// INCORRECT: Set flag before checking
// This fixes mutual exclusion but breaks progress!
 
int flag[2] = {0, 0};  // flag[i] = 1 means process i wants to enter
 
void process_0() {
    while (1) {
        // Entry section - claim intention first
        flag[0] = 1;  // I want to enter!
        
        // Wait for other process to leave
        while (flag[1] == 1) {
            // Busy wait
        }
        
        // === CRITICAL SECTION ===
        // Access shared resources here
        // === END CRITICAL SECTION ===
        
        flag[0] = 0;  // Done, release claim
        
        // Remainder section
    }
}
 
void process_1() {
    while (1) {
        flag[1] = 1;  // I want to enter!
        
        while (flag[0] == 1) {
            // Busy wait
        }
        
        // === CRITICAL SECTION ===
        // === END CRITICAL SECTION ===
        
        flag[1] = 0;
        
        // Remainder section
    }
}
 
/*
 * DEADLOCK SCENARIO:
 * 
 * Time    Process 0              Process 1
 * ----    ---------              ---------
 * t1      flag[0] = 1            
 * t2                             flag[1] = 1
 * t3      while(flag[1]==1){}   while(flag[0]==1){}
 * t4      // flag[1] is 1!       // flag[0] is 1!
 * t5      // wait forever...     // wait forever...
 *                                 
 * DEADLOCK - PROGRESS VIOLATED! Neither can proceed.
 */

Attempt 3: Strict Alternation

Another approach uses a turn variable to strictly alternate between processes:

failed_attempt_3.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// INCORRECT: Strict alternation
// This ensures mutual exclusion but violates progress!
 
int turn = 0;  // Whose turn to enter (0 or 1)
 
void process_0() {
    while (1) {
        // Entry section - wait for my turn
        while (turn != 0) {
            // Busy wait for my turn
        }
        
        // === CRITICAL SECTION ===
        // === END CRITICAL SECTION ===
        
        turn = 1;  // Give turn to process 1
        
        // Remainder section (may be very long!)
    }
}
 
void process_1() {
    while (1) {
        while (turn != 1) {
            // Busy wait
        }
        
        // === CRITICAL SECTION ===
        // === END CRITICAL SECTION ===
        
        turn = 0;
        
        // Remainder section
    }
}
 
/*
 * PROGRESS VIOLATION SCENARIO:
 * 
 * Process 0 executes 100 times per second (fast, brief remainder)
 * Process 1 executes 1 time per second (slow, long remainder)
 * 
 * Even when Process 1 is in its remainder (doesn't need critical section),
 * Process 0 must wait for Process 1 to take its turn before going again.
 * 
 * Process 0 is blocked not by contention but by the strict alternation
 * protocol. This violates the PROGRESS requirement: a process not in
 * its critical section should not prevent other processes from entering.
 */

Summary of Failed Approaches

•Single Lock Variable — Races between checking and setting allow multiple entries
•Set Flag Before Check — Both processes can set their flags and wait forever (deadlock)
•Strict Alternation — Couples processes unnecessarily; one process's inactivity blocks the other
•All combinations of the above — Various permutations all failed for similar reasons

These failures demonstrated that solving mutual exclusion was genuinely hard. It wasn't a matter of being clever enough—there were fundamental mathematical constraints that any correct solution had to satisfy. This is why Dekker's eventual success was celebrated: he found a way through a minefield that had thwarted everyone else.

Dekker's Breakthrough

Theodorus Jozef Dekker was a Dutch mathematician working on numerical analysis and algorithms at the Mathematical Centre (now CWI) in Amsterdam. His background in rigorous mathematical thinking proved essential for solving the mutual exclusion problem.

The Key Insight:

Dekker's genius was recognizing that he could combine the flag approach (which prevented race conditions) with the turn approach (which prevented deadlock) in a way that avoided the failures of each.

His solution uses:

Flag variables to indicate intention to enter the critical section
A turn variable to break ties when both processes want to enter

The critical insight is how these interact: when both processes want to enter (both flags set), the turn variable decides who proceeds. The losing process backs off by clearing its flag, allowing the winner to enter. After backing off and waiting, it sets its flag again and retries.

The Deference Principle

Dekker's key innovation is the 'deference protocol': when conflict is detected, the non-favored process temporarily surrenders its claim (clears its flag), giving the other process a clear path to enter. After the favored process finishes, the non-favored process can retry. This backing-off behavior prevents deadlock while the flag mechanism prevents race conditions.

Historical Context:

Dekker's algorithm was first published in 1965, although it's often attributed to Dijkstra's 1965 paper "Solution of a Problem in Concurrent Programming Control" where Dijkstra credited Dekker and presented the algorithm formally.

Edsger Dijkstra, who would become one of computing's giants (Dijkstra's algorithm, structured programming, semaphores), was so impressed with Dekker's solution that he published it, analyzed it, and extended it to n processes. This collaboration between mathematicians represents one of the earliest examples of rigorous computer science.

Why It Worked:

Dekker's solution satisfies all three requirements for a correct mutual exclusion solution:

Mutual Exclusion: At most one process can be in the critical section at any time. The flag check before entry prevents simultaneous entry—if both flags are set, only the process whose turn it is proceeds; the other backs off.
Progress: If no process is in the critical section and some processes wish to enter, one will eventually succeed. The turn variable always favors exactly one process, so at least one will not back off.
Bounded Waiting: A process waiting to enter will eventually succeed. After a process exits and transfers the turn, the waiting process becomes favored and will enter on its next attempt.

Dekker's Solution Components
Component	Purpose	Mechanism
flag[0], flag[1]	Express intent to enter critical section	Set before attempting entry, cleared after exit
turn	Break symmetry when both want to enter	Indicates which process has priority in case of conflict
Back-off protocol	Prevent deadlock when both flags are set	Non-favored process clears flag, waits, then retries
Turn transfer	Ensure fairness between processes	After exiting, give turn to the other process

Structure of Dekker's Algorithm

Before diving into the full implementation (covered in subsequent pages), let's understand the logical structure of Dekker's Algorithm at a high level:

Entry Protocol (for process i):

Set my flag to indicate I want to enter: flag[i] = true
Check if the other process also wants to enter: while (flag[j])
- If the other process also wants to enter, yield based on turn:
- If it's not my turn (turn != i):
  - Clear my flag: flag[i] = false (back off)
  - Wait until it becomes my turn: while (turn != i)
  - Set my flag again: flag[i] = true (retry)
Once the other process doesn't want to enter (or backed off), enter critical section

Exit Protocol (for process i):

Set turn to the other process: turn = j (give priority to them next)
Clear my flag: flag[i] = false (I'm done)

dekker_structure.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// DEKKER'S ALGORITHM - HIGH-LEVEL STRUCTURE
// First provably correct software solution to mutual exclusion
 
// Shared variables
int flag[2] = {0, 0};  // flag[i] = 1 means process i wants to enter
int turn = 0;          // Whose turn in case of conflict
 
void process_i(int i) {
    int j = 1 - i;  // Index of the other process
    
    while (1) {
        // ========== ENTRY SECTION ==========
        
        // Step 1: Indicate intent to enter
        flag[i] = 1;
        
        // Step 2: Check for conflict with other process
        while (flag[j] == 1) {
            // Both want to enter - must break the tie
            
            if (turn != i) {
                // Not my turn - I must back off
                flag[i] = 0;  // Withdraw my request temporarily
                
                // Wait for my turn
                while (turn != i) {
                    // Spin - other process has priority
                }
                
                // My turn now - reassert my intention
                flag[i] = 1;
            }
            // If it IS my turn, stay in inner loop 
            // until other process backs off
        }
        
        // ========== CRITICAL SECTION ==========
        // At this point:
        // - flag[i] == 1 (I want to be here)
        // - flag[j] == 0 (other is not contending)
        // 
        // Mutual exclusion guaranteed!
        
        critical_section();
        
        // ========== EXIT SECTION ==========
        
        // Step 3: Give turn to other process
        turn = j;
        
        // Step 4: Release my claim
        flag[i] = 0;
        
        // ========== REMAINDER SECTION ==========
        remainder_section();
    }
}

Key Structural Properties

•Flag First — Always set your flag before checking the other's flag (claim before contest)
•Deference — When both flags are set, the non-favored process explicitly yields
•Retry After Yield — After backing off and waiting, the process re-raises its flag
•Turn Transfer — After exiting, always give turn to the other process (fairness)
•Flag Clear Last — Clear flag after transferring turn (proper cleanup)

Impact on Computer Science

Dekker's Algorithm wasn't just a solution to a practical problem—it was a paradigm shift in how computer scientists thought about concurrent programs. Its impact reverberated through the next six decades of computing.

Immediate Impact:

Proof-Based Reasoning: Dekker demonstrated that synchronization algorithms could be proven correct, not just tested. This established the standard that concurrent algorithms must be accompanied by correctness arguments.
The Possibility Result: Before Dekker, it wasn't clear software-only mutual exclusion was even possible. The algorithm proved that correct synchronization requires no special hardware support—ordinary reads and writes suffice (under appropriate memory models).
Foundation for Formal Methods: Dekker's algorithm became a test case for formal verification methods. Proving its correctness helped develop the techniques that are now standard in concurrent system verification.

The Textbook Legacy

Dekker's Algorithm appears in virtually every operating systems textbook written since the 1970s. Despite being superseded by simpler solutions and hardware primitives, it remains essential teaching material because it demonstrates the subtlety of concurrent programming and the need for rigorous reasoning.

Long-Term Influence:

Dekker's work catalyzed an explosion of research in synchronization theory:

Dijkstra's Semaphores (1965): Shortly after publishing Dekker's algorithm, Dijkstra introduced semaphores, providing a higher-level synchronization primitive.
Peterson's Algorithm (1981): Gary Peterson found a simpler solution for two processes, now the standard teaching example.
Lamport's Bakery Algorithm (1974): Generalized software mutual exclusion to n processes with elegant numbered-ticket semantics.
Fischer's Algorithm (1985): Used timing assumptions to achieve mutual exclusion with single-writer registers.
Modern Hardware Primitives: Understanding software limitations drove development of hardware support like test-and-set, compare-and-swap, and load-linked/store-conditional.

Evolution After Dekker
Year	Contribution	Key Innovation
1965	Dekker's Algorithm	First correct software solution for 2 processes
1965	Dijkstra's Semaphores	Higher-level abstraction; counting synchronization
1974	Lamport's Bakery Algorithm	N-process solution using numbered tickets
1981	Peterson's Algorithm	Simpler 2-process solution; easier to verify
1991	MCS Lock	Scalable lock with O(1) cache line transfers
2000s	Transactional Memory	Hardware-assisted atomic regions

Why Study a Superseded Algorithm?

A reasonable question arises: if Peterson's algorithm is simpler and hardware primitives are faster, why study Dekker's algorithm at all?

The answer lies in educational value:

Historical Understanding: Dekker's algorithm shows how solutions evolve. Understanding the original helps appreciate improvements.
Debugging Skills: The structure of Dekker's algorithm—with its explicit back-off and retry—exposes failure modes clearly. Students who understand Dekker can diagnose synchronization bugs more effectively.
Algorithm Design Principles: The combination of flags (for safety) and turn (for liveness) represents a design pattern applicable beyond mutual exclusion.
Formal Reasoning Practice: Proving Dekker's algorithm correct exercises skills in concurrent program reasoning that apply to all synchronization work.
Appreciation for Simplicity: After struggling with Dekker's complexity, students appreciate why Peterson's simplification was significant.

The Intellectual Achievement

To fully appreciate Dekker's achievement, consider what he was working with and against:

Constraints:

No test-and-set or compare-and-swap (these came later, partly because of this work)
No disabling interrupts (needed a userspace solution)
Only ordinary memory reads and writes
No assumptions about relative process speeds
Must work even if one process is infinitely slow

Requirements:

Mutual exclusion: never two processes in critical section
Progress: if critical section is free and processes want in, one must eventually enter
Bounded waiting: a waiting process eventually enters (no starvation)

The Trap:

The natural approaches all have fatal flaws:

Be aggressive → break mutual exclusion
Be conservative → cause deadlock
Alternate strictly → violate progress

Dekker found the narrow path between these failures: be aggressive (set flag first) but defer gracefully when conflict arises (back off based on turn).

The Dancing Partners Metaphor

Dekker's algorithm is like two people trying to pass through a narrow doorway. Each raises their hand to indicate they want to go. If both raise hands, they look at a 'turn' indicator. The one whose turn it is proceeds; the other lowers their hand, waits for the first to pass, then proceeds. After passing, each flips the turn indicator to be polite to the other.

Why Dekker's Solution Works

•Mutual Exclusion Guaranteed — Both flags can be set, but only the favored process keeps its flag set; the other backs off
•Deadlock Impossible — The turn variable always breaks ties; one process is always favored
•Progress Ensured — A free critical section can always be entered; the turn only matters during contention
•Bounded Waiting Satisfied — After exiting, turn transfers; the waiting process becomes favored on next contention
•No Special Hardware — Uses only ordinary reads and writes (assuming sequential consistency)

Summary: The First Solution

We've explored the historical significance of Dekker's Algorithm—the first proven correct software solution to the mutual exclusion problem. Let's consolidate the key takeaways:

Key Takeaways

•Dekker's Algorithm (1965) was the first known correct software solution for mutual exclusion between two processes
•Previous attempts failed due to races (check-then-act), deadlocks (both claim and wait), or progress violations (strict alternation)
•The solution combines flag variables (for safety) with a turn variable (for liveness/tie-breaking)
•The deference protocol prevents deadlock: when both want entry, the non-favored process backs off temporarily
•Historical impact includes establishing proof-based concurrent programming and inspiring semaphores, Peterson's algorithm, and formal verification methods
•Educational value remains high despite simpler alternatives, as it teaches debugging skills and algorithm design principles

What's Next:

Now that we understand the historical context and significance of Dekker's Algorithm, we'll examine its core mechanism in detail. The next page focuses on the turn-based approach—how the turn variable interacts with the entry protocol to break symmetry and prevent deadlock while maintaining fairness.

Page Complete

You now understand why Dekker's Algorithm was a watershed moment in computer science. It proved that correct concurrent programming was possible through pure software, setting the stage for all subsequent synchronization theory. Next, we'll dive into the mechanics of the turn-based protocol that makes it work.