A3. Producer–consumer

intermediatebuilds on module 8, module 9

Goal

A bounded buffer is a model of any task queue: a thread pool, a connection queue, a processing pipeline. Module 9 builds one on a mutex and condition variables and explains why atomic indices don’t work without a memory model. You’ll implement the buffer twice, with locks and without, and measure when the lock-free version wins and when it loses.

After this lab you will be able to:

• write a bounded buffer on a mutex and two condition variables that neither loses nor duplicates items with any number of threads;
• explain why the condition is checked in a while rather than an if, and why consumers hang when there’s no one left to wake them;
• write a ring buffer on atomic indices with the correct memory_order;
• read ThreadSanitizer output and name the line where the race is;
• show with your own measurements when the lock-free version wins and when it doesn’t.

The same two constructs are behind the queues in thread pools, loggers, and network servers, where people repeat “lock-free is faster” without stating the conditions.

Task

Write two C programs with the same interface, pc-mutex and pc-lockfree: producers put numbers into a bounded buffer, consumers take them out and add them up.

./pc-mutex    --producers 4 --consumers 4 --items 1000000 --capacity 1024
./pc-lockfree --producers 4 --consumers 4 --items 1000000 --capacity 1024

--items sets the total number of items, split evenly among the producers. Items are numbered from 1 to items, so the expected checksum is always items × (items + 1) / 2. Consumers add up what they received.

The last line of output is fixed; the automated check relies on it:

checksum=500000500000 expected=500000500000 elapsed_ms=412

The sum must always match. A mismatch means items are being lost or duplicated, and no speed measurement after that means anything.

What it must do:

• accept the arguments --producers, --consumers, --items, --capacity;
• work with any ratio of threads: 1:1, 4:4, 8:2, 2:8;
• work with a one-item buffer and with fewer items than threads, including one item for four consumers;
• exit with code 0 when the producers are done and the buffer is empty; the check treats a run longer than 30 seconds as a hang;
• give the correct sum five runs in a row, because a race doesn’t show up every time;
• pc-mutex stays silent under ThreadSanitizer.

Constraints. pc-lockfree has no mutexes, spinlocks, or semaphores: only atomic operations from <stdatomic.h>. Both versions build with gcc and -pthread.

What you don’t need to do. You don’t need to actually process the items: the producer puts a number in, the consumer adds it to the sum. The variant with work on each item is only for the measurements (the “What exactly you’re comparing” Aside).

What to write in the report:

• ThreadSanitizer output for pc-mutex, or confirmation that it stays silent;
• a table of measurements: 1, 2, 4, and 8 threads on each side, small and large buffer, both versions, median of several runs; the machine’s core count;
• an explanation of why the difference is small at 1:1 and large at 8:8, and why with a very small buffer the lock-free version can lose;
• a separate measurement with work on each item and a conclusion on whether the difference remained.

Done when:

• ./check.sh ./pc-mutex ./pc-lockfree passes all eighteen checks, nine per program, and ThreadSanitizer stays silent;
• the report has the measurement table and answers to the three questions above.

Before you start

• Read the sections “Tools”, “Memory model”, and “Classic problems” in module 9, and the section “What threads share” in module 8.
• Unpack the course archive: the check is in labs/a3-producer-consumer/check.sh. It runs ThreadSanitizer only if pc-mutex.c is in the directory the script is called from.
• You’ll need gcc with -fsanitize=thread. Any Linux will do, including a container and WSL2; the measurements need several cores, and the Vagrant machine has two.

Stages

1. The version with a mutex and condition variables.

   A buffer of fixed capacity, one mutex, two condition variables: “there is space” and “there is an item”. The producer waits on the first, the consumer on the second.

   Check the condition in a while loop, not in an if (module 9).

2. Checking with the sanitizer.

   gcc -O2 -pthread -fsanitize=thread pc-mutex.c -o pc-tsan && ./pc-tsan

   ThreadSanitizer should stay silent. If it finds a race while the program still gives the right answer, then “it works” proves nothing here.

3. Correct termination.

   Consumers must exit when the producers are done and the buffer is empty. The most common mistake in the course: a consumer hangs forever in wait, because there’s no one left to wake it.

4. The lock-free version.

   A ring buffer on atomic read and write indices. Publishing an item consists of a compare_exchange on the index, then writing the value, then an atomic update of the ready flag.

   The order of operations matters: without the correct memory_order the consumer sees the index before the data (module 9).

5. Measurement.

   Run both versions with 1, 2, 4, and 8 threads on each side, with a small and a large buffer. Build a table.

   Explain in writing why with one producer and one consumer the difference is small but with eight it’s large, and why with a very small buffer the lock-free version can lose.

What exactly you're comparing

If the producer and consumer do any work at all on each item, the cost of synchronization drowns in that work, and you won’t see a difference.

Measure the “empty” variant and, separately, the variant with work. The conclusion that the difference disappears under a real workload is also a result: it explains why lock-free is used less often than it’s discussed.

Automated check

The check is in the archive with the course files, and the commands below are run from the unpacked directory.

cd labs/a3-producer-consumer
./check.sh ./pc-mutex ./pc-lockfree

The check runs both versions at different thread ratios, compares the checksums, and catches hangs with a timeout.

Common mistakes

Lost or duplicated items. The checksum doesn’t match. Almost always the cause is that the index is updated non-atomically, or that the space check and the write are separated.

The program hangs at the end. Either there’s no termination signal for the consumers, or broadcast was replaced with signal where several threads are waiting.

if instead of while around wait. It works only as long as there is one consumer.

Measurements without warm-up. The first run includes thread creation and cold caches, so do several repetitions and take the median.

Further, if you’re curious

Compare with a queue on two mutexes (separate ones for the head and the tail) and with pthread_spinlock, and see that the middle ground between the two extremes often beats both.