OS scheduler
Quantum
You are the kernel. Keep the interactive tasks feeling instant.
You play the scheduler, the pager and the lock manager on a budget of cores and RAM. You watch processes across cores and run queues, memory pages, locks and deadlock.
What you'll come away knowing
- Why one CPU-bound process at the head of a non-preemptive queue destroys everyone else’s latency — and that the order was nobody’s decision.
- That the scheduling quantum is a single dial with two objectives pulling against it: short is responsive and switch-heavy, long is the opposite.
- Why strict priority starves, why that is the scheduler working correctly, and what aging costs to fix it.
- That thrashing is a cliff rather than a slope: utilisation falls while the run queue grows, and the CPU is idle precisely because nothing is getting done.
- The four conditions a deadlock needs, and why circular wait is the one worth removing.
- Why the most urgent process on a machine can end up waiting on the least urgent one — and what priority inheritance actually does about it.
How the model works
Processes are drawn from five classes — CPU-bound, I/O-bound, interactive, batch and periodic real-time — each alternating CPU bursts and I/O waits from its own distribution. They move through a state machine of new, ready, running, blocked on I/O, blocked on a lock, swapped out and terminated, and the trace strip records which state each one was in at every moment. That is a Gantt chart, drawing itself.
Eight schedulers run over the same workload and can be swapped mid-run: first-come-first-served, round robin, shortest-job-first with an exponentially averaged burst prediction, shortest-remaining-time-first, strict priority with optional aging, a multi-level feedback queue with demotion and a periodic boost, a CFS-like weighted fair scheduler with virtual runtimes, and earliest-deadline-first. A context switch costs real time, and moving a process to another core costs a stretch of running on a cold cache.
Memory is demand-paged into a fixed number of physical frames, with FIFO, LRU, clock and random replacement. Each process has a working set that shifts as it moves between phases, so locality is temporary. When the sum of the working sets passes the frame count, the machine starts evicting pages it is about to need, and you can watch utilisation collapse.
Processes can run short lock scripts against named mutexes. A wait-for graph is maintained continuously and searched for cycles; the detector is checked against a brute-force search in the tests, because a detector that quietly disagrees with reality is worse than none. You can break a deadlock by killing a process, or prevent it by enforcing a global lock order — and you can watch a priority inversion form and then dissolve when inheritance is switched on.
Every constant used — latencies, timeouts, sizes — is listed with its source in docs/NOTES-quantum.md, along with what the model deliberately simplifies. The numbers are illustrative, not measurements.
Scenarios
- TutorialThree processes, one core
An editor, a compile and a file server sharing one core. Watch the Gantt chart draw itself.
- TutorialThe convoy effect
One long compile, four short interactive tasks, and no preemption.
- CorePick a quantum
Two objectives, one dial, pulling in opposite directions.
- CoreStarvation
Strict priority and a steady supply of urgent work. The batch job has been ready a long time.
- CoreThrashing
Five hungry processes, not enough frames, and a CPU that is somehow idle.
- CoreDining philosophers
Five processes, five locks, everyone reaching left before right.
- HardPriority inversion
The most urgent task on the machine, waiting on the least. Inspired by Mars Pathfinder.
- HardMeet the deadlines
Three periodic tasks. The work fits; the ordering does not.
- HardEight cores, one lock
Plenty of parallelism and a serial section in the middle of it.
Questions
Is this a real scheduler?
The eight schedulers implement the algorithms as they are described in the literature — OSTEP for MLFQ and the classics, the Linux documentation for the CFS-like one — and the tests assert each does what it claims: round robin beats first-come-first-served on interactive latency, aging rescues a starving process, earliest-deadline-first meets deadlines round robin misses. It is not a kernel: there are no interrupts, no syscalls and no hardware.
Why does a context switch cost 0.1 ms when a real one is a few microseconds?
Because the register swap is the cheap part. The expensive part is the cache and TLB the new process arrives to find cold, and that cost is real but diffuse. Pricing the whole thing at 100 microseconds puts the trade against a 1-10 ms quantum into a range you can see on screen. The notes say so explicitly, and the cost is a slider — you can set it to something realistic and watch the trade become invisible.
Does nice really work like that?
The weights are the ones from the Linux table, where each nice level is about a 1.25× change in share. But the split you measure is usually flatter than the weights suggest, and that is the algorithm rather than a simplification: a task waking from a sleep is floored to the runqueue’s minimum virtual runtime, so a process that blocks often keeps handing back the advantage it earned. Nice binds hardest on tasks that never sleep.
What is the difference between response time and turnaround time?
Turnaround is arrival to completion — what the owner of a batch job cares about. Response time is from becoming ready to first running, which is the gap between pressing a key and seeing anything happen. They pull in different directions, and almost every scheduling argument is really an argument about which one you are optimising.
Why can I not fix the thrashing scenario by tuning the scheduler?
Because the CPU is not the bottleneck. Utilisation is low precisely because every process is blocked servicing a page fault, so rearranging the order they run in changes nothing. The answers are to buy memory or to run fewer things at once, and admission control — swapping a whole process out so the rest fit — is the second one.
Is the Mars Pathfinder scenario accurate?
The mechanism is: a high-priority task blocked on a mutex held by a low-priority one, with a medium-priority task preempting the holder so the lock is never released, and a watchdog resetting the system. The names, timings and workload here are invented. The public write-up by the engineer who debugged it is linked from the insight when it fires.