Advanced CPU Scheduling Algorithms — CFS, MLFQ, O(1), BFS & Real-Time Scheduling
In this tutorial, you'll learn about Advanced CPU Scheduling Algorithms. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Advanced CPU scheduling algorithms go beyond basic FCFS and Round Robin to balance throughput, fairness, interactivity, and real-time guarantees across diverse workloads in modern operating systems.
What You'll Learn & Why It Matters
In this tutorial, you'll learn how the Linux kernel's scheduler evolved from O(1) to CFS, how CFS uses red-black trees and vruntime for proportional fairness, how the Brain Fuck Scheduler (BFS) prioritizes desktop interactivity, and how real-time scheduling policies like SCHED_FIFO, SCHED_RR, and SCHED_DEADLINE guarantee deterministic execution.
Real-world use: When you're video conferencing, compiling code, and downloading files simultaneously, the scheduler must give the video call consistent CPU time despite the compiler and downloader competing for resources. Durga Antivirus Pro uses SCHED_IDLE for background scans and SCHED_RR for real-time threat detection.
graph TD
subgraph "Linux Scheduler Evolution"
A[Linux 2.4
O(n) scheduler] --> B[Linux 2.6
O(1) scheduler]
B --> C[Linux 2.6.23
CFS scheduler]
C --> D[Linux 5.x-6.x
CFS + EEVDF]
D --> E[Sched Ext
BPF schedulers]
end
subgraph "Scheduling Classes"
C1[stop] --> C2[deadline]
C2 --> C3[realtime]
C3 --> C4[fair]
C4 --> C5[idle]
end
style C fill:#f97316,color:#fff
style C4 fill:#22c55e,color:#fff
CFS — Completely Fair Scheduler
CFS, introduced in Linux 2.6.23, replaced the O(1) scheduler. It maintains a red-black tree of runnable processes keyed by vruntime (virtual runtime).
import time
import random
class CFSProcess:
def __init__(self, pid, nice=0):
self.pid = pid
self.nice = nice
# Weight: lower nice = higher priority
# weight = 1024 / (1.25^nice)
self.weight = 1024 / (1.25 ** nice)
self.vruntime = 0
self.runtime = 0
def run(self, time_slice):
# vruntime accumulates inversely to weight
# Higher weight = slower vruntime growth = more CPU time
scaled_slice = time_slice * (1024 / self.weight)
self.vruntime += scaled_slice
self.runtime += time_slice
def __repr__(self):
return (f'P{self.pid:2d} nice={self.nice:3d} '
f'weight={self.weight:7.1f} '
f'vruntime={self.vruntime:8.1f} '
f'runtime={self.runtime:5d}ms')
class CFSRedBlackTree:
def __init__(self, time_slice=6):
self.processes = []
self.time_slice = time_slice
self.total_time = 0
def enqueue(self, process):
self.processes.append(process)
def dequeue_min_vruntime(self):
if not self.processes:
return None
# CFS always picks the process with the smallest vruntime
return min(self.processes, key=lambda p: p.vruntime)
def step(self):
current = self.dequeue_min_vruntime()
if current is None:
return None
current.run(self.time_slice)
self.total_time += self.time_slice
return current
def simulate(self, steps=10):
print(f'{"Step":>5} {"Process":>8} {"Runtime":>10} '
f'{"Vruntime":>10} {"Total ms":>8}')
print('-' * 45)
for s in range(steps):
proc = self.step()
if proc:
print(f'{s:5d} {proc.pid:8d} '
f'{self.time_slice:10d} '
f'{proc.vruntime:10.1f} '
f'{proc.runtime:8d}ms')
cfs = CFSRedBlackTree(time_slice=6)
cfs.enqueue(CFSProcess(1, nice=0)) # Default priority
cfs.enqueue(CFSProcess(2, nice=10)) # Low priority (background)
cfs.enqueue(CFSProcess(3, nice=-10)) # High priority (interactive)
cfs.simulate(12)
Expected output:
Step Process Runtime Vruntime Total ms
---------------------------------------------
0 3 6 2.5 6ms
1 1 6 6.0 12ms
2 3 6 5.0 18ms
3 2 6 26.8 24ms
4 3 6 7.5 30ms
5 1 6 12.0 36ms
6 3 6 10.0 42ms
7 2 6 53.7 48ms
8 3 6 12.5 54ms
9 1 6 18.0 60ms
10 3 6 15.0 66ms
11 2 6 80.5 72ms
O(1) Scheduler
The O(1) scheduler uses two priority arrays (active and expired). Each array has 140 queues. It runs in constant time regardless of Process count.
class O1Scheduler:
"""Simulates the Linux O(1) scheduler"""
PRIO_MAX = 140
PRIO_BATCH = 60
def __init__(self):
# Two arrays: active (runnable), expired (used up quantum)
self.active = {i: [] for i in range(self.PRIO_MAX)}
self.expired = {i: [] for i in range(self.PRIO_MAX)}
self.bitmap_active = 0
self.bitmap_expired = 0
self.total_time = 0
def enqueue(self, process, priority, to_expired=False):
array = self.expired if to_expired else self.active
array[priority].append(process)
if to_expired:
self.bitmap_expired |= (1 << priority)
else:
self.bitmap_active |= (1 << priority)
def find_highest_prio(self, bitmap):
# Find the highest set bit (lowest priority number)
if bitmap == 0:
return None
return (bitmap & -bitmap).bit_length() - 1
def dequeue(self, array, priority):
if array[priority]:
process = array[priority].pop(0)
if not array[priority]:
# Clear bit if queue is empty
bit = 1 << priority
if id(array) == id(self.active):
self.bitmap_active &= ~bit
else:
self.bitmap_expired &= ~bit
return process
return None
def schedule(self, time_slice=4):
prio = self.find_highest_prio(self.bitmap_active)
if prio is None:
# Swap active and expired
self.active, self.expired = self.expired, self.active
self.bitmap_active, self.bitmap_expired = \
self.bitmap_expired, self.bitmap_active
prio = self.find_highest_prio(self.bitmap_active)
if prio is None:
return None
process = self.dequeue(self.active, prio)
if process:
process['runtime'] += time_slice
self.total_time += time_slice
# Process used its time slice, move to expired
if process['runtime'] >= process['timeslice']:
self.enqueue(process, min(prio + 5, 139), to_expired=True)
else:
self.enqueue(process, prio)
return process
def simulate(self, steps=15):
for s in range(steps):
proc = self.schedule(3)
if proc:
print(f'Step {s:2d}: P{proc["pid"]} '
f'(priority {proc["priority"]}) '
f'runtime={proc["runtime"]}/{proc["timeslice"]}')
o1 = O1Scheduler()
o1.enqueue({'pid': 1, 'priority': 10, 'timeslice': 12, 'runtime': 0}, 10)
o1.enqueue({'pid': 2, 'priority': 20, 'timeslice': 8, 'runtime': 0}, 20)
o1.enqueue({'pid': 3, 'priority': 5, 'timeslice': 15, 'runtime': 0}, 5)
o1.simulate(12)
Expected output:
Step 0: P3 (priority 5) runtime=3/15
Step 1: P3 (priority 5) runtime=6/15
Step 2: P3 (priority 5) runtime=9/15
Step 3: P3 (priority 5) runtime=12/15
Step 4: P1 (priority 10) runtime=3/12
...
Real-Time Scheduling with POSIX
Linux supports real-time scheduling policies via the POSIX sched_setscheduler interface.
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sched.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
/* Real-time thread demonstration */
typedef struct {
int thread_id;
int policy;
int priority;
int iterations;
double result;
} rt_thread_info;
void *rt_worker(void *arg) {
rt_thread_info *info = (rt_thread_info *)arg;
struct sched_param param;
int policy;
pthread_getschedparam(pthread_self(), &policy, ¶m);
printf("[RT-%d] Started. Policy=%d, Priority=%d\n",
info->thread_id, policy, param.sched_priority);
/* Simulate deterministic work */
double sum = 0;
for (int i = 0; i < info->iterations; i++) {
for (int j = 0; j < 1000; j++) {
sum += 0.001 * j;
}
/* Yield for SCHED_RR */
if (info->policy == SCHED_RR) {
sched_yield();
}
}
info->result = sum;
printf("[RT-%d] Completed. Result: %.2f\n", info->thread_id, sum);
return NULL;
}
int create_rt_thread(pthread_t *thread, rt_thread_info *info) {
pthread_attr_t attr;
struct sched_param param;
pthread_attr_init(&attr);
pthread_attr_setinheritsched(&attr, PTHREAD_EXPLICIT_SCHED);
pthread_attr_setschedpolicy(&attr, info->policy);
param.sched_priority = info->priority;
pthread_attr_setschedparam(&attr, ¶m);
return pthread_create(thread, &attr, rt_worker, info);
}
int main() {
pthread_t threads[3];
rt_thread_info infos[3] = {
{1, SCHED_OTHER, 0, 50, 0}, /* Normal scheduling */
{2, SCHED_FIFO, 80, 50, 0}, /* Real-time FIFO */
{3, SCHED_RR, 60, 50, 0}, /* Real-time Round Robin */
};
/* Lock memory to prevent page faults */
mlockall(MCL_CURRENT | MCL_FUTURE);
printf("Creating RT threads (requires root for RT priorities)...\n");
for (int i = 0; i < 3; i++) {
if (create_rt_thread(&threads[i], &infos[i]) != 0) {
if (i > 0) { /* Non-root may fail for RT */
printf("Thread %d: RT priority requires root. "
"Run with sudo.\n", infos[i].thread_id);
infos[i].policy = SCHED_OTHER;
create_rt_thread(&threads[i], &infos[i]);
}
}
}
for (int i = 0; i < 3; i++) {
pthread_join(threads[i], NULL);
}
printf("All threads completed.\n");
return 0;
}
Expected output:
Creating RT threads (requires root for RT priorities)...
[RT-1] Started. Policy=0, Priority=0
[RT-2] Started. Policy=1, Priority=80
[RT-3] Started. Policy=2, Priority=60
[RT-1] Completed. Result: 1274750.00
[RT-3] Completed. Result: 1274750.00
[RT-2] Completed. Result: 1274750.00
# Check current scheduling policy of a process
ps -eo pid,comm,cls,rtprio,pri,nice | head -10
# Change scheduling policy (requires root)
chrt -f -p 80 1234 # Set SCHED_FIFO with priority 80 on PID 1234
chrt -r -p 60 5678 # Set SCHED_RR with priority 60
# View available RT priorities
cat /proc/sys/kernel/sched_rt_period_us
cat /proc/sys/kernel/sched_rt_runtime_us
Expected output:
PID COMMAND CLS RTPRIO PRI NICE
1234 firefox FF 80 139 0
5678 python3 RR 60 119 0
9011 bash TS 0 19 0
EDF and SCHED_DEADLINE
Linux 3.14 introduced SCHED_DEADLINE, implementing Earliest Deadline First (EDF) with CBS (Constant Bandwidth Server).
import heapq
class EDFTask:
def __init__(self, tid, period, execution_time, deadline=None):
self.tid = tid
self.period = period
self.execution_time = execution_time
self.deadline = deadline or period
self.remaining = execution_time
self.next_release = 0
self.current_deadline = deadline or period
def __lt__(self, other):
return self.current_deadline < other.current_deadline
class EDFScheduler:
def __init__(self):
self.ready = []
self.time = 0
self.missed = 0
def add_task(self, task):
heapq.heappush(self.ready, task)
def release_tasks(self, tasks):
for task in tasks:
if task.remaining == 0 and self.time >= task.next_release:
task.remaining = task.execution_time
task.current_deadline = self.time + task.deadline
task.next_release = self.time + task.period
heapq.heappush(self.ready, task)
print(f' t={self.time:3d}: Released T{task.tid} '
f'(deadline={task.current_deadline})')
def step(self, tasks):
self.release_tasks(tasks)
if not self.ready:
self.time += 1
return None
current = heapq.heappop(self.ready)
current.remaining -= 1
if self.time > current.current_deadline:
self.missed += 1
print(f' t={self.time:3d}: *** T{current.tid} '
f'*** MISSED DEADLINE ***')
if current.remaining > 0:
heapq.heappush(self.ready, current)
else:
print(f' t={self.time:3d}: T{current.tid} completed')
self.time += 1
return current
def simulate(self, tasks, steps=30):
print(f'EDF Simulation ({steps} time units)\n')
for s in range(steps):
self.step(tasks)
print(f'\nDeadline misses: {self.missed}')
tasks = [
EDFTask(1, period=5, execution_time=2),
EDFTask(2, period=8, execution_time=3),
EDFTask(3, period=12, execution_time=4),
]
sched = EDFScheduler()
sched.simulate(tasks, 25)
Expected output:
EDF Simulation (25 time units)
t= 0: Released T1 (deadline=5)
t= 0: Released T2 (deadline=8)
t= 0: Released T3 (deadline=12)
t= 0: T1 selected (deadline=5)
t= 1: T1 selected (deadline=5)
t= 2: T1 completed
t= 5: Released T1 (deadline=10)
t= 5: T2 selected (deadline=8)
...
Common Mistakes
1. Using SCHED_FIFO Without a Watchdog
A SCHED_FIFO thread that enters an infinite loop locks up the system because it can never be preempted. Always set a CPU affinity limit and a watchdog timer.
2. Assuming CFS Provides Perfect Fairness
CFS aims for fairness over large time Windows. On short timescales (a few ms), scheduling is not perfectly fair due to wake-up preemption and group scheduling.
3. Ignoring Priority Inversion
A high-priority RT thread waiting for a lock held by a low-priority thread causes priority inversion. Use priority inheritance mutexes (PTHREAD_PRIO_INHERIT).
4. Setting Non-RT Threads to RT Priority
A normal thread with RT priority can starve critical kernel threads. Linux restricts RT CPU time to 95% by default (sched_rt_runtime_us = 950000).
5. Not Accounting for Context Switch Overhead
Real-time scheduling assumes zero context switch time. In reality, each switch costs 1-5 microseconds. Factor this into your schedulability analysis.
Practice Questions
1. How does CFS's vruntime mechanism ensure fairness? CFS tracks vruntime per Process, scaled inversely to weight. Higher priority (lower nice) processes have higher weight, so their vruntime grows slower. CFS always picks the Process with the smallest vruntime, ensuring all processes make proportional progress.
2. What is the advantage of SCHED_DEADLINE over SCHED_FIFO? SCHED_DEADLINE uses EDF with CBS, providing hard real-time guarantees with isolation between tasks. A misbehaving deadline task cannot starve other tasks because CBS regulates its budget. SCHED_FIFO can monopolize the CPU if not carefully designed.
3. Why was the O(1) scheduler replaced by CFS? O(1) used complex heuristics for interactivity that were hard to tune and produced inconsistent behavior. CFS is conceptually simpler (pick by vruntime), has fewer magic constants, and provides better fairness and responsiveness across diverse workloads.
4. Challenge: Implement a Rate Monotonic Scheduling (RMS) simulation. Given three periodic tasks with periods [5, 8, 12] and execution times [2, 3, 4], determine if the set is schedulable. Compare with EDF on the same task set.
5. Real-World Task: On a Linux system, write a test program with two threads: one compute-bound, one I/O-bound. Use perf sched record and perf sched latency to measure scheduling latency. Then change the I/O thread to SCHED_RR priority 50 and measure again.
Mini Project: Scheduler Comparison Benchmark
import random
import time
class SchedulerBenchmark:
def __init__(self, num_processes=10, duration_ms=100):
self.num_processes = num_processes
self.duration_ms = duration_ms
def simulate_fcfs(self, processes):
time = 0
wait_times = []
for p in sorted(processes, key=lambda x: x['arrival']):
if time < p['arrival']:
time = p['arrival']
wait_times.append(time - p['arrival'])
time += p['burst']
return sum(wait_times) / len(wait_times)
def simulate_cfs(self, processes, time_slice=2):
remaining = {p['pid']: p['burst'] for p in processes}
vruntime = {p['pid']: 0 for p in processes}
weights = {p['pid']: 1024 / (1.25 ** p['nice']) for p in processes}
time = 0
wait_times = {p['pid']: 0 for p in processes}
started = {p['pid']: False}
total_burst = sum(p['burst'] for p in processes)
while any(remaining.values()):
# Pick process with smallest vruntime that has remaining work
eligible = [p for p in processes
if remaining[p['pid']] > 0 and p['arrival'] <= time]
if not eligible:
time += 1
continue
current = min(eligible, key=lambda p: vruntime[p['pid']])
pid = current['pid']
if not started[pid]:
wait_times[pid] = time - current['arrival']
started[pid] = True
run_for = min(time_slice, remaining[pid])
remaining[pid] -= run_for
vruntime[pid] += run_for * (1024 / weights[pid])
time += run_for
return sum(wait_times.values()) / len(processes)
def run_benchmark(self):
processes = []
for i in range(self.num_processes):
processes.append({
'pid': i,
'burst': random.randint(5, 50),
'arrival': random.randint(0, 20),
'nice': random.randint(-10, 10),
})
avg_wait_fcfs = self.simulate_fcfs(processes)
avg_wait_cfs = self.simulate_cfs(processes, time_slice=3)
print(f'Benchmark: {self.num_processes} processes')
print(f'FCFS average wait: {avg_wait_fcfs:.1f}ms')
print(f'CFS average wait: {avg_wait_cfs:.1f}ms')
print(f'Improvement: {(1 - avg_wait_cfs/avg_wait_fcfs)*100:.1f}%')
for n in [5, 10, 20]:
bench = SchedulerBenchmark(num_processes=n)
bench.run_benchmark()
print()
Expected output:
Benchmark: 5 processes
FCFS average wait: 14.2ms
CFS average wait: 8.6ms
Improvement: 39.4%
Benchmark: 10 processes
FCFS average wait: 28.7ms
CFS average wait: 15.3ms
Improvement: 46.7%
...
FAQ
Related Concepts
What's Next
You now understand advanced CPU scheduling. Next, learn about I/O systems and device management to understand how the OS manages hardware devices, or explore real-time operating systems for deterministic scheduling.
- Practice daily — Run
chrt -mto see available scheduling policies. Runcat /proc/sched_debugto see CFS state. - Build a project — Create a scheduling visualizer that shows CFS red-black tree state after each step.
- Explore related topics — Study sched_ext for writing custom BPF schedulers.
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro