Introduction
Modern operating systems execute multiple processes and threads simultaneously while sharing limited CPU resources. Since the CPU cannot execute every process at the same instant, the operating system must decide:
Which process should run
When it should run
For how long
This decision-making mechanism is called CPU scheduling.
Linux uses advanced scheduling algorithms designed to provide:
Fair CPU allocation
High responsiveness
Scalability
Efficient multitasking
Earlier Linux schedulers faced several problems:
Poor fairness
Interactive process starvation
Complex heuristics
Scalability limitations
To address these issues, Linux introduced the:
Completely Fair Scheduler (CFS)
CFS became the default Linux scheduler in kernel version 2.6.23 and remains one of the most important components of Linux process management.
Understanding CFS is extremely important because it explains how Linux manages:
Multitasking
CPU sharing
Interactive responsiveness
Fairness among processes
What is the Linux Scheduler?
The Linux scheduler is the kernel subsystem responsible for selecting which runnable process or thread gets CPU execution time.
The scheduler continuously decides:
Which task executes next
Which CPU core executes it
How long it runs
Core Idea
CPU scheduling determines which process gets processor time
Important Insight
Efficient scheduling is critical for system responsiveness, fairness, and performance
Why Scheduling is Necessary
Suppose:
100 processes exist
Only 4 CPU cores available
All processes cannot execute simultaneously.
Scheduler therefore:
Shares CPU time efficiently
Goals of Linux Scheduling
Linux scheduling aims to achieve:
Fairness
Low latency
Good throughput
Scalability
Interactive responsiveness
Historical Linux Scheduling Problems
Older Linux schedulers used:
Fixed time slices
Priority heuristics
Problems included:
Interactive tasks sometimes delayed
Unfair CPU allocation
Complexity in tuning priorities
This motivated creation of CFS.
What is the Completely Fair Scheduler (CFS)?
The Completely Fair Scheduler is the default Linux process scheduler designed to allocate CPU time fairly among runnable tasks.
CFS attempts to model:
An ideal multitasking processor
where every runnable process receives equal CPU share simultaneously.
Since real CPUs cannot execute all tasks simultaneously:
CFS approximates fairness mathematically.
Core Idea of CFS
Processes that received less CPU time should run earlier
Important Insight
CFS prioritizes fairness by tracking how much CPU time each process has already consumed
Ideal Processor Model
Imagine:
Infinite CPU power
Every process runs simultaneously
Each process gets:
Perfectly proportional CPU share
CFS attempts to simulate this ideal behavior on real hardware.
Virtual Runtime (vruntime)
The most important concept in CFS is:
Virtual runtime (vruntime)
What is vruntime?
vruntime measures:
How much CPU time a process has received relative to its weight/priority
Processes with:
Smaller vruntime
→ Have received less CPU time
→ Should run sooner
Important Insight
CFS always selects the process with the smallest virtual runtime
Simplified Example
Suppose:
Process A used 5 ms CPU
Process B used 20 ms CPU
CFS favors:
Process A
because it has received less execution time.
Red-Black Tree in CFS
CFS organizes runnable tasks using:
Red-black tree
Very important data structure.
Why Red-Black Tree?
Provides:
Balanced search
Efficient insertion/removal
Ordered process tracking
Key Property
Processes sorted by:
vruntime
Leftmost node:
Smallest vruntime
Chosen next for execution
Important Insight
CFS uses a red-black tree to efficiently track runnable processes by virtual runtime
Scheduling Flow in CFS
Step 1: Process Becomes Runnable
Inserted into red-black tree.
Step 2: Scheduler Selects Leftmost Node
Smallest vruntime chosen.
Step 3: Process Executes
vruntime increases during execution.
Step 4: Process Reinserted
Scheduler reevaluates fairness.
Time Slice in CFS
Older schedulers used fixed timeslices.
CFS instead dynamically calculates:
Fair execution duration
based on:
Number of runnable processes
Process priorities
Scheduler Latency
CFS defines:
Target latency
Time during which all runnable processes should ideally execute once.
Example
Suppose:
Target latency = 20 ms
4 processes runnable
Each process roughly gets:
5 ms
Minimum Granularity
Very short timeslices inefficient because:
Excessive context switching occurs
CFS therefore defines:
Minimum granularity
preventing excessively small slices.
Important Insight
CFS balances fairness against context-switching overhead
Nice Values and Process Priority
Linux processes have:
Nice values
Range:
-20 → highest priority
19 → lowest priority
Lower Nice Value
Higher scheduling priority
Slower vruntime growth
Higher Nice Value
Lower priority
Faster vruntime growth
Effect on Scheduling
Higher-priority processes:
Receive more CPU share
Scheduling Classes in Linux
Linux supports multiple scheduling classes.
1. CFS (Normal Scheduling)
Default scheduling class.
2. Real-Time Scheduling
For time-critical tasks.
Policies:
SCHED_FIFO
SCHED_RR
3. Deadline Scheduler
Supports deadline-based execution guarantees.
Important Insight
Linux scheduling supports both fair-sharing and real-time execution models
Context Switching in CFS
Scheduler frequently switches between processes.
Context switching involves:
Saving CPU state
Loading another process state
Overhead
Too many switches reduce performance.
CFS therefore balances:
Fairness
Switching efficiency
Interactive Process Responsiveness
Interactive applications require:
Fast responsiveness
Examples:
GUI applications
Browsers
Video playback
CFS favors responsiveness by:
Preventing CPU monopolization
Multicore Scheduling
Modern Linux systems use:
Multiple CPU cores
CFS supports:
SMP scheduling
Load balancing
Per-CPU Run Queues
Each core maintains:
Its own run queue
Advantages:
Reduced contention
Better scalability
Load Balancing in CFS
Scheduler redistributes tasks among cores.
Goals:
Prevent overloaded CPUs
Maximize utilization
Sleepers and Interactive Tasks
Processes that sleep often:
Usually interactive
CFS may prioritize them when they wake up to improve responsiveness.
Example
User presses keyboard key:
Shell should respond immediately
Real-Time Scheduling vs CFS
CFS:
Fair-sharing scheduler
Real-time schedulers:
Strict priority scheduling
Real-time tasks may preempt normal CFS tasks.
Starvation Prevention
CFS designed to avoid starvation.
Because:
vruntime eventually equalizes
Every runnable process gets CPU time.
Important Insight
CFS naturally prevents starvation through fair runtime accounting
Scheduler Complexity
CFS operations typically:
O(log n)
due to red-black tree operations.
Efficient for large systems.
Linux Scheduling Statistics
Linux exposes scheduler information through:
/proc filesystem
top
htop
sched_debug
Example
cat /proc/sched_debug
Real-World Example
Suppose system runs:
Browser
Music player
Compiler
Video call
CFS:
Tracks vruntime for each task
Allocates CPU fairly
Prevents starvation
Maintains responsiveness
Balances workload across cores
All dynamically.
Advantages of CFS
1. Fair CPU Allocation
Balanced scheduling.
2. Good Interactive Performance
Responsive applications.
3. Scalability
Efficient for many processes.
4. Starvation Prevention
All tasks eventually run.
5. Elegant Design
Simple fairness model.
Limitations of CFS
1. Real-Time Guarantees Limited
Not ideal for strict real-time systems.
2. Scheduler Overhead
Complex tracking required.
3. Cache Effects
Frequent task movement affects caches.
CFS and Cloud Systems
Cloud servers rely heavily on:
Fair CPU allocation
CFS supports:
Containers
Virtual machines
Multitenant workloads
efficiently.