Login
Phase 8: Scheduling and vCPUs
Login

xv6 §8, "Scheduling". "A common approach is to provide each process with the illusion that it has its own virtual CPU by multiplexing the processes onto the hardware CPUs."

For a hypervisor this passage is literal: a guest's virtual CPUs are multiplexed onto real ones. Phase 8 builds that with one scheduler. Glint's own threads and guests' vCPUs are the same kind of thing, scheduled by the same code. It starts from Phase 6's timer tick (6.2) and Phase 7's CPUs and locks (7.1a–7.3). It leaves Phase 9 a scheduler that threads can sleep on.

Provisional slices. Each is refined, with its quoted sentence, when the phase starts.

Slices

8.1 Context switch. A small routine saves one thread's registers and stack pointer and restores another's. Each architecture's version differs only in which registers it saves, so this is one check-in. Everything else in the phase is built on it, which is why it comes first. Its passage is xv6 §8.3 ("Code: Context switching"). Reducing all switching to this one routine, so every later slice reuses it, is Parsimony.

8.2 Threads and round-robin. Glint gets threads (a stack plus the saved state 8.1 switches) and a run queue served in turn, protected by 7.2's spinlock. It comes after 8.1 because a queue of threads is useless until one can be switched to. xv6 §8.4's simple policy is chosen first because it is the smallest policy that works. That is Parsimony: solve the problem and no more until a second guest gives a reason to.

8.3 Preemption. The timer tick from 6.2 forces a switch through 8.1, so no thread can keep a CPU forever. Hailperin §2.5 gives the reason: under cooperative multitasking, buggy code in one thread can hold all the others up. It comes after 8.2 because there must be a queue to preempt into. This is the scheduler-level counterpart of leaving hosted mode in 2.6. A spec running a thread that never yields, and showing the others still run, serves Demonstrability.

8.4 Per-CPU state. Each of the CPUs started in 7.1a and 7.1b keeps its own current thread and run queue, the role xv6's mycpu plays (§8.5). It comes after 8.3 because, until preemption, one shared queue was enough to show the mechanism working. Keeping each CPU's state in one clearly named place, instead of scattered globals, serves Clarity.

8.5 vCPUs are threads. Phase 4's run loop (4.3a, 4.3b) becomes the body of a thread, so the scheduler runs a guest's vCPU exactly as it runs Glint's own work. It comes after 8.2–8.4 because it needs threads, preemption and per-CPU queues to exist. There is one scheduling mechanism rather than two, which is Parsimony. Guests and Glint's own work are interchangeable to the scheduler, which is Loose Coupling.

8.6 Several vCPUs per guest. When a guest makes the PSCI call CPU_ON, Glint creates another vCPU thread (8.5) for it. This is the guest-side mirror of the host-side CPU_ON Glint itself used in 7.1a. It comes after 8.5 because each new vCPU is simply another such thread. Its passage is MOS4/5 §8.1.4 on multiprocessor scheduling. Linux bringing up four CPUs on Glint, visible in its own boot log, serves Demonstrability.

8.7 Proportional share. With a second guest present (the test guest from 4.2 running beside Linux), 8.2's round-robin gives way to proportional share between guests, so each guest's vCPUs get their configured fraction of the CPUs. Hailperin §3.6 describes this as "doling out processor time to them at controlled rates". It comes last because there is nothing to share fairly until there are two guests. The policy replaces round-robin behind the same run-queue interface, which is Loose Coupling.

Phase demo: Linux with 4 vCPUs and the test guest run together, each receiving its configured share.

References