Linux Completely Fair Scheduler (CFS)

 

Linux Completely Fair Scheduler (CFS)

The Completely Fair Scheduler (CFS) is the default Linux CPU scheduler introduced to replace the earlier O(1) scheduler. Its primary goal is to provide fair CPU sharing among all runnable processes rather than optimizing response time or throughput alone.

---

1. Design Philosophy of CFS

Traditional schedulers (like round-robin or MLFQ) work by:

• Giving each process a time slice

• Preempting processes after the slice expires

CFS takes a different approach:

CFS models “ideal multitasking”

Each runnable process should get an equal share of the CPU over time, proportional to its priority.

Instead of asking “Which process should run next?”, CFS asks:

“Which process has run the least so far?”

---

2. Key Idea: Virtual Runtime (vruntime)

The core concept of CFS is virtual runtime (vruntime).

What is vruntime?

• vruntime measures how much processor time a process has received

• It is normalized by priority

• A lower vruntime means the process has received less CPU time

How it works:

• When a process runs, its vruntime increases

• Processes with smaller vruntime are favored

• The scheduler always picks the process with the minimum vruntime

📌 Effect:

Processes that haven’t run much get scheduled first → fairness

---

3. No Fixed Time Slices

Unlike traditional schedulers:

• CFS does not use fixed time slices

• Instead, it uses a concept called target latency

Target Latency

• The time during which all runnable processes should get CPU time at least once

• Example: If target latency = 20 ms and 4 processes are runnable
  → each gets about 5 ms

As the number of processes increases:

• Time per process decreases

• Scheduling becomes more frequent

📌 Result:

CFS dynamically adjusts CPU allocation instead of relying on rigid slices.

---

4. Scheduling Decision

CFS maintains all runnable processes ordered by vruntime.

Scheduling rule:

Pick the process with the smallest vruntime

This ensures:

• CPU-hungry tasks gradually fall behind

• I/O-bound or interactive tasks stay responsive

• No starvation under normal conditions

---

5. Handling Priorities (nice values)

Linux supports nice values from -20 (highest priority) to +19 (lowest).

In CFS:

• Priority affects how fast vruntime increases

• Higher-priority processes accumulate vruntime more slowly

• Lower-priority processes accumulate vruntime faster

📌 Meaning:

Higher-priority tasks effectively get more CPU share over time.

---

6. Fairness Guarantee

CFS approximates the following ideal behavior:

• If N processes are runnable

• Each process gets approximately 1/N of the CPU

• Adjusted by priority

This prevents:

• Starvation

• CPU monopolization

• Long-term unfairness

---

7. Interactive and I/O-Bound Processes

CFS naturally favors interactive jobs because:

• They frequently block for I/O

• Their vruntime grows slowly

• When they wake up, they have low vruntime

• They are scheduled quickly

📌 No special heuristics are needed—fairness alone handles interactivity.

---

8. Comparison with Traditional Schedulers

Feature	Traditional Scheduler	CFS
Time slices	Fixed	Dynamic
Priority handling	Static queues	vruntime scaling
Fairness	Approximate	Explicit
Starvation	Possible	Strongly reduced
Interactive boost	Heuristic-based	Natural outcome

---

9. Advantages of CFS

• Strong fairness guarantees

• No starvation in normal workloads

• Simple scheduling logic (conceptually)

• Naturally supports interactive tasks

• Priority effects are smooth and predictable

---

10. Limitations (Conceptual)

• Not designed for real-time deadlines

• Fairness may reduce throughput for CPU-bound workloads

• Latency tuning (target latency, min granularity) still required

---

11. Summary

The Linux Completely Fair Scheduler schedules tasks based on how much CPU time they have already received, not on fixed time slices.

By always running the process with the lowest virtual runtime, CFS approximates ideal multitasking and provides proportional-share scheduling.