Scheduling Explained

The threads post left one question open: with more threads than cores, who runs next, on which core, and for how long? The answer is the scheduler¹: the kernel subsystem that multiplexes CPUs among runnable work. This post opens it up. We will look at what a context switch really costs, the goals every policy balances, the classic policies from simplest to fairest, how priorities and multicore complicate the picture, and why your editor feels instant on a loaded machine.

The context switch: the price of sharing

A context switch² swaps the running thread: save registers and program counter into the old PCB, switch page tables if the address space changes, load the new thread’s state, resume. The direct cost is small (hundreds of nanoseconds to microseconds), but the hidden cost dominates: the new thread finds cold caches and a cold TLB, so its first instructions stall while the memory hierarchy refills. Switching address spaces (process switch) pays the full price; switching threads in one process pays less, since the page table and TLB entries survive.

thread A runs … timer fires … kernel saves A, picks B, restores B … B runs
              ↑                                              ↑
        registers → PCB(A)                        PCB(B) → registers
        (plus cache/TLB pollution nobody bills for)

Two conclusions follow. Switches must be frequent enough for responsiveness but rare enough that useful work dominates overhead: the classic time slice (quantum) of a few milliseconds balances the two. And voluntary switches are free wins: when a thread blocks on I/O, the kernel schedules someone else instead of idling, which is why I/O-heavy machines stay busy.

Goals: what “good” scheduling means

Every policy optimizes some mix of competing goals:

• Throughput: jobs completed per second. Batch systems live here.
• Turnaround time: submission to completion. Short jobs hate waiting behind long ones.
• Response time: time to first reaction. Interactive systems live here.
• Fairness: every runnable thread gets a reasonable share; nobody starves.
• Predictability: similar jobs behave similarly; deadlines get met.

No policy maximizes all five. Throughput favors long uninterrupted runs; response time favors frequent switching; fairness costs overhead. The rest of the post is how classic policies pick their tradeoff.

Classic policies: from naive to fair

First-in, first-out (FIFO) runs each job to completion in arrival order. Simple, no starvation, disastrous for response time: one long compile ahead of your keystroke stalls everything (the convoy effect).

Shortest job first (SJF) runs the quickest job next, minimizing average turnaround. Optimal on paper, unusable directly: the kernel cannot know job lengths in advance (it can only estimate from recent behavior, which exponential averaging approximates).

Round-robin gives each runnable thread a fixed quantum in turn, preempting at the timer. Response time becomes predictable (n threads, quantum q: worst wait ≈ n × q), at the cost of a switch per slice and no regard for importance or job length. Timesharing was built on this.

round-robin, quantum = 10 ms, threads A B C ready
A(10) → B(10) → C(10) → A(10) → …

Priority scheduling assigns each thread a level and always runs the highest ready one. Real-time and interactive work preempts background work, which is the point, but low-priority threads can starve indefinitely under load. The standard cure is aging: raise a waiter’s priority the longer it waits, guaranteeing eventual service.

Modern general-purpose schedulers (Linux CFS³, for example) aim at fairness: track each thread’s virtual runtime and always run the one owed the most CPU, weighted by niceness. The effect approximates an ideal fluid sharing where everyone advances together, with priorities expressed as weights rather than strict ranks. Interactive feel comes free: a thread that slept on I/O accrued little runtime, so it jumps ahead when it wakes.

Priorities, preemption, multicore

Three complications complete the picture.

Priorities and inversion. Strict priorities create priority inversion: a high-priority thread blocks on a lock held by a low-priority thread, which cannot run because a medium-priority thread hogs the CPU. The chain defeats the ranking. The classic fix is priority inheritance: the lock holder temporarily borrows the waiter’s priority until it releases, unblocking the chain.

Preemptive vs cooperative. Preemptive kernels (the norm) can switch on timer, I/O, or wakeup at nearly any point, which keeps response time tight at the cost of locking everywhere inside the kernel. Cooperative designs switch only at explicit yield points: simpler, but one greedy thread stalls the machine, the same lesson the OS overview drew for user programs.

Multicore. With many cores the scheduler also places work: keep threads on their warm core (affinity) to preserve caches, balance load across cores, and pack or spread depending on power goals. Migration is a tradeoff between hot caches and idle silicon, re-decided constantly.

The big picture

Sharing CPUs means switching contexts (cheap directly, expensive in caches), choosing a policy among throughput, turnaround, response, fairness, and predictability, climbing from FIFO through round-robin and priorities to fair-share, and handling inversion, preemption, and placement on real hardware. Responsiveness is not magic: short quanta, I/O threads owed runtime, and preemption that never asks permission.

But scheduling decides who runs; memory decides what each runner sees. Every process believes it owns gigabytes of private, contiguous memory on a machine with one RAM and many tenants. Maintaining that fiction, page by page, is the next post’s subject.

Footnotes

1. Scheduling (computing) - Wikipedia

2. Context switch - Wikipedia

3. Completely Fair Scheduler - Wikipedia