A pure software lock
Petersons algorithm gives mutual exclusion for two threads using only ordinary shared variables, no special hardware instruction. It combines two ideas that fail alone but succeed together.
The two ingredients
- A pair of interested flags, one per thread, set when a thread wants to enter
- A single turn variable that breaks ties
To enter, a thread sets its own interested flag, then sets turn to the other thread, then waits while the other thread is interested and it is still the other thread turn.
Why it works
Yielding the turn to the other thread is the clever part. If both threads try at once, both write turn, and only the last write survives. That thread loses the tie and waits, while the other proceeds. The interested flags prevent a thread from racing in when its partner is mid entry. Together they give safety, progress, and bounded waiting for two threads.
The catch
Petersons assumes a sequentially consistent memory model. On real CPUs that reorder loads and stores, it needs memory fences to behave, and it does not scale beyond two threads cleanly.
Key idea
Petersons combines per thread interest flags with a yielded turn variable to give two thread mutual exclusion in software.