Peterson’s Solution: Understanding Software-Based Synchronization

To understand how operating systems solve synchronization problems, it is useful to study Peterson’s solution—a classic algorithm that provides mutual exclusion using only shared variables. Although it is not used directly in modern systems, it clearly illustrates the core ideas behind synchronization and the challenges involved.

---

Shared Variables Used in Peterson’s Solution

Peterson’s solution works for two processes, typically named P₀ and P₁. It relies on two shared variables:

1. turn

• Indicates whose turn it is to enter the critical section.

• If turn == i, then process Pᵢ is allowed to enter the critical section.

2. flag[2]

• flag[i] = true means process Pᵢ is ready to enter its critical section.

• Used to signal intent to enter the critical section.

Together, these variables allow the processes to coordinate access to shared data.

---

How a Process Enters the Critical Section

When process Pᵢ wants to enter the critical section, it follows these steps:

1. Declare intent

   flag[i] = true;
   

   This signals that process Pᵢ wants to enter the critical section.

2. Give priority to the other process

   turn = j;
   

   This ensures fairness by allowing the other process to go first if it also wants access.

3. Wait if necessary

   while (flag[j] && turn == j)
       ;
   

   Pᵢ waits only if the other process is interested and it is that process’s turn.

If both processes try to enter at the same time, the last write to turn wins, and that determines which process enters first.

---

Why Peterson’s Solution Is Correct

To prove correctness, we must show that the algorithm satisfies the three critical-section requirements.

---

1. Mutual Exclusion

A process can enter the critical section only if:

• The other process is not interested, or

• It is its turn

If both processes are interested (flag[0] == flag[1] == true), only one value of turn can exist (either 0 or 1). Therefore:

• Both processes cannot pass the while loop simultaneously

• Only one process can be in the critical section at a time

✅ Mutual exclusion is preserved

---

2. Progress

A process is blocked only if:

flag[j] == true && turn == j

If the other process is not interested (flag[j] == false), Pᵢ enters immediately.
If both want to enter, the value of turn decides.

Once the running process exits, it resets its flag, allowing the waiting process to proceed.

✅ Progress is guaranteed

---

3. Bounded Waiting

Each process waits for at most one entry of the other process before entering its own critical section.

No process can be postponed indefinitely.

✅ Bounded waiting is satisfied

---

Why Peterson’s Solution Fails on Modern Hardware

Although Peterson’s solution is logically correct, it is not guaranteed to work on modern processors.

Reason: Instruction Reordering

To improve performance, processors and compilers may reorder instructions that appear independent.

This reordering is harmless in single-threaded programs but dangerous in concurrent programs with shared data.

---

Example of Instruction Reordering

Shared variables:

boolean flag = false;
int x = 0;

Thread 1:

while (!flag)
    ;
print x;

Thread 2:

x = 100;
flag = true;

Expected Output

Thread 1 should print 100.

What Can Go Wrong?

• The processor may reorder Thread 2’s instructions:

  flag = true;
  x = 100;
  

• Thread 1 sees flag == true before x is updated

• Output becomes 0, which is incorrect

---

Impact on Peterson’s Solution

If the assignments in Peterson’s entry section:

flag[i] = true;
turn = j;

are reordered, both processes may enter their critical sections simultaneously, violating mutual exclusion.

This situation is illustrated in Figure 6.4, where both processes execute their critical sections due to reordering.

---

Key Takeaway

Peterson’s solution teaches us that:

• Correct synchronization is extremely subtle

• Software-only solutions are not reliable on modern architectures

• Proper synchronization requires hardware support, such as:

  • Atomic instructions

  • Memory barriers

  • Locks, semaphores, and mutexes

Modern operating systems therefore rely on hardware-supported synchronization primitives, which we study next.

---

Summary

• Peterson’s solution is a classic software algorithm for synchronization

• It satisfies mutual exclusion, progress, and bounded waiting

• It fails on modern systems due to instruction reordering

• Highlights the necessity of hardware-level synchronization tools