The problem

Some threads (producers) make items and others (consumers) use them. They meet in a shared buffer of N slots, used as a ring: producers write at index in, consumers read at index out, and both indexes wrap around. Three rules must hold:

  • a producer must not write into a full buffer: it has to wait for a free slot;
  • a consumer must not read from an empty buffer: it has to wait for an item;
  • two threads must not update in, out or the same slot at the same time.

The first two are about waiting (condition synchronization), the third is mutual exclusion. Waiting should also be cheap: a thread that cannot go on should sleep, not spin in a loop checking.

Producers P1 and P2 write at index in and consumers C1 and C2 read at index out of a ring buffer of 4 slots; slots 1 and 2 hold items, out points at slot 1 and in at slot 3, and both indexes wrap around. Below: semaphore empty = 2 counts free slots, full = 2 counts filled slots, mutex = 1 guards in, out and the slots.
Producers fill the ring at in, consumers empty it at out; empty and full count free and filled slots, mutex keeps one thread at a time on the indexes.

How to use the animation

Each thread runs the code under its role in an endless loop. A coloured marker shows the line each thread will run next. Every step runs exactly one line, atomically, and between any two steps any other thread may run: that is how a real scheduler can interleave threads. Choose a thread and press Step Thread to build a schedule by hand, or let the round-robin or random scheduler choose. A blocked thread moves into the queue of the semaphore it waits on. The three lines at the bottom check the program's invariants after every step and turn red when one breaks.

The semaphore solution

A semaphore is a counter with two atomic operations. wait(S) (Dijkstra's P) takes one unit: if S is 0, the thread sleeps until a unit is available. signal(S) (V) gives a unit back and wakes one sleeper, if there is one. The classic solution uses three:

semaphore empty = N;   // free slots
semaphore full  = 0;   // filled slots
semaphore mutex = 1;   // one thread in the buffer code at a time

producer:                          consumer:
    item = produce()                   wait(full)       // an item to take?
    wait(empty)      // a free slot?   wait(mutex)
    wait(mutex)                        item = buf[out]
    buf[in] = item                     out = (out + 1) % N
    in = (in + 1) % N                  signal(mutex)
    signal(mutex)                      signal(empty)    // one more free slot
    signal(full)     // one more item  consume(item)

empty and full count things, so a producer sleeps exactly when there is no free slot and a consumer exactly when there is no item. Units move from one to the other: every producer turns an empty unit into a full one and every consumer does the reverse. That gives the invariant the animation checks: empty + full plus the threads that hold a unit between their wait and signal is always N. mutex is a binary semaphore used as a lock. It protects in, out and the slots. produce() and consume() stay outside it, so the lock is held as briefly as possible.

In the animation, signal hands its unit directly to the first sleeper, whose wait then completes: the counter does not change. That is how most textbooks define it, and it keeps the queue FIFO, so no thread can be overtaken forever. Run Semaphores (correct) tab, Demo: full buffer and Demo: empty buffer.

What goes wrong when a line is missing or moved

  • No mutex. With one producer and one consumer the version without mutex works: the counting semaphores keep them on different slots. With two producers, both can pass wait(empty) and read the same in. Bug: no mutex tab, Demo: lost item interleaves them: P2 overwrites P1's item in slot 0, both move in forward, and full announces two items where only one was stored. A consumer later reads an empty slot. Such races are rare in tests and show up only under load.
  • Waits in the wrong order. If the producer calls wait(mutex) before wait(empty), a producer that finds the buffer full goes to sleep holding the mutex. The only thread that could free a slot, a consumer, now blocks on the mutex. Every thread is blocked: a deadlock. Bug: waits swapped tab, Demo: deadlock ends with the wait-for arrows drawn in red. The rule: never sleep on a condition while you hold a lock that the waker needs. The order of signals, on the other hand, does not matter for correctness.
Deadlock with the waits swapped. P1 holds mutex and sleeps on wait(empty) because empty = 0; C1 sleeps on wait(mutex) because mutex = 0. Only C1 could signal empty and only P1 can signal mutex, so both are asleep forever.
With wait(mutex) before wait(empty), P1 sleeps holding the lock the consumer needs to free a slot: a deadlock.

Monitors and condition variables

Most languages offer a lock plus condition variables instead of counting semaphores: Java's synchronized/wait/notify or Lock/Condition, POSIX pthread_mutex_t/pthread_cond_t, C++ std::condition_variable, Go's sync.Cond. The state is an explicit count, and threads sleep until a condition on it holds:

producer:                               consumer:
    lock(m)                                 lock(m)
    while (count == N)                      while (count == 0)
        wait(notFull, m)                        wait(notEmpty, m)
    buf[in] = item;  in = (in + 1) % N      item = buf[out];  out = (out + 1) % N
    count++                                 count--
    signal(notEmpty)                        signal(notFull)
    unlock(m)                               unlock(m)

wait(c, m) releases the lock and sleeps in one atomic step, so no signal can slip in between. When it is signalled, the thread does not run at once: it must take the lock again, and other threads may run first (these are Mesa semantics, used by every mainstream library). A condition variable also has no memory: a signal with nobody waiting is simply lost, which is why the condition is kept in count and not in the condition variable.

That is why the test must be while, not if. Bug: monitor with if tab, Demo: stolen wake-up: C1 sleeps on the empty buffer, P1 adds one item and signals, but C2 takes the lock first and takes the item. When C1 finally re-takes the lock it goes straight to buf[out] and reads an empty slot. Monitor with while (correct) tab, Demo: same schedule runs the same schedule: C1 re-tests count, finds it 0 and sleeps again. The loop also protects against spurious wake-ups, which POSIX and Java explicitly allow.

More details

  • One condition variable or two. With a single condition for both "not full" and "not empty", a signal can wake a thread of the wrong kind, which goes back to sleep while the right one never wakes. Use two conditions, or signalAll/notifyAll.
  • Blocking vs. spinning. A sleeping thread costs nothing until it is woken. Busy-waiting (while (count == N) {}) burns a CPU and, without memory barriers, may never even see the change.
  • Lock-free rings. With exactly one producer and one consumer, a ring buffer can work without any lock: the producer is the only writer of in, the consumer the only writer of out, and atomic loads and stores with the right memory ordering are enough. The LMAX Disruptor and the Linux kernel's kfifo work like this.

Where you meet it

Java's ArrayBlockingQueue is exactly the monitor version above (one lock, conditions notEmpty and notFull), and thread pools such as ThreadPoolExecutor hand tasks to workers through such a queue. A Go channel with a capacity is a bounded buffer, and so is a Unix pipe: write blocks when the 64 KiB pipe buffer is full and read blocks when it is empty. A socket's receive buffer is one too (see epoll). Logging libraries, audio and video pipelines, and message queues such as Kafka apply the same idea between processes and machines, where a full buffer becomes back-pressure on the producer.

See also: Readers–writers, the other classic synchronization problem. Dining philosophers shows the deadlock of the swapped waits in its general form, with the four conditions it needs. Concurrency vs parallelism shows the simplest race, counter++, happening on a single core.