FCFS Scheduling
BeginnerFirst-Come First-Served (FCFS) is the simplest non-preemptive scheduling algorithm that serves processes in arrival order, but suffers from the convoy effect where short processes wait behind long ones.
Overview
FCFS (also called FIFO scheduling) assigns the CPU to processes in the order they arrive in the ready queue. It is non-preemptive: once a process starts, it runs to completion or until it voluntarily yields for I/O. FCFS is trivially simple to implement (a plain queue) and has no starvation — every process eventually runs. However, it suffers from the convoy effect: a CPU-bound long process at the front of the queue forces all short processes behind it to wait. This dramatically increases average waiting time. FCFS is suitable for batch systems where all jobs have similar burst times, but poor for interactive systems where short response time matters.
Gantt Chart and Waiting Time Calculation
Gantt charts visualize scheduling. With FCFS, processes run in arrival order. The convoy effect is visible when a long process arrives first: all shorter processes that arrive shortly after must wait for it to complete, skewing average waiting time upward.
// FCFS Example:
// Process | Arrival | Burst
// P1 | 0 | 10 ← long process arrives first (convoy!)
// P2 | 1 | 2
// P3 | 2 | 3
//
// Gantt: | P1 (0–10) | P2 (10–12) | P3 (12–15) |
// 0 10 12 15
int[] arrival = {0, 1, 2};
int[] burst = {10, 2, 3};
int[] finish = new int[3];
int[] turnaround = new int[3];
int[] waiting = new int[3];
int currentTime = 0;
for (int i = 0; i < 3; i++) {
// FCFS: process runs as soon as previous finishes (if arrived)
currentTime = Math.max(currentTime, arrival[i]);
currentTime += burst[i];
finish[i] = currentTime;
turnaround[i] = finish[i] - arrival[i];
waiting[i] = turnaround[i] - burst[i];
System.out.printf("P%d: finish=%d, turnaround=%d, waiting=%d%n",
i+1, finish[i], turnaround[i], waiting[i]);
}
// P1: finish=10, turnaround=10, waiting=0
// P2: finish=12, turnaround=11, waiting=9 ← convoy effect!
// P3: finish=15, turnaround=13, waiting=10
double avgWait = Arrays.stream(waiting).average().orElse(0);
System.out.printf("Average Waiting Time: %.1f%n", avgWait); // 6.3Convoy Effect and When to Avoid FCFS
The convoy effect occurs when a long CPU-bound process is at the head of the queue, causing all shorter processes behind it to wait. This is analogous to being stuck behind a slow lorry on a single-lane road — everyone is delayed regardless of their own speed. FCFS is acceptable when all processes have similar burst times (e.g., batch jobs of equal size) but unsuitable for mixed workloads with varying burst times.
// Visualizing convoy effect vs no-convoy:
// Scenario A (convoy): Long process first
// P1 (burst=10), P2 (burst=1), P3 (burst=1)
// | P1——————————— | P2 | P3 |
// 0 10 11 12
// P2 waiting = 9, P3 waiting = 10, avg = 6.3
// Scenario B (no convoy): Short processes first
// P2 (burst=1), P3 (burst=1), P1 (burst=10)
// | P2 | P3 | P1——————————— |
// 0 1 2 12
// P2 waiting = 0, P3 waiting = 1, P1 waiting = 2, avg = 1.0
// FCFS implementation using a queue
Queue<int[]> readyQueue = new LinkedList<>();
// [processId, arrivalTime, burstTime]
readyQueue.add(new int[]{1, 0, 10});
readyQueue.add(new int[]{2, 1, 2});
readyQueue.add(new int[]{3, 2, 3});
int time = 0;
while (!readyQueue.isEmpty()) {
int[] proc = readyQueue.poll(); // FIFO — arrival order
time = Math.max(time, proc[1]); // handle idle CPU gaps
System.out.printf("Running P%d from t=%d to t=%d%n",
proc[0], time, time + proc[2]);
time += proc[2];
}Key Points to Remember
- 1FCFS is non-preemptive: the running process holds the CPU until completion or voluntary I/O wait.
- 2Implementation is trivially simple — a FIFO queue of processes.
- 3Convoy effect: short processes waiting behind a long CPU-bound process — average waiting time spikes.
- 4FCFS has no starvation — every process eventually reaches the head of the queue.
- 5Suitable for batch systems with similar burst times; poor for interactive or mixed workloads.
- 6Average waiting time with FCFS is highly sensitive to arrival order.
Interview Questions
Sign in to ask AriaWhat is the convoy effect in FCFS scheduling?
Is FCFS subject to starvation? Why or why not?
Given 3 processes with arrival and burst times, calculate FCFS average waiting time.
In what real-world scenario would FCFS be an appropriate scheduling algorithm?
Ask Aria about FCFS Scheduling
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.