CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 2 min read

Broadcast

Think of it this way. A shop bell can call one assistant or the whole staff. If only one assistant is needed, calling all of them wastes effort. If anyone can serve the customer, calling one is enough. If different assistants wait for different things, the wrong one may be called. The analogy stops in one place: an assistant who is called but cannot help goes back to waiting, and the calling goes on.

In plain words: pthread_cond_signal wakes at least one waiting thread. pthread_cond_broadcast wakes all of them. A test with 3 waiters, all waiting for the same flag:

signal   : 1 of 3 woke up
broadcast: 3 of 3 woke up

Which to use? A rule of thumb:

  • Signal is right when all waiters wait for the same condition and any one of them can use the change. For instance, one item added to a queue satisfies exactly one consumer.
  • Broadcast is right when the change may satisfy several waiters, or when waiters wait for different conditions on the same condition variable. For example, in a memory allocator, freeing a block can satisfy a small request but not a large one. Waking only one risks waking a thread that cannot proceed, while the thread that could proceed sleeps on. Each woken thread tests its own condition and sleeps again if it is false.

Broadcast is always correct (given the loop), and signal is an optimisation that is only correct when the argument above holds. When unsure, use broadcast. The cost is the thundering herd: many threads wake, compete for the mutex, and most go back to sleep.

A cleaner design uses one condition variable for each distinct condition (for example, not_full and not_empty for a queue, page 6), so that a signal reaches the right kind of waiter.

Broadcast

A broadcast on a condition variable wakes all threads waiting on it, each of which must retest its own condition, whereas a signal wakes at least one.

Example: after freeing memory, an allocator broadcasts so that every waiting request can check whether it now fits.

Check yourself: 1. When is one signal enough? 2. What is the cost of a broadcast? 3. Why is a separate condition variable for each condition a good design?