Linux Scheduling
Before Kernel Version 2.5
Linux used an old UNIX-style scheduler.
It didn’t work well for multi-core systems (SMP) — response time
was poor.
📌 Changes in Kernel Version 2.5
Switched to O(1) scheduling – meaning it took the same amount
of time to schedule tasks, no matter how many were running.
Improved support for multi-core CPUs by adding:
o Processor affinity (keeping a task on the same CPU)
o Load balancing (spreading tasks across CPUs)
🔄 Priority System in 2.5
Two types of priority levels:
o Time-sharing (normal programs)
o Real-time (urgent tasks like media players or controllers)
All priorities are mapped into a global priority system:
o Lower number = higher priority
o Higher priority = longer time slice to run
⚙️How It Managed Tasks
Each CPU had its own runqueue (list of tasks ready to run).
Runqueue had two arrays:
o active → currently running
o expired → finished their time slice
When all tasks in active are done, swap it with expired.
Worked fine but wasn't good for interactive tasks (like GUI apps –
they felt slow).
🌟 CFS – Completely Fair Scheduler
This replaced the old one and is still used today (with improvements).
Here's how it works:
🧠 Key Concepts of CFS
What are Scheduling Classes?
In Linux, tasks (also called processes or threads) are divided into
scheduling classes.
Think of these classes as categories that decide how and when tasks
will run.
The Two Main Classes:
1. Real-Time Class
🔥 Highest priority — runs first
Used for tasks that need immediate attention, like:
o Media playback (audio/video)
o Industrial control systems
o Critical timers
Has strict timing rules
Two policies inside:
o SCHED_FIFO (First-In, First-Out)
o SCHED_RR (Round Robin)
These tasks will always run before any normal (default) tasks,
unless they’re sleeping.
2. Default Class (CFS – Completely Fair Scheduler)
🧑💻 Normal tasks — like your browser, editor, terminal, etc.
Used for everyday processes.
Based on fairness — everyone gets CPU time according to:
o How long they’ve run (vruntime)
o Their nice value (priority)
Most programs run in this class.
🧠 How the Scheduler Chooses?
It first checks the real-time class:
o If there are any real-time tasks ready to run → they run first.
If no real-time tasks, then:
o It picks from the default class, using vruntime and fairness
logic.
⚖️Summary
Scheduling Priori
Used For Scheduling Style
Class ty
Critical time-sensitive
Real-Time Higher FIFO / Round Robin
tasks
Normal user/system Fair share using
Default (CFS) Lower
tasks vruntime
CPU Time Based on Proportion (Not Fixed Slices)
No fixed time slices like before.
Instead, tasks get CPU based on how "nice" they are (Nice values:
-20 to +19)
o Lower nice value = higher priority = gets more CPU time
⌛ Target Latency
This is the time window in which every task should run at least
once.
If more tasks are running, the latency might increase a bit.
📊 vruntime (Virtual Runtime)
Each task has a virtual runtime that tracks how long it’s been
running.
It's adjusted based on priority:
o Lower priority = faster increase in vruntime
o Higher priority = slower increase
The next task to run is the one with the lowest vruntime (least
CPU used so far).
🧩 Load Balancing and NUMA Awareness
Linux balances CPU loads, but also considers NUMA systems
(multi-CPU with memory zones).
CPUs are grouped into scheduling domains based on what they
share (like caches).
Linux tries to keep tasks in the same domain to avoid slow
memory access.
💡 Does a high-priority task have low vruntime?
👉 Yes, usually.
Because in CFS, vruntime increases slower for high-priority tasks,
they tend to stay lower compared to other tasks — so they’re picked
more often.
🔁 How vruntime works based on priority:
High priority task (lower nice value)
→ vruntime increases slowly
→ Gets more chances to run
Low priority task (higher nice value)
→ vruntime increases faster
→ Gets less CPU time
🏃♂️Who gets picked to run next?
The scheduler always picks the task with the lowest vruntime.
So tasks that:
o haven’t run much or
o have high priority
...are more likely to be picked next.
💡 What is vruntime?
vruntime is a value used by the Linux Completely Fair Scheduler
(CFS) to track how much CPU time a task has used — adjusted
based on its priority.
It helps ensure that all tasks get a fair share of the CPU, but gives
more CPU time to higher-priority tasks.
Tas Nice Priori vruntime
Result
k Value ty Grows...
Norma
A 0 Normal speed Runs fairly
l
Gets more
B -10 High Slower
CPU
Gets less
C +10 Low Faster
CPU
Even if Task C runs for 5ms, its vruntime may increase as if it
ran for 10ms, because of low priority.
Task B, being high-priority, might run for 10ms, but its vruntime
might only increase like 5ms.
💡 What is a Nice Value?
The nice value in Linux is a number that represents a task’s priority —
specifically, how "nice" it is about letting other tasks run.
It ranges from -20 to +19.
The lower the nice value, the higher the priority.
The higher the nice value, the lower the priority.
🎯 Why is it called "Nice"?
Because a process with a higher nice value is being "nicer" — it’s
saying:
“I don’t need the CPU urgently, let others go first.”
📊 Nice Value Table Summary
Nice Priority
CPU Time Behavior
Value Level
Very High Gets a lot of CPU
-20
Priority time
Normal Fair share of CPU
0
Priority time
Very Low Gets very little CPU
+19
Priority time
🧪 Example:
Let’s say we have 3 tasks:
Tas Nice
Effect
k Value
A 0 Gets normal CPU share
Gets more CPU (priority is
B -5
higher)
Gets less CPU (lower
C +10
priority)
So, Task B will run more often, and Task C will run less often.
