Loading learning content...
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.
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.
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.
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::
The challenge was to construct a proof-based solution—one that could be mathematically demonstrated correct, not merely tested until bugs stopped appearing.
| 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 |
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:
1234567891011121314151617181920212223242526272829303132333435363738394041424344
// 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! */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:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
// 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:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
// 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. */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.
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:
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.
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.
| 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 |
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):
flag[i] = truewhile (flag[j])
turn != i):
flag[i] = false (back off)while (turn != i)flag[i] = true (retry)Exit Protocol (for process i):
turn = j (give priority to them next)flag[i] = false (I'm done)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
// DEKKER'S ALGORITHM - HIGH-LEVEL STRUCTURE// First provably correct software solution to mutual exclusion // Shared variablesint flag[2] = {0, 0}; // flag[i] = 1 means process i wants to enterint 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(); }}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.
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.
| 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.
To fully appreciate Dekker's achievement, consider what he was working with and against:
Constraints:
Requirements:
The Trap:
The natural approaches all have fatal flaws:
Dekker found the narrow path between these failures: be aggressive (set flag first) but defer gracefully when conflict arises (back off based on turn).
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.
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:
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.
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.