Free lesson · Operating Systems

Process: (name, arrival_time, burst_time)

Easy10 min readoperating-systemsosconcurrency

The Simplest Possible Scheduler

First Come First Served (FCFS) is exactly what it sounds like: processes run in the order they arrive. The first process to enter the ready queue gets the CPU first. It runs until it finishes or blocks on I/O. Then the next process in line runs. No interruption, no priority, no cleverness. Just a simple queue.

FCFS is the scheduling equivalent of a checkout line at a grocery store. Whoever gets in line first gets served first. It does not matter if the person ahead of you has a cart overflowing with groceries and you only have one item - you wait until they are done.

This simplicity is both FCFS's strength and its fatal weakness. It is trivial to implement - just a FIFO queue. No complex data structures, no priority comparisons, no time quantum management. But in practice, FCFS produces terrible average waiting times for most workloads, which is why no modern operating system uses it as its primary scheduler.

Understanding FCFS matters for interviews because it is the baseline that other algorithms improve upon. When an interviewer asks you to compare scheduling algorithms, they expect you to explain what FCFS gets wrong and how later algorithms fix those problems.

How FCFS Works

The algorithm is one sentence: maintain a FIFO queue of ready processes, and always run the process at the front of the queue.

When a new process arrives, it is added to the back of the queue. When the running process finishes (or blocks on I/O), the scheduler takes the process at the front of the queue and gives it the CPU. That is the entire algorithm.

FCFS is non-preemptive - once a process starts running, it keeps the CPU until it voluntarily gives it up (by finishing, blocking on I/O, or calling a yield function). The scheduler does not interrupt running processes with a timer. This means a CPU-bound process that runs for 30 seconds will hold the CPU for the entire 30 seconds while every other process waits.

This non-preemptive nature is the root cause of most of FCFS's problems. In contrast, preemptive algorithms like Round Robin use a timer interrupt to force processes to give up the CPU after a fixed time slice. FCFS has no such mechanism - it trusts every process to be well-behaved and finish in a reasonable time. When a process violates that trust (by running for seconds or minutes without yielding), every other process suffers.

The internal implementation of FCFS is a simple linked list or array-based queue. When the scheduler needs to select the next process, it dequeues the process at the front of the ready queue - an O(1) operation. There is no comparison of priorities, no calculation of remaining time, no tree traversal. This simplicity means the scheduler itself adds essentially zero overhead to each scheduling decision, which is the one genuine advantage of FCFS over more sophisticated algorithms that require O(log n) or O(n) operations per decision.

graph LR
    subgraph QUEUE["Ready Queue (FIFO)"]
        P4["P4<br/>(arrived last)"] --> P3["P3"] --> P2["P2"] --> P1["P1<br/>(arrived first)"]
    end
    
    P1 -->|"next to run"| CPU["CPU<br/>────<br/>Currently running:<br/>P0"]
    
    CPU -->|"P0 finishes<br/>or blocks"| DONE["P0 Done<br/>(or Waiting)"]

This diagram shows the FCFS scheduling queue. Process P0 is currently running on the CPU. Processes P1 through P4 are in the ready queue in arrival order. P1 arrived first and is at the front of the queue - it will run next when P0 finishes or blocks. P4 arrived last and is at the back.

The Convoy Effect: Why FCFS Fails

The convoy effect is the defining problem of FCFS. It occurs when a long CPU-bound process arrives before several short I/O-bound processes, forcing all the short processes to wait an unnecessarily long time.

Let us walk through a concrete example. Suppose four processes arrive at time 0, in this order:

Under FCFS, P1 runs first for 100 ms. Then P2 runs for 2 ms. Then P3 for 2 ms. Then P4 for 2 ms.

The average waiting time is 76.5 ms. Processes P2, P3, and P4 each needed only 2 ms of CPU time, but they waited 100, 102, and 104 ms respectively. That is a 50x wait-to-work ratio for P2.

Now suppose the order were reversed - P2 → P3 → P4 → P1:

Same processes, same total CPU time, but the average waiting time dropped from 76.5 ms to 3.0 ms - a 25x improvement. P1 waited 6 ms instead of 0, but P2, P3, and P4 together saved 300 ms of waiting time. This is the convoy effect in action: one slow process (the "truck") creates a convoy of faster processes stuck behind it.

The convoy effect is not just a textbook problem. It appears in real systems whenever a FIFO-ordered resource (a lock, a queue, a connection pool) has a mix of fast and slow consumers. A database connection pool that serves queries in FIFO order will exhibit the convoy effect when a long-running analytics query gets ahead of hundreds of fast point lookups.

gantt
    title FCFS: Convoy Effect
    dateFormat X
    axisFormat %s

    section Schedule
    P1 CPU-bound (100ms) :p1, 0, 100
    P2 I/O-bound (2ms)   :p2, 100, 102
    P3 I/O-bound (2ms)   :p3, 102, 104
    P4 I/O-bound (2ms)   :p4, 104, 106

This Gantt chart shows the convoy effect in FCFS scheduling. P1 runs from time 0 to 100 milliseconds. P2, P3, and P4 - each needing only 2 milliseconds - are stuck waiting until P1 finishes. They do not start until time 100, 102, and 104 respectively. The three short processes collectively wait 306 milliseconds for a total of 6 milliseconds of work.

Warning: The convoy effect is not limited to CPU scheduling. Any system that uses FIFO ordering for a shared resource can exhibit it. Examples include mutex locks (a thread holding a lock for a long time blocks all waiting threads), message queues (a slow consumer blocks the queue for everyone), and even real-world scenarios like a slow customer at a single checkout lane. The solution is always the same: either allow preemption (interrupt the slow consumer) or use multiple channels (multiple checkout lanes, multiple locks, partitioned queues).

Calculating FCFS Metrics Step by Step

Being able to calculate scheduling metrics is a common interview skill. Let us work through a more complex example with processes arriving at different times.

Under FCFS, the schedule is:

P1 runs from 0 to 8 (it arrived first, runs for 8 ms). P2 runs from 8 to 12 (arrived at time 1, waited from 1 to 8, runs for 4 ms). P3 runs from 12 to 21 (arrived at time 2, waited from 2 to 12, runs for 9 ms). P4 runs from 21 to 26 (arrived at time 3, waited from 3 to 21, runs for 5 ms).

Practice this calculation until it is automatic. The pattern is always the same: completion time = start time + burst time, turnaround time = completion time − arrival time, waiting time = turnaround time − burst time.

Interview: "Explain FCFS scheduling and its main problem."

"FCFS runs processes in arrival order - first to arrive, first to run. It is non-preemptive, meaning a process keeps the CPU until it finishes or blocks. The implementation is just a FIFO queue - simple and fair in the sense that no process jumps the line.

The main problem is the convoy effect. If a long CPU-bound process arrives before several short I/O-bound processes, all the short processes are stuck waiting behind the long one. This produces high average waiting times. The solution is to use a smarter scheduling order - like Shortest Job First, which minimizes average waiting time by running short jobs before long ones - or to use preemption, which limits how long any process can hold the CPU."

When FCFS Is Actually Appropriate

Despite its problems, FCFS has legitimate use cases:

Non-preemptive environments. Some embedded systems and real-time systems use FCFS within priority levels - all processes at the same priority run in FIFO order, which is simple and predictable. The deterministic behavior of FCFS (the schedule depends only on arrival order, not on any dynamic state) makes it attractive for systems that need predictability above all else.

Fairness-critical systems. In some contexts, strict arrival-order fairness is a requirement. Print queues, for example, process jobs in the order they were submitted - it would be unfair to let a small document jump ahead of a large one that was submitted first. The person who submitted first has a reasonable expectation of being served first.

As a tiebreaker. Most practical schedulers use FCFS as a tiebreaker within more sophisticated algorithms. Round Robin is essentially FCFS with preemption. MLFQ uses FCFS within each priority queue. Even Linux's CFS uses arrival order as a tiebreaker when two processes have equal virtual runtime.

Very low-contention systems. If your system rarely has more than one process in the ready queue (because processes are mostly I/O-bound and the CPU is rarely contended), the scheduling order does not matter much. FCFS and SJF and Round Robin all produce similar results when there is usually only one candidate to schedule. The convoy effect only manifests when multiple processes are competing for the CPU simultaneously.

FCFS and Variance: Why Averages Are Not the Full Story

One aspect of FCFS that is often overlooked in textbook treatments is its effect on variance - not just the average waiting time, but the spread of waiting times across processes.

Under FCFS, the first process to arrive always waits 0 ms (it runs immediately). The last process to arrive waits for the sum of all preceding burst times. This means the variance of waiting times is very high. Some processes get excellent service (zero wait) and others get terrible service (waiting for every process ahead of them).

For a web server, high variance is a problem even if the average is acceptable. If the average response time is 50 ms but the 99th percentile is 2 seconds, 1% of users are having a terrible experience. Production systems at FAANG companies track tail latencies (P95, P99, P99.9) precisely because averages can hide individual suffering. FCFS tends to produce high tail latencies because the last processes in the queue bear the cumulative weight of everyone ahead of them.

More sophisticated algorithms like Round Robin distribute waiting time more evenly - every process waits a little, but no process waits an extreme amount. This reduces variance and improves tail latency, which is why Round Robin and its derivatives are preferred for interactive and user-facing systems.

Implementing FCFS

FCFS is straightforward to implement. Here is a simulation that shows how the algorithm works and calculates the metrics:

from collections import deque

# Process: (name, arrival_time, burst_time)
processes = [
    ("P1", 0, 8),
    ("P2", 1, 4),
    ("P3", 2, 9),
    ("P4", 3, 5),
]

# Sort by arrival time (already sorted, but make it explicit)
processes.sort(key=lambda p: p[1])

current_time = 0
results = []

for name, arrival, burst in processes:
    # Process cannot start before it arrives
    start_time = max(current_time, arrival)
    completion_time = start_time + burst
    turnaround = completion_time - arrival
    waiting = turnaround - burst
    
    results.append((name, arrival, burst, start_time, completion_time, turnaround, waiting))
    current_time = completion_time

print(f"{'Process':<10} {'Arrival':<10} {'Burst':<10} {'Start':<10} {'Complete':<10} {'Turn.':<10} {'Wait':<10}")
print("-" * 70)
for r in results:
    print(f"{r[0]:<10} {r[1]:<10} {r[2]:<10} {r[3]:<10} {r[4]:<10} {r[5]:<10} {r[6]:<10}")

avg_turnaround = sum(r[5] for r in results) / len(results)
avg_waiting = sum(r[6] for r in results) / len(results)
print(f"\nAverage Turnaround Time: {avg_turnaround:.2f} ms")
print(f"Average Waiting Time:    {avg_waiting:.2f} ms")

This simulation demonstrates the core FCFS logic: processes run in arrival order, each process starts when the CPU is free (or when it arrives, whichever is later), and metrics are calculated from the start time, completion time, arrival time, and burst time. Understanding this simulation - and being able to trace through it by hand - prepares you for the worked examples in interview scheduling questions.

Summary: FCFS Strengths and Weaknesses

Pros:
- Simplest possible scheduling algorithm - one FIFO queue
- Fair in arrival order - no process can jump the line
- No starvation - every process eventually runs
- Predictable and deterministic - same arrival order always produces the same schedule
- Zero overhead - no preemption timer, no priority comparisons

Cons:
- Convoy effect - one long process blocks all short processes behind it
- High average waiting time - especially with mixed workloads of long and short processes
- High variance in waiting time - first arrivals wait 0, last arrivals may wait a very long time
- Non-preemptive - a CPU-bound process holds the CPU until it finishes or blocks
- Poor for interactive systems - user clicks may wait behind long batch jobs
- Not suitable as a standalone scheduler for general-purpose operating systems

Exercise: Starter: Given processes P1 (burst=6, arrival=0), P2 (burst=2, arrival=1), P3 (burst=8, arrival=2), P4 (burst=3, arrival=3), calculate the average turnaround time and average waiting time under FCFS. Draw a Gantt chart showing when each process runs.

Intermediate: Take the same four processes and calculate what the average waiting time would be if you could schedule them in any order (ignoring arrival times). What is the optimal order? How much better is it than FCFS? What scheduling algorithm does this optimal order correspond to?

Advanced: Think about the convoy effect in the context of lock contention in a multi-threaded program. If a mutex uses FIFO ordering for waiting threads, and one thread holds the lock for 100 ms while 10 threads each need it for 1 ms, what is the average waiting time for the short threads? How would the situation change if the mutex used shortest-hold-time-first ordering? What are the fairness implications of each approach?

Back to Operating Systems