Scheduler Fairness Algorithms

In this lesson, you will learn how the Linux kernel uses the Completely Fair Scheduler (CFS) to ensure that every thread receives its equitable slice of CPU time.

The Problem with Static Priority

Previously, you learned about "Nice" values and static priorities. While useful for signaling importance, a system relying solely on priority would let a high-priority process starve a low-priority one indefinitely. The CFS approach flips this: it treats the CPU as a resource that should be shared proportionally, rather than a competition won by the "nicest" process.

The Virtual Runtime Concept

To achieve fairness, the CFS tracks how much time each thread has spent on the CPU using a value called vruntime (virtual runtime). Think of vruntime as a "debt" of CPU time.

• Active Threads: As a thread runs, its vruntime increases.
• Waiting Threads: When a thread is blocked (waiting for I/O, for example), its vruntime stays static.

The scheduler always picks the thread with the lowest vruntime to run next. Because the thread that hasn't run in a while has a very low vruntime, the scheduler naturally gravitates toward it, ensuring it eventually gets a turn.

Red-Black Trees

The kernel maintains these threads in a data structure called a Red-Black Tree. This is a self-balancing binary search tree where the "leftmost" node is always the thread with the smallest vruntime.

// Conceptually, the scheduler logic looks like this:
struct task_struct *next_task = pick_leftmost_node(cfs_rq);
run_task(next_task);
update_vruntime(next_task);
rebalance_tree(cfs_rq);

When a thread completes its time slice, the scheduler re-inserts it into the tree based on its new, updated vruntime. If it ran for a long time, it moves toward the right (the "heavier" side); if it was waiting, it stays toward the left (the "lighter" side). This ensures that even "low priority" tasks are guaranteed a slice of the CPU, preventing them from being completely locked out by more aggressive, high-priority processes.

Key Takeaway: The CFS maintains fairness by constantly tracking virtual runtime and prioritizing the thread with the least accumulated CPU time, ensuring no process is starved of execution.