Part 7 of 7 · 2 min read
Exercises
Easy
Easy 1: Ring indices (20 minutes)
A buffer has 4 slots. After 6 puts and 3 gets, give in, out and the number of items.
Done when: in 2, out 3, and 3 items.
Hint
in = 6 mod 4, out = 3 mod 4.
Easy 2: Semaphore values (20 minutes)
A buffer of 5 slots holds 2 items. Give empty and full.
Done when: empty 3 and full 2.
Hint
empty + full is the number of slots.
Easy 3: Spot the error (20 minutes)
A consumer is pthread_mutex_lock; sem_wait(&full); take; sem_post(&empty); pthread_mutex_unlock. What goes wrong?
Done when: it holds the mutex while it waits for an item, so the producer cannot put one: deadlock.
Hint
Which thread can free a slot?
Medium
Medium 1: Build and check (45 minutes)
Write the semaphore bounded buffer. Run 2 producers and 2 consumers with 100,000 items each. Compare the sum put with the sum taken.
Done when: equal sums in 10 runs.
Hint
Initialise empty to the number of slots and full to 0.
Medium 2: The condition-variable version (45 minutes)
Write the version with not_full and not_empty. Run the same test and compare the times.
Done when: equal sums and a table of times for both versions.
Hint
Keep the count under the mutex.
Medium 3: Make it deadlock (30 minutes)
Swap the order of the mutex and the semaphore in put, with a buffer of 2, a producer of 5 items and a late consumer. Run it with timeout 3.
Done when: exit code 124 and two lines of "produced".
Hint
The late consumer makes the producer reach the third put first.
Hard
Hard 1: Several producers, stop markers (60 minutes)
Run 3 producers and 2 consumers with stop markers. Make sure the markers are sent only after all producers finish. Show that all items are consumed.
Done when: the sum of all items matches, and both consumers end in 20 runs.
Hint
Join the producers, then put the markers.
Hard 2: Batching (90 minutes)
Change put and get to move 16 items at a time under one lock. Measure the throughput for 1 and 16 items per call.
Done when: a table that shows how batching changes throughput, with an explanation.
Hint
Take the lock once and loop over the batch.
Hard 3: Backpressure (60 minutes)
Make the consumer slow (1 ms per item). Print the buffer's fill level every 100 items for a fast producer. Show that the producer's rate falls to the consumer's rate.
Done when: a log in which the buffer is full most of the time and the producer rate equals the consumer rate.
Hint
The time per item at the producer will be about 1 ms.