FCFS Scheduling - First Come First Served

Introduction

Imagine you are standing in a queue at a bank. The person who arrives first gets served first, regardless of how simple or complex their transaction is. Someone depositing a check (2 minutes) waits behind someone applying for a home loan (45 minutes) if the loan applicant arrived first. This is exactly how FCFS scheduling works in operating systems.

FCFS (First Come First Served) is the simplest CPU scheduling algorithm. Processes are executed in the exact order they arrive in the ready queue. It is non-preemptive, meaning once a process starts executing, it runs to completion without being interrupted. While FCFS is easy to understand and implement, its simplicity comes with significant performance limitations.

How FCFS Works

The algorithm is straightforward:

1. Processes are placed in a FIFO (First In, First Out) queue as they arrive
2. The CPU picks the process at the front of the queue
3. That process runs until it finishes (or performs an I/O operation)
4. The next process in the queue gets the CPU

There are no priorities, no time slices, and no preemption. It is pure first-come, first-served.

Detailed Example with Calculations

Let us work through a complete example. Consider three processes arriving at the following times:

Gantt Chart

Calculating Waiting Time

Waiting Time = Start Time - Arrival Time

• P1: Start at 0, Arrived at 0 → Waiting Time = 0 - 0 = 0 ms
• P2: Start at 24, Arrived at 1 → Waiting Time = 24 - 1 = 23 ms
• P3: Start at 27, Arrived at 2 → Waiting Time = 27 - 2 = 25 ms

Average Waiting Time = (0 + 23 + 25) / 3 = 16 ms

Calculating Turnaround Time

Turnaround Time = Completion Time - Arrival Time

• P1: Completed at 24, Arrived at 0 → TAT = 24 - 0 = 24 ms
• P2: Completed at 27, Arrived at 1 → TAT = 27 - 1 = 26 ms
• P3: Completed at 30, Arrived at 2 → TAT = 30 - 2 = 28 ms

Average Turnaround Time = (24 + 26 + 28) / 3 = 26 ms

Notice how P2 and P3, which only need 3 ms each, had to wait 23 and 25 ms respectively because P1 (a long process) arrived first. This is the fundamental problem with FCFS.

Implementation in C

The Convoy Effect

The biggest problem with FCFS is the convoy effect. When a long CPU-bound process is at the front of the queue, all shorter processes behind it must wait, just like slow trucks on a single-lane road create a convoy of cars behind them.

Consider this scenario: one process needs 100 ms, and ten processes each need 1 ms. If the long process arrives first, the average waiting time becomes approximately 50 ms. But if we used a smarter algorithm (like SJF), the average would drop dramatically.

The convoy effect particularly hurts I/O-bound processes. These processes need the CPU only briefly between I/O operations, but under FCFS they must wait behind CPU-bound processes for their short burst, keeping I/O devices idle.

Advantages and Disadvantages

Advantages

• Simple to implement — Just a FIFO queue, no complex data structures needed
• Easy to understand — Intuitive fairness (first to arrive, first to be served)
• No starvation — Every process eventually gets executed
• Minimal overhead — No sorting, no preemption, no priority calculations

Disadvantages

• Convoy effect — Short processes suffer behind long ones
• High average waiting time — Especially when process burst times vary significantly
• Non-preemptive — Cannot respond to higher-priority arriving processes
• Poor for time-sharing systems — Users expect interactive response times
• Low CPU utilization when I/O-bound processes wait behind CPU-bound ones

When to Use FCFS

FCFS is appropriate in batch processing systems where jobs are submitted and results collected later (no user waiting at a terminal). It is also used as a component within other algorithms — for example, within a single priority level in multilevel queue scheduling, processes might be scheduled FCFS.

Real-World Analogy

FCFS is like a single-lane drive-through restaurant. Everyone gets served in order of arrival. If a family of six (complex order, long burst time) is ahead of someone ordering just a coffee (short burst time), the coffee person waits for the entire family order to be completed. This is fair in a simple sense, but not efficient. Smart restaurants solve this with express lanes — analogous to priority scheduling or SJF.

Key Takeaways

• FCFS is the simplest CPU scheduling algorithm — processes run in arrival order
• It is non-preemptive — once started, a process runs to completion
• The convoy effect causes short processes to wait unnecessarily behind long ones
• Average waiting time can be very high when burst times vary significantly
• No starvation occurs — every process eventually gets CPU time
• FCFS is used in batch systems and as a building block within more complex schedulers
• For interactive systems, FCFS is generally too slow and algorithms like Round Robin are preferred