Producer–consumer and the bounded buffer

The compile job produces a log line every 0.2 ms.

The log-writer thread pushes those lines to build.log on the SSD, and it manages one every 0.5 ms.

The producer is more than twice as fast as the consumer. It cannot simply be slowed down, and the lines cannot be dropped.

So the lines go into a buffer between them. The Nova-14 gives it 4 slots.

Now there are two brand new ways to go wrong. The producer can find the buffer full. The consumer can find it empty.

Why & what

The three things to coordinate. This problem needs three separate guarantees, and the standard solution uses one semaphore for each. Interviews test whether you can say what each is for.

• empty, starting at 4 — counts free slots. The producer waits on this. If there are no free slots, the producer sleeps.
• full, starting at 0 — counts filled slots. The consumer waits on this. If there is nothing to take, the consumer sleeps.
• mutex, starting at 1 — a lock on the buffer itself, so the producer and consumer never modify it at the same instant.

Notice that empty and full are counting semaphores doing the signalling job from Topic 4.4, while mutex is a binary one doing mutual exclusion. The two uses appear side by side in the same solution, which is why this problem is taught.

Why mutex alone is not enough. A lock stops them corrupting the buffer, but it says nothing about whether there is anything to take. Without full, the consumer would lock an empty buffer, find nothing, unlock, and try again — spinning forever. The counting semaphores handle "is there anything to do"; the mutex handles "am I allowed to touch it".

Why the order of the two waits matters. This is the detail everything hinges on. The producer must call wait(empty) before wait(mutex).

Reverse them, and picture a full buffer: the producer takes the mutex, then finds no free slot and goes to sleep — still holding the mutex. The consumer now cannot get the mutex to remove anything. Neither can ever proceed.

That is a deadlock, and it is the exact situation Module 5 is about.

How it works

The producer, in order:

1. wait(empty) — is there a free slot? Sleep here if not.
2. wait(mutex) — my turn to touch the buffer.
3. Put the line in.
4. signal(mutex) — done touching.
5. signal(full) — there is one more line waiting, so wake the consumer if it is asleep.

The consumer is the mirror image: wait(full), wait(mutex), take the line out, signal(mutex), signal(empty).

Both release the mutex before signalling the counting semaphore, so a woken thread does not immediately block on a mutex the waker still holds.

Common confusion

"empty and full always add up to 4." They do, but only when no thread is midway through the code. During an update one of the counts has been decremented and the other not yet incremented, so the sum dips. That is correct behaviour, not a bug.

"A bigger buffer solves the problem." It hides it. If the producer is permanently faster than the consumer, any buffer of any size eventually fills. The buffer smooths out bursts, not a sustained mismatch. On the Nova-14, 4 slots absorb a short flurry of log lines; a two-minute compile still ends up limited by disk speed.

"You could just swap the waits, they are both waits." No. This is the single most tested detail in the whole problem. Mutex last, always. Take the resource permit first, take the lock second.

Interview angle

"Solve the producer–consumer problem." Write the two five-line sequences. Then say what each semaphore is for, in one line each. Then — and this is what separates a memorised answer from an understood one — explain what breaks if you swap wait(empty) and wait(mutex).

"Why do you need three semaphores?" Because there are three distinct problems: don't overfill, don't take from empty, and don't touch the buffer at the same time. Mapping one semaphore to each is the answer.

"What if there are two producers?" The same code still works. The mutex already serialises access to the buffer, and empty already limits how many lines can be in flight. Nothing changes — which is a good sign that the solution is right.