Process Scheduling Algorithms

Imagine you’re a air traffic controller managing a runway. You have planes (processes) of different sizes, different urgency levels, and different destinations (CPU burst lengths). Your job: keep the runway busy, minimize waiting time, and somehow satisfy everyone.

This is essentially what the CPU scheduler does — every millisecond, deciding which runnable process gets the CPU. The algorithm you choose determines whether your system feels responsive or sluggish, whether short tasks complete quickly or get buried under long ones.

Introduction

CPU scheduling algorithms decide which runnable process to run next on each CPU core. The scheduler makes this decision based on various factors: burst time, priority, waiting time, and the scheduling policy.

Modern systems often use multiple algorithms in combination. Linux’s Completely Fair Scheduler (CFS) handles normal processes, while special schedulers handle real-time tasks. Windows uses a multi-level feedback queue that dynamically adjusts priorities.

When to Use

• System tuning — Choosing the right scheduler improves responsiveness
• Real-time applications — Guaranteeing deadlines requires specific algorithms
• Batch processing — Maximizing throughput is the primary goal
• Multi-user systems — Fairness ensures no user gets starved

When Not to Use

• Simple scripts — Default scheduler is sufficient
• Single-user interactive — System defaults are optimized for this
• Embedded with fixed workload — Custom schedulers add complexity

---

Types of Scheduling

Non-Preemptive vs Preemptive

Non-preemptive: Once a process starts running, it runs to completion (or until it blocks). Simple but can’t respond to higher priority tasks quickly.

Preemptive: The scheduler can interrupt a running process and switch to another. Modern OSes use preemptive scheduling for responsiveness.

graph LR
    subgraph Non-Preemptive
        A1[Process A starts] --> A2[A runs to completion]
    end

    subgraph Preemptive
        B1[Process B starts] --> B2[B preempted]
        B2 --> C1[Process C runs]
        C1 --> B3[B resumes]
    end

    style Non-Preemptive stroke:#4a1a1a
    style Preemptive stroke:#1a3a1a

---

Core Algorithms

First-Come, First-Served (FCFS)

The simplest algorithm: processes run in the order they arrived.

Pros: Simple, low overhead Cons: Convoy effect — short processes wait behind long ones

// Simulate FCFS scheduling
#include <stdio.h>

typedef struct {
    int pid;
    int arrival_time;
    int burst_time;
} Process;

void fcfs_schedule(Process procs[], int n) {
    int current_time = 0;

    printf("FCFS Scheduling:\n");
    printf("%-10s %-15s %-15s %-15s\n", "PID", "Start Time", "End Time", "Wait Time");

    for (int i = 0; i < n; i++) {
        int wait = current_time - procs[i].arrival_time;
        if (wait < 0) wait = 0;
        int start = current_time;
        current_time += procs[i].burst_time;
        int end = current_time;

        printf("%-10d %-15d %-15d %-15d\n", procs[i].pid, start, end, wait);
    }
}

Shortest Job First (SJF)

Select the process with the shortest burst time. Optimal for minimizing average waiting time — but requires knowing burst times in advance (which is rarely possible).

Pros: Optimal average wait time Cons: Starvation of long processes; requires burst time prediction

// Simulate SJF scheduling (non-preemptive)
#include <stdio.h>
#include <limits.h>

void sjf_schedule(Process procs[], int n) {
    int completed = 0;
    int current_time = 0;
    int total_wait = 0;

    int remaining = n;
    int visited[n];
    for (int i = 0; i < n; i++) visited[i] = 0;

    printf("\nSJF Scheduling:\n");
    printf("%-10s %-15s %-15s %-15s %-15s\n", "PID", "Arrival", "Burst", "Start", "Wait");

    while (completed < n) {
        int shortest = -1;
        int min_burst = INT_MAX;

        // Find shortest job that's arrived and not completed
        for (int i = 0; i < n; i++) {
            if (!visited[i] && procs[i].arrival_time <= current_time &&
                procs[i].burst_time < min_burst) {
                shortest = i;
                min_burst = procs[i].burst_time;
            }
        }

        if (shortest == -1) {
            current_time++;
            continue;
        }

        int wait = current_time - procs[shortest].arrival_time;
        int start = current_time;
        current_time += procs[shortest].burst_time;
        int end = current_time;

        printf("%-10d %-15d %-15d %-15d %-15d\n",
               procs[shortest].pid, procs[shortest].arrival_time,
               procs[shortest].burst_time, start, wait);

        total_wait += wait;
        visited[shortest] = 1;
        completed++;
    }

    printf("Average wait time: %.2f\n", (float)total_wait / n);
}

Round Robin (RR)

Each process gets a fixed time slice (quantum). When the quantum expires, the process goes to the back of the ready queue. Designed for time-sharing.

Pros: Fair, good response time, handles starvation Cons: Higher context switch overhead, depends on quantum size

#!/usr/bin/env python3
"""Round Robin Scheduler Simulation."""

from collections import deque

class Process:
    def __init__(self, pid, burst, arrival=0):
        self.pid = pid
        self.burst = burst
        self.arrival = arrival
        self.remaining = burst
        self.wait_time = 0
        self.turnaround = 0

def round_robin(processes, quantum):
    ready = deque(processes)
    current_time = 0
    completed = []

    print(f"Round Robin (quantum={quantum}):")
    print(f"{'Time':<8} {'Event':<20} {'Ready Queue'}")

    while ready:
        process = ready.popleft()

        if process.arrival > current_time:
            # Skip ahead if no processes have arrived
            current_time = process.arrival
            ready.append(process)
            continue

        # Execute for quantum or until completion
        exec_time = min(quantum, process.remaining)
        current_time += exec_time
        process.remaining -= exec_time

        # Other processes in ready queue wait
        for p in ready:
            if p.arrival <= current_time:
                p.wait_time += exec_time

        if process.remaining == 0:
            process.turnaround = current_time - process.arrival
            completed.append(process)
            print(f"{current_time:<8} P{process.pid} completes")
        else:
            ready.append(process)
            print(f"{current_time:<8} P{process.pid} preempted")

    return completed

# Example
processes = [Process(1, 24), Process(2, 3), Process(3, 3)]
result = round_robin(processes, 4)

print(f"\n{'PID':<8} {'Burst':<8} {'Wait':<8} {'Turnaround':<12}")
print("-" * 40)
for p in result:
    print(f"{p.pid:<8} {p.burst:<8} {p.wait_time:<8} {p.turnaround:<12}")

Priority Scheduling

Processes are assigned priorities. Higher priority processes run first. Two variants:

Preemptive: A new higher-priority process preempts the running one Non-preemptive: Higher priority only matters when current process blocks

Problem: Starvation — low priority processes may never run if higher priority ones keep arriving.

Solution: Aging — gradually increase priority of waiting processes.

// Priority Scheduling with Aging
#include <stdio.h>

#define BASE_PRIORITY 50
#define AGING_RATE 1  // Priority increases by 1 per time unit waiting

typedef struct {
    int pid;
    int base_priority;  // Lower number = higher priority
    int dynamic_priority;
    int remaining_burst;
    int waiting_time;
} Process;

void priority_with_aging(Process procs[], int n, int time_units) {
    printf("\nPriority Scheduling with Aging:\n");

    int completed = 0;
    int current_time = 0;

    while (completed < n) {
        // Update dynamic priorities (aging)
        for (int i = 0; i < n; i++) {
            if (procs[i].remaining_burst > 0 && procs[i].waiting_time > 0) {
                procs[i].dynamic_priority -= AGING_RATE;
                if (procs[i].dynamic_priority < 1) {
                    procs[i].dynamic_priority = 1;  // Max priority
                }
            }
        }

        // Find highest priority (lowest number)
        int highest = -1;
        int highest_priority = 999;

        for (int i = 0; i < n; i++) {
            if (procs[i].remaining_burst > 0 &&
                procs[i].dynamic_priority < highest_priority) {
                highest = i;
                highest_priority = procs[i].dynamic_priority;
            }
        }

        if (highest == -1) {
            current_time++;
            continue;
        }

        // Execute one time unit
        printf("Time %d: P%d (priority %d)\n",
               current_time, procs[highest].pid, procs[highest].dynamic_priority);

        procs[highest].remaining_burst--;
        current_time++;

        // Increment wait time for other processes
        for (int i = 0; i < n; i++) {
            if (i != highest && procs[i].remaining_burst > 0) {
                procs[i].waiting_time++;
            }
        }

        if (procs[highest].remaining_burst == 0) {
            completed++;
        }
    }
}

---

Multi-Level Feedback Queue (MLFQ)

MLFQ combines multiple queues with different priorities and time quantum sizes. Processes start in highest priority queue; if they use their entire quantum, they drop to lower priority. This allows short interactions to complete quickly while CPU-bound jobs get time.

graph TB
    subgraph Q1[Queue 1 - Highest Priority]
        A1[Interactive<br/>Quantum: 8ms]
    end
    subgraph Q2[Queue 2 - Medium Priority]
        B1[Mixed<br/>Quantum: 16ms]
    end
    subgraph Q3[Queue 3 - Lowest Priority]
        C1[Batch<br/>Quantum: 32ms]
    end

    A1 -->|Uses full quantum| B1
    B1 -->|Uses full quantum| C1
    C1 -->|Blocked I/O| A1

    A1 -->|Shorter quantum| Scheduler
    B1 -->|Medium quantum| Scheduler
    C1 -->|Longer quantum| Scheduler

    Scheduler -->|picks highest non-empty| A1
    Scheduler -->|picks highest non-empty| B1
    Scheduler -->|picks highest non-empty| C1

    style Q1 stroke:#1a4a1a
    style Q2 stroke:#1a1a4a
    style Q3 stroke:#4a1a1a

---

Architecture Diagram

sequenceDiagram
    participant P1 as Process A (CPU-bound)
    participant P2 as Process B (Interactive)
    participant Scheduler
    participant CPU

    Note over Scheduler,CPU: Time 0ms
    P2->>Scheduler: I/O completes, ready
    Scheduler->>CPU: Schedule P2 (interactive)
    CPU->>P2: Run P2

    Note over Scheduler,CPU: Time 8ms (quantum expires)
    Scheduler->>CPU: Preempt P2, schedule P1
    CPU->>P1: Run P1 (uses full quantum)

    Note over Scheduler,CPU: Time 16ms
    Scheduler->>CPU: Move P1 to lower queue
    Scheduler->>CPU: Schedule P2 again
    CPU->>P2: Continue P2

    Note over Scheduler,CPU: Time 24ms (P2 completes)
    Scheduler->>CPU: Schedule next in Q2
    CPU->>P1: Continue P1 in Q2

---

Production Failure Scenarios

Convoy Effect in FCFS

Problem: A long CPU-bound process blocks short I/O-bound processes. Short jobs wait while long job holds CPU.

Symptoms: System appears responsive at first, then slows as long jobs dominate.

Mitigation: Use Round Robin or SJF to give short jobs priority.

Starvation in Priority Scheduling

Problem: Low priority processes never get CPU time as high priority processes keep arriving.

Symptoms: Certain processes show extremely high wait times, never completing.

Mitigation: Implement aging — increase priority of waiting processes over time.

Quantum Too Small

Problem: Excessive context switches consume more CPU than useful work.

Symptoms: High system CPU utilization but low throughput, high context switch rate.

Mitigation: Profile with perf sched and adjust quantum. Rule: quantum should be 10x context switch cost.

Quantum Too Large

Problem: System feels unresponsive; long processes block short ones.

Symptoms: Poor response time for interactive tasks despite idle CPU.

Mitigation: Smaller quantum or combination of algorithms (interactive vs batch).

---

Trade-off Table

Algorithm	Avg Wait	Response	Throughput	Fairness
FCFS	High	Poor	Medium	Unfair
SJF	Lowest	Poor	Highest	Unfair (starvation)
Round Robin	Medium	Best	Medium	Fair
Priority	Variable	Variable	Variable	Unfair (starvation)
MLFQ	Low	Best	Highest	Fair

Scenario	Best Algorithm	Why
Batch processing	SJF	Maximize throughput
Interactive desktop	Round Robin / MLFQ	Minimize response time
Real-time systems	Fixed priority / Rate monotonic	Guarantees deadlines
Multi-user timeshare	Round Robin	Fairness
Mixed workload	MLFQ	Adapts dynamically

Quantum Setting	Context Switches	Response Time
Too small	Many	Low (but wasted overhead)
Optimal	Moderate	Good balance
Too large	Few	Poor response time

---

Implementation Snippets

Implementing a Simple MLFQ

#!/usr/bin/env python3
"""Multi-Level Feedback Queue Scheduler."""

from collections import deque

class Process:
    def __init__(self, pid, burst, priority=0):
        self.pid = pid
        self.burst = burst
        self.priority = priority  # 0 = highest
        self.remaining = burst

class MLFQScheduler:
    def __init__(self, num_queues=3, quantums=[8, 16, 32]):
        self.queues = [deque() for _ in range(num_queues)]
        self.quantums = quantums

    def add_process(self, proc):
        self.queues[proc.priority].append(proc)

    def schedule(self):
        time = 0
        completed = []

        while True:
            # Find highest non-empty queue
            chosen = None
            for i, q in enumerate(self.queues):
                if q:
                    chosen = (i, q.popleft())
                    break

            if chosen is None:
                break

            q_idx, proc = chosen
            quantum = self.quantums[q_idx]

            # Execute for quantum or until completion
            exec_time = min(quantum, proc.remaining)
            time += exec_time
            proc.remaining -= exec_time

            if proc.remaining == 0:
                proc.turnaround = time
                completed.append(proc)
                print(f"Time {time}: P{proc.pid} completed")
            else:
                # Demote to lower priority (next queue)
                next_q = min(q_idx + 1, len(self.queues) - 1)
                proc.priority = next_q
                self.queues[next_q].append(proc)
                print(f"Time {time}: P{proc.pid} demoted to Q{next_q}")

        return completed

# Example
scheduler = MLFQScheduler()
processes = [
    Process(1, 20),  # Interactive (will get demoted if CPU-bound)
    Process(2, 10),  # Short interactive
    Process(3, 40),  # Long batch
]
for p in processes:
    scheduler.add_process(p)

results = scheduler.schedule()

Measuring Scheduling Performance

#!/bin/bash
# Measure scheduling performance metrics

echo "=== Scheduler Information ==="
cat /proc/sys/kernel/sched_latency_ns
cat /proc/sys/kernel/sched_min_granularity_ns
cat /proc/sys/kernel/sched_migration_cost_ns

echo -e "\n=== Context Switches ==="
cat /proc/stat | grep ctxt

echo -e "\n=== Run Queue Length ==="
vmstat 1 5

echo -e "\n=== Process State ==="
ps -eo state,pid,cmd | sort | uniq -c | sort -rn

echo -e "\n=== Scheduler Trace ==="
sudo perf sched record -- sleep 5
sudo perf sched latency

---

Observability Checklist

Key Metrics

# CPU utilization per core
mpstat -P ALL 1

# Run queue length (should be < 4 * cores)
vmstat 1 | awk '{print $r}'

# Context switches per second
sar -w 1

# Average scheduling latency
cat /proc/sched_debug | grep latency

Tracing

# Trace scheduling decisions
sudo perf trace -e sched:*

# Scheduler latency histogram
perf sched record -- sleep 10
perf sched timehist

# Per-process scheduling info
ps -eo pid,psr,ni,time,cmd --sort=-time

---

Common Pitfalls / Anti-Patterns

Priority Manipulation Attacks

Unprivileged users setting negative nice values can starve others. Restrict via:

# /etc/security/limits.conf
* hard nice 0

Real-time Process Security

Real-time scheduling classes (SCHED_FIFO, SCHED_RR) can monopolize CPU. Require CAP_SYS_NICE or proper cgroup configuration.

---

Common Pitfalls / Anti-patterns

Ignoring quantum tuning

Default quantum may not match workload. Profile and adjust.

Using SJF without burst prediction

In production, burst times aren’t known. Use MLFQ to approximate SJF behavior.

Forgetting about I/O blocking

Processes that block frequently should get higher priority — don’t treat all runnable processes the same.

Not considering multi-core

Single queue vs per-CPU queues have different tradeoffs for cache affinity vs contention.

---

Quick Recap Checklist

• FCFS is simple but causes convoy effect
• SJF minimizes average wait but requires knowing burst times
• Round Robin is fair with good response time; quantum size matters
• Priority scheduling has starvation; use aging to mitigate
• MLFQ combines multiple algorithms, dynamically adjusting
• Quantum too small = excessive context switches; too large = poor response
• No single algorithm is best — trade-offs depend on workload

---

Interview Questions

Further Reading

• Process Scheduling — General scheduling theory, context switching, and scheduler types
• CPU Affinity & Real-Time OS — Real-time scheduling policies (SCHED_FIFO, SCHED_RR, SCHED_DEADLINE)

---

Conclusion

Process scheduling algorithms are the mechanism by which operating systems decide which runnable process gets CPU time. The choice of algorithm profoundly impacts system responsiveness, throughput, and fairness.

FCFS is simple but vulnerable to the convoy effect, where short processes wait behind long ones. SJF achieves optimal average wait time but requires knowing burst times in advance and causes starvation of long processes. Round Robin provides fair scheduling with good response time, but quantum size is critical — too small causes excessive context switches, too large degrades interactivity.

Priority scheduling allows important work to run first, but without aging, low-priority processes can starve indefinitely. Multi-Level Feedback Queue (MLFQ) dynamically adapts, giving interactive processes quick response while letting CPU-bound jobs progress without dominating. Modern Linux, Windows, and macOS all combine multiple algorithms this way.

For your next step, explore CPU interrupts and context switches to understand the mechanics of how the scheduler actually transfers control between processes, or dive into synchronization primitives (mutexes, semaphores, condition variables) which protect shared data in concurrent multi-threaded environments.