Synchronization Inside the Kernel

By the end of this lesson, you will be able to...

• State the invariants that make a shared kernel queue correct.

• Choose when a lock, local interrupt control, and a sleep/wakeup protocol are needed.

• Trace and diagnose a race, a lost wakeup, and a lock-order deadlock.

Idea in one sentence: Kernel synchronization preserves named invariants across threads, CPUs, and interrupt handlers; a lock is useful only when its scope and waiting rules match the state it protects.

A process calls read(pipe, dst, 1) on an empty pipe. On another CPU, a process will soon write one byte; in some kernels, a device-completion interrupt could also make a queue non-empty. The reader must wait without losing that future notification, and the producer must update the ring buffer without racing another producer or consumer.

This is not merely “put a mutex around the array.” The pipe queue has state, ownership, and a condition that changes over time. A correct implementation must make the transition from “I found it empty” to “I am waiting for it to become non-empty” indivisible with respect to the producer. It must also respect the execution context: an interrupt handler cannot wait for a sleeping mutex, and a CPU that only disables its own interrupts has not excluded another CPU.

Core Insight

Start with the object that must remain true. For a pipe with capacity N, head, tail, and used, a compact invariant table is:

Plain meaning: the queue is a shared notebook. A writer cannot erase the reader's place while the reader is recording it, and a reader cannot go to sleep after the writer already left the “new item” note.

Technical meaning: the lock provides mutual exclusion for the shared representation and establishes the synchronization boundary around the invariant. The condition (used == 0 or used == N) is not itself the lock. It must always be tested while holding the state lock, because another execution context can change it immediately after the test.

The naive queue breaks in two different ways

Here is an unsafe producer:

if (pipe.used < N) {
  pipe.data[pipe.tail] = byte;
  pipe.tail = (pipe.tail + 1) % N;
  pipe.used++;
}

Two CPUs can both read used == N - 1, both write the same tail, and both increment used. One byte is overwritten and the count says two bytes arrived. An atomic increment alone would not repair the queue: tail, the data write, and used are one logical transition, not three unrelated counters.

Waiting introduces a second failure:

reader: sees used == 0
producer: adds a byte; calls wakeup(readers)
reader: marks itself asleep

The wakeup finds no published sleeper, so the reader can sleep even though a byte is ready. This lost wakeup is a progress bug, not a queue-capacity bug. Rechecking the condition after every wakeup also matters: a wakeup means “the state may have changed,” not “you now own a byte.” Another reader may consume it first.

Locks, interrupt control, and sleeping solve different boundaries

A small kernel may disable local interrupts while holding a spinlock when the same CPU's interrupt handler could try to acquire that lock. This avoids self-deadlock on that CPU. The lock, not interrupt disabling, is what excludes other CPUs. Conversely, code in interrupt context must not acquire a sleeping lock or block: there is no ordinary task context in which it can safely wait. Linux's locking documentation makes this distinction explicit by separating sleeping, CPU-local, and spinning lock categories.

Worked Trace: one-byte pipe read without a lost wakeup

Assume pipe.used == 0, reader R runs on CPU 0, and writer W runs on CPU 1. The exact function names vary by kernel; the important contract is that publishing the wait state and releasing the condition lock are coordinated.

Input: R requests one byte. The pipe is empty. W will enqueue 0x41 (A).

1. The reader tests the condition while it owns the pipe state

R acquires pipe.lock, observes used == 0, and records that it will wait on the pipe's read condition. It does not release the lock and then separately set itself to sleeping; that gap is the lost-wakeup window.

State: used=0, R=running but preparing to wait, pipe.lock=held by R.

2. The scheduler handoff publishes the wait before allowing the writer in

The wait primitive marks R blocked on the read channel while coordinating with scheduler state, then releases pipe.lock as part of the handoff to the scheduler. Only after the waiter is visible may W acquire pipe.lock.

State transition: R: running -> blocked(readable(pipe)); pipe.lock: R -> free.

This is the key design property. In xv6, sleep(chan, lock) is structured so the process lock is acquired before the condition lock is released; its wakeup path can therefore not miss the published sleeper.

3. The writer performs one protected queue transition

W acquires pipe.lock, writes 0x41 at tail, advances tail, and changes used: 0 -> 1. It marks waiters on the read condition runnable, then releases pipe.lock.

Output/decision: R is runnable, not yet guaranteed to own the byte. The queue has exactly one byte and again satisfies every row of the invariant table.

4. The reader runs again and rechecks

The scheduler later runs R. It reacquires pipe.lock and tests used again. It now dequeues 0x41, advances head, changes used: 1 -> 0, releases the lock, and copies the result across the user-kernel boundary described in lesson 008.

Naive contrast: if step 2 released pipe.lock before publishing R as blocked, step 3 could wake nobody. If step 4 did not recheck, a competing reader could have taken 0x41 and R could consume an empty slot.

Lock Ordering Is a Contract Between Subsystems

One lock can preserve a local invariant; two locks introduce an ordering invariant. Suppose an operation needs both a process record and a pipe:

process.lock -> pipe.lock

Every path that needs both must acquire them in that order. If a cleanup path instead holds pipe.lock and waits for process.lock, while another CPU holds process.lock and waits for pipe.lock, neither can proceed:

CPU 0: holds process.lock, waits for pipe.lock
CPU 1: holds pipe.lock,    waits for process.lock

That is a deadlock cycle, even if each lock works perfectly. Write the lock-order graph next to the object invariants; do not leave it as tribal knowledge. Keep critical sections short, but do not move a required state update outside the lock merely to make the section look short.

There is a real trade-off. One coarse kernel.lock is simple to reason about and may be ideal for a teaching kernel, but it serializes unrelated work. Per-object locks allow more parallelism, but multiply ordering rules, wakeup interactions, and debugging paths. Measure contention before splitting a lock, then preserve the same invariant and lock order in every new path.

Common Confusions

“An atomic counter makes the ring buffer safe.” It protects only that counter's update. The buffer slot, index, count, ownership, and memory visibility must still form one coherent protocol.

“Disabling interrupts is equivalent to a lock.” It constrains local interrupt execution. On a multicore kernel another CPU can still enter the same critical section, so shared state still needs inter-CPU exclusion.

“wakeup means the condition is true.” It means a relevant state transition may have occurred. Conditions are rechecked in a loop while holding the associated lock, because wakeups can be shared, premature, or raced by another consumer.

“Sleeping while holding a spinlock is only a performance issue.” It can deadlock or stall the system: a context that needs the lock to make progress cannot run while the holder is asleep. A sleeping lock may be used only where the execution context permits it.

Check: A timer interrupt on CPU 0 needs to append an event to a queue that a thread on CPU 1 can also modify. Is disabling interrupts only on CPU 1 enough?

Think first, then reveal.

Answer: No. CPU 0 can still execute the interrupt handler concurrently. Use a lock suitable for both contexts; if the CPU holding it can be interrupted by a handler that also takes it, protect that local re-entry according to the kernel's interrupt/lock convention. Do not make the interrupt handler wait on a sleeping mutex.

Check: A reader wakes, acquires pipe.lock, and finds used == 0. Is that evidence that wakeup was incorrect?

Think first, then reveal.

Answer: Not necessarily. Another reader may have consumed the item, or a wakeup may be intentionally broad. The correct consumer loop rechecks the condition and sleeps again if it remains false; the error would be assuming that the notification transfers ownership.

Practice: review a queue boundary

For a bounded queue shared by enqueue, dequeue, and a completion interrupt, produce a one-page design note containing:

1. three representation or ownership invariants;
2. the lock that protects each invariant and whether interrupt context may acquire it;
3. the condition for empty and full waits, including where the waiter becomes visible;
4. a lock-order graph if any path needs two locks; and
5. one sentence naming the cost of your chosen granularity.

Use this rubric:

Resources

• [BOOK] MIT 6.1810 xv6 book, locking and sleep/wakeup — a small-kernel reference for lock invariants and the coordinated sleep/wakeup pattern used in the trace.
• [DOC] MIT 6.1810 coordination reading — points to sleep, wakeup, UART, and pipe code to inspect the lost-wakeup boundary in context.
• [DOC] Linux kernel: lock types and their rules — distinguishes sleeping, CPU-local, and spinning locks and their nesting constraints.

Key Takeaways

1. Synchronization starts with explicit invariants; a lock protects the state transition that keeps them true.
2. The empty-to-sleep transition must be coordinated with wakeup publication, and every wakeup requires a locked condition recheck.
3. Interrupt disabling is CPU-local, while locks coordinate shared multicore state; the chosen primitive must fit its execution context.
4. Fine-grained locking trades contention for a larger lock-order and lifecycle proof.