Linux Beyond the Basics: CFS Scheduler

Ensuring Fairness and Responsiveness

This blog post is part of the series Linux Beyond the Basics.

Introduction

Linux is celebrated for its flexibility and performance. Beneath the surface, the scheduler, a pivotal component, meticulously manages the allocation of precious processor time among various processes competing for attention.

While Linux boasts an array of schedulers, the Completely Fair Scheduler (CFS) reigns supreme as the default for general-purpose computing. Let’s explore the essence of the CFS scheduler, its significance, its inner workings, and the role process priority plays in its operation.

What is the CFS?

At its core, the Completely Fair Scheduler (CFS) is a scheduling algorithm in the Linux kernel designed to provide a fair share of CPU time to every process running on the system. Its primary objective is to ensure that no single process monopolizes the CPU, starving others of their rightful share of resources.

Why Use CFS?

The CFS scheduler stands out for several compelling reasons:

• Fairness: It lives up to its name by meticulously distributing CPU time across all processes, preventing any single task from dominating the system.
• Responsiveness: The CFS is particularly adept at handling interactive applications, guaranteeing they remain responsive even under heavy system load. This is crucial for providing a smooth and seamless user experience.
• Scalability: It gracefully manages systems with multiple CPU cores, efficiently distributing processes across them to maximize utilization and prevent any single core from becoming overwhelmed.

How CFS Works

The CFS orchestrates its scheduling magic by maintaining a virtual timeline known as the “Red-Black Tree”. Each process running on the system is represented by a node in this tree, and its position is determined by its virtual runtime. Processes with lower virtual runtimes are deemed to have received less CPU time and are, therefore, given higher priority.

The scheduler’s primary goal is to keep the virtual runtimes of all processes as close as possible, ensuring that each process receives its equitable portion of CPU cycles. It achieves this by periodically selecting the process with the lowest virtual runtime from the Red-Black Tree and granting it a time slice on the CPU.

CFS and Process Priority

While the CFS strives for fairness, it also allows for some level of prioritization through the concept of nice values. Each process is assigned a nice value, ranging from -20 (highest priority) to 19 (lowest priority). The default nice value is 0.

The nice value influences a process’s virtual runtime calculation. Processes with lower nice values (higher priority) have their virtual runtimes artificially decreased, making them appear as if they’ve received less CPU time than they actually have. Consequently, they are more likely to be selected for execution by the CFS scheduler.

Conversely, processes with higher nice values (lower priority) have their virtual runtimes artificially increased, making them appear as if they’ve received more CPU time. This reduces their chances of being scheduled, effectively giving them a smaller share of the CPU.

It is important to note that nice values provide relative prioritization. A process with a nice value of 0 will still receive a fair share of CPU time, but it will be given preference over processes with higher nice values.

CFS and Priority inversion

Priority inversion is a classic scheduling problem where a high-priority process is indirectly blocked by a lower-priority process. This typically occurs when the lower-priority process holds a shared resource (like a lock) that the high-priority process needs to proceed.

The CFS scheduler, with its focus on fairness, can be susceptible to priority inversion if not managed carefully. If a low-priority process holds a lock that a high-priority process requires, the high-priority process might be forced to wait, even though it should ideally be given precedence.

Linux provides mechanisms like priority inheritance to mitigate priority inversion. With priority inheritance, when a low-priority process holds a lock needed by a high-priority process, the low-priority process temporarily inherits the priority of the high-priority process. This ensures that the low-priority process completes its task quickly, releasing the lock and allowing the high-priority process to continue.

CFS and Cgroups

Cgroups (Control Groups) is a Linux kernel feature that allows you to partition sets of processes into hierarchical groups and apply resource limits and constraints to them. CFS integrates seamlessly with Cgroups to provide fine-grained control over CPU resource allocation.

When Cgroups are in use, the CFS scheduler doesn’t just consider individual processes; it also takes into account the Cgroups to which they belong. Each Cgroup can be assigned a specific proportion of CPU resources, ensuring that the processes within that group receive their allocated share, regardless of the overall system load.

This integration empowers system administrators and developers to create isolated environments with guaranteed resource allocations. For example, you can create a Cgroup for critical system services and allocate them a higher proportion of CPU resources, ensuring their responsiveness even under heavy load from other applications.

Example: Interactive vs. Batch Processes

Let’s use a practical example to understand how the CFS scheduler works. Imagine you’re simultaneously running a web browser (an interactive application) and a computationally intensive video encoding task (a batch process). The CFS recognizes the critical importance of responsiveness for interactive applications.

Here’s how it ensures the web browser remains responsive:

1. Virtual Runtime Dynamics: The web browser, being interactive, often spends periods idle, awaiting user input (mouse clicks, keystrokes, etc.). During these idle periods, its virtual runtime doesn’t increase significantly. On the other hand, the video encoding task relentlessly utilizes the CPU, causing its virtual runtime to escalate rapidly.
2. Prioritizing Interactivity: The CFS scheduler periodically examines the Red-Black Tree and selects the process with the lowest virtual runtime to execute next. Since the web browser’s virtual runtime remains relatively low due to its idle periods, it is frequently chosen for execution when it needs the CPU, even if only for brief intervals.
3. The Illusion of Responsiveness: These frequent, though short, time slices enable the web browser to promptly handle user input, creating the perception of snappiness and responsiveness. Meanwhile, the video encoding task, while experiencing slight delays, continues to make steady progress in the background.

Takeaway

The Completely Fair Scheduler is a crucial component of the Linux kernel, ensuring equitable and efficient CPU time allocation. Its design philosophy prioritizes fairness and responsiveness, making it an ideal choice for general-purpose computing. Understanding the CFS, including its strengths, limitations, and the role of process priority, helps us appreciate the intricacies of Linux’s resource management and gain insights into its overall performance.