Skip to main content

Race Condition and Locking Clinic

Retrieval Prompts​

  1. State, from memory, the three correctness properties of the critical-section problem.
  2. Describe the load-modify-store decomposition of counter++ in pseudo-assembly.
  3. Name the hardware primitives that make correct locks possible (TAS, CAS, LL/SC, fetch-add).
  4. State the two reasons a ticket lock is fairer than a TAS spinlock.
  5. Write, in one line, when a spinlock is preferable to a blocking mutex and when the reverse holds.

Compare and Distinguish​

Separate these pairs clearly in your own words:

  • a data race versus a race condition (hint: every data race is a race condition; not every race condition is a data race)
  • mutual exclusion versus bounded waiting
  • a spinlock versus a blocking mutex under a short critical section with preemptible holders
  • coarse-grained versus fine-grained locking with regard to correctness obligations
  • volatile (in C/C++) versus _Atomic / std::atomic

Common Mistake Check​

For each statement, identify the error and give the fix:

  1. "Reading a shared int is atomic, so I can read it without a lock while another thread writes it."
  2. "The test suite passed 1000 times; therefore the code has no race."
  3. "I used if (!predicate) cond_wait(&cv, &m); because the signaler just woke someone, so the predicate must be true."
  4. "My critical section is a single instruction, so I don't need a lock."
  5. "I only use spinlocks because they don't do a syscall, so they're always faster."

Mini Application​

For each scenario, do all four:

  1. identify the shared state
  2. identify the critical section and the invariant it must preserve
  3. write the smallest interleaving that breaks the invariant under no synchronization
  4. write the smallest fix using pthread mutex / condvar / atomics

Scenarios:

  1. A reference-counted object where multiple threads can call acquire() (increment) and release() (decrement, free at zero).
  2. A global bool ready = false; int data; where one thread writes data, then sets ready = true, and other threads spin on ready before reading data.
  3. A hash table that supports get, put, and delete, with 90% reads and 10% writes in the workload.
  4. A linked list where threads can insert at the head and scan front-to-back.

Evidence Check​

This page is complete only if, for each scenario above, you can:

  • exhibit a concrete interleaving (with a table like the one in concept 1)
  • name the Coffman/critical-section property at stake
  • point at the specific pthread primitive or atomic operation you used and justify the memory ordering