CSE Roadmap

Core tier · about 6 hours · 7 parts

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.