What is the convoy effect in FCFS scheduling?
The convoy effect is when many short processes queue behind one long CPU-bound process, so the CPU and I/O devices sit idle in turns and average waiting time rises sharply.
Explain it simply
Imagine a narrow lane where one slow tractor leads a line of cars. Nobody can overtake, so every car crawls at the tractor's speed. In FCFS, a long CPU-bound job is the tractor and the short jobs are the cars.
It also hurts utilisation. While the long job holds the CPU, I/O-bound processes finish their I/O and queue up, leaving the I/O devices idle. When the long job ends, the short ones rush through the CPU and then all wait for I/O while the CPU sits idle.
Example
Take one 100 ms job (L) and three 2 ms jobs (S1, S2, S3), all arriving at 0.
Long job first: L starts at 0, S1 at 100, S2 at 102, S3 at 104. Waiting total = 0 + 100 + 102 + 104 = 306, average 76.5 ms.
Short jobs first: S1 at 0, S2 at 2, S3 at 4, L at 6. Waiting total = 0 + 2 + 4 + 6 = 12, average 3 ms.
The work is identical; only the order changed. Preemptive algorithms like Round Robin, or SJF, break up the convoy because the short jobs get the CPU without waiting for the long one to finish.
What to say in the interview
"The convoy effect is short jobs stuck behind one long CPU-bound job under FCFS. With a 100 ms job ahead of three 2 ms jobs the average wait is 76.5 ms, against 3 ms if the short ones go first. Preemption or SJF avoids it."
Common mistakes
- Saying the convoy effect happens in Round Robin. It is specific to non-preemptive FCFS.