FCFS Scheduling — First Come First Served Algorithm

FCFS is the algorithm you implement when you have a queue and zero information about job durations. It is fair in the sense that arrival order is respected — no process waits longer than all processes that arrived before it. But 'fair' does not mean 'efficient', and the convoy effect makes FCFS genuinely harmful for interactive workloads.

Understanding FCFS matters not for implementing it (it is trivially a FIFO queue) but for understanding what it optimises and what it sacrifices. Every scheduling algorithm trades off fairness, average waiting time, response time, and throughput differently. FCFS optimises arrival-order fairness at the cost of average waiting time. This trade-off analysis is the interview skill being tested.

Algorithm and Metrics

Key metrics: - Completion Time (CT): When the process finishes - Turnaround Time (TAT): CT - Arrival Time - Waiting Time (WT): TAT - Burst Time - Response Time: Time from arrival to first execution (= WT for non-preemptive)

def fcfs(processes: list[dict]) -> list[dict]:
    """
    processes: list of {pid, arrival, burst}
    Returns processes with ct, tat, wt added.
    """
    # Sort by arrival time
    procs = sorted(processes, key=lambda p: p['arrival'])
    current_time = 0
    results = []
    for p in procs:
        start = max(current_time, p['arrival'])
        ct  = start + p['burst']
        tat = ct - p['arrival']
        wt  = tat - p['burst']
        current_time = ct
        results.append({**p, 'start': start, 'ct': ct, 'tat': tat, 'wt': wt})
    return results

processes = [
    {'pid':'P1','arrival':0,'burst':24},
    {'pid':'P2','arrival':1,'burst':3},
    {'pid':'P3','arrival':2,'burst':3},
]
results = fcfs(processes)
print(f"{'PID':<4} {'AT':>3} {'BT':>3} {'ST':>3} {'CT':>3} {'TAT':>4} {'WT':>4}")
for r in results:
    print(f"{r['pid']:<4} {r['arrival']:>3} {r['burst']:>3} {r['start']:>3} {r['ct']:>3} {r['tat']:>4} {r['wt']:>4}")
avg_tat = sum(r['tat'] for r in results) / len(results)
avg_wt  = sum(r['wt']  for r in results) / len(results)
print(f"\nAverage TAT: {avg_tat:.2f}")
print(f"Average WT:  {avg_wt:.2f}")

The Convoy Effect

In the example above, P2 and P3 each take only 3ms but wait 23ms and 25ms because P1 (24ms) arrived first. This is the convoy effect — short processes form a convoy behind a long one.

If we ran P2, P3, P1 instead (SJF order): - P2: WT=0, P3: WT=2, P1: WT=5 - Average WT = 2.33ms vs 16ms for FCFS

This is why FCFS has poor average waiting time for mixed workloads.

Gantt Chart Representation

def print_gantt(results: list[dict]) -> None:
    print('Gantt Chart:')
    bar = '|'
    times = '0'
    for r in results:
        bar += f" {r['pid']:^5}|"
        times += f"{r['ct']:>7}"
    print(bar)
    print(times)

print_gantt(results)

Frequently Asked Questions