The problem: more runnable tasks than CPUs
By now you know that a process has a control block in the kernel and moves between states — running, runnable (ready but waiting for a CPU), and blocked (waiting on I/O or a lock). At any instant your laptop has maybe four CPU cores but several hundred processes, and a good fraction of them are runnable — they have work to do right now and are only waiting for a turn. The scheduler is the kernel subsystem that decides, over and over, thousands of times a second, which runnable task each CPU runs next and for how long. Nobody calls it directly; it is invoked from inside the kernel at carefully chosen moments.
The illusion the scheduler sells is that all those processes run at the same time. They do not. On a single core, exactly one task executes at any instant; the scheduler creates the appearance of simultaneity by switching between them fast enough that you cannot perceive the gaps — this is concurrency without parallelism. Each handoff from one task to another is a context switch: the kernel saves the outgoing task's registers (rip, rsp, the general-purpose set) into its control block, loads the incoming task's saved registers, switches the address space, and resumes. It is not free — a switch costs hundreds of nanoseconds plus the cache and TLB damage of touching new memory.
So the scheduler has two jobs that pull against each other. It must give every runnable task a fair share of CPU time, so nothing starves and your editor stays responsive while a compile runs. And it must switch infrequently enough that the overhead of switching does not eat the work. Schedule too rarely and one greedy task hogs the core; schedule too often and you spend all your time saving and restoring registers instead of doing real work. Everything that follows is the kernel navigating exactly this tension.
The run queue: the per-CPU pool of who-could-run
Where does the scheduler look to find the next task? In a run queue: a data structure holding exactly the tasks that are runnable right now. Crucially, blocked tasks are not in it — a process waiting on read() from a slow disk has been removed from the run queue entirely and parked on a wait queue tied to that disk; it costs the scheduler nothing because the scheduler never even looks at it. When the disk data arrives, the interrupt handler moves it back onto a run queue, where it again competes for CPU. The run queue is the pool of contenders, not the list of all processes.
On a multi-core machine there is not one global run queue but one run queue per CPU. This is a deliberate design choice, and it is the same instinct behind per-CPU data you will meet again next guide: a single shared run queue would need a lock that every core grabs on every scheduling decision, and that lock would become a screaming bottleneck. Per-CPU run queues mean each core schedules from its own list with no cross-core lock on the common path. The cost is that the queues can drift out of balance — one core's list grows long while another sits idle — so the scheduler periodically runs load balancing, migrating tasks from busy queues to idle ones. Migration is not free either, because a task that moves to a new core leaves its warm cache behind.
Fairness done right: the Completely Fair Scheduler
For most of its history Linux's default scheduler was the Completely Fair Scheduler (CFS), merged in 2007, and its central idea is elegant enough to hold in your head. Imagine a perfect, idealized machine where N runnable tasks each run simultaneously at exactly 1/N of the CPU's speed — perfectly fair by construction. Real hardware cannot do that; it must run one task at a time. So CFS tracks, for each task, a number called virtual runtime (vruntime): roughly the amount of CPU time that task has already consumed. The rule is then breathtakingly simple — always run the task with the smallest vruntime, because that is the task that has fallen furthest behind the fair ideal.
Picture three tasks A, B, C. A runs for a slice, its vruntime climbs, and now A is no longer the smallest — so the scheduler picks B, then C, and only comes back to A once everyone else has caught up. The effect is that vruntimes tend to stay close together, which is exactly fairness: nobody pulls far ahead in CPU consumed. Priority is folded in not by jumping the line but by scaling how fast vruntime grows. A high-priority task's vruntime advances in slow motion, so it dips back to the bottom of the ordering sooner and runs more often; a low-priority task's vruntime races ahead, so it waits longer between turns. Priority changes the weight, not the rule.
idealized fair share: each of N tasks gets 1/N of the CPU
vruntime = real CPU time consumed, scaled by priority weight
(high priority -> vruntime grows SLOWER)
scheduler rule: always run the task with the SMALLEST vruntime
stored in a red-black tree keyed by vruntime:
pick-next = leftmost node (O(log n) to remove + reinsert)
[ A:50 ] A ran, vruntime 50 -> 70, reinsert:
/ \
[ -- ] [ B:60 ] ---> pick leftmost = B (smallest vruntime now)
\
[ C:90 ]How does "always pick the smallest" stay cheap with hundreds of tasks? CFS keeps the run queue as a red-black tree keyed by vruntime — a self-balancing binary tree. The task to run next is always the leftmost node, found in time proportional to the tree's depth, and after a task runs you update its vruntime and reinsert it, also in logarithmic time. There is no scan of all tasks on every decision. This is why "run queue" being literally a queue is a beginner's simplification: the real structure is a tree precisely so that "who has the smallest vruntime" is answered fast even when the pool is large.
Preemption: taking the CPU back by force
We have decided who runs. Now: how does a running task ever stop? There are two philosophies, and you met them last rung. Under cooperative scheduling, a task keeps the CPU until it voluntarily yields — by blocking on I/O, sleeping, or explicitly giving up. This is simple and was how early systems worked, but it is fatally fragile: a single task stuck in an infinite loop, never yielding, freezes the entire machine, because nothing can take the CPU away from it. One buggy program and the whole system hangs.
Every modern general-purpose OS instead uses preemptive scheduling, and the mechanism rests directly on the interrupt machinery from this rung's earlier guides. The kernel programs a hardware timer to fire an interrupt periodically — historically every ~10 ms, called a tick. When the timer fires, it raises an interrupt that forcibly transfers control out of the running task and into the kernel's handler, exactly the trap-and-mode-switch you saw for system calls, except this time the task did not ask for it. In the handler the kernel updates the running task's vruntime and checks: is there now a runnable task with a smaller vruntime? If so, it sets a flag meaning "reschedule needed," and on the way back out the kernel performs a context switch to that better task instead of resuming the interrupted one.
This is why a runaway infinite loop on Linux does not freeze your machine: the timer interrupt fires regardless of what the looping task wants, the kernel regains control on every tick, and it can simply schedule something else. The loop hogs its fair share and no more. Notice the elegant reuse — the same interrupt mechanism that delivers a keypress or a disk-done signal is what makes preemptive multitasking possible at all. Without an asynchronous interrupt the kernel could never wrest the CPU back from code that refuses to cooperate.
Preempting the kernel itself, and where this all goes
There is a subtler layer. Preempting a user task is settled. But what about code running inside the kernel — say, a process that made a slow system call and is now executing kernel code on its behalf? Early Linux was not preemptible in kernel mode: once a task entered the kernel it ran there uninterrupted by the scheduler until it returned or blocked, which kept kernel data structures simple but could let a long syscall delay a high-priority task waking up. Modern Linux is a preemptible kernel: the scheduler can switch away from a task even while it is mid-syscall in kernel code — except in clearly marked regions where it must not, such as while holding a spinlock or running an interrupt handler.
Step back and see the shape. The scheduler is not one algorithm but a layered answer to a single question — who runs next? — built from pieces you now recognize: per-CPU run queues of runnable tasks, a fairness policy (CFS) that picks by smallest vruntime from a balanced tree, and a preemption mechanism founded on the timer interrupt that lets the kernel reclaim the CPU from anyone, cooperative or not. Each scheduling decision ends in a context switch, the concrete machine-level act of swapping one task's registers and address space for another's.
And notice the open thread we just pulled: the kernel must not be preempted while holding a spinlock, and the run queue itself is shared data that needs protection. That is no accident — the scheduler is one of the kernel's most contended pieces of shared state, touched from interrupt handlers, from every CPU, concurrently. How the kernel protects such data without itself deadlocking — spinlocks, RCU, and the per-CPU trick we leaned on here — is precisely the subject of the final guide in this rung.