FCFS
First-come, first-served. Simple, convoy-prone, no preemption required.
Level: beginner
What is it?
First-Come, First-Served (FCFS) is a non-preemptive CPU scheduling policy that selects ready jobs in arrival order. Once a job starts, it typically runs until it blocks or completes, even if a shorter job arrives while it is running.
Why does it matter?
FCFS is easy to implement and has predictable queue order, but long CPU bursts can keep short jobs waiting. This convoy effect can harm average waiting time and responsiveness, especially when short interactive jobs sit behind long CPU-bound work.
Mental model
FCFS is a single checkout line with no express lane. Everyone keeps their place, but a large order delays everyone behind it.
How it works
- Waiting time is the time before a process first receives the CPU, not its total turnaround time.
- For non-preemptive FCFS with all jobs arriving at time zero, waiting times are cumulative preceding burst times.
- Arrival order matters when jobs arrive at different times.
- The convoy effect arises when many short jobs wait behind a long job.
- FCFS can still be reasonable when simplicity and fairness of queue order matter more than minimizing average wait.
Steps
- Jobs A, B, C arrive in order with CPU bursts 6, 2, 1.
- FCFS executes A from 0–6, B from 6–8, and C from 8–9.
- Waiting times are A=0, B=6, C=8; average waiting time is 14/3.
- Compare with SJF, which changes the order when all jobs are available at time zero.
Real-world usage
- Solving GATE and OS scheduling table problems.
- Reasoning about FIFO queues in simple batch systems.
- Explaining convoy effects and why response-time requirements may need another policy.
Common mistakes
- Confusing waiting time with turnaround time; turnaround also includes execution time.
- Reordering jobs by burst time while claiming to use FCFS.
- Ignoring release/arrival times in scheduling timelines.
Interview questions
Why is FCFS non-preemptive in the usual textbook model?
The selected job keeps the CPU until it blocks or finishes; the scheduler does not interrupt it merely because a shorter job arrives.
For bursts 6, 2, 1 arriving together, what is average waiting time?
FCFS waiting times are 0, 6, and 8, so the average is 14/3 time units.