Part 8 of 8 · 3 min read
Exercises
Easy
Easy 1: Which one is it? (20 minutes)
Classify each case as deadlock, livelock or starvation: (a) two threads asleep, each holding the lock the other wants, (b) two threads running flat out, retrying and failing, (c) one request in a queue is never served while others are.
Done when: three correct labels with a reason each.
Hint
Check processor use first, then whether anyone else makes progress.
Easy 2: Compute the pipe limit (20 minutes)
Pipes hold 65,536 bytes and the child buffer is 8,192 bytes. What is the largest input that the one-sided parent can send without a deadlock?
Done when: 65,536 + 8,192 + 65,536 = 139,264 bytes.
Hint
Add the capacity of both pipes and the buffer of the child.
Easy 3: Priority inversion in words (20 minutes)
Describe priority inversion in three sentences, naming the three threads and what each does.
Done when: a description that includes L, M and H, and says who waits for whom.
Hint
The medium thread does not need the lock, and still makes the high one wait.
Medium
Medium 1: Reproduce the livelock (45 minutes)
Write the two-thread trylock program with an immediate retry and with a random pause. Run each for 3 s three times and count the completed operations.
Done when: a table with the two rules and six counts, with the random version far ahead.
Hint
Use rand_r with a seed for each thread.
Medium 2: Reproduce priority inversion (45 minutes)
Write the three-thread test with SCHED_FIFO, pinned to one processor with sched_setaffinity. Run it with a normal mutex and with PTHREAD_PRIO_INHERIT.
Done when: the waiting time of H in both runs, with the inheritance run under 0.3 s.
Hint
Run as root, set the main thread to SCHED_FIFO with the highest priority, and measure with CLOCK_THREAD_CPUTIME_ID for the work loops.
Medium 3: Find the pipe limit (45 minutes)
Write the echo child and the one-sided parent. Run it with a timeout for sizes from 1 KB to 200 KB, and use a binary search to find the largest size that completes.
Done when: a number equal to twice the pipe size plus the child buffer size.
Hint
A hang shows as timeout returning 124.
Hard
Hard 1: Fix the pipe program (60 minutes)
Change the parent so that it uses poll to write and read at the same time. Test with 10 MB.
Done when: the 10 MB run completes with all bytes echoed.
Hint
Use a non-blocking write and POLLOUT, and read whenever POLLIN is set.
Hard 2: Make fork safe (60 minutes)
Reproduce the fork deadlock. Then fix it with pthread_atfork: take the mutex in the prepare handler and release it in the parent and child handlers.
Done when: the child gets the lock at once, in a run with the helper thread holding it at the time of the fork.
Hint
The prepare handler runs in the parent before the fork.
Hard 3: Safe signal handling (90 minutes)
Reproduce the signal-handler deadlock. Then fix it with a flag set in the handler, and the real work done in the main loop. Show that the lock is taken by the main loop with no hang.
Done when: a run in which the alarm is handled within 1.1 s and the program ends normally.
Hint
Declare the flag as volatile sig_atomic_t.