COMP 3150Operating Systems

Module 2 · Unit 5 · Lesson 2 of 6

First-Come, First-Served Scheduling

The simplest CPU scheduling algorithm: a single FIFO ready queue, no priorities, no time quanta, no preemption. Its simplicity makes it easy to implement and to analyse — and its failure mode, the convoy effect, is the clearest illustration of why scheduling policy matters at all.

01 Introduction

In Lesson 5.1 we established the vocabulary: the CPU–I/O burst cycle, the standard criteria, the performance metrics, and the trade-offs that make scheduling a design problem rather than a solved one. This lesson begins the survey of concrete algorithms with the oldest and simplest of them all, First-Come, First-Served (FCFS).

FCFS is exactly what its name suggests. The ready queue is a FIFO: when a process becomes ready, it is appended to the tail; when the CPU becomes free, the process at the head is selected. There are no priorities, no time quanta, and no preemption — once a process has been given the CPU, it keeps it until it blocks on I/O or terminates. The algorithm was used in the earliest batch systems, where jobs were submitted on punched cards and processed in the order they arrived, and it survives today in a surprising number of places: print spoolers, simple embedded systems, network device queues, and the default policies of several operating-system subsystems.

Studying FCFS is not merely an exercise in historical completeness. It is the baseline against which every other scheduling algorithm is measured, and its central weakness — the convoy effect — is the clearest possible demonstration of why a scheduler that ignores burst lengths performs poorly on a mixed workload. The convoy effect is also the direct motivation for shortest-job-first scheduling, which is the subject of Lesson 5.3. Understanding FCFS thoroughly makes the rest of the unit much easier to follow, because every subsequent algorithm can be understood as a response to one or another of FCFS's limitations.

This lesson covers the mechanics of the algorithm, the convoy effect and its consequences, a detailed performance analysis against the criteria from Lesson 5.1, the variants of FCFS that appear in real systems, and the contexts in which FCFS remains the right choice despite its well-known problems.

Prerequisites

This lesson builds directly on Lesson 5.1. In particular, the definitions of turnaround time, waiting time, response time, and the standard scheduling criteria are used throughout without re-derivation. If any of those terms are unfamiliar, review sections 4.5 and 4.6 of Lesson 5.1 before continuing.

02 Learning objectives

By the end of this lesson you will be able to

  • Describe the FCFS algorithm and trace a workload through an FCFS schedule.
  • Compute turnaround, waiting, and response times for an FCFS schedule.
  • Explain the convoy effect and its consequences for CPU and I/O utilization.
  • Analyse FCFS against the standard scheduling criteria.
  • Evaluate the contexts in which FCFS is an appropriate choice.

This lesson contributes to U5.2 and U5.3, and to course learning outcomes CLO1, CLO2, and CLO3.

03 Required reading

  • OSTEP — Chapter 7, Scheduling: Introduction, through the section on first-come, first-served and the convoy effect. OSTEP's treatment of the convoy effect is the clearest short explanation available and is the direct source of the worked example in this lesson.
  • Operating System Concepts — Chapter 5, Section 5.3.1, First-Come, First-Served Scheduling. The textbook's formal treatment, including the worked example with three processes and the discussion of why FCFS is troublesome for time-sharing systems.
  • Tanenbaum & Bos — Modern Operating Systems, Chapter 2, Section 2.4.2. A complementary treatment that places FCFS in the context of batch scheduling and compares it with shortest-job-first.
  • Love, R. — Linux System Programming, Chapter 3. A brief note on why Linux does not use FCFS for ordinary tasks, and what it uses instead.

Reading strategy

Read the OSTEP section first, paying particular attention to the diagram that shows the convoy effect. Then read the Silberschatz section for the formal definitions and the worked example. The two treatments complement each other: OSTEP explains the intuition, Silberschatz provides the formalism. Keep Lesson 5.1's definitions of the metrics at hand as you read — you will want to compute the numbers yourself as you work through the examples.

04 Core content

4.1 The algorithm

First-Come, First-Served is defined by two rules:

  1. The ready queue is a FIFO. When a process becomes ready, it is appended to the tail of the queue.
  2. When the CPU becomes idle, the process at the head of the queue is selected and runs until it blocks or terminates. It is never preempted.

The first rule determines the order of selection; the second rule determines the duration of each allocation. Together they describe an algorithm that requires almost no state to implement: a single queue, an enqueue operation, and a dequeue operation. There is no priority to track, no quantum to expire, and no preemption decision to make. This simplicity is FCFS's principal virtue.

The algorithm is non-preemptive: the running process is not interrupted by the scheduler. It releases the CPU only when it blocks — typically on an I/O request — or when it terminates. A new process that arrives while another is running must wait, no matter how short its burst or how urgent its work. This is the source of both FCFS's predictability and its most serious performance problem.

4.2 The ready queue as a FIFO

The central data structure is a simple queue. At any moment it contains the processes that are ready to run but do not have the CPU. When a running process blocks or terminates, the scheduler removes the process at the head of the queue and dispatches it. When a blocked process becomes ready — for example, when its I/O completes — it is appended to the tail.

The queue discipline is strict: a process that has been waiting longer is always selected before a process that has been waiting less. This is what makes FCFS fair in the narrow sense that no process can be overtaken by a process that arrived later. It is also what makes FCFS vulnerable to the convoy effect, because a long process at the head of the queue delays every process behind it.

The queue length is bounded by the degree of multiprogramming — the number of processes in memory — and by the number of processes blocked on I/O that will become ready again. On a heavily loaded system the queue can become long, and the time a process spends waiting in it can dominate its total turnaround time.

4.3 The convoy effect

The convoy effect is the phenomenon in which one long-running CPU-bound process at the head of the ready queue delays every process behind it, including many short I/O-bound processes. The I/O devices sit idle while the CPU is occupied by the long process. When the long process finally blocks or terminates, the short processes run quickly, issue their I/O requests all at once, and then all wait on I/O together — leaving the CPU idle while the I/O devices are busy. The result is a system that alternates between CPU-bound and I/O-bound phases, with each resource idle while the other is saturated.

The convoy effect under First-Come, First-Served scheduling Two timelines compare a mixed workload under FCFS and under an ideal schedule. Under FCFS, a long CPU-bound process runs first while three short I/O-bound processes wait. The I/O devices are idle during this time. When the long process finishes, the three short processes run in quick succession, issue their I/O requests together, and leave the CPU idle while the I/O devices are busy. Under an ideal schedule, the short I/O-bound processes run first, overlapping CPU work with I/O work so that both resources stay busy. THE CONVOY EFFECT UNDER FCFS FCFS CPU P1 (CPU-bound, long) P2 P3 P4 CPU idle I/O I/O idle I/O busy (P2, P3, P4) 0 10 20 30 40 50 60 IDEAL CPU P2 P3 P4 P2 P3 P4 P1 (CPU-bound, long) I/O P2 I/O P3 I/O P4 I/O P2, P3, P4 second I/O 0 10 20 30 40 50 60 CPU-bound burst I/O-bound CPU burst I/O wait Under FCFS, the long CPU-bound process delays the short I/O-bound processes; the I/O devices sit idle during the long CPU burst, and the CPU sits idle while all the short processes wait on I/O together. Under an ideal schedule, the short processes run first, so CPU work overlaps with I/O work and both resources stay busy. This is the cost of ignoring burst lengths.
Figure 5.2 — The convoy effect under FCFS. A long CPU-bound process at the head of the queue delays three short I/O-bound processes. The I/O devices are idle while the long process runs, and the CPU is idle while the short processes wait on I/O together. An ideal schedule interleaves the short processes so that CPU work and I/O work overlap.

The convoy effect is not a theoretical curiosity. It appears whenever a mixed workload contains processes with widely different burst lengths, and it is the reason FCFS performs poorly on general-purpose systems. The effect is most severe when the long process is CPU-bound and the short processes are I/O-bound — exactly the mix that a time-sharing system is designed to handle. The long process monopolizes the CPU while the I/O devices are idle; then, when it finally releases the CPU, the short processes rush through their CPU bursts and issue their I/O requests together, leaving the CPU idle while the I/O devices are saturated. The system oscillates between CPU-bound and I/O-bound phases, and neither resource is well utilized.

The convoy effect also has a direct effect on the metrics from Lesson 5.1. The short processes experience long waiting times and long response times because they are stuck behind the long process. Their turnaround times are inflated by the long process's burst. The average waiting time across the workload is dominated by the short processes, which are the majority, so the average is much worse than it would be under a schedule that ran the short processes first. This is the key insight that motivates shortest-job-first scheduling in Lesson 5.3.

The convoy effect and I/O utilization

The convoy effect is not only a CPU-scheduling problem. The I/O devices are a resource too, and FCFS wastes them. While the long CPU-bound process runs, the I/O devices sit idle even though there are I/O-bound processes ready to issue requests. A better scheduler would run an I/O-bound process during the long process's burst, so that the CPU and the I/O devices are both busy. This is the essence of multiprogramming: overlapping CPU work with I/O work. FCFS fails to achieve this overlap when the queue order is unfavourable.

4.4 Non-preemption and its consequences

FCFS is non-preemptive, and this property has several consequences that are worth separating from the convoy effect itself.

  • Predictability. Because a process is never interrupted, its progress is deterministic once it starts. It will complete in exactly its burst time, with no quantum expirations to account for. This makes FCFS easy to analyse and easy to reason about, which is one reason it survives in embedded and real-time systems where predictability matters more than average performance.
  • No response-time guarantee. A process that arrives just after a long process has started must wait for the entire burst. If the long process runs for a second, the short process waits a second — even if its own burst is a millisecond. For interactive systems, this is unacceptable: a user typing at a terminal would experience a freeze of a second or more whenever a long computation was scheduled ahead of their keystroke handler.
  • Scheduling cannot correct the order. Once a process has been dispatched, the scheduler cannot undo the decision. This means that a single unfortunate scheduling decision — running the long process before the short ones — has consequences that persist for the entire burst. Preemptive schedulers can recover from such decisions; FCFS cannot.
  • Starvation is impossible by construction. Because the queue is FIFO, every process eventually reaches the head and runs. No process can be indefinitely postponed. This is a genuine advantage over priority scheduling, which can starve low-priority processes indefinitely.

4.5 Performance analysis against the criteria

Applying the criteria from Lesson 5.1 to FCFS gives the following assessment.

FCFS against the standard scheduling criteria
Criterion Assessment Notes
CPU utilization Poor on mixed workloads The convoy effect leaves the CPU idle while I/O-bound processes wait together.
Throughput Moderate Low overhead (few context switches) helps throughput, but poor overlap with I/O hurts it.
Turnaround time Poor Short processes stuck behind long ones have inflated turnaround times.
Waiting time Poor The average waiting time is much worse than SJF; see the worked example.
Response time Very poor A process cannot respond until its turn at the head of the queue; there is no preemption.
Fairness Good Strict FIFO order; no process can overtake another. Starvation is impossible.
Predictability Excellent No preemption, no quantum; the schedule is fully determined by arrival and burst times.

The pattern is clear: FCFS is excellent on the criteria that matter for batch systems — fairness, predictability, low overhead — and poor on the criteria that matter for interactive systems — response time, waiting time, and turnaround time on mixed workloads. This is exactly the historical trajectory: FCFS was the natural choice for early batch systems, and it was abandoned for time-sharing systems as soon as interactive use became common.

4.6 Variants and real-world uses

Pure FCFS is rarely used as the primary scheduler in a general-purpose operating system. But the FIFO discipline appears in many places, sometimes as the whole policy and sometimes as a component of a larger one.

  • Print spoolers. Print jobs are typically processed in the order they were submitted. The jobs are not interactive, the resource is scarce, and fairness is the natural expectation. FCFS is the right choice.
  • Batch and cluster schedulers. In systems where jobs are submitted in advance and run to completion, FCFS is common. The Slurm workload manager, for example, offers a FIFO policy as one of its options, though production installations usually combine it with backfilling to improve utilization.
  • Network device queues. Many network interfaces process packets in the order they arrive. The discipline is simple and the hardware is fast enough that more elaborate policies are unnecessary — or were, until latency-sensitive applications made queueing delay a concern. Modern network schedulers use more sophisticated policies, but the FIFO baseline remains the default in many devices.
  • Embedded and real-time systems. In a system where tasks are known in advance and have similar burst lengths, FCFS provides determinism without complexity. Cyclic executives — the simplest real-time schedulers — are essentially FCFS with a fixed task set.
  • As a component of multilevel schedulers. A multilevel queue scheduler (Lesson 5.6) may use FCFS within one of its queues, particularly for the lowest- priority queue where processes are expected to be long-running and CPU-bound. The queue discipline inside each level can be chosen independently of the policy for selecting among levels.

FCFS as a baseline

Even when FCFS is not the right policy, it is the right baseline. When evaluating a new scheduling algorithm, it is standard practice to compare its performance against FCFS on the same workload. If the new algorithm cannot beat FCFS, it is not worth the additional complexity. This is the approach you will take in Lab 4, where you will implement several scheduling algorithms and compare them against the FCFS baseline.

4.7 FCFS and the metrics: a first look

The worked example in the next section computes the metrics for a concrete workload. Before working through it, it is worth stating the general result: under FCFS, the waiting time of a process is the sum of the burst times of all the processes that arrived before it and have not yet completed. In symbols, if processes P1, P2, …, Pn arrive at the same time and run in that order, the waiting time of Pk is: 

WT(P_k) = sum of BT(P_i) for i = 1 to k-1

The average waiting time is therefore: 

Average WT = (1/n) * sum over k of WT(P_k)
           = (1/n) * sum over k of (n - k) * BT(P_k)

This formula makes the dependence on order explicit. The first process's burst time is counted n − 1 times (it delays every other process), the second process's burst time is counted n − 2 times, and so on, while the last process's burst time is not counted at all. The consequence is that the average waiting time is minimized when the burst times are ordered from shortest to longest — the opposite of what FCFS does when the long process happens to arrive first. This is the formal statement of the convoy effect, and it is the direct motivation for shortest-job-first scheduling in Lesson 5.3.

4.8 Common misconceptions

"FCFS is fair, so it is good."

Fairness is only one criterion among several. FCFS is fair in the narrow sense of preserving arrival order, but it is poor on response time, waiting time, and utilization. A fair schedule can still be a bad schedule.

"FCFS has no overhead."

Every context switch costs time. FCFS has fewer switches than a preemptive policy, because a process runs until it blocks or terminates, but it still pays the dispatch cost on each switch.

"The convoy effect only affects the short processes."

The long process also suffers. Its turnaround time is unaffected (it started first), but the system's overall throughput and utilization are reduced, which affects every process that arrives later.

"FCFS is obsolete."

FCFS remains the right choice in many contexts: print spoolers, batch systems, embedded systems, and as a baseline for comparison. The algorithm is simple, predictable, and starvation-free.

"FCFS is the same as FIFO."

They are closely related but not identical. FIFO is a queue discipline; FCFS is a scheduling policy that uses FIFO for the ready queue. A scheduler could in principle use FIFO for some other purpose, and FCFS is defined by both the queue discipline and the non-preemptive execution rule.

"Preemption would always improve FCFS."

Preemption improves response time but increases overhead and reduces throughput. In some contexts — batch processing, embedded control — the non-preemptive determinism of FCFS is more valuable than responsiveness.

05 Worked example

The following example works through a concrete FCFS schedule, computes the standard metrics, and demonstrates the convoy effect by comparing the FCFS result with an ideal schedule on the same workload.

FCFS on a mixed workload

Four processes arrive at different times. P1 is CPU-bound with a long burst; P2, P3, and P4 are I/O-bound with short CPU bursts separated by I/O waits.

Process Arrival Burst Type
P1020CPU-bound
P212I/O-bound
P322I/O-bound
P432I/O-bound

The FCFS schedule. P1 arrives at time 0 and is immediately dispatched. P2, P3, and P4 arrive while P1 is running and are appended to the ready queue in arrival order. P1 runs until time 20, then P2, P3, and P4 run in that order. The Gantt chart is: 

| P1                      | P2  | P3  | P4  |
0                         20   22   24   26

The completion times are 20, 22, 24, and 26 respectively. Applying the formulas from Lesson 5.1:

Process Arrival Burst Start Completion Turnaround Waiting Response
P10200202000
P2122022211919
P3222224222020
P4322426232121
Average 21.5 15.0 15.0

The three short I/O-bound processes each wait about 20 time units before they run — even though their own bursts are only 2 units. Their waiting times are dominated by the long process ahead of them. The average waiting time is 15.0, and the maximum waiting time is 21.

The convoy effect in action. While P1 runs from time 0 to time 20, the I/O devices are idle. The three I/O-bound processes are ready to issue their I/O requests, but they cannot run because they do not have the CPU. Then, from time 20 to time 26, the three short processes run in quick succession. They issue their I/O requests at times 22, 24, and 26 — all within a short window — and then all three wait on I/O at the same time. The CPU is idle while they wait. The system has alternated between a CPU-bound phase (0–20) and an I/O-bound phase (22–26+), and neither resource was well utilized.

An ideal schedule. Suppose the scheduler knew the burst lengths and ran the short processes first. The ideal order is P2, P3, P4, P1: 

| P2  | P3  | P4  | P1                      |
0     2     4     6                         26

The metrics for this schedule:

Process Arrival Burst Start Completion Turnaround Waiting Response
P21213200
P32235311
P43257422
P10207272777
Average 9.0 2.5 2.5

Comparison.

Metric FCFS Ideal (shortest first) Improvement
Average turnaround21.59.02.4×
Average waiting15.02.56.0×
Average response15.02.56.0×
Maximum waiting2173.0×

The ideal schedule is dramatically better on every per-process metric. The three short processes finish quickly — their waiting times are 0, 1, and 2 — and the long process waits 7 units, which is a modest penalty compared to the 20-unit waits the short processes suffered under FCFS. The average waiting time is six times better.

The catch. The ideal schedule requires the scheduler to know the burst lengths in advance. In a real system it does not. The scheduler cannot know whether a process will run for 2 units or 20 until it has run. Estimating burst length — and adapting the schedule as estimates improve — is the central problem of shortest-job-first scheduling, which is the subject of Lesson 5.3. FCFS avoids the problem by ignoring burst lengths entirely, but the price is the convoy effect shown above.

Adding dispatch latency

Suppose each context switch costs 1 time unit. The FCFS schedule has three switches (at times 20, 22, and 24), so it loses 3 units to overhead. The ideal schedule also has three switches (at times 3, 5, and 7). The overhead is the same for both schedules in this example, but in general the number of switches depends on the policy: a preemptive policy that uses short quanta performs many more switches, and pays correspondingly more overhead. This is the trade-off examined in detail in Lesson 5.5.

06 Interactive activity

Activity · implement and explore FCFS

The goal of this activity is to implement the FCFS algorithm, trace it on the workloads from the lesson, and observe the convoy effect in a live system. Work through the steps in your course VM.

  1. Write an FCFS simulator. Write a C program that reads a list of processes (arrival time, burst time) from standard input, simulates FCFS scheduling, and prints the Gantt chart along with the completion, turnaround, waiting, and response times for each process. Compute the averages and the maximum for each metric. 
    #include <stdio.h>
#include <stdlib.h>

struct proc {
    int pid;
    int arrival;
    int burst;
    int start;
    int completion;
};

int main(void) {
    int n;
    if (scanf("%d", &n) != 1) return 1;
    struct proc *p = calloc(n, sizeof(*p));
    for (int i = 0; i < n; i++) {
        p[i].pid = i + 1;
        scanf("%d %d", &p[i].arrival, &p[i].burst);
    }

    /* Sort by arrival time (FCFS queue order) */
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (p[j].arrival < p[i].arrival) {
                struct proc t = p[i]; p[i] = p[j]; p[j] = t;
            }

    int time = 0;
    double sum_tat = 0, sum_wt = 0, sum_rt = 0;
    int max_wt = 0;

    for (int i = 0; i < n; i++) {
        if (time < p[i].arrival) time = p[i].arrival;
        p[i].start = time;
        time += p[i].burst;
        p[i].completion = time;
        int tat = p[i].completion - p[i].arrival;
        int wt  = tat - p[i].burst;
        int rt  = p[i].start - p[i].arrival;
        sum_tat += tat; sum_wt += wt; sum_rt += rt;
        if (wt > max_wt) max_wt = wt;
        printf("P%d: start=%d completion=%d tat=%d wt=%d rt=%d\n",
               p[i].pid, p[i].start, p[i].completion, tat, wt, rt);
    }
    printf("avg tat=%.2f avg wt=%.2f avg rt=%.2f max wt=%d\n",
           sum_tat/n, sum_wt/n, sum_rt/n, max_wt);
    free(p);
    return 0;
}
    Compile with gcc -Wall -Wextra -O2 -o fcfs fcfs.c.
  2. Run the simulator on the worked example. Create an input file with the workload from section 5 and verify that the output matches the hand-computed metrics. 
    4
0 20
1 2
2 2
3 2
    ./fcfs < workload.txt
    Do the numbers match? If not, check your sorting logic and your formulas.
  3. Try different arrival orders. Modify the input so that the short processes arrive first, and the long process arrives last. Run the simulator again. How do the metrics change? Confirm that FCFS gives good results when the arrival order happens to match the burst-length order.
  4. Create a convoy. Add more short I/O-bound processes to the workload — say five short processes arriving after the long one. Run the simulator and observe how the average waiting time grows. Plot the relationship between the number of short processes and the average waiting time. What does this tell you about the scalability of FCFS under a convoy?
  5. Observe FCFS-like behaviour in Linux. Linux does not use pure FCFS for ordinary tasks, but you can observe FIFO-like behaviour in specific contexts. For example, the print spooler processes jobs in submission order: 
    lpstat -o        # list queued print jobs
# Submit a few small jobs and observe the order of completion
    If the system has no printer, use cupsd's test mode, or examine the queue behaviour of at jobs: 
    echo "sleep 1" | at now + 1 minute
echo "sleep 1" | at now + 1 minute
atq              # list pending jobs in submission order
atrm 1           # remove the first job
    The at queue is a simple FIFO.
  6. Measure the cost of a context switch with FCFS-like yielding. Modify the switch-cost program from Lesson 5.1 so that instead of using sched_yield, the two threads explicitly hand off a flag and the receiving thread spins until the handoff is complete. This approximates the cost of a cooperative, non-preemptive handoff. Compare the result to the preemptive yield measurement. 
    /* Thread A sets flag = 1, then spins until flag == 0.
   Thread B spins until flag == 1, then sets flag = 0.
   Time 500000 round trips. */
    How much cheaper is the cooperative handoff? What does this suggest about the cost of preemption in a non-preemptive policy?
  7. Read man 7 sched again. Re-read the section on the scheduling policies. Compare the FIFO discipline of SCHED_FIFO with the FCFS algorithm from this lesson. In what ways are they similar, and in what ways do they differ? (Hint: pay attention to what happens when a higher-priority real-time task becomes ready.)

Reflect: under what circumstances would you choose FCFS over a more sophisticated algorithm? What information would you need about the workload to make that decision? If you could change one aspect of FCFS while keeping its simplicity, what would it be, and what would you expect to gain?

07 Knowledge check

Check your understanding

Question 1

Describe the FCFS scheduling algorithm in two sentences. Is it preemptive or non-preemptive? What data structure does it use?

Show answer
FCFS schedules processes in the order they arrive: the ready queue is a FIFO, and the process at the head is selected whenever the CPU becomes free. It is non-preemptive: once a process is running, it keeps the CPU until it blocks on I/O or terminates. The data structure is a simple FIFO queue — processes are appended to the tail when they become ready and removed from the head when they are dispatched.

Question 2

What is the convoy effect? Explain why it reduces both CPU utilization and I/O utilization.

Show answer
The convoy effect is the phenomenon in which a long CPU-bound process at the head of the ready queue delays all the processes behind it, including many short I/O-bound processes. It reduces CPU utilization because when the short processes finally run, they issue their I/O requests all at once and then all wait on I/O together, leaving the CPU idle. It reduces I/O utilization because while the long CPU-bound process is running, the I/O devices are idle even though the I/O-bound processes are ready to issue requests. The system oscillates between a CPU-bound phase (CPU busy, I/O idle) and an I/O-bound phase (I/O busy, CPU idle), so neither resource is well utilized. The fix is to interleave the short processes with the long one, so that CPU work and I/O work overlap.

Question 3

Three processes arrive at time 0 with burst times 5, 10, and 15. Compute the average waiting time under FCFS in the order P1 (5), P2 (10), P3 (15). Then compute it for the order P3 (15), P2 (10), P1 (5). Which order gives the lower average, and why?

Show answer
Order P1, P2, P3 (5, 10, 15): Completion times are 5, 15, 30. Turnaround times are 5, 15, 30. Waiting times are 0, 5, 15. Average waiting = (0 + 5 + 15) / 3 = 6.67.

Order P3, P2, P1 (15, 10, 5): Completion times are 15, 25, 30. Turnaround times are 15, 25, 30. Waiting times are 0, 15, 25. Average waiting = (0 + 15 + 25) / 3 = 13.33.

The first order (shortest first) gives the lower average waiting time. This is the general result derived in section 4.7: the average waiting time is minimized when the burst times are ordered from shortest to longest. The first process's burst is counted n − 1 times, so a short first process benefits every subsequent process. FCFS does not order by burst length, so it may produce either of these orders depending on arrival times, and when the long process happens to arrive first, the result is the convoy effect.

Question 4

Why is FCFS still used in some systems despite its poor performance on mixed workloads? Give at least two concrete examples of systems or subsystems where FCFS is the right choice, and explain why.

Show answer
FCFS is used where its virtues — simplicity, predictability, fairness in the FIFO sense, and freedom from starvation — outweigh its weaknesses. Two concrete examples: (1) Print spoolers. Print jobs are typically processed in submission order. The jobs are not interactive, the resource is scarce, and users expect their jobs to be processed in the order they were submitted. FCFS is the natural and fair choice, and the convoy effect is not a concern because print jobs are similar in length and the resource is not shared with interactive work. (2) Batch and cluster schedulers. In systems where jobs are submitted in advance and run to completion, FCFS is common — for example, the FIFO policy in Slurm. The jobs are long-running, there is no interactive response-time requirement, and FIFO order matches the expectation of users who submit jobs to a queue. Production installations often combine FIFO with backfilling to improve utilization, but the baseline discipline remains FIFO. Other examples include network device queues, embedded systems with fixed task sets, and the lowest-priority queue of a multilevel scheduler.

Question 5

The average waiting time under FCFS depends on the order of the burst times. Derive the formula for the average waiting time when n processes arrive at the same time and run in a given order. Explain why the formula implies that shortest-first minimizes the average.

Show answer
Let the processes run in the order P1, P2, …, Pn with burst times b1, b2, …, bn. The waiting time of Pk is the sum of the burst times of all the processes ahead of it: WT(Pk) = b1 + b2 + … + bk−1. Summing over all k and collecting terms, the burst time of P1 is counted n − 1 times, the burst time of P2 is counted n − 2 times, and so on, with the last process's burst time counted zero times. The average waiting time is therefore:

Average WT = (1/n) * [ (n−1)b₁ + (n−2)b₂ + … + 0·bₙ ]

To minimize this sum, the largest burst time should be multiplied by the smallest coefficient, and the smallest burst time by the largest coefficient. That is, the burst times should be ordered from shortest to longest. Any other order assigns a larger coefficient to a larger burst time, increasing the average. FCFS does not order by burst length, so it may produce the opposite order when a long process arrives first — the convoy effect — and the average waiting time suffers accordingly. This is the formal argument for shortest-job-first scheduling.

08 Unit discussion

Discussion prompt

FCFS is often described as "fair" because it preserves arrival order. But the worked example shows that FCFS can produce a schedule in which three short processes each wait twenty times longer than the long process that ran ahead of them. Is that fair? What does "fairness" mean in the context of CPU scheduling?

Consider two competing definitions: (a) fairness as order preservation — the process that arrived first runs first, regardless of burst length; and (b) fairness as proportionality — each process should receive a share of the CPU proportional to some measure of its need, so that no process is unduly delayed by others. FCFS satisfies (a) but violates (b) in the convoy scenario. Shortest-job-first satisfies (b) for the average but can starve long processes, violating (a) and (b) for those processes.

Which definition of fairness do you think a general- purpose operating system should adopt, and why? How should the scheduler handle the tension between them? Post your response to the Unit 5 discussion forum and reply to at least two classmates. Supports CLO1, CLO2, and CLO3.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for the algorithms in Lessons 5.3–5.6 and for Lab 4. Aim to spend 60–90 minutes on it.

  1. Trace an FCFS schedule by hand. For the workload below, construct the Gantt chart, compute the completion, turnaround, waiting, and response times for each process, and report the averages and the maximum waiting time.
    Process Arrival Burst
    P106
    P223
    P348
    P462
    P584
    Then verify your answer using the simulator from the interactive activity.
  2. Demonstrate the convoy effect. Using the simulator, construct a workload in which a long CPU-bound process (burst 30) arrives at time 0, and five short I/O-bound processes (burst 1 each) arrive at times 1 through 5. Compute the average waiting time. Then reorder the input so the short processes arrive first and the long process arrives last, and compute the average waiting time again. What is the ratio? What does this tell you about the importance of arrival order under FCFS?
  3. Compute the average-waiting-time formula. For the workload in question 1, compute the average waiting time using the formula from section 4.7: (1/n) * Σ (n−k) * BT(P_k). Verify that it matches the value you computed by hand. Then reorder the processes by burst time (shortest first) and compute the formula again. How much lower is the average?
  4. Measure dispatch latency. Run the switch-cost program from the Lesson 5.1 interactive activity. Run it ten times and record the results. Compute the mean and standard deviation. Then modify the program to time a larger number of switches (ten million) and see whether the per-switch cost changes. What does this suggest about the fixed overhead of the measurement itself?
  5. Observe a FIFO queue in the real system. Use the at command to submit three jobs with different sleep durations, and observe the order in which they complete. Use atq to list the queue and atrm to remove a job. Does the at daemon process jobs in submission order, or does it reorder them? Consult the man page for at and atd to find out what policy the queue uses.
  6. Compare FCFS to an ideal schedule. For the workload in question 1, construct the schedule that minimizes the average waiting time (run the processes in order of burst time, subject to arrival constraints). Compute the metrics for both schedules and report the improvement on each metric. What is the cost of FCFS's ignorance of burst lengths for this workload?
  7. Reflect. In your own words, explain why the convoy effect is a problem not just for the short processes but for the system as a whole. Then describe one situation in which FCFS's non-preemptive determinism is a genuine advantage, and one in which it is a serious disadvantage.

10 Summary

  • First-Come, First-Served (FCFS) is the simplest CPU scheduling algorithm: a FIFO ready queue, no priorities, no time quanta, and no preemption.
  • FCFS is non-preemptive: a running process keeps the CPU until it blocks on I/O or terminates. This makes it predictable and simple, but it means a long process can delay every process behind it.
  • The convoy effect is the phenomenon in which a long CPU-bound process at the head of the queue delays many short I/O-bound processes, leaving the I/O devices idle while the CPU is busy and the CPU idle while the I/O devices are busy.
  • FCFS is fair in the narrow sense of preserving arrival order, and it cannot starve any process. But it is poor on response time, waiting time, and turnaround time for mixed workloads.
  • The average waiting time under FCFS is (1/n) * Σ (n−k) * BT(P_k). This formula shows that the average is minimized when burst times are ordered from shortest to longest — the opposite of what FCFS does when a long process arrives first.
  • FCFS is still used in contexts where simplicity, predictability, and FIFO fairness matter more than average performance: print spoolers, batch and cluster schedulers, network device queues, embedded systems, and the lowest-priority queue of a multilevel scheduler.
  • FCFS is the standard baseline for evaluating other scheduling algorithms. A new algorithm that cannot beat FCFS is not worth its additional complexity.

Looking ahead

The convoy effect is the direct motivation for the next lesson. Shortest-Job-First (SJF) scheduling runs the process with the smallest burst time first, which minimizes the average waiting time — but it requires the scheduler to know or estimate burst lengths in advance. Lesson 5.3 examines SJF, its preemptive variant SRTF, the problem of burst-length estimation, and the starvation risk that comes with prioritizing short jobs. Lab 4 implements and compares FCFS, SJF, and the other algorithms in this unit on a simulated workload.

11 References

  • Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 7. Available online at ostep.org.
  • Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5, Section 5.3.1.
  • Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2, Section 2.4.2.
  • Love, R. Linux System Programming, 2nd ed., Chapter 3.
  • Linux man-pages: man 7 sched, man 1 at, man 1 atq, man 1 atrm, man 1 lp, man 1 lpstat.
  • Slurm Workload Manager documentation, Job Scheduling Policies — the FIFO and backfill policies.
👤