Part 2 of 7 · 2 min read
FCFS
Think of it this way. A shop counter serves customers in the order they join the line. It is fair in the sense that nobody is overtaken. The analogy stops in one place: a real customer with one small item may be let through, but a strict FCFS scheduler never does that.
In plain words: In first come first served, the process that arrives first gets the processor first and keeps it until it finishes or waits. The ready queue is a plain first-in, first-out queue. It is non-preemptive, so there is no timer decision and almost no overhead.
The workload of page 1 gives this trace (arrival 0, 1, 2 and 3 for A, B, C and D, with CPU times 5, 3, 8 and 2):
time: 0 5 8 16 18
| A | B | C | D |
| Process | Finish | Turnaround | Waiting | Response |
|---|---|---|---|---|
| A | 5 | 5 | 0 | 0 |
| B | 8 | 7 | 4 | 4 |
| C | 16 | 14 | 6 | 6 |
| D | 18 | 15 | 13 | 13 |
The averages are turnaround 10.25, waiting 5.75 and response 5.75.
The weakness is shown by the order. Take the same four jobs, all arriving at time 0, and change only the order of the queue:
| Order | Waiting times | Average waiting |
|---|---|---|
| C, A, B, D (long job first) | 0, 8, 13, 16 | 37 ÷ 4 = 9.25 |
| D, B, A, C (short jobs first) | 0, 2, 5, 10 | 17 ÷ 4 = 4.25 |
The result depends strongly on who happens to arrive first. When a long job is first, every short job behind it waits for the whole of it. This is the convoy effect: small cars stuck behind one slow lorry. It is worse on a mix of one CPU-bound process and many I/O-bound ones: the I/O-bound processes finish their short bursts, wait for the processor behind the long one, and the disks sit idle, so both the processor and the devices are badly used.
Convoy effect
The convoy effect is the delay of many short processes that wait in a first come first served queue behind one long process, which lowers the average waiting time and keeps devices idle.
Example: four jobs of 2, 3, 5 and 8 units average a waiting time of 4.25 when the short ones go first, and 9.25 when the 8-unit job is first.
Check yourself: 1. What is the average waiting time when the order is B, D, A, C and all four arrive at time 0? 2. Why can the convoy effect leave disks idle? 3. Is FCFS preemptive?