Process Scheduling (CFS)

Eight CPU cores and two hundred processes that all want to run. Right now. The kernel has to pick one process per core, let it run for a while, yank it off, and give someone else a turn. It does this thousands of times per second, and most of the time nobody notices.

But then one day the interactive shell freezes for two seconds while a runaway make -j64 hogs every core. Or a Kubernetes pod runs at half the expected speed because it is being throttled by a cgroup limit nobody knew existed. That is when the scheduler stops being invisible and starts being the most important thing to understand.

What Actually Happens

When schedule() is called -- either because a timer tick fires, a task blocks, or a higher-priority task wakes up -- the scheduler does the following:

1. Checks scheduling classes in strict priority order: stop (kernel-internal), deadline, realtime, fair (CFS), idle.
2. For CFS, it picks the task with the lowest vruntime from a red-black tree. The leftmost node is cached, so this is O(1).
3. The selected task runs until one of three things happens: the timer tick updates its vruntime and finds someone else has lower vruntime, a newly woken task has lower vruntime, or the task blocks voluntarily.
4. The preempted task gets reinserted into the rb-tree at its new vruntime position.

How vruntime works. When a task runs for wall-clock time dt, its vruntime increases by dt * (weight_of_nice_0 / task_weight). A nice 0 task (weight 1024) running for 1ms gets 1ms of vruntime. A nice -5 task (weight ~3121) gets only ~0.33ms of vruntime for the same wall-clock time. It accumulates vruntime three times slower, so it stays near the left of the tree and gets three times more CPU.

The timer tick. scheduler_tick() fires at HZ frequency (typically 250Hz, meaning every 4ms). It updates the current task's vruntime and checks if another task should preempt. Between ticks, a newly woken task with lower vruntime can also trigger preemption.

Load balancing. CFS maintains per-CPU runqueues. Periodically (every ~4ms when idle, ~64ms when busy), the load balancer compares load across CPUs and migrates tasks from the busiest to the idlest. It considers NUMA topology, cache affinity, and power management.

Under the Hood

Scheduling classes hierarchy. Linux supports multiple scheduling classes, checked in strict priority order: stop_sched_class (kernel-internal, highest priority), dl_sched_class (SCHED_DEADLINE), rt_sched_class (SCHED_FIFO and SCHED_RR), fair_sched_class (CFS, for SCHED_NORMAL/SCHED_BATCH), and idle_sched_class (lowest). A runnable SCHED_FIFO task always preempts any CFS task. Always.

SCHED_DEADLINE. The most sophisticated scheduling policy, and the one most people have never heard of. It implements Earliest Deadline First (EDF) with Constant Bandwidth Server (CBS). A task declares three parameters: runtime (CPU time needed per period), period (how often), and deadline (when it must complete). The kernel performs an admission test to ensure all SCHED_DEADLINE tasks can meet their deadlines. Used for audio processing, robotics, and anything that needs hard real-time guarantees.

Autogroup scheduling. This is why the desktop stays responsive during make -j64. Enabled by default since kernel 2.6.38, autogroups place each TTY session in a separate CFS task group. The build gets one group's fair share. The interactive terminal gets another. 64 compiler processes compete among themselves, not with the shell.

EEVDF (Earliest Eligible Virtual Deadline First). Starting with kernel 6.6, CFS was replaced by EEVDF. It adds a "virtual deadline" concept to improve latency fairness. Tasks are eligible to run when their vruntime is at or below the queue's average, and among eligible tasks, the one with the earliest virtual deadline runs first. This reduces tail latency compared to pure vruntime-based scheduling.

Common Questions

How does CFS handle a newly forked task's vruntime?

A new task's vruntime is set to max(parent_vruntime, cfs_rq->min_vruntime). Setting it to min_vruntime prevents starvation of existing tasks -- a freshly forked process cannot jump to the front of the queue. The sched_child_runs_first sysctl can bias the parent to be preempted by the child, which is useful when the child immediately calls exec (avoids COW faults from the parent writing to shared pages).

What is the difference between voluntary and involuntary context switches?

Voluntary switches happen when a task blocks on I/O, a mutex, or sleep. Involuntary switches happen when the scheduler preempts a running task because another task with lower vruntime (or a higher priority class) is ready. A high involuntary switch count means CPU contention. Check with /proc/[pid]/status (voluntary_ctxt_switches, nonvoluntary_ctxt_switches) or perf stat.

How do cgroups interact with CFS?

With cgroups v2, each cgroup has a cpu.weight (1-10000, default 100) that determines its proportional share. The cgroup's sched_entity competes in the parent's CFS tree. cpu.max (quota/period) sets a hard bandwidth limit -- the cgroup gets throttled when it exceeds its quota. Throttling events show up in cpu.stat as nr_throttled and throttled_usec. This is exactly what Kubernetes uses when CPU limits are set.

Why might a SCHED_FIFO process not preempt a kernel thread?

Kernel threads running in critical sections with preemption disabled (preempt_disable()) cannot be preempted, even by SCHED_FIFO. Kernel threads handling softirqs or running in interrupt context also have implicit priority over all userspace tasks. The PREEMPT_RT patchset (being merged into mainline gradually since 5.x) converts most spinlocks to sleeping locks and makes most of the kernel fully preemptible.