Part 7 of 7 · 2 min read
Exercises
Easy
Easy 1: Return values (20 minutes)
x is 4. Give the new value of x and the returned value for fetch_add(&x, 3), test_and_set(&x, 1) and cas(&x, 4, 9), each from x = 4.
Done when: (7, returns 4), (1, returns 4), (9, returns success).
Hint
fetch_add and test_and_set return the old value.
Easy 2: Trace a spinlock (20 minutes)
Two threads A and B call spin_lock at the same moment on a free lock. Write the first three exchanges and say who enters.
Done when: one exchange returns 0 (that thread enters) and the other returns 1.
Hint
The exchange is atomic, so only one sees 0.
Easy 3: Which requirement? (20 minutes)
Say which of mutual exclusion, progress and bounded waiting a plain spinlock lacks, and which a ticket lock adds.
Done when: bounded waiting is lacking and the ticket lock adds it.
Hint
A plain spinlock lets any waiter win.
Medium
Medium 1: Trace CAS (30 minutes)
Three threads each do one CAS increment on a counter at 10, in the order A reads, B reads, C reads, A CASes, B CASes, C CASes. Give the results and the final value.
Done when: A succeeds (11), B and C fail, and after their retries the final value is 13.
Hint
A failed CAS rereads and retries.
Medium 2: Write a spinlock counter (30 minutes)
Write the spinlock and use it around counter++ for two threads and a million increments each. Report the total and the time over five runs.
Done when: exactly 2,000,000 each time, and five timings.
Hint
Use __atomic_exchange_n and __atomic_store_n.
Medium 3: Lock-free counter (30 minutes)
Write the CAS counter with 4 threads, and compare its time with __atomic_fetch_add and with a mutex.
Done when: a table of three timings, all giving 4,000,000.
Hint
Use __atomic_compare_exchange_n in a do loop.
Hard
Hard 1: Reproduce the table (60 minutes)
Build the benchmark of section 4 for atomic add, spinlock, mutex and yielding spinlock, with 2, 4 and 8 threads. Report the median of five runs.
Done when: a table with the same pattern: the spinlock slows sharply when threads exceed processors.
Hint
Use clock_gettime and sort the five times.
Hard 2: Add a backoff (60 minutes)
Change the spinlock so that a failed attempt waits a growing number of loop steps before retrying. Compare the time on 8 threads with the plain spinlock.
Done when: a measured comparison with a one-paragraph explanation of the effect.
Hint
Double the delay after each failure, up to a limit.
Hard 3: The ABA problem (60 minutes)
Describe a lock-free stack that pops by CAS on the head pointer, and construct a sequence of three operations by two threads in which the CAS succeeds but the stack is corrupted.
Done when: a numbered sequence that frees a node and reuses its address, with the corruption explained.
Hint
Pop A, pop B, push A back: the head looks unchanged.