Peterson's Solution in Process Synchronization
Before Peterson's Algorithm came along in 1981, getting two processes to take turns properly without hardware support was a genuinely tricky problem. Gary Peterson came up with a clean software-only solution that handles it elegantly using just two shared variables.
It remains one of the simplest and most elegant synchronization solutions ever written, and understanding it is essential for grasping how all software-based mutual exclusion works.
The Core Idea
The algorithm relies on two things that both processes can see and modify:
- A flag array: Each process has its own flag. When it wants to enter the critical section, it sets that flag to true. Think of it as raising your hand to signal intent.
- A turn variable: This decides who actually gets to go when both processes want in at the same time. A process sets turn to the other process's index, essentially saying "after you."
If both processes raise their hands simultaneously, whoever last set the turn variable yields to the other one. This is the key insight that makes the entire algorithm work.
How It Plays Out Step by Step
When Process i wants to enter its critical section, here is what happens:
1. It sets flag[i] to true, announcing that it wants in.
2. It sets turn to j (the other process), which is its way of being polite and letting the other go first if needed.
3. It checks: Is the other process also interested (flag[j] is true) AND is it their turn (turn equals j)? If both conditions are true, it busy-waits.
4. The moment either condition breaks (the other process drops its flag OR turn shifts), it proceeds into the critical section.
5. Once done, it sets flag[i] back to false and moves on to the remainder of its work.
Process i wants to enter:
flag[i] = true // "I want in"
turn = j // "But you go first"
|
v
+---------------------------+
| Is flag[j] == true |---NO---> Enter Critical Section
| AND turn == j ? |
+---------------------------+
|
YES
|
v
Busy Wait (spin)
|
(condition breaks)
|
v
Enter Critical Section
|
v
flag[i] = false // "I'm done"What It Guarantees
| Requirement | How Peterson's Satisfies It |
|---|---|
| Mutual Exclusion | Both flag[j] == true AND turn == j must hold for Process i to be blocked. If Process i is inside, flag[i] is true and turn is j, so Process j will wait. They cannot both be inside simultaneously. |
| Progress | If no one is in the critical section, a process with its flag raised will not be stuck forever. The turn variable will eventually not point to it, or the other process will lower its flag. |
| Bounded Waiting | A process cannot be skipped more than once. If Process j finishes and sets flag[j] to false, nothing stops Process i from entering immediately. |
Implementation in C++
#include <iostream>
#include <thread>
#include <atomic>
using namespace std;
atomic<bool> flag[2] = {false, false};
atomic<int> turn;
void peterson_process(int i) {
int j = 1 - i; // The other process
while (true) {
flag[i] = true; // I want to enter
turn = j; // But you go first
while (flag[j] && turn == j) {
// Busy wait: other wants in AND it's their turn
}
// --- Critical Section ---
cout << "Process " << i << " in critical section" << endl;
// --- Exit Section ---
flag[i] = false; // I'm done, you can go
cout << "Process " << i << " in remainder section" << endl;
}
}
int main() {
thread t1(peterson_process, 0);
thread t2(peterson_process, 1);
t1.join();
t2.join();
return 0;
}Output:
Process 0 in critical section
Process 0 in remainder section
Process 1 in critical section
Process 1 in remainder section
...Each process enters the critical section one at a time, alternating in a controlled and predictable way.
Where It Gets Used
Anywhere two processes need to share a resource without stepping on each other, Peterson's Algorithm can do the job. Shared files, database records, printer access, and memory regions in real-time systems are all situations where it applies.
It also naturally prevents deadlocks since it guarantees both mutual exclusion and bounded waiting, which together eliminate the conditions that cause deadlocks.
The Two-Process Limitation
Peterson's Algorithm is strictly a two-process solution. If you have more than two processes competing for the same resource, you need something else, like the Bakery Algorithm, which extends the same general philosophy to N processes using a ticketing system.
For two processes though, Peterson's remains one of the simplest and most elegant solutions ever written. It requires no special hardware instructions, no OS support, and no complex data structures. Just two variables and a few lines of logic.