Waiting without spinning

Concurrency and the Hardware · Open board

Two cores reaching for one shared counter, and a lock that lets only one of them touch it at a time. This lesson is about what comes after the lock: a thread that holds it, finds nothing it can do yet, and has to wait.

Before you start. When two threads touch the same memory at once, an update can be lost, and a lock fixes that by letting only one thread at a time near the shared value (Concurrency & the Hardware). The scheduler, the part of the kernel that hands out turns on the cores, can set a waiting thread aside and give its turns to others until something wakes it (Whose turn, and who decides).

The idea in 30 seconds

A lock keeps two parts of a program from changing shared data at the same instant. It does not tell either one when there is something to do.
A bounded buffer is a fixed number of slots between threads (lines of work inside a program, taking turns on the processor) that make items and threads that use them. Makers wait when it is full, users when it is empty.
Waiting by checking in a loop, busy-waiting, keeps the thread running and uses up one of the chip’s processors (a core) the whole time. Measured here: about 135 million checks to receive 200 items.
A condition variable lets a thread sleep until another thread signals a change. Letting go of the lock and falling asleep happen as one step; if they were two, a signal sent between them would wake nobody and be lost.
A woken thread must recheck what it was waiting for (say, “is there an item?”), in a loop, because another thread may have taken it first.
A semaphore is a counter of permits: taking one sleeps when none are left, giving one back wakes a sleeper.

Read the story · Skip to the numbers