xv6 §12, "Concurrency revisited". "Simultaneously obtaining good parallel performance, correctness despite concurrency, and understandable code is a big challenge in kernel design."
Phase 12 returns to the virtqueues that Phase 5 introduced (5.4–5.6) and Phase 9 made event-driven (9.4), and changes them in place. A virtqueue is a ring of buffer descriptors shared by one producer and one consumer. With the right memory ordering it needs no lock. Phase 12 removes those locks and spreads device work across CPUs. Hailperin §4.8 gives the reason: a lock holder that is preempted blocks everyone waiting for the lock, which leads to priority inversion and convoys. The phase starts from Phase 7's locks and barriers and Phase 8's per-CPU scheduler. It ends with fewer locks than it started with.
Provisional slices. Each is refined, with its quoted sentence, when the phase starts.
Slices
12.1 Lock-free virtqueues. This slice rewrites the split-ring virtqueue from 5.4–5.6 and 9.4 so that it takes no lock. The ring is written only by its producer and read only by its consumer, with explicit memory barriers (from 7.4) ordering the index updates. Specs model the possible interleavings of producer and consumer and check that no buffer is lost or seen twice. Its passage is xv6 §12.3 ("No locks at all"). It comes first because every other slice in the phase relies on queues that no longer block. Removing the lock is Parsimony, improving the code by subtraction.
12.2 Per-CPU device work. This slice moves device servicing from one global device thread to the CPUs themselves. Each CPU serves the queues of the vCPUs it is running, using the per-CPU state from 8.4. It depends on 12.1: with locked queues, CPUs serving queues in parallel would contend on the locks and gain nothing. Once the queues are lock-free, the work can be spread out without new contention. Its passage is xv6 §12.4 ("Parallelism"). Each CPU touches only its own vCPUs' queues, which is Loose Coupling between CPUs: no shared device thread ties them together.
12.3 virtio-net. This slice adds a network device for guests: a virtio-net device whose transmit and receive virtqueues use 12.1's lock-free rings and 12.2's per-CPU servicing. It comes after both because networking is the heaviest user of queues, so it is the device that shows whether they scale. It is the phase's Demonstrability: throughput measured across 4 vCPUs is the evidence that 12.1 and 12.2 work, not just an argument that they should.
12.4 A lock audit. This slice lists every lock that remains in Glint,
with what it protects and its place in the lock order from 7.3, in
docs/locks.md. It also removes locks elsewhere that existed only to
serialize access to the old queues, such as the notification bookkeeping
added in 9.4, now that 12.1 and 12.2 have made them redundant. It comes last
because only then is the set of remaining locks final. The audit is Clarity,
since every lock now has a stated purpose. The removals are Parsimony,
improving the code by subtraction.
Phase demo: virtio-net throughput scales across 4 vCPUs.
References
- xv6 §12: "Simultaneously obtaining good parallel performance, correctness despite concurrency, and understandable code is a big challenge in kernel design"; §12.3 "No locks at all".
- Hailperin §4.8 "Nonblocking Synchronization": "What's needed is a lock-free TicketVendor that manages to avoid race bugs without this kind of unbounded blocking."
- Tanenbaum: MOS4/5 ch. 8 "Multiple Processor Systems".
- Rationale: Hailperin explains why lock-free virtqueues avoid priority inversion and convoys. xv6 grounds it in a small example.