Process Scheduling Algorithms in Depth
Process scheduling determines which process runs on the CPU at any given moment. The scheduler’s decisions directly impact system throughput, responsiveness, and fairness. Different workloads demand different scheduling strategies — a web server, a real-time control system, and a batch compute cluster each need a scheduler tuned to their priorities.
First-Come, First-Served (FCFS)
FCFS is the simplest scheduling algorithm: processes are queued in arrival order, and each runs to completion before the next starts. It is implemented with a FIFO queue and is the default in many batch systems. The main advantage is low overhead — no context switching between processes until one finishes. The critical weakness is the convoy effect: a single long-running process blocks all subsequent short processes, dramatically increasing average waiting time.
def fcfs(processes):
"""
processes: list of (pid, arrival_time, burst_time)
"""
time = 0
results = []
for pid, at, bt in sorted(processes, key=lambda p: p[1]):
if time < at:
time = at
start = time
time += bt
results.append({
'pid': pid, 'start': start, 'finish': time,
'turnaround': time - at, 'wait': start - at
})
return results
procs = [(1, 0, 24), (2, 0, 3), (3, 0, 3)] # convoy example
res = fcfs(procs)
for r in res:
print(f"P{r['pid']}: wait={r['wait']}, turnaround={r['turnaround']}")
# Output: P1: wait=0, turnaround=24
# P2: wait=24, turnaround=27
# P3: wait=27, turnaround=30
# Average wait: 17 — terrible for short processes behind a long oneShortest Job First (SJF)
SJF schedules the process with the smallest burst time next. It is provably optimal for minimizing average waiting time (shortest average turnaround time). The catch is that burst times are unknown in advance — the scheduler must predict them using exponential averaging of past behavior. In practice, SJF can cause starvation: long-running processes may never execute if short jobs keep arriving. Preemptive SJF (Shortest Remaining Time First) switches to a newly arrived shorter job, further improving average wait but increasing overhead.
def sjf_nonpreemptive(processes):
"""
Non-preemptive Shortest Job First.
"""
processes = sorted(processes, key=lambda p: (p[1], p[2])) # by arrival, then burst
n = len(processes)
time = 0
completed = []
remaining = processes[:]
while remaining:
# Pick shortest burst among arrived processes
available = [p for p in remaining if p[1] <= time]
if not available:
time = min(p[1] for p in remaining)
continue
chosen = min(available, key=lambda p: p[2])
remaining.remove(chosen)
pid, at, bt = chosen
start = time
time += bt
completed.append({
'pid': pid, 'start': start, 'finish': time,
'turnaround': time - at, 'wait': start - at
})
return completed
# SJF prediction using exponential averaging
def predict_burst(history, alpha=0.5):
tau = history[0] if history else 5.0 # initial guess
for actual in history:
tau = alpha * actual + (1 - alpha) * tau
return tau
# Example: process with varying CPU bursts
burst_history = [8, 6, 10, 4, 7]
predicted = [predict_burst(burst_history[:i]) for i in range(1, len(burst_history)+1)]
print("Predicted bursts:", [f"{p:.1f}" for p in predicted])
# Output: Predicted bursts: ['8.0', '7.0', '8.5', '6.2', '6.6']Round-Robin (RR)
Round-Robin is FCFS with preemption: each process runs for a fixed time quantum (typically 10–100 ms), then is moved to the back of the ready queue. RR provides fair CPU sharing and fast response time for interactive processes. The choice of quantum is critical — too small and context-switch overhead dominates; too large and the scheduler degrades toward FCFS. O(1) context switch cost means quantum should be at least 10× the switch time (usually under 1 µs) to keep overhead below 10%.
def round_robin(processes, quantum=4):
"""
processes: list of (pid, burst_time) — assumes all arrive at time 0.
"""
queue = [(pid, burst) for pid, burst in processes]
time = 0
results = {pid: {'pid': pid, 'burst': bt, 'start': None, 'finish': 0}
for pid, bt in processes}
while queue:
pid, remaining = queue.pop(0)
if results[pid]['start'] is None:
results[pid]['start'] = time
if remaining > quantum:
time += quantum
queue.append((pid, remaining - quantum))
else:
time += remaining
results[pid]['finish'] = time
for r in sorted(results.values(), key=lambda x: x['pid']):
print(f"P{r['pid']}: start={r['start']}, finish={r['finish']}, "
f"turnaround={r['finish']}")
avg_turnaround = sum(r['finish'] for r in results.values()) / len(results)
print(f"Average turnaround: {avg_turnaround:.1f}")
round_robin([(1, 24), (2, 3), (3, 3)], quantum=4)
# Output: P1: start=0, finish=30, turnaround=30
# P2: start=4, finish=7, turnaround=7
# P3: start=7, finish=10, turnaround=10
# Average turnaround: 15.7 — much better than FCFS (27) for short processesMulti-Level Feedback Queue (MLFQ)
MLFQ is the most practical general-purpose scheduler, used in BSD Unix and as the basis for the Linux scheduler before CFS. It maintains multiple queues with different priority levels. A process starts at the highest-priority queue and moves down after using its full quantum, while it moves up if it voluntarily yields the CPU (e.g., waiting for I/O). This gives interactive processes (short bursts, I/O-bound) high priority and batch processes (CPU-bound) low priority, achieving both responsiveness and throughput without prior knowledge of burst times.
class MLFQ:
"""
Multi-Level Feedback Queue with 3 levels and priority boost.
"""
def __init__(self, quanta=[4, 8, 16], boost_interval=50):
self.queues = [[] for _ in range(len(quanta))]
self.quanta = quanta
self.boost_interval = boost_interval
self.time = 0
self.processes = {} # pid -> {'burst': remaining, 'level': 0, 'yielded': True/False}
def add_process(self, pid, burst_time):
self.processes[pid] = {'burst': burst_time, 'level': 0}
self.queues[0].append(pid)
def tick(self):
self.time += 1
# Priority boost to prevent starvation
if self.time % self.boost_interval == 0:
for level in range(1, len(self.queues)):
while self.queues[level]:
pid = self.queues[level].pop(0)
self.queues[0].append(pid)
self.processes[pid]['level'] = 0
# Pick first non-empty queue (highest priority)
for level, q in enumerate(self.queues):
if q:
pid = q.pop(0)
proc = self.processes[pid]
quantum = self.quanta[level]
run_for = min(quantum, proc['burst'])
proc['burst'] -= run_for
self.time += run_for - 1 # tick accounts for 1
if proc['burst'] <= 0:
print(f" P{pid} finished at t={self.time}")
else:
# Demote if used full quantum
new_level = min(level + 1, len(self.queues) - 1)
proc['level'] = new_level
self.queues[new_level].append(pid)
return
# Demo: mix of CPU-bound and I/O-bound processes
mlfq = MLFQ()
mlfq.add_process(1, 30) # CPU-bound
mlfq.add_process(2, 5) # I/O-bound (short)
mlfq.add_process(3, 15) # mixed
for _ in range(55):
mlfq.tick()
# Output will show short jobs completing quickly at high priority,
# while CPU-bound job gets demoted to lower queuesLinux Completely Fair Scheduler (CFS)
Introduced in Linux 2.6.23, CFS replaced the O(1) scheduler with a radically different approach. Instead of fixed time slices, CFS models the CPU as a resource that should be perfectly shared among runnable processes. It maintains a red-black tree keyed by virtual runtime (vruntime) — the amount of time a process has run, normalized by its priority (nice value). The scheduler always picks the process with the smallest vruntime (leftmost node in the tree). CFS achieves fairness, O(log n) scheduling decisions, and excellent interactivity without multiple queues.
# Simplified CFS in Python
import heapq # using heap instead of red-black for clarity
class CFS:
def __init__(self, nice_values=None):
self.runqueue = [] # min-heap of (vruntime, pid)
self.vruntimes = {}
self.nice = nice_values or {}
self.weight = {}
self._init_weights()
def _init_weights(self):
# Approximate CFS weight table (nice 0 = 1024)
for nice in range(-20, 20):
self.weight[nice] = int(1024 / (1.25 ** nice))
def add_process(self, pid, nice=0):
self.vruntimes[pid] = 0
self.nice[pid] = nice
heapq.heappush(self.runqueue, (0, pid))
def schedule(self, delta=1):
"""Run the process with smallest vruntime for 'delta' time."""
if not self.runqueue:
return None
vruntime, pid = heapq.heappop(self.runqueue)
weight = self.weight.get(self.nice[pid], 1024)
# vruntime advancement: actual_time * (1024 / weight)
vruntime_advance = delta * (1024 / weight)
self.vruntimes[pid] += vruntime_advance
heapq.heappush(self.runqueue, (self.vruntimes[pid], pid))
return pid
# Demo
cfs = CFS()
cfs.add_process(1, nice=0) # default priority
cfs.add_process(2, nice=5) # lower priority (gets less CPU)
cfs.add_process(3, nice=-5) # higher priority (gets more CPU)
for _ in range(20):
ran = cfs.schedule()
for pid in [1, 2, 3]:
print(f"P{pid} (nice={cfs.nice[pid]}): vruntime={cfs.vruntimes[pid]:.2f}")
# Output demonstrates that despite equal run() calls,
# higher-priority (lower nice) processes accumulate vruntime more slowly,
# giving them more CPU timeReal-Time Scheduling
For hard real-time systems, schedulers must guarantee deadlines. Rate-Monotonic Scheduling (RMS) assigns static priorities inversely proportional to period — tasks with shorter periods get higher priority. Earliest Deadline First (EDF) dynamically prioritizes the task with the nearest deadline. RMS is optimal among fixed-priority schedulers; EDF can achieve 100% utilization theoretically but suffers from overload unpredictability. Linux supports both SCHED_FIFO and SCHED_RR (POSIX real-time policies) via the PREEMPT_RT patch set.
# Earliest Deadline First simulation
def edf(tasks, runtime=100):
"""
tasks: [(pid, period, execution_time, deadline)]
Returns schedule with deadline misses tracked.
"""
schedule = []
misses = 0
time = 0
ready = []
while time < runtime:
# Add newly released jobs
for pid, period, exec_time, deadline in tasks:
if time % period == 0:
ready.append({
'pid': pid, 'remaining': exec_time,
'deadline': time + deadline
})
# Sort by earliest deadline
ready.sort(key=lambda j: j['deadline'])
if not ready:
schedule.append(('idle', time, time + 1))
time += 1
continue
job = ready.pop(0)
schedule.append((job['pid'], time, time + 1))
job['remaining'] -= 1
if job['remaining'] > 0:
ready.append(job)
elif time + 1 > job['deadline']:
misses += 1
time += 1
return schedule, misses
tasks = [(1, 10, 3, 10), (2, 15, 5, 15), (3, 20, 4, 20)]
sched, misses = edf(tasks, runtime=60)
print(f"Deadline misses: {misses}")
# Output: Deadline misses: 0 (feasible schedule)Choosing the right scheduler depends on your workload: FCFS for batch throughput, SJF when burst times are predictable, RR for interactive fairness, MLFQ for general-purpose multitasking, CFS for modern Linux systems, and EDF for hard real-time constraints. Most modern operating systems combine multiple approaches — Linux's CFS handles normal processes while SCHED_FIFO/SCHED_RR supports real-time tasks, all running under the same kernel.