FCFS & the Convoy Effect
Scenario
You just want to buy a single pack of gum, but you are stuck in the checkout line behind someone with two carts full of groceries.
Mental model
First-Come, First-Served (FCFS) processes tasks in the exact order they arrive, which can cause massive traffic jams (the convoy effect).
FCFS is like a single-lane highway. If a slow, massive truck gets in front, every fast sports car behind it is forced to crawl at the truck's pace. The 'convoy effect' is this exact scenario: short, quick tasks are trapped waiting for one massive task to finish.
Explanation
First-Come, First-Served (FCFS) is the simplest possible CPU scheduling algorithm. When a process enters the ready queue, its process control block (PCB) is linked to the tail of the queue. When the CPU becomes free, it is assigned to the process at the head of the queue. The running process is then allowed to execute until it voluntarily yields the CPU, either by finishing its task or by requesting I/O.
Because FCFS does not interrupt a running process, it is a non-preemptive scheduling algorithm. This simplicity makes it incredibly easy to implement using a basic FIFO (First-In, First-Out) queue. There is virtually no overhead from complex decision-making logic. However, this naive approach comes with a severe performance penalty when process sizes vary significantly.
Consider a scenario where a massive CPU-bound process (like a video rendering job) arrives just moments before several tiny I/O-bound processes (like keyboard stroke handlers). The massive process takes the CPU and holds it for a long time. Meanwhile, the tiny processes, which could have finished in milliseconds, are forced to wait. This drastic increase in average waiting time is known as the Convoy Effect.
The convoy effect doesn't just hurt the waiting time of the short processes; it also starves I/O devices. While the massive process hogs the CPU, all the I/O devices sit idle because the short processes that need them are stuck in the ready queue. When the massive process finally finishes and goes to do its own I/O, the short processes quickly finish their CPU bursts and pile up in the I/O queues. Now the CPU sits idle! This constant oscillation between idle I/O devices and an idle CPU leads to terrible overall system utilization.
Ultimately, while FCFS is fair in the sense of 'first come, first served', it is practically unusable in modern interactive operating systems due to the convoy effect. It is, however, still used in certain background batch-processing environments where turnaround time for individual small tasks is not a priority.
Key points
- Non-preemptive: Once a process gets the CPU, it keeps it until it finishes or requests I/O. The OS cannot force it to stop.
- FIFO Structure: Implementation is just a simple First-In, First-Out queue, making overhead minimal.
- Convoy Effect: The phenomenon where short processes get stuck waiting a very long time for a single long process to release the CPU.
- Poor Resource Utilization: Leads to scenarios where the CPU and I/O devices take turns being completely idle, lowering system efficiency.
Common mistakes
- Assuming FCFS has the lowest average waiting time: Because it's 'fair', people assume it's efficient. Actually, FCFS often has terrible average waiting time because one long process heavily skews the average.
- Confusing FCFS with Round Robin: FCFS lets a process run to completion without interruption. Round Robin is FCFS but with a time limit (preemption) to prevent the convoy effect.
Glossary
- First-Come, First-Served
- A very basic scheduling method where the operating system handles tasks in the exact order they arrive, just like a checkout line at a grocery store.
- ready queue
- The waiting line inside the computer's memory where programs sit patiently until it is their turn to use the CPU.
- process control block
- A digital ID card created by the operating system that holds all the essential information about a program while it is running or waiting.
Recall questions
- Is FCFS a preemptive or non-preemptive scheduling algorithm?
- What is the Convoy Effect?
- How does the Convoy Effect negatively impact I/O device utilization?
Questions & answers
Given processes P1 (burst 24ms), P2 (burst 3ms), P3 (burst 3ms) arriving at time 0 in that order. What is the average waiting time under FCFS?
17ms
Approach: P1 waits 0ms. P2 waits for P1 to finish (24ms). P3 waits for P1 and P2 to finish (24 + 3 = 27ms). Average = (0 + 24 + 27) / 3 = 17ms.
If the arrival order of the previous processes changed to P2, P3, P1, what would the new average waiting time be?
3ms
Approach: P2 waits 0ms. P3 waits 3ms. P1 waits 6ms. Average = (0 + 3 + 6) / 3 = 3ms. This proves how sensitive FCFS is to arrival order and perfectly demonstrates the convoy effect.
Continue learning
Previous: Scheduling Criteria