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: …