CPU Scheduling

A modern NVMe SSD delivers a read in roughly 100 microseconds. A CPU executes roughly 3 billion instructions per second. In the time a process waits for one disk read, the CPU could have executed 300,000 instructions for something else. This gap — between CPU speed and the speed of everything outside it — is the entire motivation for scheduling.

Without scheduling, the naive approach is to let a process run until it either finishes or explicitly yields. This is called bare-metal or single-tasking execution (think MS-DOS). The CPU sits idle during every I/O wait. With scheduling, the OS detects that a process is blocked waiting for I/O, yanks it off the CPU, and hands the CPU to another runnable process. When the I/O completes, the blocked process becomes runnable again and will eventually get the CPU back.

This is the fundamental abstraction: the OS creates the illusion that each process has its own dedicated CPU, even though the hardware has only one (or a few). The mechanism that makes this work is the context switch — saving the full CPU state of the outgoing process (registers, program counter, stack pointer, page table base) and restoring the state of the incoming process. To the processes, nothing happened; to the CPU, it was running someone else for a while.

Analogy: Think of a single chef (CPU) in a kitchen. Instead of standing idle while a pot boils (I/O wait), a good chef context-switches: starts the pasta water, then chops vegetables while it heats, then stirs the sauce. The chef is nearly always doing something useful. The OS is the head chef who decides what task gets the chef's hands at each moment.

Before we can schedule processes, we need to understand what states they can be in. A process is not simply 'running' or 'not running' — it has a lifecycle:

• RUNNING: Currently executing on a CPU core.
• RUNNABLE (READY): Has everything it needs to run; just waiting for the CPU.
• BLOCKED (SLEEPING): Waiting for an event — disk I/O completion, a mutex, a timer, a network packet. Cannot use the CPU even if offered it.
• ZOMBIE: Finished executing, waiting for its parent to collect its exit code.

The scheduler's job is to manage the set of RUNNABLE processes, called the run queue (or ready queue). It selects one of them, calls context_switch(), and hands over the CPU. When a running process calls read() on a file, the kernel moves it from RUNNING to BLOCKED and runs the scheduler to pick the next RUNNABLE process. When the I/O completes, an interrupt fires, the kernel moves the process back to RUNNABLE, and it re-enters the run queue.

In Linux, process state is stored in the task_struct at field __state. The relevant values are TASK_RUNNING (meaning runnable or actually running — Linux combines these two into one state), TASK_INTERRUPTIBLE (sleeping, can be woken by signals), TASK_UNINTERRUPTIBLE (sleeping, cannot be interrupted — this is the 'D' state you see in ps), and TASK_ZOMBIE.

The run queue in the CFS scheduler is not a simple list — it is a red-black tree ordered by a 'virtual runtime' value. But the conceptual model — a queue of 'who's ready to run' — is universal across all scheduler designs.

/* Simplified: what the kernel does when a syscall blocks */
void do_blocking_read(struct file *f) {
    /* Mark current task as sleeping */
    set_current_state(TASK_INTERRUPTIBLE);

    /* Add a wait entry so the I/O completion IRQ can wake us */
    add_wait_queue(&f->wait_queue, &wait);

    /* Voluntarily give up the CPU — triggers scheduler */
    schedule();

    /* We only get here after an interrupt woke us.
     * Our state is back to TASK_RUNNING. */
    remove_wait_queue(&f->wait_queue, &wait);
}

There are two fundamental philosophies about when a process loses the CPU.

Cooperative (non-preemptive) scheduling: The running process keeps the CPU until it voluntarily yields — either by calling a blocking syscall, calling sched_yield(), or exiting. The OS never forcibly removes it. This was the model used by early Mac OS (System 1–9) and Windows 3.x. It is simple and requires no hardware timer interrupts. The fatal flaw: a buggy or malicious process can hog the CPU forever. One runaway loop and the whole system freezes.

Preemptive scheduling: The OS sets a hardware timer (the preemption timer or scheduling clock) to fire at a fixed interval — typically 1–10 milliseconds on modern Linux (the HZ kernel config parameter, e.g. CONFIG_HZ_1000 = 1000 interrupts/second = 1ms tick). When the timer fires, an interrupt transfers control to the kernel's timer interrupt handler. The handler checks: has the current process used up its time slice? If yes, it sets a need_resched flag. At the next safe point (interrupt return, or syscall return), the scheduler runs and may switch to another process.

The key insight is that preemption requires no cooperation from the process being preempted. Even an infinite loop while(1){} will be preempted. This is essential for interactive responsiveness — your video call's audio thread gets its turn even if your browser's JavaScript engine is busy.

Kernel preemption is a separate (more subtle) concept: whether the kernel itself can be preempted while running on behalf of one process to handle another. CONFIG_PREEMPT enables this in Linux. Without kernel preemption, a process running in kernel mode (e.g., inside a syscall) runs to completion before another task can run, which increases worst-case latency. CONFIG_PREEMPT_RT (the real-time patch) takes this further, converting almost all spinlocks to sleeping locks to achieve microsecond-range latencies.

/* Cooperative yield — voluntary CPU release */
#include <sched.h>

void cooperative_worker(void) {
    while (1) {
        do_some_work();
        /* Politely tell the scheduler:
         * "I'm done with my current burst, reschedule me" */
        sched_yield();
    }
}

/* On Linux, check if kernel preemption is enabled */
/* $ grep CONFIG_PREEMPT /boot/config-$(uname -r)
   CONFIG_PREEMPT=y   <- voluntary preemption
   CONFIG_PREEMPT_RT  <- full real-time preemption */

There is no single 'best' scheduler because different workloads care about different things. Before comparing algorithms, you must know what you are optimizing for:

Throughput: Jobs completed per unit time. A batch compute cluster running genomics pipelines wants to maximize this. It does not care if any individual job starts a bit later.

Turnaround time: Time from job arrival to job completion = waiting time + execution time. Minimizing average turnaround is often the goal for batch systems.

Response time / latency: Time from a request being issued to the first response being produced. Interactive applications (terminals, GUI apps, games, audio) are extremely sensitive to this. A keystroke that takes 200ms to echo feels broken.

Fairness: Every process (or every user) gets an equitable share of the CPU over time. Fairness does not mean equal shares — it means proportional to each task's weight/priority.

CPU utilization: Fraction of time the CPU is doing useful work (not idle). For server workloads, you want this close to 100%. For laptops, high utilization = high power draw.

Starvation-freedom: A low-priority process must eventually get the CPU, even under heavy load from high-priority processes. Starvation (a process waiting forever) is a liveness violation — a correctness bug, not just a performance bug.

These goals are often in tension. Maximizing throughput often means running long jobs without interruption (poor response time). Maximizing responsiveness often means short time slices (more context switches = overhead = lower throughput). A real OS scheduler, like Linux CFS, is an engineered compromise that navigates these trade-offs based on a scheduling policy.

First-Come, First-Served (FCFS): The simplest scheduler imaginable. Processes are run in the order they arrive. Non-preemptive. Easy to implement (a FIFO queue). The problem: the convoy effect. One long job at the head of the queue blocks all shorter jobs behind it. If a 30-second CPU-bound job arrives just before ten 100ms interactive jobs, those interactive jobs wait 30 seconds before getting any CPU.

Shortest Job First (SJF) / Shortest Remaining Time First (SRTF): Instead of FIFO order, always run the job with the shortest expected execution time. This is provably optimal for minimizing average turnaround time (among non-preemptive algorithms). The preemptive variant (SRTF) is optimal for average turnaround period.

The fatal flaw of SJF: you cannot know in advance how long a job will run. In the real world, you can only estimate. One common approach is exponential averaging: predict the next burst length as a weighted average of all past bursts. If past bursts were [10ms, 8ms, 12ms, ...], you extrapolate. But this is an estimate — a misbehaving job can blow past its predicted burst.

Another flaw: SJF can starve long jobs. If short jobs keep arriving, a long job may wait forever. In practice, SJF/SRTF is used mostly in batch systems where job lengths are known ahead of time (e.g., from a job submission manifest).

These two algorithms are the foundation from which every real scheduler departs. FCFS fails on latency; SJF fails on predictability and fairness. The algorithms that follow try to get the best of both worlds.

/* Simulate FCFS: jobs arrive at t=0, run in arrival order */
#include <stdio.h>

typedef struct { int id; int burst; } Job;

void fcfs(Job jobs[], int n) {
    int time = 0;
    for (int i = 0; i < n; i++) {
        int wait   = time;              /* waited since arrival */
        int finish = time + jobs[i].burst;
        int turnaround = finish;        /* arrival was t=0 */
        printf("Job %d: wait=%d turnaround=%d\n",
               jobs[i].id, wait, turnaround);
        time = finish;
    }
}

int main(void) {
    /* Three jobs: short, long, short — demonstrates convoy effect */
    Job jobs[] = {{1, 2}, {2, 20}, {3, 2}};
    fcfs(jobs, 3);
    /* Output:
       Job 1: wait=0  turnaround=2
       Job 2: wait=2  turnaround=22   <- long job
       Job 3: wait=22 turnaround=24   <- short job waited 22ms! */
}

Round Robin (RR) is the quintessential preemptive scheduler. Each process gets a fixed time slice (also called a quantum or time quantum) — say, 10ms. When the slice expires, the process is moved to the back of the ready queue and the next process runs. No process can monopolize the CPU; everyone gets a turn.

RR is excellent for response time. If there are N processes and the quantum is q, the worst-case wait before getting the CPU is (N-1) * q. With 10 processes and a 10ms quantum, you wait at most 90ms — acceptable for interactive use.

The quantum size is a critical tuning knob:

• Too small (e.g., 1ms): Context switches happen constantly. Each switch takes 1–10 microseconds of overhead (saving/restoring registers, flushing TLB entries, cache warming). With a 1ms quantum, you might spend 1% of CPU time on context switches — significant. Worse, cache thrashing: each new process pollutes the CPU cache with its working set, slowing everyone down.
• Too large (e.g., 100ms): RR degenerates toward FCFS. Response time suffers.

Typical values: Linux historically used 100ms quanta (HZ=100 era). Modern Linux with CONFIG_HZ_1000 has a 1ms timer tick but the scheduler tick and actual quantum are more complex — CFS does not use fixed quanta at all.

RR has worse turnaround than SJF (because long jobs get interrupted repeatedly) but much better response time for interactive tasks. It is fair by construction: over any window of N*q ms, every process gets exactly q ms of CPU — true fairness.

The weighted variant assigns each process a weight (priority). Higher-weight processes get proportionally larger shares. This is the direct conceptual ancestor of Linux's nice value and CFS's weight table.

/* Simulate Round Robin with quantum=4 for three jobs */
#include <stdio.h>
#include <string.h>

void round_robin(int bursts[], int n, int quantum) {
    int remaining[n];
    memcpy(remaining, bursts, n * sizeof(int));
    int time = 0, done = 0;
    while (done < n) {
        for (int i = 0; i < n; i++) {
            if (remaining[i] <= 0) continue;
            int run = remaining[i] < quantum ? remaining[i] : quantum;
            printf("t=%2d  run P%d for %dms\n", time, i+1, run);
            time += run;
            remaining[i] -= run;
            if (remaining[i] == 0) {
                printf("      P%d finished at t=%d\n", i+1, time);
                done++;
            }
        }
    }
}

int main(void) {
    int bursts[] = {10, 4, 6};  /* P1=10ms P2=4ms P3=6ms */
    round_robin(bursts, 3, 4);
}

Every real OS lets you assign a priority to a process. The scheduler always picks the highest-priority runnable process. Linux uses two priority scales:

1. Nice values (-20 to +19): A user-space hint. Lower nice = higher priority. nice -n -10 ./myprogram runs a program with elevated priority. Root is needed to go below 0. The default nice is 0.
2. Real-time priorities (1–99 in SCHED_FIFO/SCHED_RR): Completely separate from nice. Real-time tasks always preempt normal tasks.

Priority scheduling is powerful but introduces a dangerous pathology: starvation. If high-priority tasks keep arriving, a low-priority task may never run. In a busy server, a background job at nice +19 might wait minutes for CPU time.

Priority inversion is an even nastier bug. Imagine three tasks: H (high priority), M (medium), L (low). L holds a mutex. H needs that mutex and blocks. M is now the highest runnable task and preempts L, preventing L from releasing the mutex, which prevents H from running. H is effectively blocked by M, even though M has lower priority than H. This bug caused the Mars Pathfinder spacecraft to reset repeatedly in 1997 (it ran VxWorks with priority inversion in a bus mutex).

The fix is priority inheritance: when H blocks on a mutex held by L, temporarily elevate L's priority to H's level so it can finish and release the mutex. Linux's PTHREAD_PRIO_INHERIT mutex protocol implements this.

Aging is the standard starvation fix: gradually increase the priority of waiting tasks over time. If a task has been waiting 10 seconds, bump its effective priority up by 1. This guarantees eventual execution.

#include <pthread.h>
#include <stdio.h>

/* Using priority-inheriting mutex to prevent priority inversion */
int main(void) {
    pthread_mutex_t mutex;
    pthread_mutexattr_t attr;

    pthread_mutexattr_init(&attr);
    /* PTHREAD_PRIO_INHERIT: if a high-prio thread blocks on this
     * mutex, the low-prio holder gets its priority temporarily raised */
    pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
    pthread_mutex_init(&mutex, &attr);
    pthread_mutexattr_destroy(&attr);

    /* Now use mutex normally — inversion is prevented automatically */
    pthread_mutex_lock(&mutex);
    /* ... critical section ... */
    pthread_mutex_unlock(&mutex);
    pthread_mutex_destroy(&mutex);
    return 0;
}

MLFQ is the most important scheduler design to understand before studying CFS. It was first described by Corbató et al. in 1962 for the Compatible Time-Sharing System (CTSS) at MIT — one of the most influential papers in OS history. The insight: we want SJF's low turnaround time, but we cannot know job lengths in advance. What if we learn job behavior at runtime?

The rules:

1. There are N queues, each with a different priority (Q0 = highest, QN-1 = lowest).
2. A job starts in Q0 (highest priority, smallest quantum).
3. If a job uses its entire quantum without blocking, it gets demoted to the next lower queue (suspicion: CPU-bound long job).
4. If a job blocks before its quantum expires (e.g., it did I/O), it stays in its current queue (good behavior: interactive/short job).
5. The scheduler always picks from the highest non-empty queue.
6. Periodically (every S seconds), all jobs are boosted back to Q0 (prevents starvation and adapts to changing behavior).

The elegance: a short interactive job (like a keystroke handler) naturally stays in Q0, getting excellent response time. A long CPU-bound job sinks to low-priority queues, getting large quanta (efficient for throughput) but low priority. A process that starts CPU-bound but later becomes interactive will rise in priority after a boost.

MLFQ is essentially a heuristic approximation of SJF using recent history as a proxy for future behavior. It is not perfect — a CPU-bound process that carefully yields just before its quantum expires can game the system (the fix: track total CPU time used, not just per-slice usage).

Linux's O(1) scheduler (2.6.0–2.6.22) was an MLFQ variant with 140 priority levels and two arrays (active/expired). CFS replaced it, but the MLFQ insight — use execution history to infer job type — lives on in the scheduler's handling of wakeup bonuses and sleep-time tracking.

What does it mean for a scheduler to be fair? The formal definition is: given N processes with equal priority, each should receive exactly 1/N of the CPU over any sufficiently long interval.

The Ideal Fair Scheduler (a theoretical construct) runs all N processes simultaneously, each at 1/N speed. Every process advances at the same rate. Obviously impossible on a single CPU — you can only run one process at a time. But you can approximate this ideal by keeping careful track of how much CPU time each process has received and always scheduling the process that is furthest behind.

This is exactly what CFS does, via the concept of virtual runtime (vruntime). When a process runs, its vruntime increases. The amount it increases per real-time nanosecond is inversely proportional to its weight (priority). A high-priority (low nice) process's vruntime grows slowly; a low-priority process's vruntime grows quickly. The scheduler always picks the process with the smallest vruntime — the one that is furthest behind its fair share.

CFS stores all runnable processes in a red-black tree keyed by vruntime. The leftmost node (smallest vruntime) is the next process to run. Insertion, deletion, and min-lookup are all O(log N). This is why CFS is scalable to thousands of concurrent processes.

The target latency (default ~6ms, tunable via /proc/sys/kernel/sched_latency_ns) is the scheduling period within which every runnable process should get at least one turn. With N processes, each gets target_latency / N per period. But there is a floor: minimum granularity (default 0.75ms) prevents the slice from becoming so small that context-switch overhead dominates.

/* Inspect CFS parameters on your Linux system */
/* Run these in a terminal: */

// cat /proc/sys/kernel/sched_latency_ns
// -> e.g., 6000000  (6ms target scheduling latency)

// cat /proc/sys/kernel/sched_min_granularity_ns
// -> e.g., 750000   (0.75ms minimum time slice)

// cat /proc/sys/kernel/sched_wakeup_granularity_ns
// -> e.g., 1000000  (wakeup preemption threshold)

/* View vruntime and scheduling info for all tasks: */
// cat /proc/sched_debug  (requires root or CAP_SYS_ADMIN)

/* Check nice value of your shell: */
// ps -o pid,ni,comm -p $$

A context switch is not free. Understanding its cost is critical for reasoning about scheduler overhead.

Direct cost: Saving and restoring the CPU state. This includes general-purpose registers (~16 on x86-64), floating-point/SIMD registers (the xsave/xrestore instruction, which can save 512–2048 bytes of state), the program counter, stack pointer, and segment registers. The OS also switches the page table (by writing to CR3 on x86-64 or TTBR0/TTBR1 on ARM64). Writing CR3 invalidates the TLB (Translation Lookaside Buffer) — the hardware cache that translates virtual addresses to physical addresses. Post-switch, every memory access that misses the TLB requires a slow page table walk (hundreds of nanoseconds each).

Indirect cost (cache pollution): The outgoing process had its working set loaded in L1/L2/L3 cache. The incoming process has a cold cache. For a process with a large working set, the first few milliseconds after a context switch are dominated by cache misses. Benchmarks show that context switch overhead can range from a few microseconds (for tiny working sets) to hundreds of microseconds (for cache-thrashing workloads).

ASID (Address Space Identifier): Modern CPUs can tag TLB entries with an ASID, so switching from process A to process B does not necessarily flush A's TLB entries — they remain tagged and usable when A runs again. Linux uses ASIDs on x86-64 (since 4.14) and ARM64, dramatically reducing context switch cost for frequently-switched processes.

Measuring context switch overhead:

$ sudo perf stat -e context-switches,cache-misses,instructions -- stress -c 8 -t 5

This shows you context switches and cache misses caused by 8 CPU-saturating threads competing on your machine.

The practical lesson: fewer, longer time slices reduce context switch overhead but hurt interactivity. More, shorter slices improve responsiveness but incur overhead. CFS's adaptive quantum (proportional to N active tasks) is the principled middle ground.

/* Measure context switch time with two ping-pong threads */
#include <pthread.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>

#define ITERS 100000

pthread_mutex_t m1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t m2 = PTHREAD_MUTEX_INITIALIZER;

void *thread_b(void *arg) {
    for (int i = 0; i < ITERS; i++) {
        pthread_mutex_lock(&m1);    /* wait for A's signal */
        pthread_mutex_unlock(&m2); /* signal A */
    }
    return NULL;
}

int main(void) {
    pthread_t t;
    pthread_mutex_lock(&m2); /* pre-lock so B can't proceed yet */
    pthread_create(&t, NULL, thread_b, NULL);

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int i = 0; i < ITERS; i++) {
        pthread_mutex_unlock(&m1); /* wake B */
        pthread_mutex_lock(&m2);  /* wait for B -> context switch */
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);

    long ns = (t1.tv_sec - t0.tv_sec) * 1000000000L
            + (t1.tv_nsec - t0.tv_nsec);
    printf("Avg context switch: %ld ns\n", ns / (2 * ITERS));
    pthread_join(t, NULL);
}

Linux supports multiple scheduling classes with strict priority ordering. From highest to lowest: stop (migration), deadline (SCHED_DEADLINE), real-time (SCHED_FIFO, SCHED_RR), and normal (SCHED_OTHER/CFS, SCHED_IDLE).

SCHED_FIFO (First-In, First-Out real-time): A SCHED_FIFO task with real-time priority P runs until it either blocks or explicitly yields. It is never preempted by any task with equal or lower RT priority. If you have two SCHED_FIFO tasks at the same priority, they share the CPU cooperatively (the one that was runnable first goes first). This is used for hard real-time tasks like audio/video mixing daemons (PulseAudio, JACK).

SCHED_RR (Round Robin real-time): Like SCHED_FIFO but with a fixed quantum. Processes at the same RT priority share the CPU in round-robin fashion. Combines predictability with fairness among equal-priority RT tasks.

SCHED_DEADLINE (Earliest Deadline First): The most sophisticated Linux RT policy. You specify three parameters: runtime, period, and deadline. The scheduler guarantees the task gets runtime nanoseconds of CPU within each period, meeting its deadline. This is the CBS (Constant Bandwidth Server) algorithm, suitable for tasks with hard real-time requirements.

Warning: A SCHED_FIFO task at RT priority 99 can starve the entire system, including the kernel's watchdog. On a uniprocessor system, a SCHED_FIFO task in an infinite loop will hang the machine. The kernel sets aside 5% CPU time for non-RT tasks by default (/proc/sys/kernel/sched_rt_runtime_us).

To set RT scheduling: chrt -f 50 ./my_rt_task (requires CAP_SYS_NICE or appropriate rlimits).

#include <sched.h>
#include <stdio.h>
#include <string.h>

int main(void) {
    struct sched_param sp;
    memset(&sp, 0, sizeof(sp));
    sp.sched_priority = 50;  /* RT priority 1-99 */

    /* Switch THIS process to SCHED_FIFO RT scheduling.
     * Requires CAP_SYS_NICE (run as root or set rlimit). */
    if (sched_setscheduler(0, SCHED_FIFO, &sp) == -1) {
        perror("sched_setscheduler");
        return 1;
    }
    printf("Now running as SCHED_FIFO priority 50\n");
    /* From here: never preempted by any task with priority < 50.
     * Make sure to block on I/O or yield, or you'll starve others. */
    return 0;
}

Theoretical understanding is only half the story. Real kernel engineers use tools to observe the scheduler in action. This is how you move from textbook to production.

perf sched: The premier Linux scheduler analysis tool. perf sched record captures a trace of every context switch and wakeup; perf sched latency shows per-task scheduling latency statistics; perf sched timehist draws a timeline of which task ran on which CPU when. These tools reveal priority inversions, scheduling jitter, and starvation in real workloads.

ftrace / trace-cmd: The kernel's built-in tracer. echo 1 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable records every context switch with nanosecond timestamps, old and new process names, and states. This is what the kernel developers themselves use.

/proc/[pid]/sched: Per-process scheduling statistics — wait time, number of migrations, involuntary context switches. cat /proc/self/sched to see your current shell's stats.

schedtool: Inspect and set scheduling policy/priority for any process.

stress-ng --sched: Generates synthetic scheduler load for benchmarking.

When you read scheduler patches on LKML, you will often see performance data from these tools. Learning to use them is a direct path to being able to contribute scheduler patches — because any change must be backed by measurement data showing improvement without regression.

#!/bin/bash
# Observe scheduler activity on your system

# 1. Record 5 seconds of scheduler events
sudo perf sched record -- sleep 5

# 2. Show per-task scheduling latency
sudo perf sched latency

# 3. Enable sched_switch ftrace events (requires root)
sudo sh -c '
  echo 1 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable
  sleep 1
  echo 0 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable
  cat /sys/kernel/debug/tracing/trace | head -50
'

# 4. See your shell process's scheduling stats
cat /proc/$$/sched

# 5. Check the current scheduler policy for a process
chrt -p $$