Spinlocks & Race Conditions

Two threads that both add 1 to a shared counter 1,000 times can finish with a total of 1,013, or 2,000, or 1,500. Nothing is "wrong" with either thread. The bug lives in the schedule, and the kernel is full of such shared data (the process table, the run queue, the frame bitmap from earlier lessons). In this lesson your program is a tiny machine that replays an exact interleaving of threads, so you can see a race happen and then see a spinlock remove it.

Why counter++ is not one step

A line that increments a variable compiles to three machine steps:

1. LOAD: copy the counter from memory into a register.
2. INC: add 1 in the register.
3. STORE: write the register back to memory.

Each thread has its own registers, but the memory cell is shared. If thread A loads, then thread B loads, then both increment and store, both wrote the value old + 1: one increment is lost.

Two increments, final value 1. This is a race condition: the outcome depends on the relative timing, which the programmer does not control. It is also non-deterministic in real life, which makes it hard to debug. Here the schedule is part of the input, so it is reproducible.

Mutual exclusion

The three steps must behave as one critical section that only one thread is in at a time. The kernel's basic tool is the spinlock: a flag in memory with two operations.

• acquire: atomically test the flag and set it. If the lock was already held, spin: retry again and again, burning CPU, until it is free.
• release: clear the flag.

"Atomically" is the crux. Reading the flag and then setting it as separate steps would just recreate the race. Hardware provides one indivisible read-modify-write: x86 xchg swaps a register with memory in one bus transaction, and it is implicitly locked. A thread's attempt to acquire either succeeds as a whole or leaves the lock alone.

With the lock, the schedule A, B, A, B... gives B nothing to do while A is inside: every B turn is a failed attempt (a spin), and B proceeds only after A releases.

Rules that make kernel spinlocks safe

• Hold briefly. Spinning wastes a CPU, so a spinlock protects a few instructions, never a disk read. For long waits the kernel uses sleeping locks.
• Interrupts off while holding. If an interrupt handler on the same CPU tries to take a lock its interrupted code already holds, that CPU spins forever against itself. Kernels disable interrupts while a spinlock is held.
• No recursion. A thread that tries to take a lock it already holds would wait for itself. xv6 detects this and panics.
• Only the holder releases. Releasing a lock you do not hold is a bug that would silently let two threads into the critical section.
• Memory ordering. Release and acquire also act as barriers so that the work done inside the critical section is visible to the next holder.

Common mistakes

• Treating the scheduled slot of a blocked thread as progress. A failed acquire does not advance the thread.
• Letting a release by a non-holder change the lock.
• Counting a spin when the acquire actually succeeded.
• Skipping to the thread's next instruction after a failed acquire.

Your exercise

The starter parses the threads and the schedule and prints the result. You write the step function that executes one instruction of one thread.