Loading learning content...
Concurrent programming presents a fundamental challenge that doesn't exist in sequential code: symmetry. When two identical processes execute identical code, there's nothing to distinguish them. If both want to enter a critical section simultaneously and both execute the same decision logic, they'll make the same decision—and that decision will be wrong.
This symmetry is the root cause of deadlock in naive mutual exclusion attempts. When both processes set their flags and check the other's flag, both see conflict, and both wait. Neither can proceed because nothing distinguishes "you go" from "I go."
Dekker's insight was to introduce an asymmetry mechanism: the turn variable. This variable breaks the tie when both processes simultaneously want entry, designating exactly one as the "favored" process that may proceed while the other defers.
This page examines the turn-based approach in comprehensive detail—its role in the algorithm, its interaction with flags, the invariants it maintains, and the subtleties of its operation that make Dekker's algorithm correct.
By the end of this page, you will understand the precise role of the turn variable in Dekker's Algorithm, how it breaks symmetry without causing other problems, the invariants it maintains throughout execution, and why the turn transfer in the exit protocol is essential for bounded waiting.
The turn variable in Dekker's Algorithm serves a single, critical purpose: it determines which process has priority when both want to enter the critical section simultaneously.
Unlike strict alternation (which we saw fails the progress requirement), the turn variable in Dekker's Algorithm is consulted only when there is actual contention. If only one process wants to enter, it enters directly—turn is irrelevant. The turn variable only matters during the specific scenario where both flags are set.
Turn Semantics:
turn = 0 means: "If both Process 0 and Process 1 want to enter, Process 0 has priority"turn = 1 means: "If both want to enter, Process 1 has priority"The process that has the turn keeps trying (spinning) while waiting for the other to back off. The process that doesn't have the turn must actively back off—clear its flag, wait for its turn, then retry.
The Key Distinction from Strict Alternation:
Think of the turn variable as a tie-breaker in an election, not as a permission slip. You don't need the turn to vote (enter)—you only need it if the vote is tied (both want to enter). This subtle distinction is what separates Dekker's working algorithm from the failed strict alternation approach.
The entry protocol is where the turn variable does its work. Let's trace through exactly how turn interacts with the flag variables during the critical entry phase.
The Entry Protocol Logic:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
// Dekker's Entry Protocol for Process i// j = 1 - i is the other process void enter_critical_section(int i, int j) { // Step 1: Declare intention to enter flag[i] = TRUE; // Step 2: Check if other process also wants to enter while (flag[j] == TRUE) { // CONTENTION DETECTED! // Both processes want to enter - consult turn if (turn != i) { // It's NOT my turn - I must defer // Step 2a: Temporarily withdraw my request flag[i] = FALSE; // WHY: Allows the other process to enter // If I keep my flag set, we deadlock // Step 2b: Wait until it becomes my turn while (turn != i) { // Busy wait - the other process will // eventually exit and set turn = i } // Step 2c: Now it's my turn - reassert intention flag[i] = TRUE; // Back to top of outer while loop to re-check flag[j] } // Else: It IS my turn, stay in while loop // waiting for other process to back off // (they must back off because turn != j) } // Step 3: Other process's flag is clear - safe to enter!} /* * TRACE: Both processes try to enter simultaneously * Initial state: flag[0] = flag[1] = FALSE, turn = 0 * * Time Process 0 Process 1 * ---- --------- --------- * t1 flag[0] = TRUE * t2 flag[1] = TRUE * t3 while(flag[1]) while(flag[0]) * t4 flag[1] is TRUE! flag[0] is TRUE! * t5 turn == 0 (my turn) turn == 0 (not my turn!) * t6 // stay in loop flag[1] = FALSE (back off) * t7 while(turn != 1) (wait) * t8 flag[1] is FALSE! // still waiting * t9 // exit while loop // still waiting * t10 === ENTER CRITICAL === // still waiting */Detailed Analysis of Each Step:
Step 1: flag[i] = TRUE
This is the "intention declaration." Process i asserts that it wants to enter the critical section. This must happen before checking the other's flag to prevent the race condition in naive locking.
Step 2: while (flag[j] == TRUE)
This is the contention detection loop. If the other process isn't interested (flag[j] = FALSE), we exit immediately and enter the critical section. The turn variable is never consulted.
If flag[j] is TRUE, we have contention and must resolve it.
Step 2a: flag[i] = FALSE (Back off)
This is the crucial "deference" step. If it's not my turn, I temporarily withdraw my intention. This creates a window where the other process (who has the turn) can see my flag as FALSE and proceed to enter.
Without this step, both processes would spin forever with both flags TRUE—deadlock.
Step 2b: while (turn != i) (Wait for turn)
After backing off, wait for the turn to be transferred. The other process, after exiting the critical section, will set turn = i. This is how fairness is achieved.
Step 2c: flag[i] = TRUE (Retry)
Once it's my turn, reassert my intention. Now I have priority if contention recurs.
The order of operations in the entry protocol is not arbitrary—it's the result of careful design to prevent both safety violations and liveness problems. Changing the order (e.g., checking turn before flag, or not backing off when non-favored) breaks the algorithm. This is why Dekker's solution is often described as 'delicate.'
The exit protocol is where bounded waiting is achieved. After a process leaves the critical section, it must transfer the turn to the other process. This ensures that a waiting process eventually gets priority.
The Exit Protocol:
12345678910111213141516171819202122232425262728293031323334353637383940
// Dekker's Exit Protocol for Process i// j = 1 - i is the other process void exit_critical_section(int i, int j) { // Step 1: Give turn to the other process turn = j; // WHY: If the other process was waiting, they now have priority // This is how we guarantee bounded waiting // Step 2: Clear my flag flag[i] = FALSE; // WHY: Signal that I'm no longer in/wanting critical section} /* * WHY ORDER MATTERS: turn = j BEFORE flag[i] = FALSE * * Scenario: Process 0 is exiting, Process 1 is waiting (backed off) * * CORRECT ORDER: * t1: turn = 1 // P1 now has priority * t2: flag[0] = FALSE // P0 signals exit * * Process 1 sees turn = 1, exits wait loop, sets flag[1] = TRUE * If Process 0 immediately re-enters: flag[0] = TRUE * Both flags TRUE, turn = 1, so Process 1 proceeds, Process 0 defers * * WRONG ORDER (flag first): * t1: flag[0] = FALSE // P0 signals exit * t2: turn = 1 // P1 now has priority * * Between t1 and t2: * - Process 1 might see flag[0] = FALSE and enter * - Process 0 might see no contention and also enter * - RACE CONDITION! Both can end up in critical section * * Actually, this specific wrong order doesn't break mutual exclusion, * but it can affect fairness guarantees. The given order is the * canonical formulation ensuring all properties hold cleanly. */The Fairness Guarantee:
The turn transfer is what converts Dekker's algorithm from "correct" to "fair." Consider what would happen without turn transfer:
By transferring the turn on exit, we guarantee:
| Scenario | Before Transfer | After Transfer |
|---|---|---|
| Other waiting | Other keeps backing off | Other becomes favored, enters next |
| Other not waiting | No immediate effect | Other favored if contention arises later |
| Immediate re-entry by self | Would win contention again | Must defer to other if contention occurs |
| Neither wants entry | Turn value irrelevant | Turn preset for next contention |
The bounded waiting property states: after a process expresses intent to enter, it will enter within a bounded number of entries by other processes. With Dekker's turn transfer, this bound is exactly 1. After I express intent and back off, the other process can enter at most once more before I get my turn. This is optimal for two processes.
To understand why Dekker's Algorithm is correct, we need to identify the invariants—properties that remain true throughout all possible executions. The turn variable maintains several key invariants:
Invariant 1: Turn is Always Valid
turn ∈ {0, 1} at all times
The turn variable is always either 0 or 1, never any other value. It starts as one of these values and is only ever assigned j (which is 0 or 1). This seems trivial but is important for the inductive correctness argument.
Invariant 2: Turn Determines Priority During Contention
If flag[0] ∧ flag[1] then:
- If turn = 0, Process 1 will back off
- If turn = 1, Process 0 will back off
This is the core tie-breaking invariant. When both processes want entry, exactly one will yield based on the turn value. There's no scenario where both proceed or both wait.
Invariant 3: Turn Eventually Alternates Under Contention
If Process i enters with Process j waiting, then:
After Process i exits, turn = j
This ensures fairness. A waiting process becomes the favored process after its competitor exits.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
PROOF SKETCH: MUTUAL EXCLUSION Claim: At most one process is in the critical section at any time. Proof by contradiction:Assume both Process 0 and Process 1 are in the critical section. For each process to enter, it must have seen the other's flag as FALSE(otherwise it would be spinning in the while(flag[j]) loop). Case 1: One process entered before the other set its flag - Then the second process set its flag after the first entered - The first process is in critical section - The second process must see first's flag as TRUE (still set) - The second process cannot enter → contradiction Case 2: Both set their flags before seeing each other - Both see both flags as TRUE - Both check turn - turn is either 0 or 1, not both - One of them (say i where turn ≠ i) must back off - Process i clears its flag - Only process j (where turn = j) proceeds - Mutual exclusion maintained → contradiction In all cases, having both in critical section is impossible. QED. --- PROOF SKETCH: PROGRESS Claim: If no process is in critical section and some process wants to enter, some process eventually enters. Consider: Critical section is empty, Process 0 wants to enter. Case 1: Process 1 does not want to enter (flag[1] = FALSE) - Process 0 sets flag[0] = TRUE - Process 0 checks while(flag[1]) - exits immediately (flag[1] = FALSE) - Process 0 enters Case 2: Process 1 also wants to enter (flag[1] = TRUE) - turn is either 0 or 1 - Whichever process has the turn will NOT back off - The other process WILL back off (clear flag) - The favored process sees other's flag as FALSE - The favored process enters In all cases, some process enters. QED. --- PROOF SKETCH: BOUNDED WAITING Claim: A process that wants to enter will enter after at most one entry by the other process. Consider: Process 0 wants to enter, backs off because turn = 1 - Process 0 clears flag[0] and waits on turn- Process 1 enters critical section (if contending) or CS is free- If Process 1 enters, it eventually exits- On exit, Process 1 sets turn = 0- Process 0 sees turn = 0, sets flag[0] = TRUE- Now Process 0 has priority in any subsequent contention- If Process 1 tries again, it must back off (turn = 0)- Process 0 enters Process 0 enters after at most one more entry by Process 1. QED.Understanding Dekker's algorithm requires tracing through specific scenarios. Let's examine several key cases in detail.
Scenario 1: No Contention
Process 0 wants to enter; Process 1 is idle.
1234567891011121314151617
SCENARIO: NO CONTENTION Initial state: flag[0] = FALSE, flag[1] = FALSE, turn = 0 Time Process 0 flag[0] flag[1] turn---- --------- ------- ------- ----t1 flag[0] = TRUE TRUE FALSE 0t2 while(flag[1]==TRUE)? TRUE FALSE 0 -> flag[1] is FALSE, exit loopt3 === ENTER CRITICAL SECTION === (Process 1 never involved) Key observations:- Turn variable never checked (no contention)- Process 0 enters immediately after seeing flag[1] = FALSE- Works identically regardless of turn value- Same scenario works for Process 1 (symmetric)Scenario 2: Contention, Turn = 0
Both processes want to enter; turn favors Process 0.
123456789101112131415161718192021222324252627282930313233343536
SCENARIO: CONTENTION WITH turn = 0 Initial state: flag[0] = FALSE, flag[1] = FALSE, turn = 0Both processes start simultaneously. Time Process 0 Process 1 flag[0] flag[1] turn---- --------- --------- ------- ------- ----t1 flag[0] = TRUE TRUE FALSE 0t2 flag[1] = TRUE TRUE TRUE 0t3 while(flag[1]==TRUE)? while(flag[0]==TRUE)? TRUE TRUE 0 -> TRUE, enter loop -> TRUE, enter loopt4 if(turn != 0)? if(turn != 1)? TRUE TRUE 0 -> FALSE (turn=0=my id) -> TRUE (turn=0≠1)t5 (stay in while loop) flag[1] = FALSE (back off) TRUE FALSE 0t6 while(flag[1]==TRUE)? TRUE FALSE 0 -> FALSE, exit loopt7 === P0 ENTERS CRITICAL === TRUE FALSE 0t8 while(turn != 1)? TRUE FALSE 0 -> TRUE (turn=0), wait ... Process 0 completes critical section ... t20 turn = 1 (exit protocol) TRUE FALSE 1t21 flag[0] = FALSE FALSE FALSE 1t22 while(turn != 1)? FALSE FALSE 1 -> FALSE (turn=1), exitt23 flag[1] = TRUE FALSE TRUE 1t24 while(flag[0]==TRUE)? FALSE TRUE 1 -> FALSE, exit loopt25 === P1 ENTERS CRITICAL === FALSE TRUE 1 Key observations:- Process 1 backed off because turn ≠ 1- Process 0 entered while Process 1 waited- Turn transferred to 1 on Process 0's exit- Process 1 then entered without further contentionScenario 3: Repeated Contention
Both processes continuously want to enter. This tests fairness.
1234567891011121314151617181920212223242526272829303132333435
SCENARIO: REPEATED CONTENTION (Fairness Test) Initial state: flag[0] = FALSE, flag[1] = FALSE, turn = 0Both processes loop wanting to enter. Round 1: - Both set flags, both see contention - turn = 0, so P0 enters, P1 defers - P0 exits, sets turn = 1, clears flag[0] - P1: turn = 1, sets flag[1], enters - P1 exits, sets turn = 0, clears flag[1] Round 2: - Both set flags, both see contention - turn = 0, so P0 enters, P1 defers - P0 exits, sets turn = 1, clears flag[0] - P1: turn = 1, sets flag[1], enters - P1 exits, sets turn = 0, clears flag[1] Pattern: P0, P1, P0, P1, P0, P1, ... Under continuous contention, processes perfectly alternate!This is the fairest possible schedule for two processes. Note: If one process is faster and re-enters before the other: - Fast process sets flag - Slow process hasn't set flag yet - Fast process enters (no contention visible) - Fast process exits (turn transferred, but no one waiting) - Pattern depends on relative speeds and timing But: The moment slow process wants in AND fast process wants in: - Turn determines who enters - Previous entry by fast process transferred turn - Slow process gets priority this timeThe best way to internalize Dekker's algorithm is to trace through scenarios by hand. Try edge cases: what if one process is infinitely slow? What if flag writes are slightly delayed? What if a process crashes in the critical section? Understanding the algorithm's behavior in unusual scenarios builds intuition for concurrent programming.
Dekker's Algorithm uses two types of shared state—flags and turn—each serving a distinct purpose. Understanding their complementary roles is key to understanding the algorithm's elegance.
The Flag Variables: Safety
Flags express intent: "I want to enter the critical section." They are the primary mechanism for ensuring mutual exclusion (safety).
If flags were the only mechanism, we'd get the deadlock problem: both flags set, both waiting.
The Turn Variable: Liveness
Turn breaks symmetry: "In case of conflict, this is who proceeds." It is the mechanism for ensuring progress and bounded waiting (liveness).
If turn were the only mechanism (strict alternation), we'd get the progress violation: process must wait for others' turns even when no conflict exists.
| Aspect | Flag Variables | Turn Variable |
|---|---|---|
| Purpose | Express intent to enter | Break symmetry during conflict |
| Cardinality | One per process (2 for 2 processes) | One shared (1 total) |
| Writer | Each process writes its own flag | Exiting process writes turn |
| Reader | Each process reads the other's flag | Both processes read turn during contention |
| When Consulted | Always (entry and exit) | Only during contention |
| Safety Role | Primary (mutual exclusion) | None directly (assists by breaking ties) |
| Liveness Role | None (source of deadlock if alone) | Primary (progress and bounded waiting) |
The Synthesis:
Dekker's genius was recognizing that safety and liveness require different mechanisms, and that these mechanisms can be composed without interfering with each other:
This separation of concerns—flags for what you want, turn for who goes—is a design pattern that appears throughout synchronization:
Dekker established a fundamental pattern: separate 'intent declaration' from 'conflict resolution.' Declare your intention always, resolve conflicts only when they occur. This prevents unnecessary blocking while still handling true conflicts correctly. Modern lock-free algorithms still follow this pattern.
We've examined the turn variable in Dekker's Algorithm in comprehensive detail. Let's consolidate the key insights:
What's Next:
The turn variable is only half of Dekker's Algorithm. The next page examines the flag mechanism in equal detail—how flags express intent, how they're used to detect contention, and how the temporary flag clearing (back-off) prevents deadlock without breaking safety.
You now understand the turn-based approach in Dekker's Algorithm—its role as a contention tie-breaker, its interaction with the entry and exit protocols, and its complementary relationship with the flag mechanism. This understanding is essential for appreciating the algorithm's elegance and for reasoning about other synchronization protocols.