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.

Why FCFS Scheduling Fails Under Burst Load

First-Come, First-Served (FCFS) is the simplest scheduling algorithm: tasks execute in the exact order they arrive, using a FIFO queue. The core mechanic is non-preemptive — once a task gets the CPU, it runs to completion. This means no context-switch overhead, but it also means a single long task can block every subsequent task, regardless of priority or urgency.

In practice, FCFS exhibits the convoy effect: a long CPU-bound process holds the queue, forcing all I/O-bound tasks to wait. For a payment API, a single large report generation request (say, 2 seconds of CPU) can delay 1000 payment transactions behind it, each adding milliseconds of latency. The average waiting time balloons as the variance in burst times increases — mathematically, the average turnaround time is O(n) in the worst case.

Use FCFS only when all tasks have similar, predictable execution times — for example, a batch processing pipeline where each job is identical. In real-time or interactive systems, FCFS is a liability. Understanding its convoy effect is critical because it's the default behavior of many naive queue implementations (e.g., a simple BlockingQueue in Java) that teams assume are safe.

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.

How FCFS Actually Works (No Mysticism)

FCFS is the dumbest scheduling algorithm you'll ever use. That's its superpower. When a process arrives, it gets thrown at the tail of a FIFO queue. The CPU pulls from the head, runs the process to completion (or until it blocks on I/O), then moves to the next. No preemption, no priority, no fancy logic.

The kernel maintains a simple linked list of task_struct entries. Insertion is O(1). Dequeue is O(1). The scheduler has zero decisions to make. That's it. No quantum timers, no context-switch overhead from preemption, no starvation logic because every process eventually hits the front of the line.

Where this breaks down is when you have a long CPU-bound process holding the head of the queue. Every interactive process behind it waits. And waits. The FIFO queue becomes a bottleneck that makes your system feel like it's running on a 486. Windows 95 used a variant of FCFS for some legacy drivers. Users threw their mice at the screen. There's your history lesson.

// io.thecodeforge — dsa tutorial

import java.util.LinkedList;
import java.util.Queue;

class Process {
    String id;
    int burstTime;

    Process(String id, int burstTime) {
        this.id = id;
        this.burstTime = burstTime;
    }
}

public class FCFSScheduler {
    public static void main(String[] args) {
        Queue<Process> readyQueue = new LinkedList<>();
        readyQueue.add(new Process("P1", 5));
        readyQueue.add(new Process("P2", 3));
        readyQueue.add(new Process("P3", 8));

        int time = 0;
        while (!readyQueue.isEmpty()) {
            Process current = readyQueue.poll();
            System.out.println("Time " + time + ": " + current.id + " starts");
            time += current.burstTime;
            System.out.println("Time " + time + ": " + current.id + " finishes");
        }
    }
}

Example with Different Arrival Times (The Real World)

In production, processes don't all show up at time zero. That's a classroom fantasy. Real workloads have staggered arrivals, I/O bursts, and users who close browsers mid-stream. Let's build a scenario that actually hurts.

Three processes: P1 arrives at 0 with a 7ms CPU burst. P2 arrives at 2ms with a 4ms burst. P3 arrives at 4ms with a 1ms burst. FCFS doesn't care about burst length. P1 runs from 0 to 7. P2 waits until 7, runs to 11. P3 waits until 11, runs to 12. P3's tiny 1ms job sits idle for 7ms while P1 churns.

Calculate turnaround time (completion minus arrival): P1 = 7, P2 = 9, P3 = 8. Average = 8ms. Waiting time (turnaround minus burst): P1 = 0, P2 = 5, P3 = 7. Average = 4ms. P3 waited 7x its execution time. That's the Convoy Effect in its purest form.

Now imagine that P3 is a mouse movement handler. You've just introduced a 7ms input lag. Users don't tolerate that. This is why FCFS is relegated to batch systems and background jobs where latency doesn't matter.

// io.thecodeforge — dsa tutorial

import java.util.LinkedList;
import java.util.Queue;

class TimedProcess {
    String id;
    int arrivalTime;
    int burstTime;

    TimedProcess(String id, int arrival, int burst) {
        this.id = id;
        this.arrivalTime = arrival;
        this.burstTime = burst;
    }
}

public class FCFSStaggeredArrivals {
    public static void main(String[] args) {
        Queue<TimedProcess> readyQueue = new LinkedList<>();
        readyQueue.add(new TimedProcess("P1", 0, 7));
        readyQueue.add(new TimedProcess("P2", 2, 4));
        readyQueue.add(new TimedProcess("P3", 4, 1));

        int currentTime = 0;
        int totalWait = 0;
        int totalTurnaround = 0;

        while (!readyQueue.isEmpty()) {
            TimedProcess p = readyQueue.poll();
            if (currentTime < p.arrivalTime) {
                currentTime = p.arrivalTime;
            }
            int waitTime = currentTime - p.arrivalTime;
            int turnaroundTime = waitTime + p.burstTime;
            totalWait += waitTime;
            totalTurnaround += turnaroundTime;
            System.out.println(p.id + " | Arrival: " + p.arrivalTime + " | Wait: " + waitTime + " | Turnaround: " + turnaroundTime);
            currentTime += p.burstTime;
        }

        System.out.println("\nAverage Waiting Time: " + (totalWait / 3.0));
        System.out.println("Average Turnaround Time: " + (totalTurnaround / 3.0));
    }
}

Problem 1: Starvation of Late Arrivals Isn't Fairness

You'd think first-come-first-served is fair by definition. It's not. Late arrivals in FCFS don't just wait — they can wait indefinitely under sustained load. If a CPU-bound process arrives first and runs for 10 seconds, every interactive process that shows up second gets buried behind it. That's not fairness; that's a single-threaded bottleneck masquerading as a policy.

The real problem is that FCFS has no preemption. Once a process gets the CPU, it holds it until it voluntarily yields — usually by completing an I/O wait or terminating. Under burst load, this means short tasks get stuck behind long ones. The average waiting time balloons, and worst-case response time becomes unpredictable.

Why this matters in production: You can't build a real-time system on FCFS. A single misbehaving or oversized job tanks latency for everyone else. If you're running a web server, that's the difference between a 200ms response and a 5-second timeout.

// io.thecodeforge — dsa tutorial

class Process {
    String name; int burst;
    Process(String n, int b) { name = n; burst = b; }
}

public class StarvationDemo {
    public static void main(String[] args) {
        Process[] procs = {
            new Process("BigCalc", 10000),
            new Process("WebReq", 2),
            new Process("APICall", 5)
        };
        int time = 0;
        for (Process p : procs) {
            System.out.println(p.name + " starts at " + time);
            time += p.burst;
            System.out.println(p.name + " finishes at " + time);
        }
        System.out.println("Short tasks waited " + (procs[2].burst + procs[1].burst) + " ms");
    }
}

Solution: Preemptive FCFS? No, Use the Right Tool

You can't fix FCFS by making it preemptive — that's not FCFS anymore, that's Round Robin with a quantum. The real solution is admitting FCFS has a narrow sweet spot. If you need bounded response times, use a preemptive scheduler. If you need throughput for batch workloads, FCFS is fine — just don't mix long and short jobs on the same queue.

When you're stuck with FCFS in a legacy system, mitigate by isolating workloads. Use multiple queues: one for short interactive tasks (handled by SJF) and one for long batch jobs (handled by FCFS). This pattern shows up in Linux's Completely Fair Scheduler — it's not preemption that saves you, it's classification.

The production-level fix: never let a single queue mix CPU-bound and I/O-bound processes. Or, if you must, cap the burst time per process and preempt after a threshold. But then you're not running FCFS anymore. Be honest about what you need and choose the algorithm that delivers it.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class MitigationDemo {
    static class Job {
        String name; int burst; boolean isShort;
        Job(String n, int b, boolean s) { name = n; burst = b; isShort = s; }
    }

    public static void main(String[] args) {
        Queue<Job> shortQ = new LinkedList<>();
        Queue<Job> longQ = new LinkedList<>();
        shortQ.add(new Job("Web", 2, true));
        shortQ.add(new Job("API", 5, true));
        longQ.add(new Job("Batch", 10000, false));
        
        int time = 0;
        while (!shortQ.isEmpty() || !longQ.isEmpty()) {
            Job j = shortQ.poll();
            if (j == null) j = longQ.poll();
            if (j != null) {
                System.out.println(j.name + " starts at " + time);
                time += j.burst;
                System.out.println(j.name + " finishes at " + time);
            }
        }
        System.out.println("Short jobs not blocked by batch");
    }
}

First-Come, First-Served Scheduling

First-come, first-served (FCFS) scheduling is the simplest CPU scheduling algorithm, where processes are executed in the order they arrive in the ready queue. It follows a non-preemptive, FIFO (First In, First Out) discipline: the first process to request the CPU gets it, and holds it until completion or I/O block. This mimics a real-world queue like a grocery checkout. FCFS is fundamental in operating systems and discrete event simulation because it models natural fairness—no process jumps ahead. However, its simplicity hides severe performance issues under bursty workloads, as average waiting time can balloon when a long CPU burst blocks shorter ones. The algorithm's behavior is purely deterministic: given arrival times and burst durations, the order and completion times are fixed. FCFS is the baseline against which all other scheduling algorithms are measured, despite rarely being used alone in modern systems.

// io.thecodeforge — dsa tutorial
// 25 lines max
public class FCFSBasic {
    public static void main(String[] args) {
        int[] burst = {10, 5, 8}; // ms
        int[] arrival = {0, 1, 2};
        int n = burst.length;
        int[] completion = new int[n];
        int[] waiting = new int[n];
        int time = 0;
        System.out.println("FCFS Scheduling:");
        for (int i = 0; i < n; i++) {
            if (time < arrival[i]) time = arrival[i];
            completion[i] = time + burst[i];
            waiting[i] = time - arrival[i];
            System.out.println("P" + i + ": arrival=" + arrival[i] + ", burst=" + burst[i] + ", completion=" + completion[i] + ", waiting=" + waiting[i]);
            time = completion[i];
        }
    }
}

Explanation, Advantages, Disadvantages, and Characteristics

Explanation: FCFS is non-preemptive; once a process gets the CPU, it runs until it terminates or blocks. The scheduler maintains a simple FIFO queue. When a new process arrives, it's appended to the rear. The CPU picks the head of the queue. Advantages: (1) Extremely easy to implement—just a queue. (2) No starvation for CPU-bound processes if they all arrive early; every process eventually runs. (3) Low context-switching overhead. Disadvantages: (1) High average waiting time under bursty loads (convoy effect). (2) Poor response time for interactive processes. (3) Not suitable for time-sharing systems. Characteristics: Non-preemptive, starvation-free in a strict sense (every arrival gets CPU eventually), but average turnaround time can be large. It's deterministic and predictable. The algorithm favors long CPU bursts over short ones, which is the opposite of optimal for minimizing mean wait time. FCFS is the baseline, but in practice, it's used only where order matters (e.g., batch processing) or as a fallback.

// io.thecodeforge — dsa tutorial
// 25 lines max
public class FCFSMetrics {
    public static void main(String[] args) {
        int[] burst = {6, 2, 8}; // ms
        int[] arrival = {0, 0, 0}; // same time
        int n = burst.length;
        int totalWait = 0, totalTurn = 0;
        int time = 0;
        System.out.println("FCFS Metrics (all arrive at 0):");
        for (int i = 0; i < n; i++) {
            int completion = time + burst[i];
            int turn = completion - arrival[i];
            int wait = time - arrival[i];
            totalWait += wait;
            totalTurn += turn;
            System.out.println("P" + i + ": burst=" + burst[i] + ", wait=" + wait + ", turn=" + turn);
            time = completion;
        }
        System.out.println("Avg wait: " + (totalWait/(double)n) + " ms, Avg turn: " + (totalTurn/(double)n) + " ms");
    }
}