Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 66 ยท Synchronization

The Critical-Section Problem and Peterson's Solution

Learn the three requirements of a critical-section solution, see why naive locks fail, and test Peterson's algorithm against thousands of schedules.

The previous lesson showed that shared data needs protection. Now we make that precise. Every process that uses the shared data is written as a loop with four parts, and the whole difficulty is in designing the entry and exit parts so that they are correct.

TEXT
while true:
    entry section        # ask permission
        critical section # touch the shared data
    exit section         # announce you are done
    remainder section    # everything else

The three requirements

A correct solution to the critical-section problem must satisfy all of these:

Requirement Meaning
Mutual exclusion If one process is in its critical section, no other process may be in theirs.
Progress If nobody is in the critical section and some processes want in, only those processes decide who enters, and the decision cannot be postponed forever. A process in its remainder section must not block others.
Bounded waiting After a process asks to enter, there is a limit on how many times others may enter before it. No starvation.

Notice that nothing is said about speed or the number of CPUs. The solution must work for any interleaving.

Three rules for a correct lock

Mutual exclusion One inside at a time
Progress Idle processes never block others
Bounded waiting Nobody waits forever

Miss any one and the solution is wrong.

1 / 2

Two broken attempts

Before the right answer, look at two tempting wrong ones. We use the generator technique again: each yield lets the scheduler switch threads. The helper below runs random schedules and reports whether two threads were ever inside the critical section together.

Python Why the obvious locks fail

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Attempt 1 breaks mutual exclusion: both can see "free" and walk in. Attempt 2 keeps exclusion but can deadlock: both raise their flag, both wait for the other forever. A third idea, strict alternation with a turn variable alone, is safe but violates progress: a process in its remainder section that never comes back keeps the turn and blocks the other one.

Peterson's algorithm

In 1981 Gary Peterson combined the two ideas. A process raises its flag to say "I want in", then gives the turn away to the other process, and waits only while the other also wants in and it is the other's turn.

TEXT
// process i, other = 1 - i
flag[i] = true
turn    = other          // politely let the other go first
while flag[other] and turn == other:
    wait
    ... critical section ...
flag[i] = false

If both arrive together, both set turn; whichever writes last gives the turn to the other, so exactly one of them gets through. The loser enters after the winner clears its flag.

flowchart TD
    A["flag[i] = true"] --> B["turn = other"]
    B --> C{"flag[other] and turn == other?"}
    C -- yes --> C
    C -- no --> D["Critical section"]
    D --> E["flag[i] = false"]
    E --> F["Remainder section"]
    F --> A

The waiting loop only holds you if the other process also wants in and has the turn.

Python Peterson's algorithm under 3,000 schedules

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Zero violations and zero stuck runs. Mutual exclusion, progress and bounded waiting all hold: a waiting process is passed at most once.

Why Peterson is a teaching tool, not production code

Peterson's algorithm is correct under the sequential consistency assumption: every thread sees memory operations in the order the program wrote them. Modern CPUs and compilers violate that assumption on purpose for speed. They reorder stores and loads, keep values in store buffers, and cache data per core. On real hardware the algorithm can fail unless you add memory barriers.

Other limits:

  • It is written for exactly two processes. Generalizations (the filter lock, Lamport's bakery algorithm) exist but are slow.
  • Waiting is busy waiting: the loop burns CPU cycles.

That is why real systems use atomic hardware instructions instead. We build on them in the next lesson.

Kernel-level options on one CPU

On a single processor, a kernel can protect its own short critical sections by disabling interrupts: nothing can preempt the code, so nothing can interleave. That is cheap and simple, but it does not work across multiple CPUs and must never be offered to user programs, because one that forgets to re-enable interrupts would freeze the machine.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which requirement says a process in its remainder section must not stop others from entering?

    Progress says only processes that want to enter take part in the decision, and the decision cannot be delayed forever.
  2. 2. In Peterson's algorithm, what does a process do with the turn variable on entry?

    Setting turn to the other process lets the one who arrives second proceed last, which breaks ties.
  3. 3. Why can the 'set my flag, then wait for the other flag to drop' attempt fail?

    Each process waits for the other to lower a flag that stays up, so neither makes progress (a deadlock).
  4. 4. Why is Peterson's algorithm rarely used on modern CPUs as written?

    The proof assumes sequentially consistent memory. Real CPUs reorder loads and stores, so atomic instructions or barriers are needed.

Summary

  • A critical-section solution needs mutual exclusion, progress and bounded waiting.
  • Check-then-set locks violate exclusion; set-then-check locks can deadlock; plain alternation violates progress.
  • Peterson's algorithm uses flag[] plus turn and satisfies all three for two processes.
  • It relies on sequentially consistent memory and busy waits, so real systems use atomic hardware instructions.
  • Disabling interrupts is a kernel-only tool that works on a single CPU.

Next: Hardware Support, Mutexes and Spinlocks