Spinlocks & Race Conditions

Everything this course has built so far ran one step at a time. Real kernels don't get that luxury: the timer fires mid-function, another CPU core runs the same code simultaneously, an interrupt handler touches the list you were walking. Concurrency is not an add-on in a kernel — it's the weather. This lesson is about the bug it causes and the primitive that tames it.

The race, concretely

Two threads both run counter++ — which compiles to three steps: load, add, store. Interleave them badly:

T1: load counter (5)
T2: load counter (5)      ← T2 read before T1 wrote
T1: store 6
T2: store 6               ← should be 7. One increment vanished.

That's a race condition: correctness depends on timing you don't control. Races are the worst bug class in systems code because they're probabilistic — the interleaving above might happen once per million runs, always in production, never under the debugger. The kernel's scheduler and multiple cores manufacture interleavings around the clock; any shared, mutable state touched without coordination will eventually be corrupted. Not might — will.

Critical sections and mutual exclusion

The fix is structural: identify the critical section — the multi-step operation that must not interleave — and guarantee only one thread runs it at a time. The guarantee-maker is a lock: acquire before entering, release on exit, and the acquire operation itself must be atomic (hardware provides indivisible test-and-set / compare-and-swap instructions precisely for this — the one thing software alone cannot build).

The spinlock

The kernel's most primitive lock does the bluntest possible thing while waiting: it spins —

acquire(lock):  while atomic_test_and_set(lock) == was_already_held: keep trying
release(lock):  atomic_clear(lock)

Burning CPU in a retry loop sounds wasteful — and for long waits, it is (that's what blocking locks/mutexes are for: put the thread to sleep, wake it on release — using the scheduler machinery from this chapter). Spinlocks win in exactly the kernel's home conditions:

• Critical sections are tiny (update a list pointer, tweak a counter) — a few dozen cycles. Sleeping and waking costs a context switch — microseconds, thousands of times the wait. Spinning briefly is cheaper than napping.
• Some contexts can't sleep. An interrupt handler (Interrupts lesson) has no thread identity to put to sleep — spinlocks are its only lock. This single fact shapes swaths of kernel design.

Fairness is the refinement: a naive spinlock lets whoever's test-and-set lands first win — under contention, the same lucky CPU can win repeatedly while others starve. Real kernels use ticket locks or queue-based locks: waiters take a number and are served FIFO. Your exercise's semantics are exactly that — an ordered wait queue with handoff on release.

The bug taxonomy your simulator enforces

• Unlock by a non-holder — either a code path releasing a lock it never took, or a double-release. Real spinlocks often don't check (they're too cheap to afford it — corruption just happens); debug kernels do, loudly. Your checker is the debug kernel: ERR.
• Handoff correctness — on release with waiters, exactly one waiter (the first!) acquires, immediately. No thundering herd, no skipped queue positions.
• And the one your simulator doesn't cover, worth naming so you know it exists: deadlock — T1 holds A wants B, T2 holds B wants A, both spin forever. The kernel-wide defense is a global lock ordering (always take A before B, everywhere); violating it is how kernels hang. That discipline gets its own treatment when your locks start nesting.

Your exercise: Lock Interleaving Checker

Feed events, maintain per-lock holder + FIFO queue, emit ACQ / WAIT / REL / ERR — including the immediate handoff ACQ after a release with waiters. The graded edges: FIFO order among multiple waiters, ERR leaving state untouched, independent locks not interfering, and the handoff appearing on its own line at the right moment. It's forty lines of bookkeeping that make the invisible visible: after this, "who holds what, who's waiting" is a table in your head — which is precisely the mental model concurrent code is debugged with.