CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 7 of 7 · 2 min read

Exercises

Easy

Easy 1: Trace values (20 minutes)

A semaphore starts at 2. Give the value and who sleeps after: wait, wait, wait, post, post.

Done when: 1, 0, 0 (third waiter sleeps), then the sleeper wakes and takes the unit (0), then 1.

Hint

A waiter that sleeps takes the unit as soon as a post arrives.

Easy 2: Initial value (20 minutes)

Choose the initial value for: a lock, a pool of 5 printers, a signal that "data is ready".

Done when: 1, 5 and 0.

Hint

A lock needs one unit, a signal needs none until the event.

Easy 3: Invariant (20 minutes)

A semaphore starts at 5, with 8 completed waits and 4 completed posts. Give the value.

Done when: 5 + 4 − 8 = 1.

Hint

The invariant is initial + posts − waits.

Medium

Medium 1: Limit a region (30 minutes)

Write a program in which 8 threads enter a region guarded by a semaphore of 3, hold it for 100 ms, and record the maximum number inside.

Done when: a maximum of 3 and a total time near 0.30 s.

Hint

Count the threads inside with a mutex-protected counter.

Medium 2: Order two threads (30 minutes)

Write two threads in which the second prints "B" only after the first printed "A", using a semaphore at 0. Start the second thread first.

Done when: the output "A" then "B" in every run.

Hint

sem_init(&s, 0, 0).

Medium 3: Write a rendezvous (30 minutes)

Write the two-semaphore rendezvous for 2 threads, with a random sleep before the meeting point. Check that "after" is never printed before both "before" lines.

Done when: 100 runs in which both "before" lines come first.

Hint

Post first, then wait.

Hard

Hard 1: Build a semaphore (60 minutes)

Build z_wait and z_post from a mutex and a condition variable, and test it as a lock with 4 threads and 500,000 rounds each.

Done when: the total of 2,000,000 and a timing against sem_t.

Hint

The loop in z_wait is essential.

Hard 2: Barrier from semaphores (90 minutes)

Build a reusable barrier for n threads from semaphores and a counter, avoiding the problem that a fast thread laps the others.

Done when: 1,000 rounds with 4 threads in which no thread starts round k + 1 before all finish round k.

Hint

Two turnstile semaphores are one known design.

Hard 3: Misuse (60 minutes)

Write a program with a binary semaphore used as a lock and an extra sem_post in an error path. Show that two threads can then be in the critical section together. Fix it with a mutex.

Done when: a run that shows the violation, and the fix that detects it.

Hint

A mutex with the error-checking type reports a wrong unlock.