Policy and mechanism

A scheduler does two different jobs. The mechanism carries out the work: it saves the registers of the thread leaving the CPU and restores those of the thread arriving, keeps the list of threads that exist, and moves each one between running, waiting and ready. The policy makes the decisions: which ready thread runs next, for how long, and where a woken thread takes its place. Keeping the two apart lets the policy change without touching the code that has to be exactly right for the kernel to survive a switch, and it lets one mechanism serve a fair-share policy, a real-time one or a plain rotation.

The boundary between them is an interface. The mechanism calls the policy at fixed points, when a thread is created, becomes ready, blocks, exits or uses up time, and asks it for the next thread when it is about to switch. The policy answers from its own bookkeeping and never performs a switch itself: everything it needs to know arrives through those calls, and everything it decides leaves through their return values.

The trap is that the boundary carries rules of its own. The mechanism calls the policy in an order it chose, in a context it chose, and relies on invariants the policy has to keep, such as never holding a thread twice in its queue. A policy that makes the right decision at the wrong point, or keeps a duplicate entry, breaks the mechanism as surely as a bug in the switch itself, and the failure shows up far from the policy, as a thread that never runs again.

In Cosmos, the policy is IScheduler, an interface shaped after the EkibenScheduler trait of Ekiben, a pluggable scheduler API, and the mechanism is SchedulerManager. The manager keeps the thread registry, sets every SchedulerThread.State (a policy reads the state but never writes it) and takes the timer tick, and the interrupt stubs save and restore the registers; the policy keeps its bookkeeping in the SchedulerData slot of each thread and each CPU. The policy installed at boot is Stride, and a kernel installs another at run time with SchedulerManager.SetScheduler, which hands every live thread over to it. See Overview and The interface.