FCFS Scheduling — Step-Wise Animated Numericals

The Story That Explains FCFS

FCFS is the oldest and simplest CPU scheduling algorithm. Galvin introduces it first because it is easy to understand, easy to implement, and provides a clear baseline for comparing every other algorithm. Its logic fits in one line: dispatch processes in the order they arrived at the ready queue.

How FCFS Works — The Algorithm

Characteristics of FCFS

The Metrics — What We Compute

Before touching numericals, memorise these four formulas. Every FCFS problem in Galvin asks for these.

Numerical 1 — Basic FCFS (All Arrive At t=0)

Problem: Three processes arrive at time 0. Compute completion time, turnaround time, waiting time, response time, and averages.

Step-Wise Animated Gantt Chart Construction

Solution Table

Numerical 2 — Different Arrival Times

Problem: Four processes arrive at different times. Compute all metrics.

Step-Wise Reasoning

Animated Step-Wise Gantt Chart

Solution Table

Numerical 3 — The Convoy Effect

Now watch FCFS's fatal flaw in action. When one long CPU-bound process arrives just before many short I/O-bound ones, everyone piles up behind it — like cars stuck behind a slow truck.

Animated Convoy Effect

Advantages & Disadvantages

Python Implementation

from dataclasses import dataclass
from typing import List

@dataclass
class Process:
    pid:        str
    arrival:    int
    burst:      int
    start:      int = -1
    completion: int = -1

def fcfs(procs: List[Process]) -> List[Process]:
    # Sort by arrival time to enforce FIFO order
    procs = sorted(procs, key=lambda p: p.arrival)
    clock = 0
    for p in procs:
        # If CPU idle, jump clock forward to next arrival
        clock         = max(clock, p.arrival)
        p.start       = clock
        p.completion  = clock + p.burst
        clock         = p.completion
    return procs

def report(procs: List[Process]) -> None:
    print(f"{'PID':<4} {'AT':>4} {'BT':>4} {'CT':>4} {'TAT':>4} {'WT':>4} {'RT':>4}")
    tat_total = wt_total = rt_total = 0
    for p in procs:
        tat = p.completion - p.arrival
        wt  = tat - p.burst
        rt  = p.start - p.arrival
        tat_total += tat; wt_total += wt; rt_total += rt
        print(f"{p.pid:<4} {p.arrival:>4} {p.burst:>4} {p.completion:>4} {tat:>4} {wt:>4} {rt:>4}")
    n = len(procs)
    print(f"\nAvg TAT = {tat_total/n:.2f}")
    print(f"Avg WT  = {wt_total/n:.2f}")
    print(f"Avg RT  = {rt_total/n:.2f}")

# --- Run Numerical 2 ---
workload = [
    Process("P1", 0, 6),
    Process("P2", 2, 4),
    Process("P3", 4, 2),
    Process("P4", 6, 3),
]
report(fcfs(workload))

Numerical 4 — With CPU Idle Time

Watch out: if all processes have not yet arrived when the CPU is free, it sits idle. This affects CPU utilization.

Step-Wise Solution

When Is FCFS a Good Choice?

Golden Rules