Process Scheduling Algorithms — FCFS, SJF, Round Robin & CFS

Process scheduling decides which process runs next on the CPU. The right scheduler can make a slow computer feel fast and a busy server stay responsive.

What You’ll Learn

In this tutorial, you’ll learn the major scheduling algorithms: First-Come First-Served, Shortest Job First (preemptive and non-preemptive), Round Robin, priority scheduling, multilevel queue and multilevel feedback queue, and the Linux Completely Fair Scheduler (CFS). You’ll also learn scheduling metrics and the trade-offs between throughput, fairness, and responsiveness.

Why It Matters

Every operating system you use — Windows, Linux, macOS, Android — has a scheduler that determines how responsive your apps feel. A bad scheduler makes a powerful machine feel sluggish.

Real-World Use

When you open 20 browser tabs while a video renders in the background, the OS scheduler decides which task gets CPU time. Video streaming needs consistent slice times; background downloads can wait. Durga Antivirus Pro uses I/O-bound background scanning that must not interfere with foreground applications.

    gantt
    title CPU Scheduling Timeline
    dateFormat  X
    axisFormat %s
    section Process A
    Running :a, 0, 2
    section Process B
    Ready   :b1, 0, 1
    Running :b2, 1, 3
    section Process C
    Ready   :c1, 0, 2
    Running :c2, 2, 4
  

Scheduling Metrics

class Process:
    def __init__(self, pid, burst, arrival=0):
        self.pid = pid
        self.burst = burst
        self.arrival = arrival
        self.remaining = burst
        self.completion = 0
        self.start_time = None
        self.waiting = 0
        self.turnaround = 0

def print_metrics(processes, algo_name):
    print(f'\n=== {algo_name} ===')
    avg_wait = sum(p.turnaround - p.burst for p in processes) / len(processes)
    avg_turn = sum(p.turnaround for p in processes) / len(processes)
    print(f'Avg waiting time: {avg_wait:.1f}')
    print(f'Avg turnaround:  {avg_turn:.1f}')
    for p in processes:
        print(f'  P{p.pid}: burst={p.burst} arrival={p.arrival} '
              f'completion={p.completion} turn={p.turnaround}')

FCFS (First-Come, First-Served)

The simplest algorithm: processes run in arrival order. Non-preemptive — once a process gets the CPU, it runs to completion.

def fcfs(processes):
    time = 0
    for p in sorted(processes, key=lambda p: p.arrival):
        if time < p.arrival:
            time = p.arrival
        p.start_time = time
        p.completion = time + p.burst
        p.turnaround = p.completion - p.arrival
        time = p.completion

processes = [Process(1, 6, 0), Process(2, 8, 1),
             Process(3, 7, 2), Process(4, 3, 3)]
fcfs(processes)
print_metrics(processes, 'FCFS')

Expected output:

=== FCFS ===
Avg waiting time: 7.0
Avg turnaround:  13.5
  P1: burst=6 arrival=0 completion=6 turn=6
  P2: burst=8 arrival=1 completion=14 turn=13
  P3: burst=7 arrival=2 completion=21 turn=19
  P4: burst=3 arrival=3 completion=24 turn=21

Convoy effect: A long CPU-bound process delays all shorter ones behind it.

SJF (Shortest Job First)

Non-preemptive SJF: pick the shortest ready process next. Minimises average waiting time but can starve long processes.

def sjf_nonpreemptive(processes):
    ready = []
    time = 0
    completed = []
    remaining = list(processes)

    while remaining or ready:
        # Arriving processes
        for p in remaining[:]:
            if p.arrival <= time:
                ready.append(p)
                remaining.remove(p)

        if ready:
            ready.sort(key=lambda p: p.burst)
            p = ready.pop(0)
            p.start_time = time
            p.completion = time + p.burst
            p.turnaround = p.completion - p.arrival
            time = p.completion
            completed.append(p)
        else:
            time += 1

    return completed

completed = sjf_nonpreemptive(processes)
print_metrics(completed, 'SJF (Non-Preemptive)')

Expected output:

=== SJF (Non-Preemptive) ===
Avg waiting time: 5.0
Avg turnaround:  11.5
  P1: burst=6 arrival=0 completion=6 turn=6
  P4: burst=3 arrival=3 completion=9 turn=6
  P3: burst=7 arrival=2 completion=16 turn=14
  P2: burst=8 arrival=1 completion=24 turn=23

Preemptive SJF (SRTF)

Shortest Remaining Time First — preempts the running process if a new process arrives with a shorter remaining time.

def srtf(processes):
    time = 0
    completed = 0
    n = len(processes)
    prev = None
    ready = []
    remaining = {p.pid: p.burst for p in processes}

    while completed < n:
        # New arrivals
        for p in processes:
            if p.arrival == time:
                ready.append(p)

        if ready:
            # Pick process with shortest remaining time
            current = min(ready, key=lambda p: remaining[p.pid])
            remaining[current.pid] -= 1

            if current.start_time is None:
                current.start_time = time

            if remaining[current.pid] == 0:
                current.completion = time + 1
                current.turnaround = current.completion - current.arrival
                ready.remove(current)
                completed += 1

        time += 1

srtf(processes)
print_metrics(processes, 'SRTF (Preemptive SJF)')

Round Robin

Each process gets a fixed time quantum (typically 10-100ms). After the quantum expires, the process is preempted and moved to the end of the ready queue.

from collections import deque

def round_robin(processes, quantum=4):
    queue = deque()
    time = 0
    remaining = {p.pid: p.burst for p in processes}
    ready = list(processes)

    while ready or queue:
        # Arrivals
        for p in ready[:]:
            if p.arrival <= time:
                queue.append(p)
                ready.remove(p)

        if queue:
            p = queue.popleft()
            if p.start_time is None:
                p.start_time = time

            run = min(quantum, remaining[p.pid])
            remaining[p.pid] -= run
            time += run

            # New arrivals during execution
            for proc in ready[:]:
                if proc.arrival <= time:
                    queue.append(proc)
                    ready.remove(proc)

            if remaining[p.pid] > 0:
                queue.append(p)  # Back to queue
            else:
                p.completion = time
                p.turnaround = p.completion - p.arrival
        else:
            time += 1

processes2 = [Process(1, 10, 0), Process(2, 5, 2),
              Process(3, 8, 4), Process(4, 2, 6)]
round_robin(processes2)
print_metrics(processes2, f'Round Robin (quantum=4)')

Priority Scheduling

Each process has a priority number. The scheduler always picks the highest-priority ready process. Starvation: low-priority processes may never run.

Solution: aging — gradually increase the priority of waiting processes.

def priority_scheduling(processes):
    time = 0
    completed = 0
    ready = []
    priorities = {1: 3, 2: 1, 3: 2, 4: 4}  # lower = higher priority
    remaining = {p.pid: p.burst for p in processes}
    n = len(processes)

    while completed < n:
        for p in processes:
            if p.arrival <= time and p not in ready \
               and remaining[p.pid] > 0:
                ready.append(p)

        if ready:
            ready.sort(key=lambda p: priorities[p.pid])
            current = ready[0]
            remaining[current.pid] -= 1

            if current.start_time is None:
                current.start_time = time

            if remaining[current.pid] == 0:
                current.completion = time + 1
                current.turnaround = current.completion - current.arrival
                ready.remove(current)
                completed += 1

        time += 1

priority_scheduling(processes2)
print_metrics(processes2, 'Priority Scheduling')

Multilevel Feedback Queue (MLFQ)

MLFQ has multiple queues with different priorities. A process that uses its full quantum moves to a lower-priority queue; one that yields the CPU early stays in a high-priority queue. This separates interactive and batch processes automatically.

Level 0 (RR, quantum=8ms) — interactive processes
    ↓ on timeout
Level 1 (RR, quantum=16ms) — mixed
    ↓ on timeout
Level 2 (FCFS) — CPU-bound (batch)

CFS — Linux Completely Fair Scheduler

CFS uses a red-black tree of processes keyed by vruntime (virtual runtime). It always picks the process with the smallest vruntime — giving every process a fair share of CPU.

• Targeted latency: time interval each process gets to run (default ~6ms per process at 4kHz tick)
• Minimum granularity: minimum time slice before preemption (default ~1ms)
• Nice values: nice -20 gets ~95% CPU, nice +19 gets ~5%

class CFSProcess:
    def __init__(self, pid, nice=0):
        self.pid = pid
        self.vruntime = 0
        self.nice = nice
        self.weight = 1024 / (1.25 ** nice)

    def run(self, time_slice):
        self.vruntime += time_slice * (1024 / self.weight)
        return self.vruntime

def cfs_schedule(processes, total_time=100):
    time = 0
    while time < total_time:
        # Pick process with smallest vruntime
        current = min(processes, key=lambda p: p.vruntime)
        slice = 6  # target latency / n
        current.run(slice)
        time += slice
        print(f't={time:3d}: P{current.pid} run ({slice}ms) '
              f'vruntime={current.vruntime:.1f}')

procs = [CFSProcess(1, nice=0), CFSProcess(2, nice=5),
         CFSProcess(3, nice=-5)]
cfs_schedule(procs, 30)

Expected output:

t=  6: P2 run (6ms) vruntime=10.9
t= 12: P2 run (6ms) vruntime=21.8
t= 18: P1 run (6ms) vruntime=6.0
t= 24: P3 run (6ms) vruntime=1.5
t= 30: P1 run (6ms) vruntime=12.0

CPU-bound vs I/O-bound

• CPU-bound: spends most time computing (video encoding, scientific simulation). Needs large time slices for throughput.
• I/O-bound: spends most time waiting for I/O (web server, database). Needs small time slices for fast response.

A good scheduler detects: if a process uses its full quantum → CPU-bound, move down. If it yields early → I/O-bound, keep at high priority.

Common Mistakes

1. Using FCFS for interactive workloads

FCFS causes terrible response times. One long process blocks everything. Use Round Robin or MLFQ for interactive systems.

2. Ignoring starvation in priority scheduling

Low-priority processes may never run. Always implement aging (increase priority over time).

3. Setting the Round Robin quantum wrong

Too small (1ms) → excessive context switching overhead. Too large (100ms) → poor interactivity. 10-50ms is typical.

4. Equating “shortest” with “best” in SJF

SJF minimises average waiting time but requires knowing burst times in advance — impossible in practice. Use MLFQ instead.

5. Confusing preemptive and non-preemptive

Preemptive: OS can interrupt a running process. Non-preemptive: process must voluntarily yield. Most modern OS are preemptive.

6. Overlooking context switch overhead

Each context switch (saving/loading registers, TLB flush) takes ~1-5 microseconds. At 1000 switches/second, that’s 1-5% CPU overhead.

Practice Questions

1. What’s the difference between preemptive and non-preemptive scheduling? Preemptive: the OS can forcibly remove a process from the CPU. Non-preemptive: the process runs until it blocks or yields.

2. Why does Round Robin perform poorly with a very small quantum? Context switch overhead dominates. If switching takes 1ms and the quantum is 2ms, 33% of CPU is wasted on switching.

3. What problem does MLFQ solve? It automatically separates interactive (I/O-bound) and batch (CPU-bound) processes without needing a priori knowledge.

4. How does CFS achieve fairness? It tracks vruntime per process and always picks the one with the smallest vruntime. All processes make proportional progress.

5. What is the convoy effect in FCFS? A long CPU-bound process arriving first delays all subsequent short processes, increasing average waiting time.

Challenge

Implement an MLFQ scheduler with 3 levels: Level 0 (RR q=8), Level 1 (RR q=16), Level 2 (FCFS). Demote processes that use their full quantum; promote processes that wake up from I/O. Test with a mix of I/O-bound and CPU-bound processes.

Real-World Task

On a Linux machine, run top and identify which processes are I/O-bound (high %wait) vs CPU-bound (high %CPU). Check which scheduler is in use: cat /sys/block/sda/queue/scheduler.

FAQ

Mini Project: Scheduler Simulator

Build an interactive scheduling simulator that:

1. Lets you define processes (burst, arrival, priority, I/O frequency)
2. Runs FCFS, SJF, RR, Priority, and MLFQ algorithms
3. Visualises a Gantt chart of execution
4. Reports waiting time, turnaround, and response time for each

Security angle: Understanding scheduling helps build fair-share resource allocation in multi-tenant environments (cloud, container hosts). Durga Antivirus Pro uses background priority scanning to avoid interfering with user foreground tasks.

What’s Next

Before moving on, you should understand:

• The difference between FCFS, SJF, Round Robin, and priority scheduling
• How MLFQ separates interactive and batch processes
• CFS’s vruntime-based fairness
• Scheduling metrics: turnaround, waiting, response time

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.