Part 7 of 7 · 2 min read
Exercises
Easy
Easy 1: Return values (20 minutes)
A default mutex is held by thread A. Give the result of pthread_mutex_trylock in thread B, and after A unlocks.
Done when: EBUSY while A holds it, and 0 (lock taken) after A unlocks.
Hint
trylock never waits.
Easy 2: Choose the lock (20 minutes)
A critical section takes 50 nanoseconds and the holder cannot be preempted. Another takes 5 milliseconds and does disk I/O. Pick spinlock or mutex for each.
Done when: spinlock for the first and mutex for the second, with the reasons.
Hint
Compare the wait with the cost of a context switch.
Easy 3: State trace (20 minutes)
Give the futex state after each of: A locks a free mutex; B tries and sleeps; A unlocks.
Done when: 1, 2, 0 (then B wakes and sets 2).
Hint
The unlock sees 2 and wakes a thread.
Medium
Medium 1: Fix the bug (30 minutes)
A function locks a mutex, then returns early with an error without unlocking. Rewrite it with one exit point.
Done when: a version that unlocks on every path.
Hint
Set a result variable, jump to the end, and unlock there.
Medium 2: Recursive or not (30 minutes)
Write a program with a function f that locks a mutex and calls g, which also locks it. Run it with the default type, the error-checking type and the recursive type.
Done when: a hang (or timeout) for the default type, EDEADLK for error-checking, and success for recursive.
Hint
Use pthread_mutexattr_settype.
Medium 3: Count the system calls (30 minutes)
Run a mutex counter program with 1, 2 and 4 threads under strace -f -c -e trace=futex. Report the number of futex calls for each.
Done when: a table that shows few calls for one thread and many more for four.
Hint
strace -f follows the threads.
Hard
Hard 1: Write the futex mutex (90 minutes)
Implement the three-state mutex of section 3 with syscall(SYS_futex, ...). Test it with 4 threads and a million increments each.
Done when: the exact total 4,000,000 in ten runs, and a timing against pthread_mutex_t.
Hint
FUTEX_WAIT_PRIVATE and FUTEX_WAKE_PRIVATE are for one process.
Hard 2: Show the waiting cost (60 minutes)
Repeat the experiment of section 2 (holder sleeps 300 ms) for a spinlock and a mutex, measuring the waiter's CPU time with getrusage(RUSAGE_THREAD).
Done when: about 0 ms for the mutex and about 260 ms for the spinlock.
Hint
RUSAGE_THREAD gives the calling thread's own usage.
Hard 3: Deadlock by hand (60 minutes)
Write the transfer function without ordering, with two threads that transfer in opposite directions in a loop. Show that it hangs, and then fix it with the address order.
Done when: a run that hangs, and a run of 1,000,000 transfers with the fix.
Hint
Use a short loop and a timeout to detect the hang.