First-Come, First-Served (FCFS) Scheduling
First-Come, First-Served (FCFS) is the simplest CPU-scheduling algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a standard FIFO (First-In, First-Out) queue.
When a process enters the ready queue, its Process Control Block (PCB) is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue.
Example Calculation
Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds:
| Process | Burst Time (ms) |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
If the processes arrive in the order P1, P2, P3, and are served in FCFS order, we get the following execution timeline (represented as a Gantt chart):
+-------------------------+------+------+
| P1 | P2 | P3 |
+-------------------------+------+------+
0 24 27 30Let's calculate the Waiting Time and Turnaround Time for each process.
Waiting Time = Start Time - Arrival Time:
- P1 waits for 0 - 0 = 0 ms.
- P2 waits for 24 - 0 = 24 ms (it has to wait for P1 to finish).
- P3 waits for 27 - 0 = 27 ms (it has to wait for P1 and P2 to finish).
The Average Waiting Time is therefore: (0 + 24 + 27) / 3 = 17 ms.
Turnaround Time = Completion Time - Arrival Time:
- P1 turnaround is 24 - 0 = 24 ms.
- P2 turnaround is 27 - 0 = 27 ms.
- P3 turnaround is 30 - 0 = 30 ms.
The Average Turnaround Time is therefore: (24 + 27 + 30) / 3 = 27 ms.
The Convoy Effect
What happens if the processes arrive in a different order? Suppose they arrive in the order P2, P3, P1. The Gantt chart would now look like this:
+------+------+-------------------------+
| P2 | P3 | P1 |
+------+------+-------------------------+
0 3 6 30Let's calculate the Waiting Time and Turnaround Time for this new order:
Waiting Time:
- P1 waits for 6 - 0 = 6 ms.
- P2 waits for 0 - 0 = 0 ms.
- P3 waits for 3 - 0 = 3 ms.
The Average Waiting Time is now: (6 + 0 + 3) / 3 = 3 ms.
Turnaround Time:
- P1 turnaround is 30 - 0 = 30 ms.
- P2 turnaround is 3 - 0 = 3 ms.
- P3 turnaround is 6 - 0 = 6 ms.
The Average Turnaround Time is now: (30 + 3 + 6) / 3 = 13 ms.
This is a massive reduction from the 17 ms wait time and 27 ms turnaround time in the first example! This massive variance illustrates a major flaw in FCFS known as the Convoy Effect: short processes waiting behind a single very long process results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.
Real-Life Example
A classic real-life example of FCFS scheduling is a line at a supermarket checkout. The customer who arrives first is served first. If the person at the front of the line has a massive cart full of groceries (a long CPU burst), everyone else behind them with only one or two items (short CPU bursts) must wait a very long time before they can pay. This perfectly mirrors the Convoy Effect!
Advantages of FCFS
- Simplest algorithm to design and implement.
- Easy to manage using a basic FIFO queue.
- No overhead of frequent context switching since it is strictly non-preemptive.
- No risk of starvation; every process is guaranteed to eventually execute.
Disadvantages of FCFS
- Average waiting time is often quite long and highly unpredictable.
- Highly susceptible to the Convoy Effect, leading to poor CPU and device utilization.
- Terrible for interactive or time-sharing systems since it cannot guarantee fair response times.
Calculate the Average Waiting Time
Question 1 of 1Test your FCFS math skills. Assume two processes arrive at time 0 in the order: Process A (Burst Time = 10ms) followed by Process B (Burst Time = 6ms).