🎫

FCFS Scheduling — Step-by-Step With Animated Numericals

First-Come-First-Served: the simplest CPU-scheduling algorithm. Learn the metrics, then solve four worked numericals with animated Gantt charts — including the dreaded convoy effect.

FIFO Order Gantt Charts 4 Numericals Convoy Effect

Press Next → or use ← → arrow keys

Section 01

The Story That Explains FCFS

🏦 ANALOGY · THE BANK TELLER QUEUE

One teller, one rope-line. The rule is ancient and fair: whoever joins first is served first — no skipping, no priority. If the person at the front is depositing 500 coins one by one, everyone behind waits, even the customer with a 30-second cheque. That is FCFS: the CPU is the teller, processes are customers, and arrival order is everything.

Section 02

How FCFS Works — The Algorithm

🔁 Six simple steps

1

Keep the ready queue as a strict FIFO (first-in, first-out) list.

2

When a process arrives, append its PCB to the tail of the queue.

3

When the CPU is free, remove the process at the head.

4

Dispatch it — it runs until it finishes or blocks on I/O (non-preemptive).

5

On completion, loop back to step 3 for the next head.

6

A process returning from I/O re-enters at the tail.

⛔

Non-Preemptive

Once a process gets the CPU it keeps it until it voluntarily releases it. No interrupts.

⚖️

Fair (FIFO)

Strict arrival order — no process ever starves; everyone eventually runs.

🪶

Trivial O(1)

One linked list, negligible scheduling overhead — the simplest algorithm there is.

Section 03

The Metrics — What We Compute

Metric	Formula	Meaning
Completion Time (CT)	`start + burst`	The instant the process finishes
Turnaround Time (TAT)	`CT − AT`	Total time from arrival to completion
Waiting Time (WT)	`TAT − BT`	Time spent waiting in the ready queue
Response Time (RT)	`start − AT`	Time until the first CPU execution

🔑

The FCFS Shortcut: RT = WT

Because FCFS is non-preemptive, a process runs to completion the moment it first starts — there is no gap between "first run" and "kept running." So Response Time equals Waiting Time. Also useful: CPU Utilisation = busy ÷ total, and Throughput = processes ÷ total time.

Numerical 1

Basic FCFS — All Arrive at t = 0

Process	AT	BT	Start	CT	TAT	WT
P1	0	10	0	10	10	0
P2	0	5	10	15	15	10
P3	0	8	15	23	23	15
Averages →					16.00	8.33

📐

Draw the Chart First

With all three arriving at t=0, they run in order P1 → P2 → P3. Read completion times straight off the chart (10, 15, 23), then TAT = CT − AT and WT = TAT − BT. Avg TAT = 16 ms, Avg WT = 8.33 ms, CPU utilisation 100%.

Numerical 2

Different Arrival Times

Process	AT	BT	Start	CT	TAT	WT
P1	0	6	0	6	6	0
P2	2	4	6	10	8	4
P3	4	2	10	12	8	6
P4	6	3	12	15	9	6
Averages →					7.75	4.00

🧮

Still in Arrival Order

P1 arrives first and runs 0→6; by then P2, P3, P4 have all queued, so they run in arrival order. Note TAT differs from CT now, because arrival times aren't zero: TAT = CT − AT. Avg TAT = 7.75 ms, Avg WT = 4.00 ms.

Numerical 3

The Convoy Effect — Everyone Waits for P1

Process	AT	BT	Start	CT	TAT	WT
P1 CPU-bound	0	100	0	100	100	0
P2	1	1	100	101	100	99
P3	2	1	101	102	100	99
P4	3	1	102	103	100	99
Avg WT →						74.25

🚚

Three 1-ms Jobs Each Waited 99 ms!

One long CPU-bound process arrived just before three tiny ones — and they all piled up behind it, like cars stuck behind a slow truck. Average waiting time explodes to 74.25 ms. This is the convoy effect, FCFS's fatal flaw.

Section 07

Advantages & Disadvantages

✅

Dead Simple

One FIFO queue, O(1) overhead. The easiest scheduler to build and reason about.

✅

No Starvation

Strict FIFO is fair — every process is guaranteed to run eventually.

✅

Great Baseline

Predictable order makes it the reference point for comparing smarter algorithms.

❌

Convoy Effect

Short jobs get trapped behind long ones, wrecking average waiting time.

❌

Bad for Interactive

No priority and no preemption — a long job freezes the UI for everyone.

❌

Can't React to Urgency

Non-preemptive: a newly-arrived critical job still waits its turn. Utilisation drops when convoys form.

Numerical 4

With CPU Idle Time

Process	AT	BT	CT	TAT	WT
P1	0	3	3	3	0
P2	5	4	9	4	0
P3	10	2	12	2	0
Averages →			3.00	0.00

⏳

When the Queue Empties, Jump the Clock

Each process arrives after the previous one finishes, so nobody ever waits — Avg WT = 0. But the CPU sits idle for 3 ms total (t=3–5 and t=9–10). Busy 9 of 12 ms → CPU utilisation = 75%. When the queue is empty, advance the clock to the next arrival.

Section 08

Python Implementation

def fcfs(procs):
    # Sort by arrival to enforce FIFO order
    procs = sorted(procs, key=lambda p: p.arrival)
    clock = 0
    for p in procs:
        clock        = max(clock, p.arrival)   # idle? jump ahead
        p.start      = clock
        p.completion = clock + p.burst
        clock        = p.completion
    return procs

# TAT = CT - AT   ·   WT = TAT - BT   ·   RT = start - AT

✅

Matches the Hand Calculation Exactly

Run it on Numerical 2's workload and it prints Avg TAT = 7.75, Avg WT = 4.00 — identical to what we computed by hand. The whole algorithm is just: sort by arrival, walk the clock forward, and jump ahead whenever the CPU would otherwise sit idle.

Section 10

When Is FCFS a Good Choice?

✅

Batch Systems

Overnight billing, payroll, ETL — nobody's waiting interactively, so FIFO order is perfectly fine.

✅

Uniform Workloads

When every job has a similar burst time, there's no long truck to convoy behind — averages stay low.

✅

Simple Embedded

Microcontrollers with a fixed, predictable task set benefit from FCFS's tiny footprint.

❌

Interactive Systems

A long job freezes the UI — users need preemption and priority, which FCFS can't offer.

❌

Time-Sharing

The convoy effect destroys throughput when many users share one machine.

❌

Real-Time

No priority guarantee means no way to meet deadlines — a non-starter for safety-critical work.

Section 11

Seven Rules for Solving FCFS

🎫 FCFS · PROBLEM-SOLVING RULES

1

Order strictly by arrival time; break ties by PID.

2

FCFS is non-preemptive — once a process starts, it keeps the CPU until it's done.

3

Response Time = Waiting Time — there's no preemption gap.

4

Compute in order: draw the Gantt chart first, then CT → TAT → WT → RT.

5

Watch for idle CPU time — when the queue empties, jump the clock to the next arrival.

6

Beware the convoy effect — a huge first block wrecks the average waiting time.

7

FCFS never starves anyone — every process runs eventually.

FINAL

First Come, First Served — Mastered

FIFOThe whole idea

4Metrics: CT·TAT·WT·RT

0Preemptions ever

74.25Convoy avg WT (ms)

O(1)Scheduling cost

🎯

You Can Now Solve Any FCFS Problem

Draw the Gantt chart in arrival order, read off completion times, then compute turnaround and waiting times. You've seen all four cases: simultaneous arrivals, staggered arrivals, the convoy effect, and CPU idle time.

📚

Where To Go Next

The natural sequel is SJF (Shortest Job First), which fixes the convoy effect by running short jobs first, then Round Robin and Priority scheduling. Compare each one's average waiting time against this FCFS baseline.

🎫 End of tutorial · Press ← to review, or click Restart