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 one

Shortest 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 processes

Multi-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 queues

Linux 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 time

Real-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.