# The scheduler Every runnable process carries one number, `vruntime`: the CPU time it has consumed, divided by its weight. The scheduler always runs whichever runnable process has the smallest one. That is the whole rule. Everything below is either a consequence of that rule or a guard against one of the two ways it goes wrong. ## What it replaced, and why It was xv6's round-robin: walk the process table from end to end, run everything `RUNNABLE` in slot order, and take the CPU back on the next timer tick. Three things were wrong with it on a machine that now runs a shell, a network stack and a display server at once. **Slot order is not fairness.** A process that blocked after a microsecond and one that burned its whole slice were treated as equals, because nothing counted what anyone had used. A compile and the shell you were typing into got alternate turns, and the shell felt it. **Every tick was a context switch.** `yield()` fired unconditionally on the timer, so a process alone on a CPU paid a full switch — `switchuvm`, a `%cr3` reload, a flushed TLB — a hundred times a second, only to be handed straight back to itself. **Nothing could be said to matter more than anything else.** No nice, no priority, nothing for a driver thread that has to answer a device promptly. ## What falls out of the rule - **Fairness**, without anything enforcing it. Running advances your clock, so the process whose clock is furthest behind is by definition the one that has had least CPU, and it is the one that runs next. Equal weights converge on equal shares. - **Interactivity**, without a heuristic. A process that spends its life blocked on a keystroke barely advances its vruntime, so when the keystroke arrives it is already at the front of the queue. Older schedulers guessed at "is this interactive?", and that guess was the part that was always either gameable or wrong. - **Priority**, as one multiplication. Weight scales how fast your clock runs; a process of twice the weight is charged half the vruntime for the same real time, so it is chosen twice as often. This is the only line in the scheduler where `nice` does anything. ## The two guards ### Sleepers do not get to collect a debt A process blocked for ten seconds comes back ten seconds of vruntime behind everything else. Left alone it would monopolise the CPU until it caught up — the standard way a naive fair scheduler turns one sleeper into a system-wide stall. `min_vruntime` is the floor: it tracks the front of the queue and only ever moves forward. A waking process is pulled up to no worse than `min_vruntime - SCHED_LATENCY_NS`: far enough forward to be scheduled promptly, not so far as to be owed anything. ### Forking does not reset your bill `fork()` copies the parent's vruntime to the child. Were the child to start level with everyone, a process could clear its own CPU debt by forking, and something that forks per request would collect a fresh full share every time while a long-running process kept paying for everything it had ever used. `nice` is inherited for the ordinary reason: the point of `nice make -j8` is that the compilers it forks are niced too. ## Slices A slice is `SCHED_LATENCY_NS` (20 ms) divided between the runnable processes, floored at `SCHED_MIN_GRAN_NS` (2 ms). With few processes each gets a long slice and switches are rare; as the count grows the slice shrinks until the floor, below which a switch would cost more than the work done inside it, and the period is allowed to stretch instead. The floor is deliberately **shorter than a timer tick**. The tick is when preemption is *considered* — `trap()` asks `sched_slice_expired()` and only then yields — but time is *measured* with the TSC, against the `tsc_hz` the LAPIC calibration already establishes at boot. Tick-granularity accounting on a 100 Hz timer would make every slice a multiple of 10 ms whether it deserved it or not. ## Nice, and who may use it `nice` runs −20 to 19 with 1.25 between adjacent levels, so one step is about a 10% change in share when two processes compete — the convention UNIX has used long enough that programs and people both expect it. The weight table is `1024 / 1.25^nice`, with nice 0 at 1024 so the common case multiplies by one. `setpriority(2)` is the only way to set it, and it is the one place in `kernel/proc/proc.c` where the uids are actually consulted rather than merely tracked. Two rules, with the two errnos POSIX gives them: - **`EPERM`** — you may only renice something you own. Without it any user can push every root process to nice 19 and have the run of the machine. - **`EACCES`** — *lowering* nice, which is asking for more CPU, is root's alone. Without it nice is not a courtesy but a way for any process to outrank the rest of the system by asking. Both bite now that there are users ([users.md](users.md)); root is exempt from both. ## Deliberately not a red-black tree Linux keeps the runnable set in a red-black tree and Zircon in a WAVL tree, so "smallest vruntime" is O(log n) with the leftmost node cached. Here it is a linear scan of the process table — the same scan the old round-robin did. `NPROC` is 128 slots; the scan is a handful of cache lines and runs with `ptable.lock` already held, whereas a balanced tree is three hundred lines of rotations that have to stay correct through every exit path in `proc.c`. The scan is the right trade until something measures it as the problem, and the measurement comes first. Replacing it changes `pick_next()` and nothing else, which is the point of it being one function. ## Still one lock, still one queue Every CPU picks out of the same table under `ptable.lock`. Per-CPU run queues with work stealing are the other half of a real SMP scheduler, and they are a separate change: they need a load balancer, and a load balancer that is wrong is worse than a global lock that is merely contended. At the core counts this actually runs on, the lock is not yet what hurts. ## Looking at it | | | | --- | --- | | `/proc//schedstat` | vruntime in nanoseconds, nice, slices run. | | `/proc//status` | `voluntary_ctxt_switches` and `nonvoluntary_ctxt_switches`. | The middle field of `schedstat` differs from Linux, which reports run-queue wait time there. That time is not measured here, and inventing a number is worse than putting something true in its place. The two switch counts are worth telling apart: a high **voluntary** count means a process is waiting on something, and a high **involuntary** count means it is being preempted. That is the difference between "this is slow" and "this is competing". ### A note on measuring it under QEMU Without KVM, the guest's timer interrupts coalesce under load, so the tick clock — and therefore `utime`/`stime` in `/proc//stat`, and `sleep` — runs slow against the TSC. `schedstat` is TSC-based and does not, which is why the two disagree on a busy TCG guest and why shares are worth measuring as a **delta between two samples** rather than as absolute totals.