FCFS Scheduling — Convoy Effect Cripples Payment API

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

FCFS is trivially a FIFO queue. You sort processes by arrival time, then execute each to completion. The metrics tell the real story: average waiting time can skyrocket when a long job arrives early.

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.

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

Gantt Chart Representation

A Gantt chart visually shows which process runs at each time interval. For FCFS, the chart is simply the processes in arrival order, each spanning its burst duration. This representation makes the convoy effect obvious: long bars push short bars to the right.

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)

When to Use FCFS in Practice

In most general-purpose operating systems, FCFS is used only as a fallback scheduler for equal-priority processes under SCHED_OTHER. Linux's Completely Fair Scheduler (CFS) is fundamentally different — it's a weighted fair queuing scheduler that preempts to maintain fairness.

FCFS vs. SJF vs. Round Robin

Comparing scheduling algorithms around burst time variance:

FCFS minimises the maximum waiting time for processes with the same arrival order — that's its fairness guarantee. But it maximises average waiting time when burst times vary.

SJF exploits knowledge of burst times to minimise average waiting time, but can starve long processes. Round Robin trades off average waiting time for response time — good for interactive workloads.

In production, you rarely pick one in isolation. Hybrid schedulers like CFS combine elements: target latency (like RR) with fairness (like FCFS) and dynamic priority adjustments.

Frequently Asked Questions