CSE Roadmap

Core tier · about 5 hours · 7 parts

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.