Petersons Solution - Learning Module

Loading content...

0/240

Flag Array

Signaling Intent in Concurrent Systems

In the previous page, we explored how the turn variable resolves conflicts when both processes want to enter the critical section simultaneously. But how do we know when a conflict exists? How does Process 0 know whether Process 1 is interested in the critical section at all?

The answer lies in the flag array—a pair of boolean variables that explicitly communicate each process's intent. The flags are the signaling mechanism that transforms Peterson's Solution from a simple tie-breaker into a complete synchronization protocol.

Where the turn variable asks "whose turn is it if we're both waiting?", the flags ask "is anyone waiting in the first place?"

What You Will Learn

By the end of this page, you will understand the precise semantics of the flag array, why each process needs its own flag, how flags prevent unnecessary blocking and ensure progress, the critical timing of flag modifications, and how flags and turn together form a complete solution.

The Purpose of Flags

The flag array in Peterson's Solution serves a single, crucial purpose: signaling interest. Each flag is a boolean variable owned by one process:

flag[0] — Controlled exclusively by Process 0, indicates whether Process 0 wants to enter the critical section
flag[1] — Controlled exclusively by Process 1, indicates whether Process 1 wants to enter the critical section

Ownership and Visibility:

flag_ownership.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
// Flag array declaration
bool flag[2] = {false, false};
 
// ═══════════════════════════════════════════════════════════════════
// OWNERSHIP RULES:
// ═══════════════════════════════════════════════════════════════════
// flag[i] is WRITTEN only by Process i
// flag[j] is READ by Process i (to check other's interest)
//
// This is crucial: each process has exclusive write access to its
// own flag, preventing write-write conflicts on the flags themselves.
// ═══════════════════════════════════════════════════════════════════
 
void process_0() {
    while (true) {
        // Process 0 WRITES to flag[0]
        flag[0] = true;     // "I am interested"
        
        turn = 1;
        
        // Process 0 READS flag[1]
        while (flag[1] && turn == 1) {
            // Check if Process 1 is interested
        }
        
        // Critical section
        
        // Process 0 WRITES to flag[0]  
        flag[0] = false;    // "I am no longer interested"
    }
}
 
void process_1() {
    while (true) {
        // Process 1 WRITES to flag[1]
        flag[1] = true;     // "I am interested"
        
        turn = 0;
        
        // Process 1 READS flag[0]
        while (flag[0] && turn == 0) {
            // Check if Process 0 is interested
        }
        
        // Critical section
        
        // Process 1 WRITES to flag[1]
        flag[1] = false;    // "I am no longer interested"
    }
}

The Signaling Protocol:

Before attempting entry: A process sets its flag to true, announcing: "I want to enter the critical section."
While considering entry: A process reads the other's flag to determine if there's competition.
After exiting: A process sets its flag to false, announcing: "I have left the critical section and have no current interest."

This protocol ensures that each process always has accurate (if slightly delayed) information about the other's intentions.

Exclusive Writes, Shared Reads

Notice that each flag has exactly one writer (its owning process) but potentially one reader (the other process). This single-writer/multiple-reader pattern avoids the need for synchronization on the flags themselves—there's no race condition on which value to write, only on when the read observes the write.

Flags and the Progress Property

One of the three essential properties of a correct critical section solution is progress: if no process is in the critical section and one or more processes want to enter, then the selection of which process enters cannot be postponed indefinitely. Furthermore, only processes attempting to enter can participate in this decision.

The flag array is directly responsible for ensuring progress. Let's see why:

How Flags Enable Progress:

progress_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
// The while loop condition in Peterson's Solution:
while (flag[j] && turn == j) {
    // Wait...
}
 
// ═══════════════════════════════════════════════════════════════════
// PROGRESS SCENARIO 1: Other process not interested
// ═══════════════════════════════════════════════════════════════════
// 
// Process 0 wants to enter. Process 1 is in its non-critical section
// with flag[1] = false (not interested).
//
// P0's condition: flag[1] && turn == 1
//                 false && (anything)
//                 → false
//
// Result: P0 enters IMMEDIATELY.
//         No waiting occurs because no one else is interested.
//         Progress is satisfied.
 
// ═══════════════════════════════════════════════════════════════════
// PROGRESS SCENARIO 2: Other process is in critical section
// ═══════════════════════════════════════════════════════════════════
//
// Process 0 wants to enter. Process 1 is in critical section
// with flag[1] = true.
//
// P0's condition: flag[1] && turn == j
//                 true && (depends on turn)
//
// If turn == 0: P0 enters immediately (it's P0's turn)
// If turn == 1: P0 waits... but P1 will eventually exit!
//
// When P1 exits: flag[1] = false
// P0's condition becomes: false && (anything) → false
// P0 enters.
//
// Result: P0 enters after P1 exits.
//         The decision was made by P1's exit (clearing flag[1]).
//         Progress is satisfied.
 
// ═══════════════════════════════════════════════════════════════════
// PROGRESS SCENARIO 3: Both processes racing to enter
// ═══════════════════════════════════════════════════════════════════
//
// Both processes want to enter. Both flags are true.
// Turn determines who enters.
//
// If turn == 0:
//   P0's condition: flag[1] && turn == 1 → true && false → false → ENTER
//   P1's condition: flag[0] && turn == 0 → true && true → true → WAIT
//
// If turn == 1:
//   P0's condition: flag[1] && turn == 1 → true && true → true → WAIT
//   P1's condition: flag[0] && turn == 0 → true && false → false → ENTER
//
// Result: Exactly one process enters immediately.
//         The other waits but will enter when the first exits.
//         No indefinite postponement.
//         Progress is satisfied.

The Key Insight:

The flag check (flag[j]) is a short-circuit condition. When the other process's flag is false:

The entire while condition is false (due to AND logic)
The loop body never executes
Entry is immediate

This short-circuit behavior ensures that a process not interested in the critical section (flag = false) cannot block another process from entering. Only interested processes (flag = true) can participate in the synchronization decision.

Progress Guaranteed

Unlike simple alternation (where a slow process blocks a fast one), Peterson's Solution only considers the flags of processes actively trying to enter. If you're not raising your flag, you're not part of the decision process. This is exactly what the progress property requires.

Timing of Flag Modifications

The correctness of Peterson's Solution depends critically on when flag modifications occur. Let's examine the exact timing:

Entry Section: Flag Set to True

The flag is set to true as the first operation in the entry section, before setting turn, and before checking the while condition.

flag_timing_entry.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
// Entry section
flag[i] = true;     // ← FIRST: Announce intent
turn = j;           // ← SECOND: Yield to other
while (flag[j] && turn == j) {
    // THIRD: Check and wait if needed
}
 
// Why this order matters:
// ═══════════════════════════════════════════════════════════════════
// If we set flag[i] AFTER turn = j:
//
// P0: turn = 1
// P1: turn = 0
// P1: flag[1] = true
// P1: Check (flag[0] && turn == 0) → (false && true) → false → ENTER
// P0: flag[0] = true
// P0: Check (flag[1] && turn == 1) → (true && false) → false → ENTER
//
// 💥 BOTH IN CRITICAL SECTION! Mutual exclusion violated!
//
// The problem: P1 checked flag[0] BEFORE P0 set it.
// If flag is set first, this race doesn't happen.
// ═══════════════════════════════════════════════════════════════════
 
// Correct order guarantees:
// By the time a process checks the while condition, its own flag
// is already true. If the other process is also checking, it will
// see our flag as true, and the turn variable will break the tie.

Exit Section: Flag Set to False

The flag is set to false as the only operation in the exit section, immediately upon leaving the critical section.

flag_timing_exit.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Exit section
flag[i] = false;    // ← ONLY operation: Clear intent
 
// Why this is sufficient:
// ═══════════════════════════════════════════════════════════════════
// When we clear flag[i], any process waiting in its while loop
// will see flag[i] become false. This makes their condition:
//
//   flag[i] && turn == i  →  false && (anything)  →  false
//
// The waiting process exits its loop and enters the critical section.
//
// We don't need to modify turn because:
// 1. If the other process is waiting, clearing our flag releases them.
// 2. If we try to re-enter, we'll set turn = j, giving them priority.
// ═══════════════════════════════════════════════════════════════════
 
// Critical invariant:
// flag[i] = true  →  Process i is in entry section OR critical section
// flag[i] = false →  Process i is in non-critical or remainder section

Flag Must Be Cleared!

A process MUST clear its flag when exiting. If a process crashes or forgets to clear its flag, the other process may wait forever, thinking the crashed process is still interested. This is a limitation of Peterson's Solution—it has no mechanism to handle process failures.

Why Two Flags?

A natural question is: could we use a single shared variable instead of two separate flags? Let's explore why two flags are necessary:

Attempt 1: Single "interested" Counter

single_counter_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
// ⚠️ BROKEN: Single counter doesn't work
int interested = 0;  // Number of processes interested
 
void process_BROKEN(int i) {
    while (true) {
        // Entry section
        interested++;        // Increment to show interest
        
        while (interested > 1) {
            // Wait while both are interested
        }
        
        // Critical section
        
        interested--;        // Decrement on exit
    }
}
 
/*
 * PROBLEM 1: Race condition on increment
 * 
 * Both processes can read interested=0, then both increment to 1.
 * Both see interested=1, both enter!
 * 
 * The increment itself isn't atomic (it's read-modify-write).
 * We'd need an atomic increment, but that's what we're trying to avoid!
 * 
 * PROBLEM 2: Can't distinguish WHO is interested
 * 
 * With a counter, we know how many are interested but not who.
 * We can't implement the "after you" protocol because we can't
 * favor a specific process—we only know a count.
 */

Attempt 2: Single Boolean with Complex Logic

single_bool_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
// ⚠️ BROKEN: Single boolean has same issues
bool someone_interested = false;
 
void process_BROKEN(int i) {
    while (true) {
        // Entry section
        someone_interested = true;   // Show interest
        
        // How do I check if the OTHER process is interested?
        // I just set it to true! I've lost information about
        // whether they were interested before I was.
        
        // Critical section??
        
        someone_interested = false;
    }
}
 
/*
 * FUNDAMENTAL PROBLEM: Lost information
 * 
 * With a single shared boolean:
 * - We can't distinguish Process 0's interest from Process 1's
 * - Setting it to true overwrites the other's state
 * - We need SEPARATE state for each process
 * 
 * Two flags solve this by giving each process its own variable
 * to write without affecting the other's state.
 */

Why Two Flags Work:

Two separate flags provide essential properties:

Independent State: Each process controls its own flag without affecting the other's state.
No Write Conflicts: flag[0] is only written by P0; flag[1] is only written by P1. No race on writes.
Complete Information: Each process can determine the exact state of the other process's intentions.
Asymmetric Checking: P0 checks flag[1]; P1 checks flag[0]. Each process checks the other's state, enabling the turn-based conflict resolution.

Generalization to N Processes

For N processes, Peterson's Solution can be generalized using N flags (one per process) plus a more complex turn mechanism. Each process still writes only to its own flag. The filter algorithm and tournament barriers are extensions of this idea.

Flag Array as a State Machine

Understanding the flag array as a state machine helps visualize all possible system states and transitions. With two boolean flags, there are exactly four possible states:

All Possible Flag States
State	flag[0]	flag[1]	Meaning
Idle	false	false	Neither process is interested in critical section
P0 Interested	true	false	Only Process 0 wants to enter
P1 Interested	false	true	Only Process 1 wants to enter
Contention	true	true	Both processes want to enter (conflict!)

State Transitions and Their Implications:

state_transitions.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
// State Machine for Peterson's Solution Flags
// ═══════════════════════════════════════════════════════════════════
 
                   P0 starts entry
         (Idle) ────────────────────→ (P0 Interested)
        ↗     ↖                        ↙           ↘
    P1 exits   P0 exits          P0 can enter    P1 starts entry
               │                  immediately!        │
               │                       ↓              ↓
    (P1 Interested) ←────────────────────── (Contention)
           ↓                                     ↓
    P1 can enter                          Turn determines
    immediately!                          who enters first
 
// ═══════════════════════════════════════════════════════════════════
// STATE: Idle (false, false)
// ═══════════════════════════════════════════════════════════════════
// No synchronization needed. Any process can immediately transition
// to its interested state and enter the critical section.
// This is the common case when processes aren't contending.
 
// ═══════════════════════════════════════════════════════════════════
// STATE: P0 Interested (true, false) / P1 Interested (false, true)
// ═══════════════════════════════════════════════════════════════════
// Only one process wants entry. That process enters immediately
// because the other's flag is false, making the while condition false.
// No conflict resolution needed.
//
// Example for P0:
//   while (flag[1] && turn == 1)
//   → while (false && anything)
//   → while (false)
//   → Don't wait, enter immediately!
 
// ═══════════════════════════════════════════════════════════════════
// STATE: Contention (true, true)
// ═══════════════════════════════════════════════════════════════════
// Both flags are raised. Now and only now does turn matter.
// The turn variable determines which process waits.
// This is the only state where the while loop can iterate.

The Contention State is Rare

In most real-world scenarios, processes don't attempt to enter the critical section at exactly the same time. The (false, false), (true, false), and (false, true) states are far more common. Peterson's Solution is optimized for these cases—entry is immediate with no spinning. Only in the contention state does actual waiting occur.

The Flag-Turn Interplay

The elegance of Peterson's Solution lies in how flags and turn interact. Neither mechanism alone is sufficient, but together they achieve all three correctness properties. Let's examine their interplay:

Division of Responsibilities:

Flags Provide

•Intent signaling — announces interest to other process
•Progress guarantee — uninterested process doesn't block
•Release mechanism — clearing flag unlocks waiters
•Independence — each process controls its own state

Turn Provides

•Conflict resolution — decides winner when both want entry
•Deadlock prevention — asymmetric state breaks ties
•Bounded waiting — last entrant yields to waiting process
•Serialization — atomic write orders simultaneous attempts

The Condition Structure:

The while-loop condition flag[j] && turn == j is a conjunction (AND) of two checks:

flag[j] — Is the other process interested?
turn == j — Is it the other process's turn?

Both must be true to wait. This structure implements the complete protocol:

condition_truth_table.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Truth table for while condition: flag[j] && turn == j
// ═══════════════════════════════════════════════════════════════════
 
flag[j]  │  turn == j  │  Result  │  What happens
─────────┼─────────────┼──────────┼───────────────────────────────────
false    │  false      │  false   │  Enter immediately (other uninterested)
false    │  true       │  false   │  Enter immediately (other uninterested)
true     │  false      │  false   │  Enter immediately (my turn, other can wait)
true     │  true       │  TRUE    │  WAIT (other interested + other's turn)
 
// ═══════════════════════════════════════════════════════════════════
// Key insight: The only way to wait is if BOTH conditions are true.
// This means:
//   1. The other process is genuinely interested (progression-safe)
//   2. It's genuinely the other's turn (fair conflict resolution)
//
// The AND logic ensures minimal waiting:
//   - If other isn't interested → don't wait
//   - If other is interested but it's my turn → don't wait
//   - Only wait if other is interested AND it's their turn
// ═══════════════════════════════════════════════════════════════════

Perfect Cooperation

Flags prevent unnecessary waiting (progress). Turn prevents deadlock and ensures fairness (mutual exclusion + bounded waiting). Each mechanism patches the weakness of the other, creating a complete solution. This is a beautiful example of compositional design in concurrent algorithms.

Flag Visibility and Memory Ordering

A critical assumption of Peterson's Solution is that when one process writes to a flag, the other process eventually sees that write. In the idealized model where Peterson developed his algorithm, this happens immediately. In real hardware, it's more complex.

The Visibility Problem:

visibility_problem.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
// IDEALIZED MODEL (Peterson's assumption)
// ═══════════════════════════════════════════════════════════════════
// Memory is a single shared entity. A write by one process is
// immediately visible to reads by another process.
//
// P0: flag[0] = true;    // Write
// P1: if (flag[0]) ...   // Read sees true IMMEDIATELY
 
// REAL HARDWARE (what actually happens)
// ═══════════════════════════════════════════════════════════════════
// Each CPU has local caches and store buffers. Writes may be:
//   1. Buffered in CPU 0's store buffer
//   2. Write eventually reaches cache, then memory
//   3. CPU 1's cache may still have stale value
//   4. CPU 1 might read stale (old) value!
 
// CPU 0                    Store Buffer          CPU 1
// ─────────                ────────────          ─────────
// flag[0] = true  →→→→→→→  [flag[0]=true]        read flag[0]
//                          pending...            ↓
//                                                OLD VALUE!
 
// This can break Peterson's Solution:
// ═══════════════════════════════════════════════════════════════════
// P0: flag[0] = true
// P0: turn = 1
// P0: read flag[1] → sees false (P1 hasn't set it YET... or has it?)
// P0: enters critical section
//
// MEANWHILE:
// P1: flag[1] = true (but P0 might not see this yet!)
// P1: turn = 0
// P1: read flag[0] → might see false (store buffer hasn't drained!)
// P1: enters critical section
//
// 💥 BOTH IN CRITICAL SECTION!

Memory Barriers to the Rescue:

On real multi-processor systems, Peterson's Solution requires memory barriers (also called memory fences) to ensure visibility:

A write barrier ensures all preceding writes are visible before subsequent operations
A read barrier ensures all preceding reads are completed before subsequent reads
A full barrier does both

With proper barriers, the algorithm becomes:

peterson_with_barriers.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
void process(int i) {
    int j = 1 - i;
    
    while (true) {
        flag[i] = true;
        MEMORY_BARRIER();     // Ensure flag write is visible
        
        turn = j;
        MEMORY_BARRIER();     // Ensure turn write is visible
        
        while (flag[j] && turn == j) {
            // Barrier inside loop not strictly necessary
            // if we trust the loop will eventually see updates
        }
        
        // Critical section
        access_shared_resource();
        
        flag[i] = false;
        MEMORY_BARRIER();     // Ensure flag clear is visible
    }
}
 
// With barriers:
// - When P0 reads flag[1], it sees P1's most recent write
// - When P1 reads flag[0], it sees P0's most recent write  
// - The algorithm works as Peterson intended

Don't Use Peterson's Without Barriers!

On modern multi-core processors (x86, ARM, etc.), Peterson's Solution without memory barriers is BROKEN. The algorithm was designed for an idealized memory model that doesn't match real hardware. Always use proper synchronization primitives (mutexes, atomics) unless you deeply understand your platform's memory model.

Summary: The Flag Array

We've explored the flag array in depth—understanding how these simple boolean variables enable progress and communicate intent between processes. Let's consolidate our knowledge:

Key Takeaways

•Flags signal intent — Each flag indicates whether its owning process wants to enter the critical section.
•Exclusive write access — Each process writes only to its own flag, preventing write-write conflicts.
•Flags ensure progress — When flag[j] is false, the while condition short-circuits, allowing immediate entry.
•Timing is critical — Flag must be set to true BEFORE setting turn and before checking the while condition.
•Exit clears the flag — The only exit operation is flag[i] = false, which releases any waiting process.
•Two flags are necessary — A single shared variable cannot provide independent state for each process.
•Flags define contention — Only when both flags are true does the turn variable actually matter.
•Visibility requires barriers — On real hardware, memory barriers are needed to ensure flag changes are seen across processors.

What's Next:

Now that we deeply understand both the flag array and the turn variable, we're ready to formally prove that Peterson's Solution is correct. In the next page, we'll rigorously verify that the algorithm satisfies mutual exclusion, progress, and bounded waiting.

Page Complete

You now understand the flag array's role in Peterson's Solution. These simple boolean variables, combined with the turn variable, create a complete synchronization protocol. Next, we'll prove this correctness mathematically.