The idea: a lock, a place to sleep, and the state
A monitor is shared state plus one lock that guards it plus one or more condition variables where threads sleep until the state is what they need. In C it is a pthread_mutex_t m and a pthread_cond_t c next to the data. In Java every object is a monitor: synchronized takes its lock, wait() sleeps on it, notify() and notifyAll() wake sleepers.
The page has one monitor: the counter count of items ready, the mutex m and the condition c ("count > 0"). Consumers C1 and C2 take an item, producer P adds one:
consumer: producer:
pthread_mutex_lock(&m); pthread_mutex_lock(&m);
while (count == 0) count++;
pthread_cond_wait(&c, &m); pthread_cond_signal(&c);
count--; pthread_mutex_unlock(&m);
pthread_mutex_unlock(&m);
How to use the animation
Each thread runs its code in a loop, one line per step, and each line is atomic. Pick a thread and press Step Thread to build any schedule yourself, or run a demo. A thread's box sits in the panel it is in. A red name means it is blocked. To keep runs repeatable, unlock hands m straight to the head of the entry queue.
wait releases the lock and takes it back
pthread_cond_wait(&c, &m) does two things in one atomic step: it releases m and puts the thread in c's wait set. Without the release nobody could ever enter the monitor to change count. Without the atomicity, a signal could slip in between the release and the sleep and be missed.
A woken thread does not run at once. It moves to the entry queue and the call returns only when it holds m again. Then it runs with the lock held, as before the call. (Demo: wait and signal.) This is Mesa semantics, used by POSIX, Java, C++ and Go. The signaller keeps the lock and keeps running.
Why while, not if
Between the signal and the moment the woken thread gets m, other threads can run. In Demo: stolen wake-up with if, C2 is already in the entry queue when P signals C1. C2 gets m first and takes the only item. C1 then returns from wait and, with if, goes straight to count--: count becomes −1. With while (Demo: same schedule with while) C1 checks again, sees 0 and goes back to sleep.
The loop also handles spurious wake-ups: POSIX and Java allow wait to return with no signal at all. So the rule has no exception: always wait in a loop that re-checks the condition.
signal or broadcast
| signal (notify) | broadcast (notifyAll) | |
|---|---|---|
| wakes | one waiter | every waiter |
| cost | one thread competes for m | all compete for m; most go back to sleep |
| safe when | all waiters wait for the same thing and any one can use the change | always (with the while loop) |
Demo: broadcast wakes everyone wakes C1 and C2 for one item. C1 gets it, C2 re-checks and sleeps again. Use broadcast when waiters wait for different conditions on one variable, or when one change can help several of them.
Lost wake-ups
A condition variable has no memory. A signal with nobody in the wait set does nothing. That is harmless when the state is changed under the lock: count remembers the item, and a consumer that comes later sees it before it would wait (Demo: normal hand-off through the entry queue).
It breaks when the producer changes the state without the lock. In Demo: lost wake-up, C1 checks count == 0 and is about to wait. P adds an item and signals right then: nobody is in the wait set yet, so the signal is lost. C1 then sleeps with count = 1. If P took m, it would have to wait until C1's pthread_cond_wait had released it, and by then C1 is in the wait set.
The same ideas in other languages
| POSIX C | Java | C++ | |
|---|---|---|---|
| lock | pthread_mutex_lock | synchronized | std::unique_lock |
| wait | pthread_cond_wait | wait() | cv.wait(lock) |
| wake one | pthread_cond_signal | notify() | notify_one() |
| wake all | pthread_cond_broadcast | notifyAll() | notify_all() |
Java's ReentrantLock with newCondition() gives one lock several condition variables, as in ArrayBlockingQueue. C++ cv.wait(lock, pred) writes the while loop for you.
See also Mutex for how the lock itself sleeps in the kernel, Semaphore, a counter that does remember its signals, and Bounded Buffer, the classic monitor with two conditions.
See also Semaphore vs Condition Variable: why a semaphore remembers a post and a condition variable forgets a signal.
What the page leaves out
Real mutexes do not hand the lock to the head of the queue: a woken thread races with newcomers, which makes stolen wake-ups more likely, not less. The page leaves out spurious wake-ups as an event, timed waits (pthread_cond_timedwait), several condition variables on one lock, Hoare-style monitors where the signaller hands the lock to the woken thread at once, and how pthread_cond_wait is built on futexes in the kernel.