Scheduling

Watch the system run

This is a simplified simulation of the pipeline system in tests/pipeline/system.sysk, which takes no input, so it runs from start to end on its own (the default system waits on a person; see Input): the same tasks, channels, depths and message counts, the same 1 ms quantum and round-robin rule. How long each piece of work takes is made up (a spinner's round is about 4 ms), so the real order differs in detail; the shape does not. Amber lines are timer interrupts.

The rules

1. The timer. timer_arm (in irq.S) sets the CLINT's compare register 10,000 ticks of its 10 MHz clock past the last deadline: 1 ms, without drift (Time, sysk 022). The tick paces the scheduler and is when deadlines are checked; the time a task reads comes from the counter itself, in nanoseconds (sysk 024). When it fires in user mode, trap.S calls on-timer, which re-arms the timer, counts the tick and calls reschedule.
2. Round robin. pick-next looks at the tasks after the current one, wrapping around, and returns the first that is not done. If every task is done it returns ntasks, the boot context, which then finishes the boot.
3. Device interrupts. A device's interrupt (the PLIC's, mcause 11) from user mode makes trap.S call on-device: it claims the source, marks the device's driver signalled and returns to the same task. The claim stays open, keeping the source quiet, until the driver has served its device and calls device-ack, which takes its Device (sysk 023; uart-ack before, for the UART only). A task waits on several sources at once with alt: its receiving channels, room on the streams it sends on, and its device, each with a guard; alt returns the first ready, wanted source at or after a start the task chooses, so starting after the last one served is fair.
4. Waiting is giving up the turn. send on a full channel and recv on an empty one loop on wait inside their atomic block: reschedule, so the next task gets the rest of the quantum (the timer is not reset). Every kernel call that completes and every tick counts as progress; if a whole round of the other tasks passes with none, every task is waiting, and wait idles instead of spinning: cpu_wait stops the hart (wfi) until an interrupt is pending, with interrupts still off, and the kernel handles it there.
5. Finishing. When a task's function returns, task-main calls finish, which marks it done and never comes back to it.
6. Faulting. A task that breaks a rule makes trap.S call on-fault (sysk 105), which keeps the fault in the task's slot, marks it done, ends every channel it sends on and never comes back to it. A job's task also ends its job, as job-stop would (pool-end, shared), and job-start starts its slot from the first frame again (slot-restart, shared too): on-fault runs on the faulted task's own stack, so it cannot restart it there (A fault kept).
7. Switching. ctx-switch saves the callee-saved registers on the current kernel stack, stores the stack pointer, loads the next task's, and loads its PMP regions. Everything else a task had in registers was saved by trap.S on the way in.

The task table never grows. A system with jobs (sysk 017) makes its slots at boot like any other task; what changes while it runs is which catalogue program a slot runs, decided by the job the kernel last judged and started (Jobs). A server that serves the job's programs waits for them like for its device: alt counts a service the job has bound and the server has not yet opened as ready, so the server needs nothing from the job to start (Files for jobs, sysk 031).

What the scheduler knows can be read, as files (sysk 028): /task/NAME/status says whether a task is done and when its alarm is due, and /time the nanoseconds and ticks. kernel/sched.sysp, the only file that touches kernel state, gives kernel/files.sysp a few accessors for them, and keeps each task's 8 fids in a table of its own; sys-serve answers a request in one atomic block, so a file is a snapshot (Files).

Who ran

Each tick is charged to one place (sysk 060). on-timer runs only when the timer interrupts a task running its own code, since a wait loop runs with interrupts off; so it charges that task, and a status's ticks is how much of the machine the task has had. A tick that comes while every task waits is taken by idle, inside whichever task's wait stopped the hart, and charged to none of them: /time's idle. Every task's ticks and the idle ones add up to /time's ticks. In the simulation above, each task's count is beside its state, and the idle ones last.

What a task waits for is said by the one place that waits. Every blocking loop in the kernel calls wait with a reason: send, recv and a lease's service-open their channel, sleep-until the clock, a slot and a job's end job, and alt the one source it wants, or alt for several, as a tree's tree-recv does while none of its holders has a request (sysk 063). wait records it for the task across the reschedule and clears it when the task runs again. A task reads the kernel's tree only while it runs, and every other task is then inside a reschedule, so a status says what each one waits for as it is. Plan 9's /proc/N/status keeps a process's times in the same way, and ps and stats read them; sysk's top is the shell's watch over every task's status (The shell).

Why the kernel cannot be interrupted

A trap clears machine mode's interrupt-enable bit, and the kernel never sets it again: the kernel always runs with interrupts off and is only ever entered from a task. Nothing can interrupt kernel code, which is what sysp's atomic blocks assume. A kernel path can still let others run on purpose: a send waiting for room calls reschedule partway through, and other tasks run until it is switched back to. ctx-switch's contract is what says the kernel invariant holds again when it resumes. Back in user mode the timer can fire again: RISC-V always lets machine-level interrupts through while a less privileged mode runs. See User mode and PMP for the trap path.

Proven, not hoped

• on-timer is sysp. Its postcondition, (and (running k) (same-task (old k) k)), is exactly the rely every task assumes between its atomic blocks: whatever runs while a task is paused keeps the kernel's invariant and comes back to it.
• pick-next is proven to return a task, or the boot context when none is left; reschedule is proven to keep the invariant and come back to the same task.
• The tick counter stops at a billion, so it cannot overflow. sysp would not accept it otherwise.
• What is taken on trust here are the assembly's contracts: timer-arm, timer-stop, install-kernel, ctx-init, ctx-restart (a stopped job's task prepared to start again, sysk 074), and above all ctx-switch's: when this task resumes, the invariant holds and it is current again. That one is justified by the proven contracts of everything that switches.

Fairness, that a task able to move eventually does, is what the round-robin rule gives the deadlock check to assume. The spinners are there to test it: they never yield, and the boot test checks that both make progress, interleaved.