Part 6 of 7 · 4 min read
Reordering
When correct code fails: reordering
Think of it this way. A written recipe says "stir, then taste". A cook with a helper might hand the spoon over before the stirring has reached the pot. The result differs from what the recipe's author imagined. A processor does something like this with memory operations. The analogy stops in one place: a cook knows what is meant, and a processor only follows the rules of its memory model.
In plain words: Peterson's proof assumes that each thread's writes become visible to the other thread in the order they were written. Real processors do not guarantee it. A processor puts its writes into a store buffer and carries on with later instructions, so a later read can complete before an earlier write is visible to other processors. In Peterson's lock, the write flag[me] = 1 may still be in the buffer when the read flag[other] runs. Both threads then read 0, both pass, and mutual exclusion fails. Compilers can also reorder memory accesses.
A test shows it on the test machine. Two threads each run Peterson's lock around counter++ two million times, with the flags as plain volatile variables, and then with the writes and reads as sequentially consistent atomic operations (they keep the order the programmer wrote):
plain volatile: expected 4000000, got 3999124
expected 4000000, got 3998945
expected 4000000, got 3998371
sequentially consistent: expected 4000000, got 4000000 (three runs)
The plain version lost between 200 and 1,700 updates in five runs, so two threads sometimes entered together. The version with ordered operations was exact in every run. Only the ordering changed. The loss was small in proportion (about 0.03 per cent), and that is dangerous: a bug that appears once in thousands of operations passes most tests.
The lesson is that software-only algorithms need more than the algorithm. They need an ordering guarantee from the processor, which is a memory barrier (or fence): an instruction that stops the processor and the compiler from moving memory operations across it. Hardware designers offer better building blocks, the atomic instructions of page 2, and the library locks of page 3 use them. Production code does not use Peterson's lock. It is taught because it shows what a correct solution must achieve with nothing more than shared variables.
Memory barrier
A memory barrier (or fence) is an instruction, or a compiler directive, that prevents memory operations before it from being reordered with operations after it, so that other processors see the writes in the order the program intended.
Example: a sequentially consistent store of flag[me] acts as a barrier before Peterson's test reads flag[other].
Common mistake
Believing that volatile makes shared variables safe between threads. In C, volatile only stops the compiler from removing or caching accesses. It does not stop the processor from reordering them, and it does not make an update atomic. Use atomic operations or locks.
Interview angle
Answer in your head first, then open it.
What are the three requirements for a critical-section solution?
Mutual exclusion, progress and bounded waiting.
Why is "check the flag, then set it" not a lock?
The check and the set can interleave, so two threads can both pass.
How does Peterson's algorithm work?
Flags show interest and a turn variable breaks ties, the last writer of turn waits.
Why does Peterson's algorithm fail on modern hardware without barriers?
Store buffers and compiler reordering let a read pass an earlier write.
What does volatile guarantee in C?
Only that the compiler performs each access, not atomicity or ordering between processors.
Check yourself:
1. What does a store buffer allow to happen?
2. How many updates were lost in the plain version, in proportion?
3. Why is volatile not enough for shared data?
Words you will meet
| Word | Meaning |
|---|---|
| Race condition | Result depends on how threads interleave |
| Critical section | Code that must not run in two threads at once |
| Entry and exit section | Code that asks for and gives back permission |
| Mutual exclusion | At most one thread in the critical section |
| Progress | Only those wanting in decide, and not for ever |
| Bounded waiting | A limit on how often others pass a waiting thread |
| Safety and liveness | Nothing bad happens, and something good happens |
| Store buffer | A queue of writes not yet visible to others |
| Memory barrier | A point across which memory operations are not reordered |
Quick notes
- A critical section is a segment of code in which a thread accesses data that other threads may also access, so that the segment must not be executed by more than one thread at the same time.
- Mutual exclusion is the property that at most one thread is inside its critical section at any moment; together with progress and bounded waiting, it defines a correct solution of the critical-section problem.
- Progress is the requirement that when no thread is in its critical section and some want to enter, the choice of which one enters is made only among those wanting.
- Peterson's algorithm is a software solution to the critical-section problem for two threads that uses a flag array, in which each thread announces that it wants to enter, and a.
- A memory barrier (or fence) is an instruction, or a compiler directive, that prevents memory operations before it from being reordered with operations after it, so that other processors see the writes in the order the program intended.