Process Scheduling Algorithm in Operating Systems: Completely Fair Scheduler (CFS)

Process Scheduling Algorithm in Operating Systems: Completely Fair Scheduler (CFS)

1. Problem Description

The Completely Fair Scheduler (CFS) is the default process scheduling algorithm in the Linux kernel. Its core goal is to fairly allocate CPU time to all runnable processes while maintaining good responsiveness for interactive processes. Unlike traditional schedulers based on time-slicing or priority levels, CFS quantifies a process's CPU usage via virtual runtime (vruntime) and selects the process with the smallest vruntime for execution, aiming to achieve "complete fairness."

2. Core Philosophy: Fairness and Trade-offs

The design of CFS must address two key issues:

  1. How to define fairness?
    • Ideally, each process should receive an equal share of CPU time (e.g., with n processes, each gets 1/n of the CPU time).
    • However, process priorities must be considered (higher-priority processes should receive more resources).
  2. How to avoid frequent switching?
    • Excessive scheduling frequency leads to context switch overhead, while too low a frequency reduces responsiveness.

3. Key Mechanism: Virtual Runtime (vruntime)

(1) Calculation of vruntime

  • Each process has a vruntime variable, which records its "consumed CPU time" weighted by its priority.
  • Formula:

\[ \text{vruntime} = \text{actual runtime} \times \frac{\text{base priority weight}}{\text{process priority weight}} \]

  • Priority Weight: In Linux, priorities (0~139) are mapped to weight values, with higher priorities corresponding to larger weights.
  • Effect: The vruntime of high-priority processes increases slower, while that of low-priority processes increases faster, thereby allowing high-priority processes to receive more CPU time.

(2) Illustrative Example

Assuming the system's base weight is 1024:

  • Process A (high priority, weight=2048): After running for 1 second, its vruntime increases by \(1 \times \frac{1024}{2048} = 0.5\) seconds.
  • Process B (low priority, weight=512): After running for 1 second, its vruntime increases by \(1 \times \frac{1024}{512} = 2\) seconds.
  • Scheduling Policy: Select the process with the smallest vruntime for execution. Thus, Process A's vruntime grows slower, making it more likely to be scheduled again.

4. Data Structure: Red-Black Tree

CFS uses a red-black tree to maintain the ordering of runnable processes by vruntime:

  • Key Value: The process's vruntime.
  • Minimum Node: The leftmost node in the tree is the process with the smallest vruntime, i.e., the next process to be scheduled.
  • Operational Efficiency: Insertion, deletion, and finding the minimum node all have a time complexity of O(log n), efficiently supporting a large number of processes.

5. Detailed Scheduling Process

(1) Scheduling Trigger Events

  • A process voluntarily relinquishes the CPU (e.g., waiting for I/O).
  • A timer interrupt (periodically checks if a process switch is needed).
  • A new process is created or woken up.

(2) Scheduling Decision

  1. Select the process with the smallest vruntime from the red-black tree.
  2. Calculate the actual runtime for this process:
    • CFS sets a target latency (sched_latency, default 6ms), representing the time within which all runnable processes should run at least once.
    • Each process's time slice = sched_latency / n (where n is the number of processes).
    • If there are too many processes, to ensure responsiveness, the minimum time slice is min_granularity (default 0.75ms).

(3) vruntime Initialization for New Processes

  • To prevent a new process's vruntime from being much smaller than that of older processes (which could lead to CPU monopolization), the new process's vruntime is initialized to the current minimum vruntime in the red-black tree.

6. Optimizations for Interactive Processes

  • Sleep Bonus: If a process sleeps due to I/O operations, upon wakeup, its vruntime is appropriately reduced, making it more likely to be scheduled and improving responsiveness.
  • Example: A text editor, after waking from sleep, has its vruntime temporarily lowered to quickly gain CPU time and respond to user input.

7. Summary: Advantages and Characteristics of CFS

  1. Fairness: Achieves priority-weighted fair allocation through vruntime.
  2. Efficiency: The red-black tree ensures efficient scheduling decisions.
  3. Adaptability: Time slices are dynamically adjusted to balance throughput and responsiveness.
  4. Configurability: Parameters like sched_latency can be optimized for different workloads.

Through these mechanisms, CFS delivers good performance across various scenarios, including servers, desktops, and embedded systems.