Introduction

In a single-core universe, only one timeline exists. The Scheduler is the god that fractures this timeline into parallel universes (Multitasking). It does this not by “Fairness”, but by Physics.

Linux’s Completely Fair Scheduler (CFS) models an “Ideal Multi-Tasking CPU” where every process runs simultaneously at $1/N$ speed. Since this is impossible, it uses Time Dilation Math to approximate it.

The Physics: Red-Black Trees

In older kernels (O(1)), the Runqueue was a Linked List. In CFS, the Runqueue is a Red-Black Tree.

• Left Nodes: Tasks that need CPU ASAP (Low vruntime).
• Right Nodes: Tasks that have run enough (High vruntime).
• Operation: The CPU always picks the left-most node.

Physics: Retrieving the next task is $O(1)$. Inserting a task back into the tree is $O(log N)$. This means scheduling overhead increases logarithmically with system load, not linearly.

The Math: vruntime and Time Dilation

How does nice work? It doesn’t give you “more slots”. It dilates time.

$vruntime += \text{Actual Runtime} \times \frac{\text{Weight Of Nice 0}}{\text{Weight Of Task}}$

• Nice 0 (Default): 1 second of runtime = 1 second of vruntime.
• Nice -10 (High Priority): 1 second of runtime = 0.2 seconds of vruntime.
  • Result: The tree thinks you haven’t run much, so it keeps picking you (Left-most).
• Nice +10 (Low Priority): 1 second of runtime = 5 seconds of vruntime.
  • Result: One millisecond of CPU shoots you to the far right of the tree.

Deep Dive: Real-Time Classes (SCHED_FIFO)

CFS (SCHED_NORMAL) is polite. Real-Time (SCHED_FIFO/RR) is a dictator.

Physics: A SCHED_FIFO task bypasses the Red-Black Tree entirely. It runs until:

1. It exits.
2. It yields.
3. A higher priority Real-Time task wakes up.

Danger: If you write a while(1) loop in SCHED_FIFO, your system hangs. Even the terminal (SSH) cannot run to kill it, because SSH is SCHED_NORMAL.

Code: Pinning (CPU Affinity)

The Scheduler tries to keep processes on the same core (Cache Locality). But it will move them if another core is idle (Load Balancing). For HFT/Gaming, this movement destroys performance (Cache Thrashing).

The Soltuion: CPU Pinning.

# Pin process 1234 to Core 0 and Core 1
taskset -p 0x3 1234

# Run a command only on Core 7 (Isolate it)
taskset -c 7 ./my_critical_process

Practice Exercises

Exercise 1: The Heavyweight (Beginner)

Scenario: Two processes. One is Nice 0, one is Nice -20. Task: Run them both (stress -c 1). Use top to observe CPU % split. (Hint: The Nice -20 process should behave as if “Time flows slower” for it, effectively consuming ~95% CPU).

Exercise 2: The Starvation (Intermediate)

Scenario: Run a while(1) loop with chrt -f 99 (Highest Realtime). Task: (DO NOT DO THIS on a production machine). What happens? Why does the mouse cursor stop moving?

Exercise 3: Latency Profiling (Advanced)

Task: Use perf sched record and perf sched latency to measure the “Wakeup Latency” (Time from ‘Ready’ to ‘Running’) of your database.

Knowledge Check

1. Why does the Scheduler use a Red-Black Tree instead of a Queue?
2. How does a Nice value of +19 affect vruntime?
3. What is the difference between SCHED_FIFO and SCHED_RR?
4. Why is context switching expensive for data-heavy apps?
5. How does the Scheduler detect “Interactive” (UI) threads?

Summary

• CFS: Fairness via geometric weighting.
• Nice: Time dilation controls.
• Real-Time: Dangerous power tools.