Petersons Solution - Learning Module

Loading content...

0/227

Turn Variable

The Tiebreaker of Synchronization

In any system where multiple parties compete for the same resource, there must be a mechanism to resolve conflicts when both parties want access simultaneously. In Peterson's Solution, this critical responsibility falls to a single, shared integer variable: turn.

The turn variable is deceptively simple—it's just an integer that can be 0 or 1. Yet this simplicity belies its profound importance. The turn variable is the tie-breaker, the deadlock preventer, and the fairness enforcer all in one. Without it, two processes setting their flags simultaneously would deadlock forever. With it, exactly one process always proceeds while the other waits gracefully.

What You Will Learn

By the end of this page, you will understand the precise role of the turn variable, why each process sets it to favor the other, how this prevents deadlock, why the last writer always 'loses' (and why that's actually winning), and how the turn variable's semantics differ from simple alternation schemes.

The Role of the Turn Variable

The turn variable serves a single, focused purpose: resolving contention when both processes want to enter the critical section simultaneously. To understand why this is necessary, let's first see what happens without it.

The Flag-Only Problem:

Consider a simplified mutual exclusion attempt using only flags:

flag_only_deadlock.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
// ⚠️ BROKEN: Flags alone cause deadlock
bool flag[2] = {false, false};
 
void process_BROKEN(int i) {
    int j = 1 - i;
    
    while (true) {
        // Entry section
        flag[i] = true;           // Announce interest
        
        while (flag[j]) {         // Wait while other is interested
            // Busy wait...
        }
        
        // Critical section
        access_shared_resource();
        
        // Exit section
        flag[i] = false;
    }
}
 
/*
 * DEADLOCK SCENARIO:
 * 
 * Time  P0                    P1                    flag[0]  flag[1]
 * ────  ────────────────────  ────────────────────  ───────  ───────
 *  1    flag[0] = true        (hasn't started)      true     false
 *  2    (continues)           flag[1] = true        true     true
 *  3    while(flag[1]) → ✓    while(flag[0]) → ✓    true     true
 *  4    WAIT                  WAIT                  true     true
 *  5    WAIT                  WAIT                  true     true
 *  ...  WAIT FOREVER          WAIT FOREVER          true     true
 * 
 * 💥 DEADLOCK! Both processes are waiting for the other to lower their flag,
 *    but neither will because they're both stuck in the while loop.
 */

Why Deadlock Occurs:

When both processes set their flags to true before either checks the loop condition:

Process 0 sees flag[1] == true and waits
Process 1 sees flag[0] == true and waits
Neither process will ever set its flag to false (they're stuck waiting)
Both wait forever → Deadlock

The Turn Variable Solution:

The turn variable breaks this deadlock by introducing asymmetry. Even when both flags are true, the turn variable distinguishes one process from the other. The key insight is that only one value can be stored in turn at any moment.

The Atomic Tiebreaker

The turn variable works because memory writes are atomic at the word level. When both processes write to turn, these writes are serialized—one happens before the other. Whichever write happens last determines the final value. This creates an ordering on simultaneous requests.

Write Semantics: Favoring the Other

A crucial and counterintuitive aspect of Peterson's Solution is that each process sets turn to the other process's ID, not its own. Process 0 executes turn = 1, and Process 1 executes turn = 0.

Why Not Set Turn to Your Own ID?

One might naively think: "I want to enter, so I should set turn to my ID to claim my turn." But this would break the algorithm:

turn_to_self_WRONG.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
58
// ⚠️ BROKEN: Setting turn to your own ID
void process_BROKEN(int i) {
    int j = 1 - i;
    
    while (true) {
        flag[i] = true;
        turn = i;            // ❌ WRONG: "I want my turn!"
        
        while (flag[j] && turn == j) {
            // Wait...
        }
        
        // Critical section
        access_shared_resource();
        
        flag[i] = false;
    }
}
 
/*
 * DEADLOCK SCENARIO (again!):
 * 
 * 1. P0: flag[0] = true
 * 2. P0: turn = 0
 * 3. P1: flag[1] = true  
 * 4. P1: turn = 1
 * 5. P0: Check (flag[1] && turn == 1) → (true && true) → WAIT
 * 6. P1: Check (flag[0] && turn == 0) → (true && false) → ENTER? 
 * 
 * Actually wait... P1 enters because turn=1, so turn==0 is false for P1.
 * So ONE process might enter, but consider this:
 * 
 * 1. P0: flag[0] = true
 * 2. P1: flag[1] = true
 * 3. P0: turn = 0   (turn is now 0)
 * 4. P1: turn = 1   (turn is now 1)
 * 5. P0: Check (flag[1] && turn == 1) → (true && true) → WAIT!
 * 6. P1: Check (flag[0] && turn == 0) → (true && false) → ENTER!
 * 
 * Hmm, seems OK here. But what about:
 * 
 * 1. P0: flag[0] = true
 * 2. P1: flag[1] = true
 * 3. P1: turn = 1   (turn is now 1)
 * 4. P0: turn = 0   (turn is now 0)
 * 5. P0: Check (flag[1] && turn == 1) → (true && false) → ENTER!
 * 6. P1: Check (flag[0] && turn == 0) → (true && true) → WAIT!
 * 
 * Also seems OK. But the problem is BOUNDED WAITING is violated!
 * 
 * If P0 keeps entering, exiting, and re-entering:
 * - P0 sets flag[0]=true, turn=0, enters (if P1 is slow)
 * - P0 exits, P1 starts checking
 * - P0 immediately re-enters: flag[0]=true, turn=0
 * - P0 enters again before P1 can!
 * 
 * Process 0 can starve Process 1 indefinitely.
 */

The Correct Semantics: "After You"

By setting turn to the other process's ID, each process is effectively saying: "If we're both interested, you can go first." This is the key to both deadlock prevention AND bounded waiting:

Deadlock Prevention: If both processes say "after you," the last one to say it actually waits, breaking the symmetry.
Bounded Waiting: If Process 0 just exited the critical section and Process 1 is waiting, when Process 0 tries to re-enter, it sets turn = 1. This means Process 1 will get priority on this attempt.

The "after you" protocol ensures that no process can repeatedly jump ahead of a waiting competitor.

The Last One to Yield, Yields

Here's the beautiful paradox: each process sets turn to favor the other, effectively "yielding" priority. But when both yield simultaneously, only one yielding gesture persists (the last write). That process—the one whose yield was recorded last—actually ends up waiting. The other process's earlier yield was overwritten, so it proceeds.

The Last Writer Wins (By Waiting)

When both processes execute their entry sections concurrently, both will write to the turn variable. Since memory writes are serialized at the hardware level, these writes form a total order—one happens before the other. The process whose write happens last will be the one that waits.

The Serialization of Writes:

write_serialization.pseudo
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
// Both processes attempting entry simultaneously
 
Process 0:                          Process 1:
─────────────────                   ─────────────────
flag[0] = true;                     flag[1] = true;
turn = 1;  ←──────┐     ┌──────→    turn = 0;
                  │     │
                  ▼     ▼
            ┌─────────────────┐
            │ MEMORY SYSTEM   │
            │                 │
            │ Serializes the  │
            │ two writes to   │
            │ 'turn'          │
            │                 │
            │ Final value:    │
            │ Either 0 or 1   │
            │ (not both!)     │
            └─────────────────┘
 
Case A: P0's write happens last
─────────────────────────────────
Memory sees: turn = 0, then turn = 1
Final value: turn = 1
Result: P0 waits (turn == j where j=1 for P0)
        P1 enters (turn != j where j=0 for P1)
 
Case B: P1's write happens last
─────────────────────────────────
Memory sees: turn = 1, then turn = 0  
Final value: turn = 0
Result: P1 waits (turn == j where j=0 for P1)
        P0 enters (turn != j where j=1 for P0)

Why This Guarantees Exactly One Entry:

The key observation is that the turn variable can only hold ONE value at a time. When both processes check their while conditions:

Process 0 checks: turn == 1 (am I yielding?)
Process 1 checks: turn == 0 (am I yielding?)

Exactly one of these conditions is true. Therefore:

If turn == 0: P1's condition is true (P1 waits), P0's condition is false (P0 enters)
If turn == 1: P0's condition is true (P0 waits), P1's condition is false (P1 enters)

There is no state where both conditions are true or both are false (assuming both flags are set).

When turn = 0

•Process 0's last action: turn = 1
•Process 1's last action: turn = 0 (overwrote)
•Process 0 checks: turn == 1 → false → ENTER
•Process 1 checks: turn == 0 → true → WAIT
•Process 1 "won" the race to write, so it waits

When turn = 1

•Process 1's last action: turn = 0
•Process 0's last action: turn = 1 (overwrote)
•Process 0 checks: turn == 1 → true → WAIT
•Process 1 checks: turn == 0 → false → ENTER
•Process 0 "won" the race to write, so it waits

Winning by Losing

There's a delightful irony in Peterson's Solution: the process that 'wins' the race to write to turn is the one that waits! By being faster to yield, you end up yielding. This ensures that in a tie, the slower process (which might have been waiting longer) gets priority.

Turn vs. Simple Alternation

A common misconception is that Peterson's Solution is simply an alternation scheme where processes take turns. This is fundamentally incorrect. Let's understand the difference:

Simple Alternation (WRONG):

simple_alternation_WRONG.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
// ⚠️ BROKEN: Simple alternation violates progress
int turn = 0;
 
void process_alternation(int i) {
    int j = 1 - i;
    
    while (true) {
        // Wait for my turn
        while (turn != i) {
            // Busy wait...
        }
        
        // Critical section
        access_shared_resource();
        
        // Give turn to other process
        turn = j;
        
        // Non-critical section
        do_other_work();
    }
}
 
/*
 * PROGRESS VIOLATION:
 * 
 * Scenario: P1 is processing slowly, P0 wants to enter repeatedly
 * 
 * 1. P0: Enters (turn = 0)
 * 2. P0: Exits, sets turn = 1
 * 3. P0: Does non-critical work (fast!)
 * 4. P0: Wants to re-enter, but turn = 1
 * 5. P0: MUST WAIT for P1 to take its turn first!
 * 6. P1: Still in non-critical section, working slowly...
 * 7. P0: Waiting, waiting, waiting...
 * 
 * 💥 PROGRESS VIOLATED! P0 cannot enter even though P1 isn't interested!
 *    The requirement for synchronization should depend on INTEREST,
 *    not on strict alternation.
 */

How Peterson's Solution Differs:

In Peterson's Solution, the turn variable is only consulted when both processes are interested (both flags are true). If only one process wants entry, it enters immediately regardless of the turn value.

This crucial difference means:

Progress is maintained: A process only waits if the other is actively competing, not because of some arbitrary alternation.
No artificial coupling: The speed of one process's non-critical section doesn't artificially limit the other's critical section access.
Demand-based synchronization: Turn matters only during conflict, not during normal operation.

Peterson's Solution vs. Simple Alternation
Aspect	Simple Alternation	Peterson's Solution
When P0 can enter	Only when `turn == 0`	When `flag[1] == false` OR `turn == 0`
P1 not interested case	P0 still waits if `turn == 1`	P0 enters immediately (`flag[1]` is false)
Progress property	❌ Violated	✅ Satisfied
Speed coupling	Fast process limited by slow one	Independent execution speeds
Turn variable purpose	Strict ordering of access	Conflict resolution only
Turn variable modified	After exiting critical section	Before attempting entry

A Critical Distinction

Notice that in Peterson's Solution, the turn variable is set during the ENTRY section, not the EXIT section. This is fundamentally different from alternation. In Peterson's algorithm, 'turn' doesn't mean 'whose turn is it now'—it means 'who should go first if we're both waiting right now.'

Turn Variable and Bounded Waiting

The turn variable plays a crucial role in ensuring bounded waiting—the guarantee that once a process requests entry to the critical section, there's a limit on how many times other processes can enter before it.

The Bounded Waiting Guarantee:

In Peterson's Solution, once a process starts its entry section, it will enter the critical section after waiting for at most one critical section execution by the other process.

Why This Works:

Let's analyze what happens when Process 0 is waiting for Process 1:

bounded_waiting_analysis.pseudo
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
58
59
60
61
// Scenario: P0 is waiting, P1 is in critical section
 
State:
  flag[0] = true   (P0 wants entry, is waiting)
  flag[1] = true   (P1 is in critical section)
  turn = 0         (was set by P1 when it entered)
 
// P0 is spinning: while (flag[1] && turn == 0) { }
 
// P1 exits critical section:
P1: flag[1] = false;
 
// Now P0's condition becomes:
//   flag[1] && turn == 0
//   false && true
//   false → P0 exits loop and enters!
 
// ═══════════════════════════════════════════════════
// But what if P1 immediately tries to re-enter?
// ═══════════════════════════════════════════════════
 
// P1 re-enters entry section:
P1: flag[1] = true;
P1: turn = 0;        // ← Sets turn to favor P0!
 
// P1 checks its condition:
//   flag[0] && turn == 0
//   true && true
//   true → P1 must wait!
 
// Meanwhile, P0's condition:
//   flag[1] && turn == 0
//   true && true
//   true → Wait... P0 should wait too?
 
// ═══════════════════════════════════════════════════
// RESOLUTION: Order of operations matters!
// ═══════════════════════════════════════════════════
 
// Critical insight: P1 exited (flag[1]=false) BEFORE re-entering
// P0 sees flag[1]=false and proceeds BEFORE P1 can set flag[1]=true again
// Even if interleaving occurs, the analysis shows P0 enters
 
// Alternative interleaving where P1 is very fast:
Timeline:
  P1: flag[1] = false (exit)
  P1: flag[1] = true  (immediate re-entry attempt)
  P1: turn = 0        (yield to P0)
  P0: Check condition (sees flag[1]=true, turn=0) → still true, wait?
  
  NO! P1's "turn = 0" means P1 is yielding to P0.
  P0's turn check: turn == 1? No, turn == 0.
  P0's full condition: flag[1] && turn == 1
                       true && false = false → P0 ENTERS!
  
  P1's condition: flag[0] && turn == 0
                  true && true = true → P1 WAITS!
 
// The key: P1 set turn = 0, giving priority to P0.
// P0 only waits when turn == 1, but turn == 0 now.
// So P0 enters, P1 waits.

The Bound is ONE:

The maximum number of times Process 1 can enter the critical section while Process 0 is waiting is exactly ONE (the time Process 1 was already in when Process 0 started waiting). After that:

Process 1 exits and sets flag[1] = false
If Process 1 tries to re-enter, it must set turn = 0 (favoring Process 0)
Process 0, already waiting with flag[0] = true, will now see its condition as false
Process 0 enters before Process 1 can

This bound of one is optimal for a two-process solution—you can't guarantee a process enters immediately if another is already in the critical section.

Fairness Guaranteed

The turn variable's 'after you' semantics directly produce bounded waiting. By always favoring the other process when entering, no process can repeatedly jump ahead of a waiting competitor. This is a form of fairness embedded directly in the algorithm's structure.

Initial Value of Turn

A frequently asked question about Peterson's Solution is: What should the initial value of turn be, and does it matter?

The Answer: It doesn't matter.

The initial value of turn can be 0 or 1—the algorithm works correctly either way. Let's understand why:

initial_value_analysis.pseudo
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
// Initial state
flag[0] = false;
flag[1] = false;
turn = ???;  // Does the initial value matter?
 
// ═══════════════════════════════════════════════════
// Case 1: turn = 0 initially, P0 enters first
// ═══════════════════════════════════════════════════
P0: flag[0] = true;
P0: turn = 1;          // turn is now 1
P0: Check (flag[1] && turn == 1)
    → (false && true)
    → false → ENTER!
 
// Initial turn value was irrelevant because flag[1] = false
 
// ═══════════════════════════════════════════════════
// Case 2: turn = 1 initially, P0 enters first
// ═══════════════════════════════════════════════════
P0: flag[0] = true;
P0: turn = 1;          // turn was 1, still 1
P0: Check (flag[1] && turn == 1)
    → (false && true)
    → false → ENTER!
 
// Same outcome! Initial turn value was irrelevant.
 
// ═══════════════════════════════════════════════════
// Case 3: turn = 0 initially, both enter simultaneously
// ═══════════════════════════════════════════════════
P0: flag[0] = true;
P1: flag[1] = true;
P0: turn = 1;          // turn is now 1
P1: turn = 0;          // turn is now 0
// Final turn value is 0 (P1's write happened last)
P0: Check → (true && false) → ENTER
P1: Check → (true && true) → WAIT
 
// Initial value was overwritten by both processes
 
// ═══════════════════════════════════════════════════
// CONCLUSION: Initial value never affects outcome
// ═══════════════════════════════════════════════════
// Before any process reaches the while check, it has:
// 1. Set its own flag to true
// 2. Set turn to favor the other process
// 
// So by the time turn is read, both processes have
// written to it (in the contention case) or flags
// determine the outcome (in the single-entry case).

Why Initial Value Is Irrelevant:

Single Process Entry: When only one process wants entry, the other's flag is false. The condition flag[j] && turn == j short-circuits to false regardless of turn's value.
Simultaneous Entry: Both processes overwrite turn before checking it. The final value depends on which write happened last, not on the initial value.
Sequential Entry: The first process sets turn when entering. By the time the second process checks, turn has already been set.

In every case, the initial value is either irrelevant (flag check dominates) or overwritten before being read.

Conventional Initialization

While any initial value works, conventionally turn is initialized to 0. This isn't because 0 is special—it's just a programming convention. Some texts initialize to 0, others to 1. Neither is wrong. What matters is that both processes use the same turn variable and each sets it to the OTHER's ID.

Turn Variable Not Modified on Exit

A subtle but important aspect of Peterson's Solution is that the turn variable is not modified in the exit section. The exit section only clears the flag:

// Exit section
flag[i] = false;  // Just this. No turn modification.

Why Not Set Turn on Exit?

One might think that when exiting, a process should set turn to favor the other process. But this is unnecessary and actually could complicate the algorithm:

Already Favoring: The exiting process already set turn to favor the other when it entered the entry section. That yielding is still in effect.
No Waiting Process: If no other process is waiting (flag[j] = false), setting turn would be meaningless—there's no one to receive the favor.
Waiting Process Already Has Priority: If another process is waiting and we're exiting, we must have set turn to favor them when we entered. They're waiting because we were in the critical section, but our flag clearing releases them.

An Alternative Design That Works (But Is Different):

alternative_with_exit_turn.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
// Alternative design: Set turn on exit
// This works but has different semantics
 
void process_alternative(int i) {
    int j = 1 - i;
    
    while (true) {
        // Entry section (still need flag and turn)
        flag[i] = true;
        turn = j;
        
        while (flag[j] && turn == j) {
            // Wait...
        }
        
        // Critical section
        access_shared_resource();
        
        // Exit section (with turn modification)
        turn = j;            // Explicitly favor other
        flag[i] = false;
    }
}
 
/*
 * This works but is REDUNDANT:
 * 
 * The turn = j in the entry section already provides bounded waiting.
 * Adding turn = j in exit doesn't add correctness.
 * 
 * Proof: When this process re-enters, it will set turn = j again
 * anyway. So if the other process is waiting, it will get priority
 * when we try to re-enter, not when we exit.
 * 
 * Peterson's original design is more elegant: minimal code that
 * achieves all three properties (mutual exclusion, progress,
 * bounded waiting).
 */

Elegance in Minimalism

Peterson's Solution is remarkable partly for what it doesn't do. The exit section is a single operation: flag[i] = false. This minimalism isn't laziness—it's evidence that the entry section's design is sufficient to guarantee all correctness properties. Additional operations would be redundant.

Summary: The Turn Variable

We've thoroughly analyzed the turn variable—a single integer that serves as the cornerstone of conflict resolution in Peterson's Solution. Let's consolidate our understanding:

Key Takeaways

•Turn breaks deadlock — Without turn, two processes with raised flags would wait forever. Turn creates asymmetry by being a single value that both processes read.
•Each process favors the other — Setting turn = j (the other's ID) implements an "after you" protocol. This is counter-intuitive but essential.
•Last writer waits — When both processes write to turn simultaneously, the last one to write ends up waiting. This serializes concurrent requests.
•Turn is not alternation — Peterson's Solution only consults turn when both flags are raised. Single-process entry ignores turn entirely (progress property).
•Turn ensures bounded waiting — A waiting process is guaranteed entry after at most one critical section by the other (because that other must set turn to favor the waiting process upon re-entry).
•Initial value is irrelevant — Before turn is read, it's always written by at least one process, so initialization doesn't affect correctness.
•Exit doesn't modify turn — The entry section's turn assignment is sufficient for all guarantees; no exit-time modification is needed.

What's Next:

Having mastered the turn variable, we'll now examine the flag array in detail. While turn resolves conflicts, the flags signal intent—determining whether conflict resolution is even necessary. Understanding both mechanisms is essential for the complete correctness proof that follows.

Page Complete

You now have a deep understanding of the turn variable's role in Peterson's Solution. This simple integer, combined with the flag array, creates a complete solution to the critical section problem—demonstrating that elegant synchronization doesn't require complex mechanisms.