The Scheduling Problem

A core executes one instruction stream at a time. If 100 processes are all runnable, 92 of them are not running at any given instant — they are waiting in a data structure the kernel owns, the ready queue (or run queue), which holds every task that is runnable but not currently on a core. The code that pulls a task from that queue and puts it on a core is the scheduler. Nothing else in the system decides who runs; user code can only ask nicely (nice, sched_setscheduler, SetPriorityClass).

Not every process is in that queue. A process that is blocked in read() on a socket, sleeping in sleep(1), or waiting on a mutex is not runnable and costs the scheduler nothing; it sits in a wait queue attached to whatever it is waiting for, and is moved back to the ready queue when the event arrives (see Process States). On a typical machine with 500 processes, the ready queue is usually a handful long. The interesting case is when it is not.

The scheduler runs at well-defined moments, not continuously: when the running task blocks or exits, when a timer interrupt says its slice is over, when a higher-priority task wakes up, or when a task voluntarily yields. Each of those is a scheduling point; at each one the scheduler picks the next task and, if it differs from the current one, performs a Context Switching.

If a task keeps the core until it decides to give it up, one infinite loop freezes the machine — that was the world of cooperative multitasking (Windows 3.x, classic Mac OS). The fix is a hardware timer that interrupts the core periodically (historically every 1–10 ms; modern kernels program it on demand). At the interrupt the kernel is in control, checks whether the running task has used its time slice (its quantum), and if so puts it back on the ready queue and picks another. Taking the core away from a task that has not asked to stop is preemption.

The quantum is a knob with two bad ends. Too long and an interactive task that wakes up has to wait behind a compute-bound one for the whole slice — you type a key and the echo arrives 100 ms later. Too short and the machine spends its time context switching instead of computing: at a 1–5 µs switch cost, a 10 µs quantum would be half overhead. Kernels resolve this with a target latency rather than a fixed slice: "every runnable task should get a turn within roughly N milliseconds", with N scaling with the number of runnable tasks, bounded below by a minimum granularity so slices never become absurdly short.

This is the latency vs throughput trade-off in its purest form. Throughput wants long uninterrupted runs (warm caches, few switches). Latency wants every waiting task to get a core soon. A batch server can tune towards throughput; a desktop or a request-serving process tunes towards latency, and the default on general-purpose kernels leans towards latency because unresponsiveness is what users notice.

Tasks reveal their nature by how they leave the core. A CPU-bound task runs until preempted — it always uses its whole slice. An I/O-bound task runs for a few microseconds, issues a read() or waits on a socket, and blocks — it rarely uses its slice. A text editor, a shell, a network server waiting for requests and a database waiting for disk are all I/O-bound most of the time.

Every general-purpose scheduler treats these differently, because the right policy falls out of the constraint: a task that blocked voluntarily has consumed less than its share, so when it wakes up it deserves to run soon, ahead of the task that has been grinding through its full slices. Older schedulers implemented this as an explicit interactive bonus to priority; fairness-based schedulers get it for free by tracking how much CPU each task has actually received and always running the one furthest behind. Either way the effect is the same: the keystroke handler preempts the compiler, and the compiler barely notices because the handler is done in 50 µs.

Priority is the other axis. A static priority (nice −20…19 on Unix, priority classes on Windows) says how large a share a task should get when there is contention, not that it runs first no matter what — except for real-time policies (SCHED_FIFO, SCHED_RR, Windows REALTIME_PRIORITY_CLASS), which do exactly that and can therefore starve everything else. Fairness is the property that no task waits unboundedly long; a scheduler that lacks it exhibits starvation, which the Scheduling Simulator: FCFS, Round Robin, Priority lets you provoke.

The Linux Completely Fair Scheduler (CFS, 2007–2023) implemented fairness by giving every task a virtual runtime: the CPU time it has consumed, scaled by its weight (nice 0 has weight 1024; each nice step changes the weight by roughly 1.25×). Runnable tasks were kept in a red-black tree ordered by vruntime, and the scheduler always ran the leftmost node — the task that had received the least weighted CPU time. A task that slept accumulated no vruntime, so on wakeup it was far to the left and ran promptly: the interactive boost as a side effect of the accounting, not a heuristic.

Slice length was not a constant. CFS aimed for a target latency (about 6 ms scaled by the log of core count) divided among runnable tasks, with a minimum granularity (about 0.75 ms) so that 100 runnable tasks did not produce 60 µs slices. With 100 runnable CPU-bound tasks on one core, each got about 0.75 ms roughly every 75 ms.

Linux 6.6 (2023) replaced the CFS pick logic with EEVDF (Earliest Eligible Virtual Deadline First). It keeps the weighted-fairness accounting but tracks each task’s lag (how far behind or ahead of its fair share it is) and assigns each a virtual deadline computed from its requested slice; the scheduler runs the eligible task with the earliest deadline. This makes latency-sensitive tasks with short slice requests get the core sooner without breaking fairness, and gives the kernel a principled answer to "who should run" instead of CFS’s accumulated heuristics for wakeups and preemption.

This is one implementation. Windows uses a 32-level priority-based preemptive scheduler with temporary priority boosts on wakeup and a fairness pass that raises starved threads; macOS/XNU uses priority bands with a timeshare decay policy; FreeBSD’s ULE and the real-time kernels used in embedded systems make yet other choices. The constraints are universal; the policies are not.

The ready queue is literally the Queue you implemented in the DSA domain when the policy is first-come-first-served or round-robin: enqueue on wakeup or preemption, dequeue to run. The moment the policy involves priority, the data structure becomes a Priority Queue — a Binary Heap keyed on priority gives O(log n) pick and insert, and O(1) peek at the best candidate. CFS chose a red-black tree over a heap because it also needed to remove arbitrary nodes (a task blocking mid-slice) and find neighbours; the same O(log n) bound, more operations supported.

The transfer runs in both directions. Task-scheduling interview problems ("schedule jobs with cooldown", "minimum time to finish tasks with priorities") are the same problem the kernel solves, with the same tools; and understanding that a scheduler tick is a heap pop makes its cost model — O(log n) per scheduling point, independent of the number of *blocked* processes — obvious rather than memorised.