Readers-writer spinlock implementation for lab locks MIT OCW OS

2026-07-23

Stack Overflow: View Question

Tags: c, gcc, multiprocessing, operating-system, locking

Score: 2 | Views: 112

The asker is working through MIT 6.828/6.S081 and hit the classic "lab locks" exercise: implement a reader-writer spinlock where many readers can share the lock, but a writer needs exclusive access. Conceptually simple, but easy to botch in ways that only show up at high concurrency.

Why this is hard. A textbook RW-lock has three subtleties that beginners rarely appreciate until they hit a race:

Sketch of a direction. The cleanest spinlock RW-lock uses a single int:

#define WRITER_BIT 0x80000000
// low 31 bits = reader count, top bit = writer held

void racquire(rwlock *l) {
  while (1) {
    int v = __atomic_load_n(&l->s, __ATOMIC_RELAXED);
    if (v & WRITER_BIT) continue;             // writer present, spin
    if (__atomic_compare_exchange_n(&l->s, &v, v+1,
        0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
      return;
  }
}

void wacquire(rwlock *l) {
  int zero = 0;
  while (!__atomic_compare_exchange_n(&l->s, &zero, WRITER_BIT,
      0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
    zero = 0;                                  // reset expected
  }
}

Release for readers is __atomic_fetch_sub(&l->s, 1, __ATOMIC_RELEASE); for writers, __atomic_store_n(&l->s, 0, __ATOMIC_RELEASE).

Gotchas. First, disable interrupts around acquire in kernel context — xv6's push_off()/pop_off() — otherwise a timer interrupt can preempt a lock holder and deadlock the same CPU. Second, don't use __sync builtins (deprecated, full-barrier only); use __atomic with explicit orderings so the lab's benchmark actually shows reader parallelism. Third, the lab's grading test spins many readers to prove they can hold concurrently — if your reader path takes an exclusive cache line every time (e.g. one giant global counter), throughput collapses due to cache-line bouncing even though correctness is fine. A per-CPU reader counter with a shared writer flag scales far better if the lab pushes on that.

The challenge: Writing an RW-spinlock that's simultaneously race-free, memory-ordering-correct, starvation-aware, and cache-friendly — four constraints that pull against each other in ways only visible under real contention.

All newsletters