Concurrency Control

Concurrency refers to situations where multiple instruction streams are interleaved. In xv6, it arises from three sources:

Multiprocessor hardware: multiple CPUs sharing physical RAM and executing independently.
Thread switching: the kernel switching a single CPU among threads.
Interrupts: a device interrupt handler running alongside interruptible code that touches the same data.

Any of these can leave a data structure in a broken state if accesses are not carefully controlled. Strategies for correctness under concurrency are called concurrency control techniques; xv6 uses several, but this chapter focuses on the lock. A lock provides mutual exclusion: only one CPU at a time can hold it, so data guarded by a lock is never accessed by more than one CPU simultaneously. The downside is performance; locks serialize concurrent operations, reducing parallelism.

Race Conditions

A race condition occurs when a memory location is accessed concurrently and at least one access is a write. The outcome is either a lost update or a read of an incompletely-updated structure, and it depends entirely on the exact timing of the CPUs involved, making races notoriously hard to reproduce and debug. A print statement added during debugging can shift timing enough to make the race disappear entirely.

The motivating example: two processes call wait on different CPUs, each calling kfree to free child pages and push them onto the shared free list. Without locks, both CPUs read the current list head into l->next before either writes the new head back. The second write to list overwrites the first; one element is permanently lost.

Both CPUs execute l->next = list simultaneously against shared memory over the bus.

CPU1 and CPU2 both complete line 15 before either executes line 16, causing the lost update.

The fix is wrapping the sensitive lines in acquire/release:

acquire(&listlock);
l->next = list;
list = l;
release(&listlock);

The instructions between acquire and release form a critical section. A lock protects not just data but the data’s invariants, which are properties that must hold across operations. For the linked list, the invariant is that list points to the first element and each next points to the next element.

The insertion temporarily violates this invariant before completing, so the lock ensures no other CPU observes the structure during that window. Critical sections guarded by the same lock are atomic with respect to each other, so each sees only complete updates, never partial ones.

Locks limit performance because they serialize operations that could otherwise run in parallel:

Two processes calling kfree concurrently must now take turns, yielding no benefit from running on separate CPUs.
Multiple processes competing for the same lock is called lock contention; avoiding it is a major kernel design challenge.
To reduce contention on a global free list, a kernel can maintain a per-CPU free list and steal from another CPU’s list only when the local one is empty.
Lock placement matters too: moving acquire to before malloc inside push is correct but serializes the allocation itself, adding unnecessary overhead outside the critical section.

Spinlocks

A spinlock has a single locked field: zero when available, non-zero when held. The naive implementation, checking whether the lock is free and then claiming it, fails on multiprocessors because two CPUs can both observe it as free simultaneously and both proceed to take it. The check and the claim must happen as a single atomic step.

RISC-V provides an atomic swap instruction that reads a memory location, writes a new value to it, and returns what was there, all indivisibly. xv6 uses this to implement both operations:

acquire loops, repeatedly swapping 1 into the lock and inspecting the old value. A returned 0 means the lock was free and is now held; a returned 1 means another CPU holds it, so the loop retries.
release uses the same atomic mechanism to write 0 back. A plain assignment cannot be trusted here because the compiler is free to implement it as multiple stores.

Lock Granularity

Two basic rules govern where locks are necessary:

Any variable that can be written by one CPU while another CPU can read or write it must be protected by a lock.
Locks protect invariants: if an invariant spans multiple memory locations, all of them typically need a single lock to keep the invariant intact.

These rules say when locks are necessary, not when to omit them. Locking too much reduces parallelism. At the extreme, a single “big kernel lock” acquired on kernel entry and released on exit is correct but allows only one CPU in the kernel at a time. Many uniprocessor OSes were ported to multiprocessors this way, but it sacrifices all parallel execution. Granularity decisions must ultimately be driven by performance measurements alongside complexity considerations.

The trade-off plays out concretely in xv6:

Coarse-grained: a single lock over the entire free list means CPUs allocating simultaneously must take turns, wasting cycles. Per-CPU free lists with their own locks would allow truly parallel allocation.
Fine-grained: each file gets its own lock, so processes working on different files rarely contend. This could go further with per-region locks within a file, but complexity grows with granularity.

Deadlock

Deadlock occurs when two code paths each hold a lock the other needs. If

path 1 acquires locks A then B, and
path 2 acquires B then A, then
a thread holding A waiting for B will block forever against a thread holding B waiting for A. The solution is for all code paths to acquire locks in the same global order. This means lock ordering is effectively part of each function’s specification: callers must invoke functions in a way that respects the agreed order.

xv6 has several concrete ordering rules:

cons.lock must be acquired before any process lock, because consoleintr holds cons.lock while calling wakeup, which in turn acquires the waiting process’s lock.
Creating a file requires holding a directory lock, the new inode’s lock, a disk block buffer lock, the disk driver lock, and the calling process’s lock, always acquired in that order.

Lock	Purpose
`bcache.lock`	Allocation of block buffer cache entries
`cons.lock`	Serializes console hardware access, avoids intermixed output
`ftable.lock`	Allocation of file structs in the file table
`itable.lock`	Allocation of in-memory inode entries
`vdisk_lock`	Disk hardware access and DMA descriptor queue
`kmem.lock`	Memory allocation
`log.lock`	Transaction log operations
`pi->lock`	Operations on each pipe
`pid_lock`	Incrementing the next PID
`p->lock`	Changes to a process’s state
`wait_lock`	Avoiding lost wakeups in wait
`tickslock`	Operations on the ticks counter
`ip->lock`	Operations on each inode and its content
`b->lock`	Operations on each block buffer

In practice, global lock ordering is harder to maintain than it sounds. It can conflict with program structure, require knowledge of lock identities that are only discovered at runtime, and grows more difficult as locking becomes finer-grained. Re-entrant locks might seem like a way around some of these problems, but they break the atomicity intuition by allowing a function to enter a critical section that another invocation is still inside, causing silent errors. A deadlock, by contrast, panics the kernel and forces the developer to address the root problem. xv6 uses non-re-entrant locks for this reason.

Interrupt Handlers

Some spinlocks protect data accessed by both kernel threads and interrupt handlers. tickslock, for example, serializes access to ticks between the timer interrupt handler and sys_sleep (the kernel implementation of the sleep system call). This creates a deadlock risk:

sys_sleep (the kernel implementation of the sleep system call) acquires tickslock.
The timer interrupt fires on the same CPU.
The interrupt handler tries to acquire tickslock, finds it held, and spins.
sys_sleep cannot resume until the handler returns, but the handler cannot return until it acquires the lock. The CPU deadlocks permanently.

The fix is to never hold a spinlock while interrupts are enabled on the same CPU. xv6 takes a conservative approach: it disables interrupts whenever any lock is acquired, not just locks shared with interrupt handlers. Interrupts may still fire on other CPUs, so a handler on another CPU can safely wait to acquire a spinlock held by a thread.

xv6 uses push_off and pop_off to handle nested critical sections correctly:

push_off disables interrupts and increments a per-CPU nesting count.
pop_off decrements the count and restores interrupts only when it reaches zero, returning to the state that existed before the outermost lock was acquired.

The ordering is strict: push_off must execute before the lock is claimed, and pop_off must execute only after the lock is fully released. Either reversal creates a brief window where the lock is held with interrupts enabled, which can deadlock the system.

Memory Ordering

CPUs and compilers routinely reorder instructions to improve performance. Both follow rules that preserve correctness for serial code, but those rules permit reorderings that break concurrent code. The CPU’s set of ordering rules is called the memory model.

For locking, the danger is a store inside a critical section being moved to after the lock release. Consider this insertion:

l = malloc(sizeof *l);
l->data = data;
acquire(&listlock);
l->next = list;
list = l;
release(&listlock);

If the compiler moved line 4 to after release, another CPU could acquire the lock, observe the updated list, but find l->next still uninitialized. To prevent this, xv6 places a memory barrier (__sync_synchronize()) in both acquire and release. A memory barrier tells the compiler and CPU not to reorder loads or stores across it, ensuring all writes inside a critical section are visible to other CPUs before the lock is released.

Sleep-locks

Spinlocks are unsuitable for long-held operations. The file system keeps a file locked while reading and writing to disk, which can take tens of milliseconds. Two properties of spinlocks make this problematic:

Waiting processes can only spin, wasting CPU time for the entire duration.
A process cannot yield the CPU while holding a spinlock: a second thread trying to acquire the same lock would spin forever since the first cannot be rescheduled to release it, and yielding would also violate the interrupt-disable requirement.

Sleep-locks solve this by yielding the CPU while waiting to acquire, and allowing yields and interrupts while held. Internally, a sleep-lock wraps a locked field with a spinlock; when a thread tries to acquire a held sleep-lock, it atomically yields the CPU and releases the internal spinlock, letting other threads run in the meantime.

The different behaviour of sleep-locks comes with restrictions:

Sleep-locks cannot be used inside interrupt handlers, since interrupts are enabled while they are held.
Sleep-locks cannot be used inside spinlock critical sections, since they may yield the CPU.
Spinlocks can be used inside sleep-lock critical sections.

In short, spinlocks suit short critical sections where brief spinning is acceptable. Sleep-locks suit lengthy operations where holding the CPU would be wasteful.

Concurrency Patterns

Xv6 also uses a few synchronization patterns that are broader than a single acquire/release pair. The common theme is that each shared object needs protection for both its current contents and its lifetime.

The buffer cache combines a global lock for cache membership with per-buffer sleep-locks for block contents.
Reference counts in files, inodes, buffers, and pipes keep objects alive while other code still holds pointers to them.
Pathname lookup uses inode references as temporary shared ownership, avoiding deadlock from holding exclusive inode locks across . and .. traversal.
Some handoffs cross function or CPU boundaries: yield acquires a process lock that the scheduler later releases.
Some data is protected by ownership rather than a lock, such as user pages owned by one process after allocation.
Interrupt disabling protects CPU-local assumptions, especially in code like mycpu() where a timer interrupt could otherwise move the running process to another CPU.

These patterns improve correctness without turning the whole kernel into one giant critical section, but they also make performance depend on lock granularity and contention. Pipes scale well because each pipe has its own lock; process creation and scheduling contend more because they touch shared structures like pid_lock, kmem.lock, and the process table.

Real World

Programming with locks remains challenging despite years of research. It is generally best to hide locks inside higher-level constructs like synchronized queues, though xv6 does not do this. Using a tool that identifies race conditions is also wise, since missing a required lock is easy.

Most operating systems support POSIX threads (Pthreads), which allow a user process to run multiple threads concurrently across CPUs. Pthreads provides user-level locks, barriers, and optionally re-entrant locks. Pthreads support requires cooperation from the kernel:

If one thread blocks in a system call, another thread of the same process should be able to run on that CPU.
If a thread changes the process’s address space, the kernel must update the hardware page tables on all CPUs running threads of that process.

Lock performance degrades significantly under high contention. When multiple CPUs compete for the same lock, the atomic instruction that claims it must transfer the relevant cache line between CPU caches, potentially invalidating other copies. A cache line fetched from another CPU’s cache can be orders of magnitude more expensive than one from local cache.

To avoid this overhead, many operating systems use lock-free data structures and algorithms. A linked list, for example, can support searches with no locking and insertions with a single atomic instruction. Lock-free programming is more complex than lock-based programming, however, since instruction and memory reordering must be managed manually. xv6 avoids it for that reason.

My Knowledge Base

Explorer

10 Synchronization