The timer interrupt is the kernel's answer to the halting problem. Scheduling is what it cannot answer.
Cooperative multitasking asks each program to yield. A program that never does takes the machine with it, and no kernel can screen for that in advance: Turing, 1936.
Preemptive multitasking does not ask. A hardware timer raises an exception after a fixed number of cycles; the kernel saves the context and runs another. The halting problem is not solved; it is made irrelevant by a bound.
Every kernel principle in this class has this shape: what cannot be decided is bounded.
The emulator's loop from week 3 with one more exit: after timeout instructions it raises a timer exception and returns the context, as it would on a system call or a page fault. The caller, the kernel, decides what happens next.
The kernel in selfie is a loop around this call: pick a context, run it for a slice, handle what stopped it, pick again. That loop is the operating system by emulation.
Running: its registers are in the processor. Ready: saved, waiting for a slice. Blocked: saved, waiting for input, a child, a lock. The timer moves running to ready; a system call that must wait moves running to blocked; the awaited event moves blocked to ready.
A finite state machine per context. The kernel's whole knowledge of a program is which of three states it is in and a few kilobytes of saved registers. By Rice it knows nothing about what the program is doing, and needs to know nothing.
A queue; the timer moves the running context to the back. Every context gets a slice every n slices. Fair, simple, and what selfie does. It optimises nothing.
Real schedulers weigh interactivity, deadlines, fairness across users, energy. Each is a policy; each can be gamed; each is a bound on something that cannot be decided.
With deadlines and several processors, finding a schedule that meets every deadline is NP-hard: one more job multiplies the schedules to try. Even knowing every job's length, which by Rice it cannot, the kernel could not afford the optimum.
Two limits, one design: the scheduler does not know and could not compute. So it is a policy, chosen by people, adjusted by measurement. Week 11 measures.
create_context, load, the kernel loop, and mipster with a timeout are all there. The assignment is to arrange them into a list of contexts and a scheduler. Look at how the existing code handles a context that exits, and keep the case of one instance behaving exactly as before.
Bach · Wachet auf, ruft uns die Stimme — Netherlands Bach Society. The watchman’s call at midnight, and the sleepers who did not budget their oil: the timer interrupt, with consequences. Time-sharing has a cantata.
An Experimental Time-Sharing System — Corbató, Merwin-Daggett and Daley, 1962: CTSS at MIT, the first time-sharing system, with the timer interrupt as its centre. And, more technical, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment — Liu and Layland, 1973: the scheduling theory, rate-monotonic and earliest-deadline-first, with the proofs.