FCFS Scheduling: Average Waiting Time

Imagine you're at a single counter — a railway ticket window, a bank teller, a canteen. People arrive, form a queue, and are served one by one in the exact order they arrived. No cutting in line. No priority. That is First-Come, First-Served (FCFS) scheduling, also called FIFO (First-In, First-Out).

In an operating system, the "people" are processes (programs in execution), and the "counter" is the CPU. Each process needs a certain amount of CPU time — its burst time. The scheduler simply picks the process that arrived earliest and runs it to completion before touching the next one.

The Intuition Behind Waiting Time

A process doesn't start running the moment it arrives. It has to wait until every process that arrived before it finishes. So the waiting time of a process is the total time it spends sitting in the ready queue, not getting any CPU.

For the very first process to arrive, waiting time is zero — it gets the CPU immediately. The second process waits for the first to finish. The third waits for the first and second to finish, and so on.

The Precise Calculation

Given a list of processes with their arrival times and burst times, here is the step-by-step method:

1. Completion Time (CT) — when a process finishes execution.

   For the first process: $CT_1 = \text{arrival}_1 + \text{burst}_1$

   For every subsequent process: $CT_i = \max(\text{arrival}_i, CT_{i-1}) + \text{burst}_i$

2. Turnaround Time (TAT) — total time from arrival to completion.

   $TAT_i = CT_i - \text{arrival}_i$

3. Waiting Time (WT) — turnaround time minus burst time.

   $WT_i = TAT_i - \text{burst}_i$

4. Average Waiting Time — the mean of all waiting times.

   $\text{Average WT} = \frac{1}{n} \sum_{i=1}^{n} WT_i$

Worked Example (All Arrive at Time 0)

Suppose three processes arrive together at time 0:

Since all arrive at 0, the order is P1 → P2 → P3.

• P1: starts at 0, finishes at 6.

  $WT_1 = 0 - 0 - 6 = 0$ (or simply: it starts immediately, so wait = 0)

• P2: starts at 6, finishes at 14.

  $WT_2 = 14 - 0 - 8 = 6$

• P3: starts at 14, finishes at 18.

  $WT_3 = 18 - 0 - 4 = 14$

Average waiting time: $\frac{0 + 6 + 14}{3} = \frac{20}{3} \approx 6.67$ units.

Worked Example (Different Arrival Times)

Now consider processes arriving at different times:

Step-by-step:

• P1 arrives at 0, starts immediately. Finishes at $0 + 5 = 5$.

  $WT_1 = 5 - 0 - 5 = 0$

• P2 arrives at 2, but P1 is still running until 5. So P2 starts at 5, finishes at $5 + 3 = 8$.

  $WT_2 = 8 - 2 - 3 = 3$

• P3 arrives at 4, but P1 runs until 5, then P2 runs until 8. So P3 starts at 8, finishes at $8 + 2 = 10$.

  $WT_3 = 10 - 4 - 2 = 4$

Average waiting time: $\frac{0 + 3 + 4}{3} = \frac{7}{3} \approx 2.33$ units.

Why This Matters

FCFS is simple and fair in the sense that no process starves — every process eventually gets the CPU. But it has a notorious weakness called the convoy effect: a long process at the front of the queue forces every short process behind it to wait, inflating the average waiting time dramatically. That is why real operating systems rarely use pure FCFS for interactive tasks.

Average waiting time is the key metric here. It tells you how "responsive" the system feels to the user. Lower is better. And in FCFS, that number depends entirely on the order of arrivals and the mix of burst times — you have no control over it once the queue forms.