Skip to main content

Code Katas

Focused, repeatable coding exercises designed to build fluency in concurrent programming. Complete each kata multiple times until the pattern feels automatic. Work in C + pthreads unless specified; port to another language only after you can do the C version cold.

Kata 1: Thread-Safe Bounded Queue​

Time limit: 20 minutes
Goal: Implement a bounded FIFO queue of integers with a fixed capacity, accessed concurrently by multiple producers and consumers.
Setup: One mutex, two condition variables (not_full, not_empty). Blocking put and get. Capacity N chosen at construction.

Implementation checklist:

  • while-loop predicate check on both put and get
  • state updates and signal inside the mutex
  • no dynamic allocation inside the critical section
  • correct modular indexing

Validation: run 4 producers and 4 consumers at 100,000 ops each with a capacity of 16. Final state must show items_produced == items_consumed and no wrong values (use a per-thread counter sum check).

Repeat until: You can write the full 50 lines from memory and explain why while, not if, and why two condvars, not one.

Kata 2: Readers-Writers with Starvation Analysis​

Time limit: 25 minutes
Goal: Implement three variants of a readers-writers lock and characterize their starvation behavior empirically.
Setup: Shared integer counter. 10 reader threads each doing 10,000 reads with a 10 us read critical section. 1 writer thread doing 1,000 writes with a 100 us write critical section.

Variants:

  1. Reader-preferring (concept 11 reference).
  2. Writer-preferring.
  3. FIFO fair.

Instrument each with:

  • total throughput (ops/second)
  • writer latency distribution (min, p50, p99, max)

Then write one paragraph per variant: who starves, why, and under what workload each is correct.

Repeat until: You can explain the three waits-for graphs and the cost of each fairness choice without looking at the concept page.

Kata 3: Deadlock Demo and Prevention​

Time limit: 20 minutes
Goal: Produce a deterministic deadlock and fix it with a Coffman-based prevention strategy.
Setup: Two pthread_mutex_t called m1 and m2, and two worker functions: worker_a locks m1 then m2; worker_b locks m2 then m1. Between the two lock acquisitions, each worker sleeps 10 ms to make the race deterministic.

Tasks:

  1. Run two threads (one worker_a, one worker_b). Confirm the program hangs.
  2. Add a diagnostic: every 1 s, print which mutex each thread is waiting on. Capture the cycle.
  3. Apply the ordering fix: sort the mutex addresses and always acquire the lower address first. Show that the program now terminates.
  4. In a second version, use pthread_mutex_trylock + rollback + randomized backoff. Note when this livelocks and why the randomized part matters.
  5. Write a two-sentence analysis naming the Coffman condition broken by each fix.

Repeat until: You can write the deadlock-prone version and both fixes from memory, and can explain why trylock alone is not sufficient.

Kata 4: Lock-Free Stack (Treiber)​

Time limit: 25 minutes
Goal: Implement a lock-free stack using CAS and reason about ABA.
Setup: Use C11 <stdatomic.h> or GCC __atomic_* builtins. Define a node_t { int val; node_t *next; } and an _Atomic(node_t *) top.

Implementation:

  • push(v): allocate node, CAS-loop setting top = n with n->next = old_top.
  • pop(): CAS-loop reading top, setting top = top->next. Do not free the popped node yet (see analysis).

Tests:

  • 8 threads each pushing 100,000 values and popping 100,000 values. Stress for 10 seconds.
  • Run with ThreadSanitizer (-fsanitize=thread). Confirm no reported race.

Analysis:

  • Construct a 4-thread schedule that exhibits ABA. Describe it in comments.
  • Describe two mitigations: tagged pointers (requires double-word CAS) and hazard pointers. Do not implement hazard pointers; describe the algorithm in pseudocode.

Repeat until: You can write the push and pop CAS loops from memory, name the correct memory orderings (release on push store, acquire on pop load), and produce an ABA schedule on demand.

Completion Standard​

  • Can complete each kata within its time limit
  • Can explain the core technique being practiced without looking at the concept page
  • Can write a correct interleaving that would break each naive version
  • Kata 1 and 2 run clean under ThreadSanitizer
  • Kata 3 has both a working deadlock and a working prevention fix
  • Kata 4 includes an ABA trace in the comments