CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Why the loop? (20 minutes)

Give two reasons why a wait must be in a while loop.

Done when: a spurious wakeup, and another thread changing the condition after the wakeup.

Hint

Think of what happens between the signal and the relock.

Easy 2: Signal or broadcast (20 minutes)

A queue has one condition variable not_empty and many identical consumers. After one item is added, which call is enough? A memory allocator frees a block that may suit several waiting requests. Which call?

Done when: signal for the first and broadcast for the second.

Hint

Does the change help one waiter or several?

Easy 3: Name the mistake (20 minutes)

A thread sets ready = 1 and signals without holding the mutex, while another tests the flag under the mutex. What can go wrong?

Done when: the waiter can test 0 and then sleep after the signal was sent, so the signal is lost.

Hint

The test and the wait must be under one hold of the mutex.

Medium

Medium 1: Reproduce the lost wakeup (30 minutes)

Write the test of section 3 with and without the flag, using pthread_cond_timedwait.

Done when: a timeout for the version without the check and an immediate return for the version with it.

Hint

Use an absolute time for timedwait.

Medium 2: Signal against broadcast (30 minutes)

Start three waiters on one flag. Set the flag and call signal, count how many wake, then repeat with broadcast.

Done when: 1 of 3 and 3 of 3.

Hint

Let the main thread sleep before it sets the flag, so all three wait.

Medium 3: Run the monitor (30 minutes)

Write the account monitor of section 5. Start three customers who withdraw 50 each and a depositor who deposits 20 ten times. Print the final balance.

Done when: all three get their money and the final balance is 50.

Hint

Broadcast in deposit.

Hard

Hard 1: A one-shot event (60 minutes)

Write an event type with event_set and event_wait using a mutex, a flag and a condition variable, so that any number of threads can wait and one thread sets it. Test with 8 waiters.

Done when: all 8 waiters return, also those that call event_wait after the event was set.

Hint

The flag keeps the memory, so late waiters never sleep.

Hard 2: A barrier (90 minutes)

Write a reusable barrier for n threads with a mutex, a counter and a condition variable. Test with 4 threads over 1,000 rounds.

Done when: in each round, no thread passes before all four have arrived, checked by a shared round counter.

Hint

Use a generation number so that a fast thread cannot rejoin the old round.

Hard 3: Timed wait (60 minutes)

Write a get_with_timeout function for the account monitor that waits for funds for at most 200 ms using pthread_cond_timedwait, and returns an error if the time runs out.

Done when: a test that returns ETIMEDOUT with no deposits, and succeeds when a deposit arrives within 100 ms.

Hint

pthread_cond_timedwait takes the absolute CLOCK_REALTIME time.