Peterson's Solution (Critical Section)

The critical-section problem

Two processes share a variable, for example a bank balance. The part of each program that touches it is a critical section (CS). If both run it at the same time you get a race condition and a corrupted balance. Each process therefore runs

loop forever:
    entry protocol        <- we have to design this
    critical section
    exit protocol
    remainder section     <- everything else

A correct entry/exit protocol must give three guarantees:

1. Mutual exclusion: at most one process is inside the CS.
2. Progress: if the CS is empty and someone wants in, only the processes that want in take part in deciding who enters, and the decision cannot be postponed forever. In particular, a process in its remainder section must not block anyone.
3. Bounded waiting: after a process asks to enter, there is a limit to how many times others can enter before it does. Nobody waits forever.

Peterson’s solution (1981) does this for two processes using only ordinary reads and writes. The 3D model lets you run four attempts. Each fixes a problem of the one before.

Attempt 1: no protection

The “entry protocol” is empty. Run it with the alternating schedule: P0 reaches the CS, then P1 walks in right behind it. Both are inside. Mutual exclusion fails.

Attempt 2: strict alternation

One shared variable turn says whose turn it is:

while (turn != i) ;      // wait for my turn
critical section
turn = j                 // hand the turn over

Mutual exclusion holds, because turn has only one value. But the processes are forced to take turns. If P1 is busy in its remainder section and never gives the turn back, P0 cannot enter a second time even though the CS is empty. This breaks progress: P0 runs at the speed of the slowest process. Try the schedule Only P0 runs.

Attempt 3: flags only

Each process announces its interest with a boolean flag[i] and waits while the other one is interested:

flag[i] = true           // I want to enter
while (flag[j]) ;        // wait while the other wants to enter
critical section
flag[i] = false

Now P1 in its remainder section has flag[1] = false, so P0 may enter as often as it likes. But run the alternating schedule: P0 raises its flag, P1 raises its flag, and then each sees the other’s flag and waits. Deadlock. Each process is too polite.

Peterson’s solution: flags and turn

Combine the two ideas. Raise your flag, then politely give the other process priority with turn:

flag[i] = true                       // I want to enter
turn = j                             // but you may go first
while (flag[j] && turn == j) ;       // wait only if j wants in AND it is j's turn
critical section
flag[i] = false                      // I am done

Because the processes wait only when the other one wants in and has the priority, the deadlock disappears. The value of turn breaks the tie: both processes write it, and the last one to write loses (waits), because it wrote the other’s number.

One run, step by step (alternating schedule)

Step	Process	Instruction	Result
1	P0	flag[0] = true	flags = (T, F)
2	P1	flag[1] = true	flags = (T, T)
3	P0	turn = 1	turn = 1
4	P1	turn = 0	turn = 0 (P1 wrote last)
5	P0	test flag[1] && turn == 1	turn is 0, so the test is false: P0 enters
6	P1	test flag[0] && turn == 0	true: P1 is blocked
7	P0	critical section
8	P1	test	still blocked
9	P0	flag[0] = false	exit protocol
10	P1	test	flag[0] is false: P1 enters

P1 gave P0 priority by writing turn = 0 last, so P0 went first and P1 followed right after.

Why mutual exclusion holds

Suppose P0 and P1 were both inside the CS. Both set their flags first, so flag[0] and flag[1] are both true. P0 got through its test, so it saw turn == 0. P1 got through its test, so it saw turn == 1. But turn has only one value, and the last write to it came from one of the two processes. That process wrote the other’s number and then could not pass its test while the other flag was still up. Contradiction, so they cannot both be inside.

Progress: if P1 is in its remainder section, flag[1] is false, so P0’s wait condition is false and it enters at once. Bounded waiting: after P0 has set its flag, P1 can enter at most once, because when P1 exits, it lowers its flag, and if it comes back it sets turn = 0, which lets P0 through.

Checking all the interleavings

You can test a protocol by running some schedules, but a proof must cover all of them. Because there are only a few shared states, the code below visits every reachable combination of program counters, flags and turn:

Algorithm	Reachable states	Mutual exclusion	Deadlock	P0 alone can re-enter
No protection	9	✗	no	yes
Strict alternation	16	✓	no	✗ (progress fails)
Flags only	21	✓	yes	yes
Peterson	42	✓	no	yes

Limits of Peterson’s algorithm

• Busy waiting. The waiting process spins and burns CPU. This kind of lock is a spinlock, acceptable for very short critical sections only. Semaphores and mutexes put the waiting process to sleep.
• Only two processes. The filter lock and Lamport’s bakery algorithm extend the idea to n processes.
• Modern hardware reorders memory operations. Peterson’s proof assumes each write becomes visible to the other core immediately and in order. Real CPUs use store buffers and compilers reorder code, so on today’s machines the algorithm needs memory barriers. In practice operating systems use atomic hardware instructions such as test-and-set and compare-and-swap to build locks.

Code

# Each process repeats its program forever. A process is INSIDE the critical section
# while its program counter points at 'cs'.
PROGRAMS = {
    'none':     ['enter', 'cs', 'rem'],
    'turn':     ['wait_turn', 'cs', 'give_turn', 'rem'],
    'flags':    ['set_flag', 'wait_flag', 'cs', 'clear_flag', 'rem'],
    'peterson': ['set_flag', 'set_turn', 'wait_both', 'cs', 'clear_flag', 'rem'],
}

def step(algo, state, i):
    """Run one instruction of process i. Returns the new state, or None if i is blocked (spinning)."""
    pcs, flag, turn = list(state[0]), list(state[1]), state[2]
    j = 1 - i
    prog = PROGRAMS[algo]
    op = prog[pcs[i]]
    if op == 'wait_turn' and turn != i:
        return None                                   # while (turn != i) ;
    if op == 'wait_flag' and flag[j]:
        return None                                   # while (flag[j]) ;
    if op == 'wait_both' and flag[j] and turn == j:
        return None                                   # while (flag[j] && turn == j) ;
    if op == 'set_flag':
        flag[i] = True
    elif op in ('set_turn', 'give_turn'):
        turn = j
    elif op == 'clear_flag':
        flag[i] = False
    pcs[i] = (pcs[i] + 1) % len(prog)
    return (tuple(pcs), tuple(flag), turn)

def inside(algo, state, i):
    return PROGRAMS[algo][state[0][i]] == 'cs'

def check(algo):
    """Explore EVERY interleaving of the two processes (breadth of the whole state space)."""
    start = ((0, 0), (False, False), 0)
    seen, todo = {start}, [start]
    both_inside = deadlock = False
    while todo:
        s = todo.pop()
        both_inside |= inside(algo, s, 0) and inside(algo, s, 1)
        moves = [step(algo, s, i) for i in (0, 1)]
        deadlock |= all(m is None for m in moves)     # nobody can move at all
        for m in moves:
            if m is not None and m not in seen:
                seen.add(m)
                todo.append(m)
    # progress test: P1 never leaves its remainder section; can P0 still enter twice?
    s, entries = start, 0
    for _ in range(40):
        s = step(algo, s, 0) or s
        entries += inside(algo, s, 0)
    return len(seen), not both_inside, deadlock, entries >= 2

for algo in PROGRAMS:
    states, mutex, dead, alone = check(algo)
    print(f'{algo:9} states={states:2}  mutual exclusion={mutex!s:5}  deadlock={dead!s:5}  P0 alone can re-enter={alone}')
# none      states= 9  mutual exclusion=False  deadlock=False  P0 alone can re-enter=True
# turn      states=16  mutual exclusion=True   deadlock=False  P0 alone can re-enter=False
# flags     states=21  mutual exclusion=True   deadlock=True   P0 alone can re-enter=True
# peterson  states=42  mutual exclusion=True   deadlock=False  P0 alone can re-enter=True

Common mistakes

• Swapping the two lines (turn = j before flag[i] = true). Then both processes can pass their tests at once and mutual exclusion fails. Always raise the flag first.
• Writing turn = i instead of turn = j. Peterson’s trick is to give the other process priority.
• Using || instead of && in the waiting condition. A process must wait only when the other wants in and has the priority.
• Confusing progress with bounded waiting. Progress: the CS being empty must not keep a willing process out. Bounded waiting: nobody is overtaken forever.
• Thinking busy waiting is a bug. It is the price of using only plain variables. It is fine for very short waits, but wasteful for long ones.