Operating SystemsPeterson's Solution

Peterson's Solution

LevelIntermediate

Duration75 mins

TopicPeterson's Solution

1 / 5

Two-Process Solution

The Elegant Dance of Mutual Exclusion

In the world of concurrent programming, Peterson's Solution stands as one of the most elegant and instructive algorithms ever devised. Published by Gary L. Peterson in 1981, this algorithm solves the critical section problem for exactly two processes using nothing more than shared memory and a few carefully designed variables.

What makes Peterson's Solution remarkable is not just that it works—it's how it works. The algorithm combines two simple ideas—expressing intent and yielding precedence—in a way that satisfies all three requirements for a correct critical section solution: mutual exclusion, progress, and bounded waiting. Understanding Peterson's Solution provides deep insight into the fundamental challenges of synchronization and why modern hardware requires more sophisticated mechanisms.

What You Will Learn

By the end of this page, you will understand the core structure of Peterson's Solution, how it coordinates exactly two processes, the role each variable plays in the algorithm, and why this particular combination of mechanisms successfully achieves mutual exclusion. You'll also see the complete algorithm in action through detailed execution traces.

Historical Context and Motivation

Before Peterson's elegant solution appeared in 1981, the problem of mutual exclusion had already been studied for nearly two decades. The journey to Peterson's Solution is itself instructive:

The Problem's Origins:

In 1965, Edsger Dijkstra first formally defined the mutual exclusion problem, recognizing that as computers began to support multiple concurrent processes, controlling access to shared resources would be fundamental. His initial solution involved a complex algorithm for N processes that was difficult to understand and verify.

Dekker's Algorithm (1965):

Theodorus Dekker developed the first known correct software solution for two processes. While groundbreaking, Dekker's algorithm was intricate, involving nested conditions and multiple variables in a way that made correctness difficult to verify by inspection.

The Search for Simplicity:

For sixteen years, researchers sought simpler solutions that maintained correctness while being easier to understand and prove correct. Peterson achieved this goal spectacularly with an algorithm that uses only three shared variables and straightforward logic.

Why Study a 'Solved' Problem?

Modern systems use hardware-supported primitives like compare-and-swap and memory fences. So why study Peterson's Solution? Because it teaches the essence of synchronization: what problems arise, what properties a solution must satisfy, and how simple mechanisms combine to achieve complex guarantees. This understanding is essential when designing, analyzing, or debugging concurrent systems—even those using advanced hardware support.

Peterson's Contribution:

Peterson's 1981 paper, "Myths About the Mutual Exclusion Problem," didn't just present a new algorithm—it challenged prevailing assumptions about what was necessary for correct synchronization. By showing that mutual exclusion could be achieved with just two flags and a turn variable, Peterson demonstrated that simplicity and correctness could coexist.

The algorithm's elegance lies in its use of two independent mechanisms:

Intent signaling (flags) — Each process declares its intention to enter the critical section
Conflict resolution (turn) — When both processes want entry simultaneously, a single variable determines who proceeds

Neither mechanism alone is sufficient. Together, they form a complete solution.

The Two-Process Model

Peterson's Solution is specifically designed for scenarios involving exactly two processes (or threads) that need to coordinate access to a shared resource. Understanding this model is crucial before examining the algorithm itself.

The Scenario:

Imagine two processes, conventionally labeled Process 0 and Process 1, both executing concurrently. Each process has:

A non-critical section — Regular computation that doesn't require exclusive access
A critical section — Code that accesses shared resources and must not execute concurrently with the other process's critical section

The Structure of Each Process:

process_structure.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
while (true) {
    // ═══════════════════════════════════════════════════
    // NON-CRITICAL SECTION
    // Regular computation, no shared resource access
    // ═══════════════════════════════════════════════════
    do_local_work();
    
    // ═══════════════════════════════════════════════════
    // ENTRY SECTION
    // Algorithm to request access to critical section
    // Must ensure mutual exclusion, progress, bounded waiting
    // ═══════════════════════════════════════════════════
    enter_critical_section();  // Peterson's algorithm here
    
    // ═══════════════════════════════════════════════════
    // CRITICAL SECTION
    // Exclusive access to shared resources
    // Only one process can be here at a time
    // ═══════════════════════════════════════════════════
    access_shared_resource();
    
    // ═══════════════════════════════════════════════════
    // EXIT SECTION  
    // Release access, allow other process to proceed
    // ═══════════════════════════════════════════════════
    exit_critical_section();   // Peterson's algorithm here
}

Key Assumptions:

Peterson's Solution operates under specific assumptions about the execution environment:

Atomic Memory Operations — Reading and writing a single word-sized variable appears to happen instantaneously. If Process 0 writes a value and Process 1 reads that variable, Process 1 sees either the old value or the new value—never a partial or corrupted value.
Sequential Execution Within Each Process — Instructions within a single process execute in program order. The processor doesn't reorder reads and writes in a way that changes the algorithm's observable behavior.
Interleaving Model — The two processes' instructions interleave in some (unpredictable) order, but each individual instruction is atomic. This models what we observe on a single-processor system with context switching.
Fair Scheduling — A process that is ready to execute will eventually be scheduled. No process is starved of CPU time indefinitely.

Critical Assumption Alert

These assumptions are not always true on modern hardware! Modern CPUs reorder instructions and use write buffers that can violate assumption #2. Memory caches can cause different processors to see different values, violating assumption #1. We'll explore these issues in detail when we discuss Peterson's Solution's limitations. For now, assume we're on an idealized system where these assumptions hold.

The Algorithm's Variables

Peterson's Solution uses exactly three shared variables to coordinate between the two processes. Understanding each variable's purpose is essential to understanding the algorithm:

The Shared Variables:

peterson_variables.c
1
2
3
4
5
6
7
8
9
10
11
// Shared variables for Peterson's Solution
// Both processes have access to these variables
 
// FLAG ARRAY: Indicates each process's intent to enter critical section
// flag[i] = true means "Process i wants to enter the critical section"
// flag[i] = false means "Process i is not interested in the critical section"
bool flag[2] = {false, false};
 
// TURN VARIABLE: Resolves conflicts when both processes want entry
// turn = i means "If both want entry, Process i should go first"
int turn = 0;  // Initial value doesn't matter; either 0 or 1 works

Variable Semantics

•flag[0] — Boolean indicating Process 0's intent. When true, Process 0 is interested in entering the critical section. When false, Process 0 has no current interest in critical section access.
•flag[1] — Boolean indicating Process 1's intent. Symmetric to flag[0] but for Process 1.
•turn — Integer (0 or 1) indicating whose 'turn' it is to enter when both processes are interested. This variable is set by the process entering the entry section, not by the process leaving the critical section.

The Intuition Behind Two Types of Variables:

Why do we need both flags and a turn variable? Consider what happens with only one type:

Flags alone are insufficient: If both processes set their flags to true before either checks the other's flag, we have a deadlock—each waits for the other, and neither proceeds.

Turn alone is insufficient: If only a turn variable controls access, a fast process might monopolize the critical section while the slow process is in its non-critical section. This violates the progress requirement—a process that doesn't want the critical section shouldn't prevent another from entering.

Together, they form a complete solution:

Flags ensure that a process only waits if the other actually wants entry (progress)
Turn breaks ties when both want entry simultaneously (avoiding deadlock)
A process sets turn to favor the other, ensuring the other gets a chance (bounded waiting)

The "After You" Protocol

Think of Peterson's Solution as a polite protocol: Each process announces its intention (raises flag), then says "after you" (sets turn to the other). If both do this simultaneously, the last "after you" wins—and both agree on who that was because they both read the same turn variable.

The Complete Algorithm

Now we present Peterson's Solution in its entirety. The algorithm is symmetric—both processes execute the same code, differing only in their process ID (0 or 1) and thus which elements of the flag array they access.

Peterson's Algorithm:

petersons_algorithm.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
// Shared variables (global scope)
bool flag[2] = {false, false};
int turn = 0;
 
// ═══════════════════════════════════════════════════════════════════
// PROCESS i (where i is either 0 or 1)
// ═══════════════════════════════════════════════════════════════════
void process(int i) {
    int j = 1 - i;  // The other process: if i=0 then j=1, if i=1 then j=0
    
    while (true) {
        // ───────────────────────────────────────────────────────────
        // NON-CRITICAL SECTION
        // ───────────────────────────────────────────────────────────
        do_noncritical_work();
        
        // ┌─────────────────────────────────────────────────────────┐
        // │                    ENTRY SECTION                        │
        // │  Step 1: Announce intent to enter critical section      │
        // │  Step 2: Give priority to the other process             │
        // │  Step 3: Wait while other process has priority & wants  │
        // └─────────────────────────────────────────────────────────┘
        
        flag[i] = true;         // Step 1: "I want to enter"
        turn = j;               // Step 2: "But you can go first"
        
        while (flag[j] && turn == j) {
            // Busy wait (spin)
            // Stay here while:
            //   - The other process wants entry (flag[j] == true), AND
            //   - It's the other process's turn (turn == j)
            // 
            // Exit the loop when:
            //   - The other process doesn't want entry (flag[j] == false), OR
            //   - It's our turn (turn == i, meaning turn != j)
        }
        
        // ───────────────────────────────────────────────────────────
        // CRITICAL SECTION
        // At this point, we have exclusive access
        // ───────────────────────────────────────────────────────────
        access_shared_resource();
        
        // ┌─────────────────────────────────────────────────────────┐
        // │                    EXIT SECTION                         │
        // │  Simply retract our intent to enter                     │
        // └─────────────────────────────────────────────────────────┘
        
        flag[i] = false;        // "I'm done, no longer interested"
    }
}

Dissecting the Entry Section:

The entry section contains the algorithm's essential logic in just three elements:

flag[i] = true — The process announces: "I want to enter the critical section." This prevents the other process from incorrectly assuming no one is interested.
turn = j — The process yields: "But I'll give you priority." By setting turn to the other process's ID, this process is being courteous. If both processes execute this simultaneously, the last write wins—and both will agree on that value.
while (flag[j] && turn == j) — The process waits only if both conditions are true:
- The other process wants entry (flag[j] == true)
- It's not our turn (turn == j, meaning turn equals the other process)
If either condition becomes false, we proceed to the critical section.

When We Enter Immediately

•Other process not interested (flag[j] == false)
•It's our turn (turn == i, meaning turn != j)
•Other process finished and cleared its flag
•Other process hasn't started its entry section yet

When We Must Wait

•Other process is interested (flag[j] == true)
•AND it's the other's turn (turn == j)
•Both conditions must be simultaneously true
•We wait (spin) until either condition becomes false

Execution Trace: No Conflict

Let's trace through Peterson's algorithm in the simplest case: where only one process wants to enter the critical section at a time. This demonstrates that the algorithm doesn't impose unnecessary overhead when there's no contention.

Scenario: Process 0 Enters Alone

Initial state: flag[0] = false, flag[1] = false, turn = 0

Execution Trace: Process 0 Enters Without Contention
Step	Action	flag[0]	flag[1]	turn	Outcome
1	P0: `flag[0] = true`	true	false	0	P0 announces interest
2	P0: `turn = 1`	true	false	1	P0 offers turn to P1
3	P0: Check `flag[1] && turn == 1`	true	false	1	`false && true` = false
4	P0: Enter critical section	true	false	1	P0 has exclusive access
5	P0: Exit, `flag[0] = false`	false	false	1	P0 releases interest

Key Observations:

No waiting occurred — Because flag[1] == false, the while-loop condition (flag[1] && turn == 1) is immediately false. Process 0 doesn't spin at all.
Turn value is irrelevant — When only one process is interested, the turn variable doesn't affect the outcome. Process 0 could enter regardless of what turn holds because the first conjunct (flag[1]) is false.
Minimal overhead — In the non-contented case, the algorithm performs:
- One write (flag[i] = true)
- One write (turn = j)
- One read and comparison (the while condition)
- One write on exit (flag[i] = false)

This is the best-case behavior: constant-time entry when no other process is competing.

Progress Property Satisfied

This trace demonstrates the progress property: if only Process 0 wants to enter and Process 1 is in its non-critical section (with flag[1] = false), Process 0 can enter immediately. A process not interested in the critical section cannot block another process from entering.

Execution Trace: With Conflict

Now let's examine the critical case: both processes want to enter simultaneously. This is where Peterson's Solution truly proves its worth. We'll trace through a scenario where both processes begin the entry section at nearly the same time.

Scenario: Simultaneous Requests

Initial state: flag[0] = false, flag[1] = false, turn = 0

Both Process 0 and Process 1 begin their entry sections. The interleaving of their instructions will determine who enters first.

Execution Trace: Both Processes Request Entry
Step	Process	Action	flag[0]	flag[1]	turn
1	P0	`flag[0] = true`	true	false	0
2	P1	`flag[1] = true`	true	true	0
3	P0	`turn = 1`	true	true	1
4	P1	`turn = 0`	true	true	0
5	P0	Check `flag[1] && turn == 1`	true	true	0
—	—	`true && false` = false	—	—	—
6	P0	Enter critical section	true	true	0
7	P1	Check `flag[0] && turn == 0`	true	true	0
—	—	`true && true` = true	—	—	—
8	P1	Spins (waiting)	true	true	0

Analysis of the Critical Moment:

At step 4, Process 1 executes turn = 0, overwriting Process 0's earlier turn = 1. This is the key moment:

Both flags are now true (both processes are interested)
turn == 0 (because P1's write happened last)

What each process sees:

Process 0 checks: flag[1] && turn == 1 → true && false → false → Enters!
Process 1 checks: flag[0] && turn == 0 → true && true → true → Waits!

The mutual exclusion is preserved because:

Both processes set turn to favor the other process
Only one value can persist (the last write wins)
Whichever value persists, the favored process waits while the other enters

The Symmetry of Politeness

Notice the beautiful symmetry: each process says 'after you' by setting turn to the other's ID. When both do this simultaneously, the last 'after you' sticks—and that process actually waits while the other proceeds. It's as if two polite people at a door both say 'after you,' and the one who said it last actually holds the door.

Continuation: Process 1 Eventually Enters

Let's continue the trace to show that Process 1 does get to enter after Process 0 finishes:

Continuation: Process 1 Gets Its Turn
Step	Process	Action	flag[0]	flag[1]	turn
9	P0	In critical section...	true	true	0
10	P0	Exit: `flag[0] = false`	false	true	0
11	P1	Check `flag[0] && turn == 0`	false	true	0
—	—	`false && true` = false	—	—	—
12	P1	Enter critical section	false	true	0
13	P1	Exit: `flag[1] = false`	false	false	0

Key Insight:

Process 1 was waiting because both conditions were true (flag[0] == true AND turn == 0). The moment Process 0 cleared its flag, the first condition became false, breaking the while-loop and allowing Process 1 to enter.

This demonstrates bounded waiting: Process 1 had to wait for at most one critical section execution by Process 0 before gaining entry.

Why the Order Matters

A subtle but crucial aspect of Peterson's Solution is the order of operations in the entry section. The algorithm only works correctly because:

We set flag[i] before setting turn
We set turn before checking the while condition

Let's see what goes wrong if we change the order:

Incorrect Version: Setting turn before flag

peterson_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
// ⚠️ INCORRECT VERSION - DO NOT USE
void process_BROKEN(int i) {
    int j = 1 - i;
    
    while (true) {
        // Entry section (WRONG ORDER!)
        turn = j;           // ❌ Set turn BEFORE flag - THIS IS WRONG!
        flag[i] = true;     // Now announce interest
        
        while (flag[j] && turn == j) {
            // Wait...
        }
        
        // Critical section
        access_shared_resource();
        
        // Exit section
        flag[i] = false;
    }
}
 
/* 
 * PROBLEM: Race condition allows both processes to enter!
 * 
 * Consider this interleaving:
 * 1. P0: turn = 1          (turn is now 1)
 * 2. P1: turn = 0          (turn is now 0)
 * 3. P0: flag[0] = true
 * 4. P0: Check (flag[1] && turn == 1) → (false && false) → false → ENTER!
 * 5. P1: flag[1] = true
 * 6. P1: Check (flag[0] && turn == 0) → (true && true) → true → WAIT
 * 
 * Wait, that seems to work... but consider:
 * 
 * 1. P0: turn = 1          (turn is now 1)
 * 2. P1: turn = 0          (turn is now 0)
 * 3. P1: flag[1] = true
 * 4. P1: Check (flag[0] && turn == 0) → (false && true) → false → ENTER!
 * 5. P0: flag[0] = true  
 * 6. P0: Check (flag[1] && turn == 1) → (true && false) → false → ENTER!
 * 
 * 💥 BOTH IN CRITICAL SECTION - MUTUAL EXCLUSION VIOLATED!
 */

Why the Correct Order Works:

In the correct version, flag[i] = true happens before turn = j. This means:

Before any process checks the while condition, its own flag is already raised
If both processes are executing the entry section:
- Both flags will be true before either checks
- The turn variable determines who waits
- Because only one value can be in turn, exactly one process waits

The Invariant:

After executing flag[i] = true; turn = j;, if Process i proceeds past the while loop, either:

flag[j] == false (the other process isn't interested), OR
turn == i (it's our turn because the other process set turn = i after we set turn = j)

In either case, Process j cannot currently be past its own while loop because:

If flag[j] == false, j hasn't started its entry section
If turn == i, then j is waiting in its while loop (checking turn == i)

Memory Ordering is Critical

The algorithm depends on these operations executing in order. On modern processors with out-of-order execution and store buffers, the CPU might reorder these writes or delay their visibility to other processors. This is why Peterson's Solution requires memory barriers or fences on real hardware—a topic we'll cover when discussing limitations.

Summary: The Two-Process Solution

We've explored the foundational concepts of Peterson's Solution—a landmark algorithm in the history of concurrent programming. Let's consolidate the key insights:

Key Takeaways

•Peterson's Solution solves mutual exclusion for two processes using only shared memory—no hardware support required (under the assumed memory model).
•Three shared variables coordinate access: two boolean flags indicating intent, and one integer turn variable for conflict resolution.
•Flags signal intent — A process raises its flag before attempting entry, ensuring the other process knows about its interest.
•Turn resolves conflicts — When both processes want entry, the turn variable determines who proceeds. Each process sets turn to favor the other.
•The order of operations matters — flag[i] = true must precede turn = j, which must precede the while loop check.
•The algorithm is symmetric — Both processes execute identical code, differing only in their process ID.

What's Next:

In the following pages, we'll dive deeper into the mechanics of Peterson's Solution:

Turn Variable — A detailed analysis of how the turn variable resolves contention and prevents deadlock
Flag Array — Understanding how intent signaling ensures progress and prevents unnecessary blocking
Correctness Proof — Formal verification that the algorithm satisfies mutual exclusion, progress, and bounded waiting
Limitations — Why Peterson's Solution doesn't work correctly on modern hardware without additional precautions

Page Complete

You now understand the structure and intuition behind Peterson's Solution. This classical algorithm demonstrates that mutual exclusion can be achieved through pure software coordination, providing a foundation for understanding more sophisticated synchronization mechanisms.

1 / 5

Loading learning content...

Operating SystemsPeterson's Solution

Peterson's Solution

LevelIntermediate

Duration75 mins

TopicPeterson's Solution

1 / 5

Two-Process Solution

The Elegant Dance of Mutual Exclusion

What You Will Learn

Historical Context and Motivation

Before Peterson's elegant solution appeared in 1981, the problem of mutual exclusion had already been studied for nearly two decades. The journey to Peterson's Solution is itself instructive:

The Problem's Origins:

Dekker's Algorithm (1965):

The Search for Simplicity:

Why Study a 'Solved' Problem?

Peterson's Contribution:

The algorithm's elegance lies in its use of two independent mechanisms:

Intent signaling (flags) — Each process declares its intention to enter the critical section
Conflict resolution (turn) — When both processes want entry simultaneously, a single variable determines who proceeds

Neither mechanism alone is sufficient. Together, they form a complete solution.

The Two-Process Model

The Scenario:

Imagine two processes, conventionally labeled Process 0 and Process 1, both executing concurrently. Each process has:

A non-critical section — Regular computation that doesn't require exclusive access
A critical section — Code that accesses shared resources and must not execute concurrently with the other process's critical section

The Structure of Each Process:

process_structure.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
while (true) {
    // ═══════════════════════════════════════════════════
    // NON-CRITICAL SECTION
    // Regular computation, no shared resource access
    // ═══════════════════════════════════════════════════
    do_local_work();
    
    // ═══════════════════════════════════════════════════
    // ENTRY SECTION
    // Algorithm to request access to critical section
    // Must ensure mutual exclusion, progress, bounded waiting
    // ═══════════════════════════════════════════════════
    enter_critical_section();  // Peterson's algorithm here
    
    // ═══════════════════════════════════════════════════
    // CRITICAL SECTION
    // Exclusive access to shared resources
    // Only one process can be here at a time
    // ═══════════════════════════════════════════════════
    access_shared_resource();
    
    // ═══════════════════════════════════════════════════
    // EXIT SECTION  
    // Release access, allow other process to proceed
    // ═══════════════════════════════════════════════════
    exit_critical_section();   // Peterson's algorithm here
}

Key Assumptions:

Peterson's Solution operates under specific assumptions about the execution environment:

Atomic Memory Operations — Reading and writing a single word-sized variable appears to happen instantaneously. If Process 0 writes a value and Process 1 reads that variable, Process 1 sees either the old value or the new value—never a partial or corrupted value.
Sequential Execution Within Each Process — Instructions within a single process execute in program order. The processor doesn't reorder reads and writes in a way that changes the algorithm's observable behavior.
Interleaving Model — The two processes' instructions interleave in some (unpredictable) order, but each individual instruction is atomic. This models what we observe on a single-processor system with context switching.
Fair Scheduling — A process that is ready to execute will eventually be scheduled. No process is starved of CPU time indefinitely.

Critical Assumption Alert

The Algorithm's Variables

Peterson's Solution uses exactly three shared variables to coordinate between the two processes. Understanding each variable's purpose is essential to understanding the algorithm:

The Shared Variables:

peterson_variables.c
1
2
3
4
5
6
7
8
9
10
11
// Shared variables for Peterson's Solution
// Both processes have access to these variables
 
// FLAG ARRAY: Indicates each process's intent to enter critical section
// flag[i] = true means "Process i wants to enter the critical section"
// flag[i] = false means "Process i is not interested in the critical section"
bool flag[2] = {false, false};
 
// TURN VARIABLE: Resolves conflicts when both processes want entry
// turn = i means "If both want entry, Process i should go first"
int turn = 0;  // Initial value doesn't matter; either 0 or 1 works

Variable Semantics

•flag[0] — Boolean indicating Process 0's intent. When true, Process 0 is interested in entering the critical section. When false, Process 0 has no current interest in critical section access.
•flag[1] — Boolean indicating Process 1's intent. Symmetric to flag[0] but for Process 1.
•turn — Integer (0 or 1) indicating whose 'turn' it is to enter when both processes are interested. This variable is set by the process entering the entry section, not by the process leaving the critical section.

The Intuition Behind Two Types of Variables:

Why do we need both flags and a turn variable? Consider what happens with only one type:

Flags alone are insufficient: If both processes set their flags to true before either checks the other's flag, we have a deadlock—each waits for the other, and neither proceeds.

Together, they form a complete solution:

Flags ensure that a process only waits if the other actually wants entry (progress)
Turn breaks ties when both want entry simultaneously (avoiding deadlock)
A process sets turn to favor the other, ensuring the other gets a chance (bounded waiting)

The "After You" Protocol

The Complete Algorithm

Peterson's Algorithm:

petersons_algorithm.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
// Shared variables (global scope)
bool flag[2] = {false, false};
int turn = 0;
 
// ═══════════════════════════════════════════════════════════════════
// PROCESS i (where i is either 0 or 1)
// ═══════════════════════════════════════════════════════════════════
void process(int i) {
    int j = 1 - i;  // The other process: if i=0 then j=1, if i=1 then j=0
    
    while (true) {
        // ───────────────────────────────────────────────────────────
        // NON-CRITICAL SECTION
        // ───────────────────────────────────────────────────────────
        do_noncritical_work();
        
        // ┌─────────────────────────────────────────────────────────┐
        // │                    ENTRY SECTION                        │
        // │  Step 1: Announce intent to enter critical section      │
        // │  Step 2: Give priority to the other process             │
        // │  Step 3: Wait while other process has priority & wants  │
        // └─────────────────────────────────────────────────────────┘
        
        flag[i] = true;         // Step 1: "I want to enter"
        turn = j;               // Step 2: "But you can go first"
        
        while (flag[j] && turn == j) {
            // Busy wait (spin)
            // Stay here while:
            //   - The other process wants entry (flag[j] == true), AND
            //   - It's the other process's turn (turn == j)
            // 
            // Exit the loop when:
            //   - The other process doesn't want entry (flag[j] == false), OR
            //   - It's our turn (turn == i, meaning turn != j)
        }
        
        // ───────────────────────────────────────────────────────────
        // CRITICAL SECTION
        // At this point, we have exclusive access
        // ───────────────────────────────────────────────────────────
        access_shared_resource();
        
        // ┌─────────────────────────────────────────────────────────┐
        // │                    EXIT SECTION                         │
        // │  Simply retract our intent to enter                     │
        // └─────────────────────────────────────────────────────────┘
        
        flag[i] = false;        // "I'm done, no longer interested"
    }
}

Dissecting the Entry Section:

The entry section contains the algorithm's essential logic in just three elements:

flag[i] = true — The process announces: "I want to enter the critical section." This prevents the other process from incorrectly assuming no one is interested.
turn = j — The process yields: "But I'll give you priority." By setting turn to the other process's ID, this process is being courteous. If both processes execute this simultaneously, the last write wins—and both will agree on that value.
while (flag[j] && turn == j) — The process waits only if both conditions are true:
- The other process wants entry (flag[j] == true)
- It's not our turn (turn == j, meaning turn equals the other process)
If either condition becomes false, we proceed to the critical section.

When We Enter Immediately

•Other process not interested (flag[j] == false)
•It's our turn (turn == i, meaning turn != j)
•Other process finished and cleared its flag
•Other process hasn't started its entry section yet

When We Must Wait

•Other process is interested (flag[j] == true)
•AND it's the other's turn (turn == j)
•Both conditions must be simultaneously true
•We wait (spin) until either condition becomes false

Execution Trace: No Conflict

Scenario: Process 0 Enters Alone

Initial state: flag[0] = false, flag[1] = false, turn = 0

Execution Trace: Process 0 Enters Without Contention
Step	Action	flag[0]	flag[1]	turn	Outcome
1	P0: `flag[0] = true`	true	false	0	P0 announces interest
2	P0: `turn = 1`	true	false	1	P0 offers turn to P1
3	P0: Check `flag[1] && turn == 1`	true	false	1	`false && true` = false
4	P0: Enter critical section	true	false	1	P0 has exclusive access
5	P0: Exit, `flag[0] = false`	false	false	1	P0 releases interest

Key Observations:

No waiting occurred — Because flag[1] == false, the while-loop condition (flag[1] && turn == 1) is immediately false. Process 0 doesn't spin at all.
Turn value is irrelevant — When only one process is interested, the turn variable doesn't affect the outcome. Process 0 could enter regardless of what turn holds because the first conjunct (flag[1]) is false.
Minimal overhead — In the non-contented case, the algorithm performs:
- One write (flag[i] = true)
- One write (turn = j)
- One read and comparison (the while condition)
- One write on exit (flag[i] = false)

This is the best-case behavior: constant-time entry when no other process is competing.

Progress Property Satisfied

Execution Trace: With Conflict

Scenario: Simultaneous Requests

Initial state: flag[0] = false, flag[1] = false, turn = 0

Both Process 0 and Process 1 begin their entry sections. The interleaving of their instructions will determine who enters first.

Execution Trace: Both Processes Request Entry
Step	Process	Action	flag[0]	flag[1]	turn
1	P0	`flag[0] = true`	true	false	0
2	P1	`flag[1] = true`	true	true	0
3	P0	`turn = 1`	true	true	1
4	P1	`turn = 0`	true	true	0
5	P0	Check `flag[1] && turn == 1`	true	true	0
—	—	`true && false` = false	—	—	—
6	P0	Enter critical section	true	true	0
7	P1	Check `flag[0] && turn == 0`	true	true	0
—	—	`true && true` = true	—	—	—
8	P1	Spins (waiting)	true	true	0

Analysis of the Critical Moment:

At step 4, Process 1 executes turn = 0, overwriting Process 0's earlier turn = 1. This is the key moment:

Both flags are now true (both processes are interested)
turn == 0 (because P1's write happened last)

What each process sees:

Process 0 checks: flag[1] && turn == 1 → true && false → false → Enters!
Process 1 checks: flag[0] && turn == 0 → true && true → true → Waits!

The mutual exclusion is preserved because:

Both processes set turn to favor the other process
Only one value can persist (the last write wins)
Whichever value persists, the favored process waits while the other enters

The Symmetry of Politeness

Continuation: Process 1 Eventually Enters

Let's continue the trace to show that Process 1 does get to enter after Process 0 finishes:

Continuation: Process 1 Gets Its Turn
Step	Process	Action	flag[0]	flag[1]	turn
9	P0	In critical section...	true	true	0
10	P0	Exit: `flag[0] = false`	false	true	0
11	P1	Check `flag[0] && turn == 0`	false	true	0
—	—	`false && true` = false	—	—	—
12	P1	Enter critical section	false	true	0
13	P1	Exit: `flag[1] = false`	false	false	0

Key Insight:

This demonstrates bounded waiting: Process 1 had to wait for at most one critical section execution by Process 0 before gaining entry.

Why the Order Matters

A subtle but crucial aspect of Peterson's Solution is the order of operations in the entry section. The algorithm only works correctly because:

We set flag[i] before setting turn
We set turn before checking the while condition

Let's see what goes wrong if we change the order:

Incorrect Version: Setting turn before flag

peterson_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
// ⚠️ INCORRECT VERSION - DO NOT USE
void process_BROKEN(int i) {
    int j = 1 - i;
    
    while (true) {
        // Entry section (WRONG ORDER!)
        turn = j;           // ❌ Set turn BEFORE flag - THIS IS WRONG!
        flag[i] = true;     // Now announce interest
        
        while (flag[j] && turn == j) {
            // Wait...
        }
        
        // Critical section
        access_shared_resource();
        
        // Exit section
        flag[i] = false;
    }
}
 
/* 
 * PROBLEM: Race condition allows both processes to enter!
 * 
 * Consider this interleaving:
 * 1. P0: turn = 1          (turn is now 1)
 * 2. P1: turn = 0          (turn is now 0)
 * 3. P0: flag[0] = true
 * 4. P0: Check (flag[1] && turn == 1) → (false && false) → false → ENTER!
 * 5. P1: flag[1] = true
 * 6. P1: Check (flag[0] && turn == 0) → (true && true) → true → WAIT
 * 
 * Wait, that seems to work... but consider:
 * 
 * 1. P0: turn = 1          (turn is now 1)
 * 2. P1: turn = 0          (turn is now 0)
 * 3. P1: flag[1] = true
 * 4. P1: Check (flag[0] && turn == 0) → (false && true) → false → ENTER!
 * 5. P0: flag[0] = true  
 * 6. P0: Check (flag[1] && turn == 1) → (true && false) → false → ENTER!
 * 
 * 💥 BOTH IN CRITICAL SECTION - MUTUAL EXCLUSION VIOLATED!
 */

Why the Correct Order Works:

In the correct version, flag[i] = true happens before turn = j. This means:

Before any process checks the while condition, its own flag is already raised
If both processes are executing the entry section:
- Both flags will be true before either checks
- The turn variable determines who waits
- Because only one value can be in turn, exactly one process waits

The Invariant:

After executing flag[i] = true; turn = j;, if Process i proceeds past the while loop, either:

flag[j] == false (the other process isn't interested), OR
turn == i (it's our turn because the other process set turn = i after we set turn = j)

In either case, Process j cannot currently be past its own while loop because:

If flag[j] == false, j hasn't started its entry section
If turn == i, then j is waiting in its while loop (checking turn == i)

Memory Ordering is Critical

Summary: The Two-Process Solution

We've explored the foundational concepts of Peterson's Solution—a landmark algorithm in the history of concurrent programming. Let's consolidate the key insights:

Key Takeaways

•Peterson's Solution solves mutual exclusion for two processes using only shared memory—no hardware support required (under the assumed memory model).
•Three shared variables coordinate access: two boolean flags indicating intent, and one integer turn variable for conflict resolution.
•Flags signal intent — A process raises its flag before attempting entry, ensuring the other process knows about its interest.
•Turn resolves conflicts — When both processes want entry, the turn variable determines who proceeds. Each process sets turn to favor the other.
•The order of operations matters — flag[i] = true must precede turn = j, which must precede the while loop check.
•The algorithm is symmetric — Both processes execute identical code, differing only in their process ID.

What's Next:

In the following pages, we'll dive deeper into the mechanics of Peterson's Solution:

Turn Variable — A detailed analysis of how the turn variable resolves contention and prevents deadlock
Flag Array — Understanding how intent signaling ensures progress and prevents unnecessary blocking
Correctness Proof — Formal verification that the algorithm satisfies mutual exclusion, progress, and bounded waiting
Limitations — Why Peterson's Solution doesn't work correctly on modern hardware without additional precautions

Page Complete

1 / 5