CSE Roadmap

Core tier · about 5 hours · 7 parts

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.