CPU Scheduling

Definition: The OS process scheduler component that decides which runnable process or thread gets CPU execution time and for how long.

How It Works

Preemptive scheduling: the OS forcefully interrupts a running process when its time quantum expires or a higher-priority process becomes runnable, saving its context for later resumption via a timer interrupt.
Non-preemptive scheduling: a process keeps the CPU voluntarily until it finishes, yields, or blocks on I/O. Simpler to implement, but one long-running process can stall everything behind it.
First-Come First-Served (FCFS): runs processes in arrival order. Simple, but a single long job at the front causes the convoy effect, where short jobs queue up behind it.
Shortest Job First (SJF): picks the process with the smallest remaining burst time next. Minimizes average waiting time provably, but requires knowing or estimating burst length in advance, which isn’t generally possible.
Round Robin (RR): each process gets a fixed time quantum, then moves to the back of the ready queue. Fair and bounds worst-case wait, but throughput is sensitive to quantum size.
Priority Scheduling: each process has a priority number; the scheduler always runs the highest-priority runnable process. Can starve low-priority work indefinitely without aging.
Multilevel Feedback Queue (MLFQ): several ready queues with different quanta and priorities. A process that uses its whole quantum gets demoted to a lower-priority, longer-quantum queue; a process that blocks early (I/O-bound) stays high priority. Approximates SJF without needing to know burst times upfront.
Scheduling metrics: turnaround time (completion time minus arrival time), waiting time (turnaround time minus burst time), response time (time to first CPU access), and overall CPU utilization/throughput.
Real-time scheduling classes sit alongside the general-purpose ones: Rate Monotonic Scheduling assigns fixed priority by task period (shorter period, higher priority) and is optimal among fixed-priority schemes for periodic tasks; Earliest Deadline First (EDF) dynamically runs whichever ready task has the nearest deadline, and can achieve up to 100% CPU utilization under the right conditions, something fixed-priority schemes can’t guarantee.
Linux exposes scheduling policy per-thread, not just per-process: SCHED_OTHER (CFS/EEVDF, the default time-shared policy), SCHED_FIFO and SCHED_RR (fixed-priority real-time policies that preempt any SCHED_OTHER task unconditionally), and SCHED_DEADLINE (EDF-based, for tasks with hard timing requirements).

Under the Hood

Every runnable task has kernel-side state: on Linux this is struct task_struct, which holds the process ID, register save area, memory map pointers, open file table, and scheduling-specific fields like priority and vruntime. A context switch saves the currently running task’s registers and program counter into this structure, then loads the next task’s saved registers, switches the page table base register (CR3 on x86) if it’s a different process, and resumes execution at the saved program counter.

Linux’s default scheduler for normal tasks is the Completely Fair Scheduler (CFS). Instead of fixed time slices, CFS tracks a per-task vruntime, the amount of CPU time a task has consumed, weighted by its nice value. Runnable tasks live in a red-black tree keyed by vruntime, and the scheduler always picks the leftmost node, the task with the least accumulated runtime. As that task runs, its vruntime grows and it’s re-inserted further right in the tree, so over time every task converges toward equal CPU share. Linux 6.6 replaced CFS’s core with the EEVDF (Earliest Eligible Virtual Deadline First) algorithm, which improves latency for tasks that briefly go idle, but the red-black-tree-of-runnable-tasks design remains conceptually similar.

The scheduler runs on every timer tick (the tick rate is configurable, commonly 100-1000 Hz) and whenever a task blocks, wakes up, or a syscall returns to a preemption checkpoint. Waking a blocked task (e.g., after an I/O completion) inserts it back into the run queue and may trigger an immediate preemption if its priority/vruntime warrants running now rather than waiting for the next tick.

Multi-core systems complicate the picture with per-CPU run queues rather than one global queue, since a single shared queue would need a lock every scheduling decision and become a bottleneck as core counts grow. Each core mostly schedules from its own queue, and a periodic load balancer redistributes tasks across cores when one queue backs up while another sits idle. This introduces cache-affinity tradeoffs: migrating a task to an idle core can help throughput immediately but costs the “warm cache” the task built up on its old core, so real load balancers weigh queue imbalance against migration cost rather than migrating on every opportunity.

Each CPU’s runnable SCHED_OTHER tasks live in a per-core cfs_rq (CFS run queue) structure, which owns the red-black tree described above. Real-time tasks (SCHED_FIFO/SCHED_RR) live in a separate rt_rq structure, a set of priority-indexed linked lists rather than a tree, since fixed-priority selection just needs “highest non-empty priority list, take the head,” no ordering computation required. A core’s actual scheduling decision checks its real-time run queue first and only falls through to CFS/EEVDF selection if no real-time task is runnable, which is exactly how SCHED_FIFO/SCHED_RR tasks can starve normal tasks if they never block.

Debugging Workflow

Diagnosing a scheduling-related slowdown, a service that feels sluggish despite the box not being obviously overloaded, usually starts with distinguishing “not enough CPU” from “CPU available but scheduled poorly”:

$ vmstat 1
procs -----------memory---------- ---swap-- -----io---- --system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 12 0    0    812340  9821 442110    0    0     0     2 4210 9800 62 18  0  0  0

A high r (runnable) column relative to CPU core count means more tasks want to run than there are cores, real contention. A high cs (context switches per second) alongside modest CPU usage points at excessive switching overhead, sometimes from too many threads or too small a timer tick, rather than genuine compute demand.

$ pidstat -w 1        # per-process voluntary/involuntary context switches
$ top -H -p <pid>     # per-thread CPU usage within a single process
$ chrt -p <pid>       # inspect a process's current scheduling policy and priority

A process with a suspiciously high involuntary-switch count is being preempted a lot, worth checking if it’s fighting for CPU against a SCHED_FIFO/SCHED_RR task at a higher priority class, visible in ps -eo pid,cls,pri,cmd by looking for FF/RR in the CLS column.

Why It Matters

Directly determines user-perceived responsiveness versus raw throughput. Interactive desktop systems favor short quanta and priority boosts for I/O-bound tasks; batch and HPC systems favor longer quanta to reduce context-switch overhead.
Multi-core scheduling adds load balancing: the kernel must decide not just when a task runs but which core it runs on, migrating tasks between per-CPU run queues to avoid idle cores while minimizing cache-unfriendly migrations.
Real-time operating systems extend scheduling with deadline guarantees (Rate Monotonic Scheduling, Earliest Deadline First) that general-purpose schedulers like CFS don’t provide, because CFS optimizes for fairness, not hard timing deadlines.

Common Pitfalls

Starvation: low-priority tasks never run if higher-priority tasks keep arriving. Mitigated with aging, gradually raising the priority of tasks that have waited too long.
Priority inversion: a high-priority thread blocks on a resource held by a low-priority thread, while medium-priority threads preempt the low-priority holder and indirectly starve the high-priority thread. This caused the Mars Pathfinder’s watchdog-triggered resets, fixed in-flight via priority inheritance.
Picking too small a Round Robin quantum drowns actual work in context-switch overhead; picking too large a quantum makes RR degrade toward FCFS’s poor interactive responsiveness.
Treating a context switch as free. It flushes a large fraction of a core’s L1/L2 cache and TLB entries for the outgoing process, so switching too aggressively costs real throughput even though no scheduling policy explicitly “charges” for it.
Running latency-sensitive work at SCHED_OTHER and expecting real-time guarantees. Only SCHED_FIFO/SCHED_RR/SCHED_DEADLINE give preemption guarantees over normal tasks, and misusing them (a runaway SCHED_FIFO thread that never blocks) can starve the entire rest of the system, including the kernel’s own housekeeping threads.
Confusing “the scheduler picked this order” with “this order is guaranteed.” Scheduling decisions are advisory within a policy’s fairness/priority rules, not a guarantee about exact wall-clock timing, which is why busy-waiting on scheduling order instead of using proper synchronization is a reliability bug waiting to happen.

History

Linux used an O(1) scheduler (constant-time task selection via priority arrays) from the 2.6 kernel series before CFS. It was fast but its heuristics for distinguishing interactive from batch tasks were notoriously hard to tune correctly.
CFS replaced it in Linux 2.6.23 (2007), trading fixed priority arrays for the vruntime/red-black-tree fairness model, which sidestepped most of the O(1) scheduler’s interactivity heuristics entirely.
EEVDF landed in Linux 6.6 (2023), keeping CFS’s fairness goal but scheduling by virtual deadline instead of pure least-vruntime-first, improving latency for tasks that sleep briefly and wake up needing to run soon.

Linux Scheduling Policies Quick Reference

Policy	Class	Preemptible by higher policy	Selection basis
`SCHED_OTHER`	Normal (default)	Yes, by any real-time policy	CFS/EEVDF `vruntime`/virtual deadline
`SCHED_BATCH`	Normal	Yes	Like `SCHED_OTHER`, but discourages preemption for throughput
`SCHED_IDLE`	Normal	Yes	Runs only when nothing else is runnable
`SCHED_RR`	Real-time	By `SCHED_FIFO`/`SCHED_DEADLINE` or higher RT priority	Fixed priority, round-robin among equal priority
`SCHED_FIFO`	Real-time	By `SCHED_DEADLINE` or higher RT priority	Fixed priority, runs to completion/block
`SCHED_DEADLINE`	Real-time	No (highest)	Earliest Deadline First among deadline tasks

Comparison

Algorithm	Preemptive	Needs burst estimate	Starvation risk	Typical use
FCFS	No	No	Low	Simple batch queues
SJF / SRTF	Optional	Yes	High (long jobs)	Theoretical baseline, batch systems
Round Robin	Yes	No	Low	Time-sharing, interactive systems
Priority	Optional	No	High (without aging)	Real-time-ish workloads, needs aging
MLFQ	Yes	No	Low	General-purpose OS (approximates SJF)
CFS (Linux)	Yes	No	Low	Default Linux scheduler for normal tasks
Rate Monotonic	Yes	Yes (fixed period)	Low (bounded by utilization limit)	Hard real-time, periodic tasks
EDF	Yes	Yes (deadlines)	Low (up to 100% utilization)	Hard real-time, `SCHED_DEADLINE`

Example

Round Robin with a 4ms quantum scheduling three processes:

Ready queue (quantum=4ms): P1(burst=10) P2(burst=4) P3(burst=6)
t=0  : P1 runs 0-4ms  (6ms remaining)
t=4  : P2 runs 4-8ms  (0ms remaining, done)
t=8  : P3 runs 8-12ms (2ms remaining)
t=12 : P1 runs 12-16ms (2ms remaining)
t=16 : P3 runs 16-18ms (done)
t=18 : P1 runs 18-20ms (done)

P2 finishes fastest despite arriving after P1, because Round Robin bounds how long any one process can hold the CPU before yielding to the next. Tools like top and chrt on Linux let you observe and change a process’s scheduling policy and priority (SCHED_OTHER, SCHED_FIFO, SCHED_RR) directly. nice/renice adjust a SCHED_OTHER task’s weight within CFS/EEVDF without changing its policy, while chrt -f 50 ./program runs a process under the real-time SCHED_FIFO policy at priority 50.

FAQ

Does a higher nice value mean higher priority? No, it’s inverted. A lower nice value (down to -20) means higher priority and a larger CPU share; a higher nice value (up to 19) means lower priority. The name comes from “how nice this process is to others.”

Can a normal user process starve the kernel itself? Not directly. Kernel threads and interrupt handling run at a level the scheduler and hardware prioritize outside normal task scheduling, though a misbehaving SCHED_FIFO real-time thread that never blocks can still make a system unresponsive by never letting SCHED_OTHER tasks, including ones doing useful housekeeping, run at all.

Why doesn’t CFS use fixed time slices like Round Robin? A fixed slice size is a blunt tradeoff between fairness and overhead. CFS instead computes an ideal, continuously updated share of CPU time per task and lets scheduling granularity adapt to how many tasks are runnable, avoiding the need to hand-tune a single global quantum.

Referenced by

Dig deeper

Spot an error in this note?