Synchronization

A kernel’s own data structures, run queues, memory allocators, device driver state, are shared between however many contexts might touch them at once: an interrupt handler running on the same CPU that just preempted ordinary kernel code, or, on a multiprocessor system, entirely different CPUs executing kernel code simultaneously. Without something enforcing exclusive access, two of these contexts modifying the same structure at overlapping moments corrupts it in ways that are hard to reproduce and harder to diagnose, since the resulting failure often shows up far from, and long after, the actual conflicting access.

A concrete race

Consider a run queue implemented as a singly linked list, with enqueue inserting a task at the head:

void enqueue(struct task *t) {
    t->next = run_queue_head;
    run_queue_head = t;
}

If an interrupt fires between the two lines above, and the interrupt handler itself calls enqueue on some other task, the original call resumes afterward and overwrites run_queue_head with a pointer built from a now-stale value, silently dropping whatever the interrupt handler had just inserted from the list entirely. On a single CPU, this specific example is preventable just by disabling interrupts around the two lines; on a multiprocessor system, a second CPU running enqueue concurrently on a genuinely different instruction stream produces the identical corruption, and disabling interrupts on the first CPU does nothing to stop the second CPU from running at the same time.

Disabling interrupts

Disabling interrupts (the cli instruction on x86, paired with sti to re-enable them) prevents an interrupt handler on the same CPU from running during a critical section, making it sufficient by itself for protecting data that only ordinary kernel code and interrupt handlers on a single CPU ever touch. It is not free: while interrupts are disabled, the CPU cannot respond to hardware events at all, including the timer interrupt that would otherwise trigger a scheduling decision, so a critical section protected this way needs to stay short or it measurably delays interrupt handling elsewhere in the system, timer ticks included. It’s also entirely useless on its own against a second CPU running the same code path concurrently, since disabling interrupts is a per-CPU operation with no effect on any other core.

Spinlocks

A spinlock extends interrupt disabling to the multiprocessor case with a shared flag that every CPU checks before entering a critical section, busy-waiting (spinning) in a tight loop until the flag is clear rather than doing anything else while it waits:

void spin_lock(volatile int *lock) {
    while (__sync_lock_test_and_set(lock, 1)) {
        while (*lock) { /* spin */ }
    }
}

void spin_unlock(volatile int *lock) {
    __sync_lock_release(lock);
}

The inner spin loop, reading the lock without attempting to acquire it on every iteration, exists specifically to avoid hammering the atomic test-and-set instruction itself while waiting, since that instruction typically requires exclusive ownership of the relevant cache line and repeatedly requesting it from every spinning CPU generates cache-coherency traffic that measurably slows down the CPU that actually holds the lock and is trying to release it. A spinlock intended to also protect against a same-CPU interrupt handler needs to disable interrupts for the duration it’s held, not just perform the atomic operation, since spinning with interrupts still enabled can deadlock a CPU against itself if an interrupt fires on that same core and its handler then also tries to acquire the same already-held lock.

Mutexes and semaphores

Spinning is only sensible when a lock is expected to be held briefly; a lock protecting a section that might block on disk I/O or wait an unbounded amount of time is better served by a mutex, which puts a waiting task to sleep instead of burning CPU time in a loop, waking it again once the lock becomes available. This requires the mutex to interact with the scheduler directly: acquiring an already-held mutex removes the calling task from the run queue and places it on a wait queue associated with that mutex, and releasing the mutex moves one waiting task (or, depending on design, all of them, to re-contend for it) back onto the run queue. A semaphore generalizes this same wait-queue mechanism to a counter rather than a single binary held/free state, allowing up to some fixed number of holders at once rather than exactly one, useful for protecting a pool of a fixed number of interchangeable resources, such as a fixed set of buffers, rather than a single exclusive-access data structure. On a system where tasks also carry scheduling priority, a mutex’s wait queue introduces a problem beyond ordinary contention: a low-priority holder can indirectly stall a high-priority waiter, the subject of priority inversion.

Atomic operations and the LOCK prefix

Both spinlocks and the compare-and-swap operations mutexes are commonly built on ultimately depend on the CPU providing an operation that is indivisible even under concurrent execution from another core, since an ordinary read-modify-write sequence built from separate instructions has exactly the same race condition problem as the enqueue example above, just at a smaller scale. On x86, the LOCK prefix applied to certain instructions (CMPXCHG, XADD, XCHG among them) asserts exclusive ownership of the relevant memory location’s cache line for the duration of that single instruction, guaranteeing no other CPU’s access to the same location can interleave with it. CMPXCHG in particular, compare-and-swap, is the building block most higher-level lock-free algorithms are built from: it compares a memory location against an expected value and only writes a new value if the comparison succeeds, letting software detect and retry when another CPU modified the location first rather than blindly overwriting whatever is there.

Memory ordering

A CPU and compiler are both free to reorder memory accesses that don’t have an observable data dependency on each other, an optimization that’s invisible to single-threaded code but can break an algorithm relying on one CPU’s writes becoming visible to another CPU in a specific order. A memory barrier (mfence on x86, or narrower lfence/sfence variants for load-only or store-only ordering) forces all memory accesses before it in program order to complete, and become visible to other CPUs, before any access after it proceeds. Most lock and atomic-operation implementations already include the necessary barriers as part of the operation itself, which is why code built entirely from locks and atomics rarely needs explicit barriers of its own; hand-rolled lock-free code that reads and writes shared state without going through either is where missing barriers most often produce bugs that are timing-dependent and close to impossible to reproduce reliably.

Implementation notes

A spinlock held across a call that itself blocks, or across a page fault serviced by code that expects to sleep, can deadlock the entire system rather than just the two contending CPUs, since every other CPU spinning on that lock has no way to know the holder isn’t merely slow but is waiting on something that will never resolve while the lock is held; this is why kernel code holding a spinlock is conventionally required to avoid anything that might sleep for the section’s entire duration. Acquiring multiple locks in inconsistent order across different code paths is the classic cause of deadlock even without any single lock being held too long: if one path acquires lock A then lock B while another acquires B then A, the two can each end up holding one lock while waiting for the other, indefinitely, and the usual discipline avoiding this is a single fixed global ordering that every code path acquiring more than one lock must follow.

References

^ Intel, Intel 64 and IA-32 Architectures Software Developer’s Manual, volume 3, section on locked atomic operations (defines the LOCK prefix and which instructions accept it)
^ Linux kernel documentation, “Linux Kernel Memory Barriers” (a detailed treatment of memory ordering from a real kernel’s perspective)

Synchronization

A concrete race

Disabling interrupts

Spinlocks

Mutexes and semaphores

Atomic operations and the LOCK prefix

Memory ordering

Implementation notes

References

See also