Process Scheduling — The CFS

You might have 200 processes but only 8 CPU cores. The scheduler decides which process runs on which core at any given moment. Linux's scheduler, the CFS (Completely Fair Scheduler), uses a clever algorithm to share CPU time fairly.

The Scheduler's Job

What does the scheduler actually do? Every few milliseconds (or when a process sleeps or is preempted), the scheduler picks the "most deserving" process from the run queue and puts it on the CPU. It balances fairness (every process gets CPU time), responsiveness (interactive tasks feel snappy), and throughput (CPU-intensive work makes progress).

How CFS Works — vruntime

CFS tracks a number called vruntime (virtual runtime) for each process — how long it has run, weighted by priority. The core idea is simple:

Always run the process with the LOWEST vruntime.

When a process runs: its vruntime increases.
When a process sleeps: its vruntime stays frozen.
When it wakes: it has low vruntime, so it gets CPU soon.

Result: every process gets proportionally equal CPU time.

CFS uses a red-black tree (a self-balancing binary search tree) to store runnable processes, sorted by vruntime. The leftmost node (lowest vruntime) is always the next to run. Picking the next process is O(log n).

Priority and Weight

Not all processes are equal — nice values change how fast vruntime grows. A higher-priority process accumulates vruntime more slowly, so it gets scheduled more often.

Lower nice value (-20) = higher weight = vruntime grows slowly = more CPU
Higher nice value (+19) = lower weight = vruntime grows fast = less CPU

# A process with nice=-5 gets roughly twice the CPU of nice=0

Scheduling Policies

Policy	Who uses it	Behavior
SCHED_NORMAL	Regular processes	CFS — fair sharing, default
SCHED_BATCH	Background batch jobs	CFS with lower wakeup priority
SCHED_IDLE	Very low priority tasks	Only runs when nothing else wants CPU
SCHED_FIFO	Real-time tasks	Run until done or voluntarily yields. No preemption.
SCHED_RR	Real-time tasks	Like FIFO but with time slices — round-robin among equal priority
SCHED_DEADLINE	Time-critical tasks	Earliest Deadline First — guaranteed to complete before deadline

Real-time policies (FIFO, RR) always preempt NORMAL processes. Within RT, higher priority numbers run first.

Multi-CPU Scheduling

How does the scheduler handle multiple CPUs? Each CPU has its own run queue. A load balancer periodically checks if queues are uneven and migrates processes between CPUs. This is why binding a process to a specific CPU (CPU affinity) can sometimes improve performance — it avoids cache misses from migration.

# Bind process to CPU 0 and 1
taskset -cp 0,1 PID

# Start a command on specific CPUs
taskset -c 2,3 my-program

# Check current affinity
taskset -cp PID