1. Introduction
First Come First Serve (FCFS) is the simplest and most intuitive CPU scheduling algorithm. It follows the principle of non-preemptive scheduling, where processes are executed strictly in the order in which they arrive in the ready queue.
The basic idea is straightforward:
The process that arrives first gets the CPU first.
Once a process is allocated the CPU, it continues execution until it either completes its CPU burst or terminates. The operating system does not forcibly interrupt the process to allow another process to execute.
FCFS is analogous to waiting in a line at a ticket counter, bank, or supermarket checkout. The first customer who joins the queue is the first one to be served.
Because of its simplicity, FCFS was one of the earliest scheduling algorithms used in operating systems and remains important for understanding more advanced scheduling techniques.
Although FCFS is easy to implement and guarantees that every process eventually receives CPU time, it suffers from several performance limitations, particularly in interactive and time-sharing environments.
2. Basic Concept
FCFS scheduling is based on the FIFO (First-In, First-Out) principle.
Processes enter the ready queue according to their arrival time.
The operating system always selects:
The process at the front of the ready queue.
The selected process receives the CPU and continues execution until completion.
During execution:
No preemption occurs
No priority consideration exists
No process can bypass another
The execution order is determined solely by arrival time.
Conceptual Representation
Ready Queue
Front Rear
P1 → P2 → P3 → P4
CPU allocation occurs in the same order:
CPU Execution
P1 → P2 → P3 → P4
This makes FCFS one of the fairest algorithms with respect to arrival order.
3. Working Mechanism
The FCFS scheduler continuously monitors the ready queue.
Whenever the CPU becomes available:
Select process at front of queue
Remove process from queue
Allocate CPU
Execute process until completion
Select next process
Step-by-Step Flow
Step 1: Process Arrival
Processes enter the ready queue.
Example:
Ready Queue
[P1, P2, P3]
Step 2: CPU Allocates First Process
The scheduler selects:
P1
because it arrived first.
Step 3: Process Executes Completely
P1 executes until completion.
No interruption occurs.
Step 4: Next Process Selected
After P1 finishes:
P2
receives the CPU.
Step 5: Continue Until Queue Empty
Execution order becomes:
P1 → P2 → P3
This process repeats until all processes complete.
4. Example with Gantt Chart
Consider the following processes:
| Process | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 2 |
Step 1: Determine Execution Order
Processes arrive in the order:
P1 → P2 → P3
Therefore FCFS executes them in the same order.
Gantt Chart
0 5 8 10
| P1 | P2 | P3 |
Completion Time (CT)
P1
Starts at 0
Completes at 5
CT(P1) = 5
P2
Starts at 5
Completes at 8
CT(P2) = 8
P3
Starts at 8
Completes at 10
CT(P3) = 10
Turnaround Time (TAT)
Definition:
| Process | CT | AT | TAT |
|---|---|---|---|
| P1 | 5 | 0 | 5 |
| P2 | 8 | 1 | 7 |
| P3 | 10 | 2 | 8 |
Calculations
P1
5 − 0 = 5
P2
8 − 1 = 7
P3
10 − 2 = 8
Waiting Time (WT)
Definition:
| Process | TAT | BT | WT |
|---|---|---|---|
| P1 | 5 | 5 | 0 |
| P2 | 7 | 3 | 4 |
| P3 | 8 | 2 | 6 |
Calculations
P1
5 − 5 = 0
P2
7 − 3 = 4
P3
8 − 2 = 6
Average Waiting Time
Thus:
Average WT = 3.33 units
Average Turnaround Time
Thus:
Average TAT = 6.67 units
5. Characteristics
FCFS possesses several distinctive characteristics.
Non-Preemptive
Once a process receives the CPU:
It cannot be interrupted
It executes until completion
FIFO Based
Scheduling order depends entirely on arrival order.
Simple Implementation
Requires only a queue data structure.
Deterministic Behavior
Execution order is predictable.
No Starvation
Every process eventually receives CPU time.
No process can be indefinitely postponed.
6. Advantages
Easy to Understand
The algorithm closely resembles everyday queue systems.
Example:
First Arrive
↓
First Served
Easy to Implement
Requires only:
Ready Queue
Arrival Tracking
Implementation complexity is minimal.
Low Scheduling Overhead
No complex calculations required.
The scheduler simply selects the first process.
Fair in Arrival Order
Processes are treated according to arrival sequence.
No process is skipped.
No Starvation
Every process eventually reaches the front of the queue.
7. Disadvantages
Despite its simplicity, FCFS suffers from several serious limitations.
7.1 Convoy Effect (Very Important)
The most important drawback of FCFS is:
Convoy Effect
Concept
A long CPU-bound process at the front of the queue forces all shorter processes to wait.
Example:
| Process | Burst Time |
|---|---|
| P1 | 20 |
| P2 | 2 |
| P3 | 1 |
Execution:
P1 → P2 → P3
Although P2 and P3 are very short:
They must wait for P1 to finish.
Gantt Chart
0 20 22 23
| P1 | P2 | P3 |
Waiting Times
P1 = 0
P2 = 20
P3 = 22
Short jobs suffer enormous delays.
Why Called Convoy Effect?
A large process behaves like a slow truck leading a convoy of vehicles.
All smaller processes become trapped behind it.
Long Process
↓
Short Processes Wait
Consequences
Poor average waiting time
Poor turnaround time
Reduced responsiveness
7.2 Poor Performance for Interactive Systems
Interactive systems require:
Quick responses
Frequent user interaction
FCFS performs poorly because:
Short interactive jobs may wait behind long CPU-bound jobs.
Example:
Browser Request
↓
Must Wait Behind Long Job
Result:
Slow user experience
Poor responsiveness
7.3 High Response Time
Since processes execute strictly in arrival order:
Interactive requests may experience large delays.
Example:
Long Process
↓
User Request
↓
Long Wait
Response time becomes unpredictable.
7.4 Not Suitable for Time-Sharing Systems
Modern operating systems rely heavily on:
Preemption
Fast response
Fair CPU sharing
FCFS lacks these capabilities.
Therefore it is generally unsuitable for:
Desktop systems
Mobile operating systems
Interactive servers
8. Key Insight
The most important insight regarding FCFS is:
FCFS optimizes simplicity rather than performance.
Advantages:
Extremely simple
Easy to implement
No starvation
Disadvantages:
High waiting times
Convoy effect
Poor responsiveness
Thus FCFS is often used as a baseline for comparing more advanced scheduling algorithms.
9. When is FCFS Suitable?
Although rarely used as the primary scheduler in modern interactive systems, FCFS remains useful in certain situations.
Batch Processing Systems
Batch workloads often prioritize:
Simplicity
Throughput
Examples:
Payroll processing
Report generation
Offline computation
Systems Where Order Matters
When processes must execute in arrival order:
Arrival Order = Execution Order
FCFS becomes appropriate.
Low Overhead Environments
Systems requiring minimal scheduling complexity may benefit from FCFS.
Examples:
Simple embedded systems
Educational operating systems
Performance Summary
| Criterion | FCFS Performance |
|---|---|
| CPU Utilization | Good |
| Throughput | Moderate |
| Waiting Time | Often Poor |
| Turnaround Time | Often Poor |
| Response Time | Poor |
| Fairness | Good (arrival order) |
| Starvation | None |
| Scheduling Overhead | Very Low |