SchOS/docs/architecture/scheduler.md

<!-- SPDX-License-Identifier: GPL-2.0-or-later -->
# 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/<pid>/schedstat` | vruntime in nanoseconds, nice, slices run. |
| `/proc/<pid>/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/<pid>/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.