4.3 Software Solutions: Lock Variable, Strict Alternation & Peterson's Algorithm

Back to Operating Systems Notes

📚Module 04: Process Synchronization & ConcurrencyTopic 4.3⏱️15 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Technical Interviews

💡 Core Intuition

🍳 The Everyday Analogy: The Shared Office Whiteboard & Polite Post-it Note

Imagine two software engineers, Alice ($P_0$) and Bob ($P_1$), sharing a single whiteboard (the Critical Section):

Architecture Flow

The Shared Whiteboard Politeness Protocol

Mapping progressive software synchronization attempts to real-world peer coordination

💡 Hover or click any card for deep-dive operational details

🪙Attempt 1: Turn Token

Strict Alternation Token

Turn Variable (0 or 1)

Alice must use it, then Bob must use it, in rigid alternating sequence.

→

Upgrade to Intent Flag

📌Attempt 2: Intent Flags

I Want To Write Sticky Notes

Flag Array [flag0, flag1]

Each engineer posts a sticky note before stepping up to the board.

→

Combine Flag + Turn

🤝Peterson's Masterpiece

Polite Deference Token

Peterson's Algorithm

I declare intent, but politely grant first turn to you.

• Strict Turn: High fairness, but zero flexibility (Progress fails).
• Intent Flags: Shows active interest, but simultaneous claims cause a standoff (Deadlock occurs).
• Peterson's Insight: Declare your intent, but set the turn token to the other person. Whoever yields last yields gracefully without deadlock.

---

💻 Bridging to Computer Science

In operating systems, computer scientists historically sought pure software-based solutions to the 2-process critical section problem without relying on specialized hardware instructions. This evolutionary path progresses through four distinct algorithms:

1. The Lock Variable Solution (Naive, Flawed)
2. The Turn Variable Solution / Strict Alternation (Flawed Progress)
3. The Flag Variable Solution (Deadlock Hazard)
4. Peterson's Algorithm (Complete, Provably Correct)

---

📑Table of Contents

• 💡 Core Intuition
• 📚 Core Deep-Dive & Concepts
  • 1. Evolutionary Comparison of Software Solutions
  • 2. Solution 1: Turn Variable (Strict Alternation)
  • 3. Solution 2: Flag Variable (Intent Array)
  • 4. Solution 3: Peterson's Algorithm (The Unified Masterpiece)
• 📐 Architecture / Visual Blueprint
  • Peterson's Simultaneous Contention Trace
• 🏭 In The Real World: Production Case Study
  • Why Peterson's Algorithm Fails on Modern CPUs (Memory Reordering)
• 🎯 Exam & Interview Pitfall Check

---

📚 Core Deep-Dive & Concepts

1. Evolutionary Comparison of Software Solutions

The 4 Software Synchronization Solutions Evolution

Tracing the progression from naive attempts to mathematically verified algorithms

🔓

1. Lock Variable

Completely Flawed

• Mechanism: Single shared boolean variable lock initialized to 0.
• Fatal Flaw: Preemption between reading lock == 0 and writing lock = 1.
• Verdict: VIOLATES Mutual Exclusion. Completely invalid.

Key Abstractions / Calls

while (lock != 0);lock = 1;Fails ME

🪙

2. Turn Variable

Strict Alternation

• Mechanism: Shared turn variable alternately set to 0 and 1.
• Strengths: Follows Mutual Exclusion perfectly.
• Fatal Flaw: VIOLATES Progress due to rigid alternating coupling.

Key Abstractions / Calls

while (turn != 0);turn = 1;Fails Progress

🚩

3. Flag Array

Intent Signaling

• Mechanism: Boolean array flag[2] signaling active intent to enter.
• Strengths: Follows Mutual Exclusion.
• Fatal Flaw: VIOLATES Progress due to permanent Deadlock when flags overlap.

Key Abstractions / Calls

flag[0] = T;while (flag[1]);Deadlock Risk

🏆

4. Peterson's Algorithm

Provably Correct

• Mechanism: Combines both flag array (intent) and turn variable (politeness).
• Mutual Exclusion: Satisfied 100%.
• Progress & Bounded Waiting: Satisfied 100%.

Key Abstractions / Calls

flag[i] = T;turn = j;Passes All 3

---

2. Solution 1: Turn Variable (Strict Alternation)

Definition: In the Turn Variable solution, a shared Boolean variable turn is initialized to $0$ or $1$. Each process spins until turn matches its own process ID, executes its Critical Section, and transfers turn to its peer.

// Shared variable: boolean turn (initially 0 or 1)

// Process P0                          // Process P1
void P0() {                           void P1() {
    while (1) {                           while (1) {
        while (turn != 0); // Spin            while (turn != 1); // Spin
        /* Critical Section */                /* Critical Section */
        turn = 1;                             turn = 0;
        /* Remainder Section */               /* Remainder Section */
    }                                     }
}                                     }

Turn Variable: Criteria Compliance Analysis

Evaluating why strict alternation guarantees mutual exclusion but destroys progress

Satisfied

Mutual Exclusion: PASSED

✅

Dominant Architecture / DomainGuaranteed Single Occupancy

• •turn can only hold ONE scalar value at any instant (0 or 1).
• •P0 enters if and only if turn == 0.
• •P1 enters if and only if turn == 1.
• •Both processes can never enter the Critical Section simultaneously.

"This solution follows Mutual Exclusion as two processes cannot enter CS at the same time."

Violated

Progress: FAILED

❌

Dominant Architecture / DomainSuffers from Strict Alternation

• •Forced Alternation: P0 cannot enter twice in a row without P1 executing.
• •Remainder Section Lockout: If P1 terminates or idles in its remainder section, turn remains 1 forever.
• •Zero Intent Inquiry: We never ask the process whether it actually wishes to enter the CS or not.

"The solution does not follow Progress as it is suffering from strict alternation."

---

3. Solution 2: Flag Variable (Intent Array)

To avoid forcing uninterested processes to take turns, we introduce an explicit intent array:

// Shared variable: boolean flag[2] = {false, false};

// Process P0                          // Process P1
void P0() {                           void P1() {
    while (1) {                           while (1) {
        flag[0] = true;                       flag[1] = true;
        while (flag[1]); // Wait              while (flag[0]); // Wait
        /* Critical Section */                /* Critical Section */
        flag[0] = false;                      flag[1] = false;
        /* Remainder Section */               /* Remainder Section */
    }                                     }
}                                     }

Why the Flag Solution Dies in Deadlock:

1. Suppose both processes wish to enter simultaneously.
2. $P_0$ executes flag[0] = true;
3. A timer interrupt occurs. $P_1$ executes flag[1] = true;
4. Now, both flags are true (flag[0] == true and flag[1] == true).
5. $P_0$ enters its while-loop: while(flag[1]) $\to$ spins because flag[1] is true.
6. $P_1$ enters its while-loop: while(flag[0]) $\to$ spins because flag[0] is true.
7. Neither process ever resets its flag, and neither ever enters the Critical Section.
8. Result: Deadlock occurs! In attempting to achieve progress, the system ends up frozen.

---

4. Solution 3: Peterson's Algorithm (The Unified Masterpiece)

Definition: Peterson's Algorithm is a classic software-based solution to the critical section problem for two processes. It combines both the intent flag array and the turn variable.

// Shared variables:
boolean flag[2] = {false, false};
int turn = 0; // or 1

// Process P0 (i = 0, j = 1)           // Process P1 (i = 1, j = 0)
void P0() {                           void P1() {
    while (1) {                           while (1) {
        flag[0] = true;                       flag[1] = true;
        turn = 1;                             turn = 0;
        while (flag[1] && turn == 1);         while (flag[0] && turn == 0);
        
        /* === CRITICAL SECTION === */        /* === CRITICAL SECTION === */
        
        flag[0] = false;                      flag[1] = false;
        /* Remainder Section */               /* Remainder Section */
    }                                     }
}                                     }

Step-by-Step Mathematical Correctness Proof:

1. Proof of Mutual Exclusion

For both $P_0$ and $P_1$ to be in their Critical Sections simultaneously, both while-loop exit conditions must evaluate to false at the exact same instant:

• $P_0$ enters only if: flag[1] == false OR turn == 0
• $P_1$ enters only if: flag[0] == false OR turn == 1

If both processes are actively competing to enter, both have set their flags to true (flag[0] == true and flag[1] == true). Therefore, entry depends entirely on turn. But turn is a scalar hardware memory variable—at any physical instant, turn is either $0$ or $1$, but never both simultaneously.

• If turn == 0, $P_0$ enters and $P_1$ spins.
• If turn == 1, $P_1$ enters and $P_0$ spins.
• Mutual Exclusion is strictly guaranteed.

2. Proof of Progress

• If $P_1$ is in its Remainder Section (flag[1] == false), $P_0$ sets flag[0] = true; turn = 1;. When $P_0$ evaluates while(flag[1] && turn == 1), since flag[1] is false, the loop condition fails immediately and $P_0$ enters the Critical Section without waiting.
• If both wish to enter at the same instant, both set their flags to true. Whichever process sets turn last overwrites the other process's turn assignment, allowing the other process to enter immediately. Zero deadlock occurs. Progress is satisfied.

3. Proof of Bounded Waiting

Suppose $P_0$ finishes its Critical Section and immediately wants to re-enter. Upon exit, $P_0$ sets flag[0] = false. If $P_0$ attempts to enter again, it sets flag[0] = true and must set turn = 1. Since $P_1$ has been waiting with flag[1] == true, the fact that $P_0$ overwrote turn with $1$ ensures that $P_1$ exits its spin-loop and enters the Critical Section before $P_0$ can enter a second time.

• $P_0$ can cut ahead of waiting $P_1$ at most $1$ time.
• Bounded Waiting is strictly satisfied.

---

📐 Architecture / Visual Blueprint

Peterson's Simultaneous Contention Trace

Peterson's Algorithm: Simultaneous Contention Resolution

Tracing how simultaneous entry requests are deterministically resolved by the final turn write

Process P0

flag[0], flag[1]

turn variable

Process P1

1

Process P0→flag[0], flag[1]

P0 Declares Intent: flag[0] = true

2

Process P1→flag[0], flag[1]

P1 Declares Intent: flag[1] = true

3

Process P0→turn variable

P0 Sets turn = 1

4

Process P1→turn variable

P1 Overwrites turn = 0

5

Process P0→turn variable

P0 Checks: (turn == 1) is FALSE

6

Process P1→turn variable

P1 Spins: (turn == 0 && flag[0]) is TRUE

---

🏭 In The Real World: Production Case Study

Why Peterson's Algorithm Fails on Modern CPUs (Memory Reordering)

While mathematically perfect on classical sequentially consistent hardware, Peterson's Algorithm fails catastrophically on modern x86 and ARM processors without memory fences:

// Process P0 Entry Section
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);

The Hardware Problem: Out-of-Order Execution

Modern superscalar processors use Store Buffers and aggressively reorder independent memory operations for performance.

• To the CPU core, writing to flag[0] and writing to turn target two completely independent memory addresses.
• A modern CPU may reorder the memory writes: committing turn = 1 before flag[0] = true arrives at the cache coherency bus.
• If both cores reorder their store instructions, both processes can enter the Critical Section simultaneously, violating Mutual Exclusion!

The Production Fix: Memory Barriers

In Linux and modern C11/C++20, developers enforce sequential consistency using hardware memory fences:

// Correct production implementation with Memory Barriers
void P0_modern() {
    flag[0] = true;
    turn = 1;
    __atomic_thread_fence(__ATOMIC_SEQ_CST); // Memory barrier (mfence / dmb)
    while (flag[1] && turn == 1);
    
    /* Critical Section */
    
    flag[0] = false;
}

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Prove mathematically why Peterson's algorithm satisfies the Mutual Exclusion criterion. Answer:

1. In Peterson's algorithm, process $P_0$ can enter its critical section only if: flag[1] == false OR turn == 0.
2. Similarly, process $P_1$ enters only if: flag[0] == false OR turn == 1.
3. If both processes attempt to enter simultaneously, both set their intent flags to true (flag[0] == true and flag[1] == true).
4. Therefore, entry depends strictly on the value of turn.
5. Since turn is a scalar hardware variable, it can only hold either $0$ or $1$ at any physical instant. The process for which turn matches its own ID will enter, while the other will spin. Simultaneous entry is physically impossible, proving Mutual Exclusion.

Question 2: Why does the Turn Variable solution fail the Progress criterion? Answer: The Turn Variable solution enforces strict alternation ($P_0 \to P_1 \to P_0 \to P_1$). If $P_0$ executes its critical section, it sets turn = 1. If $P_1$ does not wish to execute and remains in its remainder section, turn remains $1$ permanently. If $P_0$ wishes to enter the critical section a second time, it is blocked indefinitely by $P_1$, even though the critical section is completely empty.

Common Interview Traps

• The Inverted Line Order Trap in Peterson's Entry Section: If a programmer swaps the order of lines in Peterson's Entry Section:

  turn = 1;       // Swapped!
  flag[0] = true; // Swapped!

  A race condition occurs where both processes can observe flag as false and enter simultaneously. Intent (flag) must always be declared before yielding turn (turn).
• Thinking Peterson's Algorithm Supports N Processes: Standard Peterson's Algorithm is strictly a two-process solution. Extending it to $N$ processes requires Filter's Algorithm or Lamport's Bakery Algorithm, or OS primitives like Semaphores.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic4.2 The 3 Critical Section CriteriaNext Topic →4.4 Hardware Synchronization: TSL & Swap