The scheduler decides which ready thread runs on each core next. Every switch costs thousands of cycles in save, restore, and cold caches, so each decision trades fairness against throughput against latency — and the kernel makes it hundreds of times per second on every core.
The three timescales the OS schedules on
Scheduling happens at three levels that operate on very different clocks. The long-term scheduler admits programs from disk into memory and sets the degree of multiprogramming, the number of processes competing at once; most general-purpose systems admit eagerly and leave this control nearly idle. The short-term scheduler picks the next thread for a core on every timer interrupt (typically 100–1,000 Hz) and on every system call that blocks or wakes a thread — this is the hot path everything below describes. The medium-term scheduler swaps whole processes out of memory under pressure; many desktop and server systems rarely invoke it, while memory-constrained kernels depend on it.
What the classic algorithms optimize for
| Algorithm | Rule | Strength | Weakness |
|---|---|---|---|
| FCFS (first-come, first-served) | Run in arrival order | Simple and starvation-free | Convoy effect: short jobs queue behind long ones |
| SJF (shortest job first) | Run the shortest next burst | Optimal average waiting time | Needs burst estimates; starves long jobs |
| SRTF (shortest remaining time first) | Preemptive SJF | Best response for short work | Still starves long work |
| Priority | Run the highest priority | Flexible policy expression | Starves low priorities without aging |
| Round robin | Fixed time slice (quantum) per thread | Fair with bounded response time | Slices under ~1 ms drown in switch overhead |
| Multilevel queue | Separate queue per class | Isolates interactive from batch work | Fixed classes misbehave as workloads shift |
| MLFQ (multilevel feedback queue) | Queues plus demotion and periodic boosting | Learns which threads are interactive | Many tuning knobs; easy to misconfigure |
No row dominates. Batch systems favor SJF-style throughput, interactive systems favor round robin response time, and general kernels layer feedback on top so a text editor and a video encoder can share one machine without manual tuning.
How Linux tracks fairness with virtual runtime
Linux ran the Completely Fair Scheduler (CFS) from 2007, when it replaced the O(1) scheduler, until kernel 6.6 (2023) traded it for EEVDF. Both keep every runnable thread in a red-black tree keyed by virtual runtime — CPU time consumed, weighted so a low-priority thread accrues it faster (EEVDF layers per-task latency tolerance on top). Each decision picks the leftmost node, the thread owed the most CPU, and the tree re-sorts on every tick. Fairness falls out of the data structure instead of a pile of queues.
Two refinements keep the theory fast in practice. Processor affinity keeps a thread on the core holding its warm caches rather than migrating it for perfect balance. Load balancing periodically equalizes queue weight across cores, so one busy core and three idle ones resolve toward even shares. Tunables live where operators expect: nice values shift weight, and sched_latency_ns bounds the period over which every runnable thread is guaranteed a turn.
How real-time tasks preempt everything else
Ordinary fairness is wrong for deadlines, so Linux schedules real-time classes strictly above CFS. SCHED_FIFO runs a real-time thread until it blocks or yields, with no time slicing among equals. SCHED_RR adds round robin within equal priorities, so cooperating real-time threads share. SCHED_DEADLINE assigns each task a runtime budget per period and admits it only when the kernel can prove the budget is satisfiable. Misuse is a system freeze wearing a priority's clothes: one SCHED_FIFO loop that never blocks starves everything below it, including the shell that would kill it.
Key takeaways
- Short-term scheduling is the hot path: every interrupt and every blocking call re-asks which thread deserves the core.
- Classic algorithms each optimize one goal — throughput, response time, or adaptability — and every choice names what it sacrifices.
- CFS-era fairness (EEVDF since kernel 6.6) was a min-search over virtual runtime, with affinity and load balancing keeping the abstraction cheap on real hardware.
- Real-time classes sit above fair scheduling and demand proof of feasibility, because an unbounded real-time thread is a denial of service.
- Try the single-threaded CPU scheduler problem to implement one policy by hand, and read Processes and threads for the entities being scheduled.
Production cost model and latency numbers
To apply Scheduling: How the OS Chooses What Runs Next effectively in production systems, engineers must move beyond qualitative diagrams and quantify the exact hardware and network costs at each boundary:
| Operation / Boundary | Typical Latency | Dominant Bottleneck | Production Mitigation |
|---|---|---|---|
| L1 / L2 Cache Access | 1 ns – 4 ns | Register dependency chains & pointer chasing | Contiguous memory layouts, cache-line alignment (64 B), and batch iteration |
| Main Memory (DRAM) Fetch | 60 ns – 100 ns | TLB misses, random heap indirection, NUMA hops | HugePages (2 MB), arena/slab allocators, and pre-allocated ring buffers |
| Kernel Syscall / Context Switch | 1 µs – 5 µs | User-to-kernel mode switch, page-table flush, lock contention | Non-blocking readiness loops (epoll / io_uring), batching, and zero-copy I/O |
| NVMe SSD Random Read / fsync | 50 µs – 500 µs | Block I/O queue depth, write amplification, WAL flushes | Group commit, sequential append logs, and bounded buffer-pool pinning |
| Intra-Region RPC Roundtrip | 0.5 ms – 2.5 ms | Serialization, TCP/TLS framing, tail queueing ($L = \lambda W$) | Connection pooling, deadline propagation, and p95 hedged requests |
Failure modes, debugging, and operational checklist
In real incidents, systems rarely fail at average (p50) load—they fail when a slow dependency, skewed hot key, or resource leak pushes concurrency across a non-linear saturation cliff. When reviewing code or architecture that relies on Scheduling: How the OS Chooses What Runs Next, walk through three verification questions:
- What is the invariant under partial failure or contention? If a worker crashes mid-operation, a network packet is delayed and reordered, or two threads race on the same state transition, prove which atomic primitive, version number, or idempotency key prevents silent corruption.
- How is backpressure enforced when demand exceeds capacity? Unbounded in-memory queues, unthrottled retries, and blocking calls without explicit deadlines turn a localized
100 msslowdown into a fleet-wide Out-Of-Memory (OOM) cascade. Always bound queue depths, propagate caller deadlines, and shed excess load early. - Which metrics and traces isolate the bottleneck in under 60 seconds? Instrument saturation, queue wait time vs service execution time, cache hit/miss ratios, and error rates by failure reason so on-call engineers can immediately distinguish a compute bottleneck from an I/O or lock-contention stall.