CPU Scheduling Problem: FCFS, SJF, SRTF, and Round Robin Walkthrough

Medium

Interview Question: "Given four processes with varying arrival times and burst times, construct Gantt charts and compute completion time (CT), turnaround time (TAT), and waiting time (WT) for FCFS, Non-Preemptive SJF, Preemptive SRTF, and Round Robin (q = 3 ms). Why does SRTF achieve minimal average waiting time, and why is it rarely used in production kernels?"

Problem Specification & Dataset

Consider four processes arriving in the ready queue with the following characteristics:

Process	Arrival Time (AT)	Burst Time (BT)
P1	0 ms	8 ms
P2	1 ms	4 ms
P3	2 ms	9 ms
P4	3 ms	5 ms

The two numbers every part of this problem comes down to:

Turnaround Time: how long a process was in the system, start to finish — TAT = CT - AT
Waiting Time: of that time, how much was spent just waiting for the CPU — WT = TAT - BT

Part 1: First-Come, First-Served (FCFS)

FCFS executes processes strictly in order of their arrival without preemption.

Gantt Chart

P18ms

P24ms

P39ms

P45ms

08122126

Step-by-Step Calculation Table

Process	AT	BT	Completion (CT)	Turnaround Time (TAT = CT - AT)	Waiting Time (WT = TAT - BT)
P1	0 ms	8 ms	8 ms	8 - 0 = 8 ms	8 - 8 = 0 ms
P2	1 ms	4 ms	12 ms	12 - 1 = 11 ms	11 - 4 = 7 ms
P3	2 ms	9 ms	21 ms	21 - 2 = 19 ms	19 - 9 = 10 ms
P4	3 ms	5 ms	26 ms	26 - 3 = 23 ms	23 - 5 = 18 ms

Average Turnaround Time: (8 + 11 + 19 + 23) / 4 = 61 / 4 = 15.25 ms
Average Waiting Time: (0 + 7 + 10 + 18) / 4 = 35 / 4 = 8.75 ms

The Convoy Effect: P4 only requires 5 ms of computation, but sat waiting for 18 ms behind the long burst of P3. FCFS heavily penalizes short jobs when scheduled behind long CPU-bound tasks.

Part 2: Shortest Job First (SJF): Non-Preemptive

In Non-Preemptive SJF, once a process begins execution, it runs to completion. Whenever the CPU becomes idle, the scheduler dispatches the available arrived process with the shortest burst time.

Execution Timeline:

t = 0 ms: Only P1 has arrived. P1 starts and runs uninterrupted until t = 8 ms.
t = 8 ms: P1 finishes. Arrived processes in ready queue: P2 (BT = 4 ms), P3 (BT = 9 ms), P4 (BT = 5 ms). Shortest job is P2. Runs t = 8 -> 12 ms.
t = 12 ms: P2 finishes. Remaining in queue: P4 (BT = 5 ms), P3 (BT = 9 ms). Shortest job is P4. Runs t = 12 -> 17 ms.
t = 17 ms: P4 finishes. Remaining in queue: P3 (BT = 9 ms). Runs t = 17 -> 26 ms.

Gantt Chart

P18ms

P24ms

P45ms

P39ms

08121726

Step-by-Step Calculation Table

Process	AT	BT	Completion (CT)	Turnaround Time (TAT = CT - AT)	Waiting Time (WT = TAT - BT)
P1	0 ms	8 ms	8 ms	8 - 0 = 8 ms	8 - 8 = 0 ms
P2	1 ms	4 ms	12 ms	12 - 1 = 11 ms	11 - 4 = 7 ms
P4	3 ms	5 ms	17 ms	17 - 3 = 14 ms	14 - 5 = 9 ms
P3	2 ms	9 ms	26 ms	26 - 2 = 24 ms	24 - 9 = 15 ms

Average Turnaround Time: (8 + 11 + 14 + 24) / 4 = 57 / 4 = 14.25 ms
Average Waiting Time: (0 + 7 + 9 + 15) / 4 = 31 / 4 = 7.75 ms

Part 3: Shortest Remaining Time First (SRTF): Preemptive SJF

In SRTF, if a newly arrived process has a remaining burst time strictly less than the currently running process, the current process is preempted immediately.

Execution Timeline:

t = 0 ms: P1 starts running (BT = 8 ms).
t = 1 ms: P2 arrives with BT = 4 ms. P1 has remaining burst 7 ms. Because 4 < 7, P2 preempts P1!
t = 1 -> 5 ms: P2 runs to completion at t = 5 ms. During this interval, P3 arrives at t = 2 ms (BT = 9 ms) and P4 arrives at t = 3 ms (BT = 5 ms).
t = 5 ms: Ready queue: P4 (BT = 5 ms), P1 (rem = 7 ms), P3 (BT = 9 ms). Shortest remaining job is P4. Runs t = 5 -> 10 ms.
t = 10 ms: P4 completes. Ready queue: P1 (rem = 7 ms), P3 (BT = 9 ms). Shortest remaining job is P1. Runs t = 10 -> 17 ms.
t = 17 ms: P1 completes. Only P3 remains (rem = 9 ms). Runs t = 17 -> 26 ms.

Gantt Chart

P11ms

P24ms

P45ms

P17ms

P39ms

015101726

Step-by-Step Calculation Table

Process	AT	BT	Completion (CT)	Turnaround Time (TAT = CT - AT)	Waiting Time (WT = TAT - BT)
P1	0 ms	8 ms	17 ms	17 - 0 = 17 ms	17 - 8 = 9 ms
P2	1 ms	4 ms	5 ms	5 - 1 = 4 ms	4 - 4 = 0 ms
P4	3 ms	5 ms	10 ms	10 - 3 = 7 ms	7 - 5 = 2 ms
P3	2 ms	9 ms	26 ms	26 - 2 = 24 ms	24 - 9 = 15 ms

Average Turnaround Time: (17 + 4 + 7 + 24) / 4 = 52 / 4 = 13.00 ms
Average Waiting Time: (9 + 0 + 2 + 15) / 4 = 26 / 4 = 6.50 ms

Part 4: Round Robin (RR, Quantum = 3 ms)

Processes are dispatched in a circular FIFO queue for a maximum time quantum of q = 3 ms. If a process does not finish within 3 ms, it is preempted and returned to the tail of the ready queue.

Ready Queue Trace (q = 3 ms):

t = 0 ms: P1 arrives. Queue: [P1]. P1 runs t = 0 -> 3 ms (remaining burst = 5 ms).
During this window: P2 arrives at t = 1 ms, P3 arrives at t = 2 ms, and P4 arrives at t = 3 ms.
Newly arrived P4 is enqueued before preempted P1. Queue becomes: [P2, P3, P4, P1].
t = 3 -> 6 ms: P2 runs 3 ms (remaining burst = 1 ms). Queue: [P3, P4, P1, P2].
t = 6 -> 9 ms: P3 runs 3 ms (remaining burst = 6 ms). Queue: [P4, P1, P2, P3].
t = 9 -> 12 ms: P4 runs 3 ms (remaining burst = 2 ms). Queue: [P1, P2, P3, P4].
t = 12 -> 15 ms: P1 runs 3 ms (remaining burst = 2 ms). Queue: [P2, P3, P4, P1].
t = 15 -> 16 ms: P2 runs its remaining 1 ms and completes at t = 16 ms! Queue: [P3, P4, P1].
t = 16 -> 19 ms: P3 runs 3 ms (remaining burst = 3 ms). Queue: [P4, P1, P3].
t = 19 -> 21 ms: P4 runs its remaining 2 ms and completes at t = 21 ms! Queue: [P1, P3].
t = 21 -> 23 ms: P1 runs its remaining 2 ms and completes at t = 23 ms! Queue: [P3].
t = 23 -> 26 ms: P3 runs its remaining 3 ms and completes at t = 26 ms! Queue empty.

Gantt Chart

P13ms

P23ms

P33ms

P43ms

P13ms

P21ms

P33ms

P42ms

P12ms

P33ms

036912151619212326

Step-by-Step Calculation Table

Process	AT	BT	Completion (CT)	Turnaround Time (TAT = CT - AT)	Waiting Time (WT = TAT - BT)
P1	0 ms	8 ms	23 ms	23 - 0 = 23 ms	23 - 8 = 15 ms
P2	1 ms	4 ms	16 ms	16 - 1 = 15 ms	15 - 4 = 11 ms
P3	2 ms	9 ms	26 ms	26 - 2 = 24 ms	24 - 9 = 15 ms
P4	3 ms	5 ms	21 ms	21 - 3 = 18 ms	18 - 5 = 13 ms

Average Turnaround Time: (23 + 15 + 24 + 18) / 4 = 80 / 4 = 20.00 ms
Average Waiting Time: (15 + 11 + 15 + 13) / 4 = 54 / 4 = 13.50 ms

Comparative Scorecard & Engineering Analysis

Algorithm	Preemptive?	Avg Turnaround Time (TAT)	Avg Waiting Time (WT)	Best / Worst Property
SRTF	Yes	13.00 ms (Optimal)	6.50 ms (Lowest)	Mathematically optimal average wait time, but causes severe starvation.
SJF	No	14.25 ms	7.75 ms	Excellent throughput, but non-preemptive convoy delays possible.
FCFS	No	15.25 ms	8.75 ms	Minimal scheduling overhead, but suffers from convoy effect.
Round Robin (q = 3 ms)	Yes	20.00 ms	13.50 ms	Highest average wait time, but provides excellent interactive response time and zero starvation.

So why don't real kernels just use SRTF?

SRTF wins on paper — lowest average wait time of all four, by a clear margin. But Linux and Windows don't use it, for three practical reasons:

It needs to see the future. SRTF has to know a process's burst time before running it. A real kernel has no way to predict whether a process will run for 2ms or 2 seconds before it blocks on I/O.
It starves big jobs. If short tasks keep arriving, a long-running job (video encoding, a simulation) can get pushed back indefinitely — it never looks like the "shortest" option.
Switching isn't free. The math above assumes a context switch costs 0ms. In reality it costs a few microseconds — reloading registers, swapping the page table, warming the cache back up. SRTF's constant preemption adds that cost up fast.

What's used instead: real kernels run Multilevel Feedback Queues (MLFQ) or Completely Fair Scheduling (CFS) — both approximate SRTF's "run the shortest job first" instinct without needing to predict the future or starving anything.

Python Verification: Multi-Algorithm CPU Scheduling Simulator

The following executable Python script implements FCFS, SJF, SRTF, and Round Robin, calculating exact completion times, Gantt traces, and waiting time averages:

"""
CPU Scheduling Algorithms Simulator
Demonstrates:
  1. FCFS (First-Come, First-Served)
  2. SJF (Shortest Job First - Non-Preemptive)
  3. SRTF (Shortest Remaining Time First - Preemptive)
  4. Round Robin (Time Quantum = 3)
"""

from typing import List, Dict, Tuple

class Process:
    def __init__(self, pid: str, arrival: int, burst: int):
        self.pid = pid
        self.arrival = arrival
        self.burst = burst
        self.remaining = burst
        self.completion = 0

    def tat(self) -> int:
        return self.completion - self.arrival

    def wt(self) -> int:
        return self.tat() - self.burst


def run_fcfs(procs: List[Process]) -> Tuple[float, float]:
    p_sorted = sorted(procs, key=lambda p: p.arrival)
    current_time = 0
    for p in p_sorted:
        if current_time < p.arrival:
            current_time = p.arrival
        current_time += p.burst
        p.completion = current_time

    avg_tat = sum(p.tat() for p in p_sorted) / len(p_sorted)
    avg_wt = sum(p.wt() for p in p_sorted) / len(p_sorted)
    return avg_tat, avg_wt


def run_sjf_non_preemptive(procs: List[Process]) -> Tuple[float, float]:
    current_time = 0
    completed = []
    ready = []
    unstarted = sorted(procs, key=lambda p: p.arrival)

    while len(completed) < len(procs):
        while unstarted and unstarted[0].arrival <= current_time:
            ready.append(unstarted.pop(0))

        if not ready:
            current_time = unstarted[0].arrival
            continue

        ready.sort(key=lambda p: (p.burst, p.arrival))
        active = ready.pop(0)
        current_time += active.burst
        active.completion = current_time
        completed.append(active)

    avg_tat = sum(p.tat() for p in completed) / len(completed)
    avg_wt = sum(p.wt() for p in completed) / len(completed)
    return avg_tat, avg_wt


def run_srtf(procs: List[Process]) -> Tuple[float, float]:
    current_time = 0
    completed = []
    total = len(procs)

    while len(completed) < total:
        available = [p for p in procs if p.arrival <= current_time and p.remaining > 0]
        if not available:
            current_time += 1
            continue

        available.sort(key=lambda p: (p.remaining, p.arrival))
        active = available[0]
        active.remaining -= 1
        current_time += 1

        if active.remaining == 0:
            active.completion = current_time
            completed.append(active)

    avg_tat = sum(p.tat() for p in completed) / len(completed)
    avg_wt = sum(p.wt() for p in completed) / len(completed)
    return avg_tat, avg_wt


def run_round_robin(procs: List[Process], quantum: int = 3) -> Tuple[float, float]:
    current_time = 0
    queue: List[Process] = []
    unstarted = sorted(procs, key=lambda p: p.arrival)
    completed = []

    while len(completed) < len(procs):
        while unstarted and unstarted[0].arrival <= current_time:
            queue.append(unstarted.pop(0))

        if not queue:
            current_time = unstarted[0].arrival
            continue

        active = queue.pop(0)
        run_slice = min(active.remaining, quantum)
        active.remaining -= run_slice
        current_time += run_slice

        # Enqueue new arrivals that landed during this time slice
        while unstarted and unstarted[0].arrival <= current_time:
            queue.append(unstarted.pop(0))

        if active.remaining == 0:
            active.completion = current_time
            completed.append(active)
        else:
            queue.append(active)

    avg_tat = sum(p.tat() for p in completed) / len(completed)
    avg_wt = sum(p.wt() for p in completed) / len(completed)
    return avg_tat, avg_wt


def main():
    print("=== CPU Scheduling Problem Verification ===\n")
    dataset = [("P1", 0, 8), ("P2", 1, 4), ("P3", 2, 9), ("P4", 3, 5)]

    # 1. FCFS
    fcfs_procs = [Process(pid, arr, bst) for pid, arr, bst in dataset]
    tat_fcfs, wt_fcfs = run_fcfs(fcfs_procs)
    print(f"FCFS:        Avg TAT = {tat_fcfs:5.2f} ms | Avg WT = {wt_fcfs:5.2f} ms")

    # 2. SJF
    sjf_procs = [Process(pid, arr, bst) for pid, arr, bst in dataset]
    tat_sjf, wt_sjf = run_sjf_non_preemptive(sjf_procs)
    print(f"SJF (NP):    Avg TAT = {tat_sjf:5.2f} ms | Avg WT = {wt_sjf:5.2f} ms")

    # 3. SRTF
    srtf_procs = [Process(pid, arr, bst) for pid, arr, bst in dataset]
    tat_srtf, wt_srtf = run_srtf(srtf_procs)
    print(f"SRTF:        Avg TAT = {tat_srtf:5.2f} ms | Avg WT = {wt_srtf:5.2f} ms [Optimal]")

    # 4. Round Robin (q=3)
    rr_procs = [Process(pid, arr, bst) for pid, arr, bst in dataset]
    tat_rr, wt_rr = run_round_robin(rr_procs, quantum=3)
    print(f"Round Robin: Avg TAT = {tat_rr:5.2f} ms | Avg WT = {wt_rr:5.2f} ms")

if __name__ == "__main__":
    main()

Problem Specification & Dataset​

The two numbers every part of this problem comes down to:​

Part 1: First-Come, First-Served (FCFS)​

Gantt Chart​

Step-by-Step Calculation Table​

Part 2: Shortest Job First (SJF): Non-Preemptive​

Execution Timeline:​

Gantt Chart​

Step-by-Step Calculation Table​

Part 3: Shortest Remaining Time First (SRTF): Preemptive SJF​

Execution Timeline:​

Gantt Chart​

Step-by-Step Calculation Table​

Part 4: Round Robin (RR, Quantum = 3 ms)​

Ready Queue Trace (q = 3 ms):​

Gantt Chart​

Step-by-Step Calculation Table​

Comparative Scorecard & Engineering Analysis​

So why don't real kernels just use SRTF?​

Python Verification: Multi-Algorithm CPU Scheduling Simulator​

Problem Specification & Dataset

The two numbers every part of this problem comes down to:

Part 1: First-Come, First-Served (FCFS)

Gantt Chart

Step-by-Step Calculation Table

Part 2: Shortest Job First (SJF): Non-Preemptive

Execution Timeline:

Gantt Chart

Step-by-Step Calculation Table

Part 3: Shortest Remaining Time First (SRTF): Preemptive SJF

Execution Timeline:

Gantt Chart

Step-by-Step Calculation Table

Part 4: Round Robin (RR, Quantum = 3 ms)

Ready Queue Trace (q = 3 ms):

Gantt Chart

Step-by-Step Calculation Table

Comparative Scorecard & Engineering Analysis

So why don't real kernels just use SRTF?

Python Verification: Multi-Algorithm CPU Scheduling Simulator