Linux - Scheduler

In the Linux kernel, the scheduler is the component responsible for deciding which process (or thread) gets to use the CPU, for how long, and when.

Because a computer often has hundreds of tasks running but only a limited number of CPU cores, the scheduler must rapidly switch between tasks to give the illusion that everything is running simultaneously.

The Core Objectives

The Linux scheduler tries to balance several competing goals:

• Fairness: Every process should get a fair share of CPU time.
• Throughput: Maximize the total amount of work the system completes.
• Latency/Responsiveness: Ensure interactive tasks (like moving a mouse or typing) react instantly.
• Efficiency: Minimize the "overhead" (the CPU time spent deciding what to do next rather than doing actual work).

Evolution of Schedulers

Linux has used several different scheduling algorithms over the decades:

A. The O(1) Scheduler (Kernel 2.6.0 to 2.6.22)

• How it worked: It used a constant-time algorithm, meaning it took the same amount of time to pick a task regardless of how many tasks were running.
• The Problem: While great for servers, it was bad at identifying "interactive" tasks, leading to a "laggy" feel on desktop computers.

B. The Completely Fair Scheduler (CFS) (Kernel 2.6.23 to 6.5)

• How it works: Instead of fixed time slices, CFS uses a "Red-Black Tree" to track vruntime (virtual runtime). The task that has had the least amount of time on the CPU is placed at the left of the tree. The scheduler always picks the leftmost task.
• Concept: It models a "perfect, ideal multi-tasking CPU" where every process gets $1/N$ of the power.

C. EEVDF Scheduler (Kernel 6.6+)

• The New Standard: As of late 2023, Linux began replacing CFS with EEVDF (Earliest Eligible Virtual Deadline First).
• Why? CFS was fair but struggled with "latency." EEVDF allows processes to request a specific "deadline," helping tasks that need quick bursts of CPU (like audio processing or video games) without hurting overall fairness.

Scheduling Classes (Policies)

Linux doesn't treat all processes the same. It uses "Scheduling Classes" to categorize them:

Normal Policies (For most apps)

• SCHED_OTHER (or SCHED_NORMAL): The default for almost everything (web browsers, compilers, etc.). It uses the CFS/EEVDF logic.
• SCHED_BATCH: For non-interactive, CPU-heavy jobs. It assumes the task won't need to respond to user input, so it allows the task to run longer to improve cache efficiency.
• SCHED_IDLE: For extremely low-priority tasks (like background system cleanup) that should only run if the CPU is completely empty.

Real-Time Policies (For critical tasks)

• SCHED_FIFO (First-In, First-Out): A high-priority task runs until it either finishes or voluntarily gives up the CPU. It will pre-empt (kick off) any normal task.
• SCHED_RR (Round Robin): Similar to FIFO, but if multiple tasks have the same priority, they rotate.
• SCHED_DEADLINE: The most powerful. The task tells the kernel: "I need $X$ amount of CPU time every $Y$ milliseconds." The kernel guarantees it will happen.

Important Concepts

Nice Values

Users can influence the scheduler using a "Nice" value, ranging from -20 (highest priority) to 19 (lowest priority).

• A "nice" process is polite; it lets others go first.
• A "negative nice" process is selfish and grabs more CPU time.

Preemption

Linux is a preemptive kernel. This means if a high-priority task suddenly becomes ready (e.g., data arrives from the internet), the scheduler can forcibly stop the currently running lower-priority task to let the important one run.

CPU Affinity

The scheduler tries to keep a process on the same CPU core where it last ran. This is because that core's L1/L2 Cache likely still contains the process's data. Moving it to a different core (migrating) causes a performance hit.

How to see/manage the scheduler

If you want to see how your Linux system is handling scheduling, you can use these commands:

• top or htop: See the "NI" (Nice) and "PR" (Priority) columns.
• chrt: View or change the real-time attributes of a process.
  • Example: chrt -p 1234 (Shows the policy of process 1234).
• renice: Change the priority of a process while it is running.
  • Example: renice +10 -p 1234 (Makes process 1234 lower priority).
• taskset: Force a process to run on a specific CPU core (CPU Affinity).