Chapter 11 of 38

FCFS Scheduling

Think about the queue at a railway ticket counter. Whoever reaches the counter first gets served first. The clerk does not stop in the middle of your booking to help someone else, and nobody is allowed to jump the line.

The simplest CPU scheduling algorithm works exactly like that counter. It is called First-Come, First-Served (FCFS) scheduling.

FCFS scheduling gives the CPU to processes in the order in which they arrive in the ready queue. Once a process gets the CPU, it keeps it until it finishes its CPU burst or blocks (for example, for I/O).

FCFS is easy to understand and easy to implement, but it has one big weakness, the convoy effect, which you will see with real numbers in this chapter. Understanding why FCFS performs badly is the best way to understand why smarter algorithms like SJF and Round Robin exist.


Quick Recap of the Terms

In CPU Scheduling Basics we defined the times that every scheduling question uses. Here they are again, because we will calculate all of them:

Term

Meaning

Formula

Arrival Time (AT)

When the process enters the ready queue

Given

Burst Time (BT)

CPU time the process needs

Given

Completion Time (CT)

When the process finishes

Read from the Gantt chart

Turnaround Time (TAT)

Total time spent in the system

TAT = CT - AT

Waiting Time (WT)

Time spent waiting in the ready queue

WT = TAT - BT

Response Time (RT)

Time until the process gets the CPU for the first time

RT = first start - AT

We draw the schedule as a Gantt chart: a bar showing which process runs in each time interval, with the times written underneath.


How FCFS Works

FCFS keeps the ready queue as a plain FIFO queue:

New process arrives  →  added to the TAIL of the ready queue
CPU becomes free     →  scheduler picks the process at the HEAD

  Ready queue (FIFO)
  HEAD                         TAIL
  [ P1 ] → [ P2 ] → [ P3 ] → [ P4 ]
     ↓
    CPU

The rules are short:

  1. Sort processes by arrival time.

  2. Give the CPU to the earliest arrival.

  3. Let it run until its burst finishes. No one can interrupt it.

  4. If no process has arrived yet when the CPU becomes free, the CPU stays idle until the next arrival.

  5. If two processes arrive at the same time, the usual tie-breaker is the lower process number (P1 before P2).

FCFS is non-preemptive. The scheduler only makes a decision when the running process finishes or blocks, never in the middle of a burst.


Example 1: All Processes Arrive Together

Three processes arrive at time 0 in the order P1, P2, P3.

Process

Arrival Time

Burst Time

P1

0

24

P2

0

3

P3

0

3

FCFS runs them in the order they arrived:

|  P1  |  P2  |  P3  |
0      24     27     30

Process

AT

BT

CT

TAT = CT - AT

WT = TAT - BT

P1

0

24

24

24

0

P2

0

3

27

27

24

P3

0

3

30

30

27

Average TAT = (24 + 27 + 30) / 3 = 81 / 3 = 27
Average WT  = (0 + 24 + 27) / 3  = 51 / 3 = 17

Same Processes, Different Arrival Order

Now suppose the two short processes happened to arrive first, in the order P2, P3, P1 (all still at time 0):

|  P2  |  P3  |  P1  |
0      3      6      30
WT(P2) = 0,  WT(P3) = 3,  WT(P1) = 6

Average WT  = (0 + 3 + 6) / 3   = 9 / 3  = 3
Average TAT = (3 + 6 + 30) / 3  = 39 / 3 = 13

The total work is the same 30 units, yet the average waiting time drops from 17 to 3. Nothing changed except the order.

Under FCFS, the average waiting time depends heavily on the order of arrival, and it can be very large when a long process arrives before short ones.

Why does this happen? When a process runs, everyone behind it waits for its full burst. A long burst at the front of the queue gets "charged" to every process behind it. A short burst at the front costs the others very little. That simple observation is the whole idea behind Shortest Job First, the topic of the next chapter.


The Convoy Effect

Picture a slow truck on a narrow single-lane road. A line of fast cars builds up behind it, and none of them can overtake. That is a convoy.

In an operating system the same thing happens with FCFS:

  • One CPU-bound process (long CPU bursts, little I/O) holds the CPU for a long time.

  • Many I/O-bound processes (short CPU bursts, lots of I/O) finish their I/O and line up in the ready queue behind it.

  • While they wait, the I/O devices sit idle, because nobody is issuing I/O requests.

  • When the CPU-bound process finally blocks for I/O, the short processes rush through the CPU quickly and all go to the I/O queue, and now the CPU sits idle.

Phase 1:  CPU busy with big job       I/O devices idle
          [BIG]  ← P2 P3 P4 P5 waiting

Phase 2:  big job does I/O            short jobs zip through CPU
          then everyone is doing I/O  CPU idle

          ... and the cycle repeats

Convoy effect: many short processes wait behind one long process, which lowers both CPU utilization and device utilization.

The convoy effect is the reason FCFS is a poor choice for interactive, time-sharing systems.


Example 2: Different Arrival Times

Most exam questions give different arrival times. Let's solve one step by step.

Process

Arrival Time

Burst Time

P1

0

4

P2

1

3

P3

2

1

P4

3

2

P5

4

5

Step-by-step trace

t = 0  : only P1 has arrived → P1 runs for 4 → finishes at 4
t = 4  : queue = P2, P3, P4, P5 (all arrived by now)
         P2 is at the head → runs for 3 → finishes at 7
t = 7  : P3 runs for 1 → finishes at 8
t = 8  : P4 runs for 2 → finishes at 10
t = 10 : P5 runs for 5 → finishes at 15
|  P1  |  P2  |  P3  |  P4  |  P5  |
0      4      7      8      10     15

Process

AT

BT

CT

TAT

WT

RT

P1

0

4

4

4

0

0

P2

1

3

7

6

3

3

P3

2

1

8

6

5

5

P4

3

2

10

7

5

5

P5

4

5

15

11

6

6

Average TAT = (4 + 6 + 6 + 7 + 11) / 5 = 34 / 5 = 6.8
Average WT  = (0 + 3 + 5 + 5 + 6) / 5  = 19 / 5 = 3.8
Throughput  = 5 processes / 15 units  = 1/3 process per unit

Notice that P3 needs only 1 unit of CPU but waits 5 units. Its turnaround time (6) is six times its burst. Short jobs suffer most under FCFS.

Also notice that WT equals RT for every process. That is always true for FCFS (and for any non-preemptive algorithm when each process has a single burst): a process waits once, then runs to completion, so its only waiting happens before its first run.


Example 3: When the CPU Goes Idle

If the CPU finishes a process and nobody has arrived yet, it simply waits. Many students forget this gap.

Process

Arrival Time

Burst Time

P1

0

3

P2

5

2

P3

6

4

|  P1  | IDLE |  P2  |  P3  |
0      3      5      7      11

P1 finishes at 3, but P2 only arrives at 5. The CPU is idle from 3 to 5. P2 then starts at 5, not at 3.

Process

AT

BT

CT

TAT

WT

P1

0

3

3

3

0

P2

5

2

7

2

0

P3

6

4

11

5

1

Average TAT = (3 + 2 + 5) / 3 = 10 / 3 ≈ 3.33
Average WT  = (0 + 0 + 1) / 3 = 1 / 3  ≈ 0.33

CPU utilization = busy time / total time = 9 / 11 ≈ 81.82%

Example 4: The Table Is Not in Arrival Order

Questions sometimes list processes out of order to test whether you really sort by arrival time.

Process

Arrival Time

Burst Time

P1

2

5

P2

0

3

P3

4

2

FCFS cares about arrival time, not the process number. P2 arrived first, so it runs first:

|  P2  |  P1  |  P3  |
0      3      8      10
P1: CT = 8,  TAT = 8 - 2  = 6, WT = 6 - 5 = 1
P2: CT = 3,  TAT = 3 - 0  = 3, WT = 3 - 3 = 0
P3: CT = 10, TAT = 10 - 4 = 6, WT = 6 - 2 = 4

Average TAT = 15 / 3 = 5
Average WT  = 5 / 3  ≈ 1.67

Adding Context-Switch Overhead

Real context switches are not free (see Process Control Block & Context Switching). Some questions say "a context switch takes 1 unit". Let's redo Example 2 with a 1-unit switch between every two processes (no switch is counted before the very first process):

|  P1  |  CS  |  P2  |  CS  |  P3  |  CS  |  P4  |  CS  |  P5  |
0      4      5      8      9      10     11     13     14     19

Process

CT

TAT

WT

P1

4

4

0

P2

8

7

4

P3

10

8

7

P4

13

10

8

P5

19

15

10

Average TAT = 44 / 5 = 8.8
Average WT  = 29 / 5 = 5.8
CPU utilization = useful work / total time = 15 / 19 ≈ 78.95%

The 4 switches cost 4 units, and every process after the first got delayed. Even so, FCFS needs as few context switches as any algorithm can (one dispatch per process), because it never preempts; only other non-preemptive algorithms such as non-preemptive SJF can match it. Round Robin, which you will meet soon, switches far more often.


FCFS in C

The program below sorts processes by arrival time, builds the Gantt chart (including idle gaps) and computes CT, TAT and WT. It uses the data from Example 2.

#include <stdio.h>

struct proc {
    char name[4];
    int at, bt;        /* arrival time, burst time        */
    int ct, tat, wt;   /* completion, turnaround, waiting */
};

int main(void) {
    struct proc p[] = {
        {"P1", 0, 4, 0, 0, 0},
        {"P2", 1, 3, 0, 0, 0},
        {"P3", 2, 1, 0, 0, 0},
        {"P4", 3, 2, 0, 0, 0},
        {"P5", 4, 5, 0, 0, 0},
    };
    int n = sizeof p / sizeof p[0];

    /* FCFS = serve in order of arrival. Stable insertion sort by
       arrival time, so equal arrivals keep their input order.     */
    for (int i = 1; i < n; i++) {
        struct proc key = p[i];
        int j = i - 1;
        while (j >= 0 && p[j].at > key.at) {
            p[j + 1] = p[j];
            j--;
        }
        p[j + 1] = key;
    }

    int time = 0;
    double total_tat = 0, total_wt = 0;

    printf("Gantt: ");
    for (int i = 0; i < n; i++) {
        if (time < p[i].at) {            /* CPU idle until next arrival */
            printf("[%d]IDLE ", time);
            time = p[i].at;
        }
        printf("[%d]%s ", time, p[i].name);
        time += p[i].bt;                 /* runs to completion */
        p[i].ct  = time;
        p[i].tat = p[i].ct - p[i].at;
        p[i].wt  = p[i].tat - p[i].bt;
        total_tat += p[i].tat;
        total_wt  += p[i].wt;
    }
    printf("[%d]\n\n", time);

    printf("Proc  AT  BT  CT  TAT  WT\n");
    for (int i = 0; i < n; i++)
        printf("%-4s %3d %3d %3d %4d %3d\n",
               p[i].name, p[i].at, p[i].bt, p[i].ct, p[i].tat, p[i].wt);

    printf("\nAverage TAT = %.2f\n", total_tat / n);
    printf("Average WT  = %.2f\n", total_wt / n);
    return 0;
}

Output:

Gantt: [0]P1 [4]P2 [7]P3 [8]P4 [10]P5 [15]

Proc  AT  BT  CT  TAT  WT
P1     0   4   4    4   0
P2     1   3   7    6   3
P3     2   1   8    6   5
P4     3   2  10    7   5
P5     4   5  15   11   6

Average TAT = 6.80
Average WT  = 3.80

The numbers match our hand calculation. Two details are worth noticing:

  • The sort is stable, so processes with the same arrival time keep their original order. That implements the "lower process number first" tie-breaker for free.

  • The if (time < p[i].at) check handles the idle CPU case from Example 3.

A real kernel does not sort an array. It keeps a linked-list queue: enqueue at the tail on arrival, dequeue from the head on dispatch. Both operations are O(1), which is why FCFS has almost zero scheduling overhead.


Properties of FCFS

Property

FCFS

Preemptive?

No

Selection rule

Earliest arrival time

Data structure

FIFO queue

Scheduling overhead

Very low, O(1) per decision

Starvation possible?

No, every process eventually reaches the head (assuming each burst finishes)

Average waiting time

Often high, depends on arrival order

Response time

Can be poor for short jobs

Suitable for

Batch systems, simple embedded loops, tie-breaking inside other algorithms

Not suitable for

Interactive and time-sharing systems

Advantages

  • Simple to understand, implement and debug.

  • Fair in the "first come" sense: no process can jump the queue.

  • No starvation.

  • Minimal overhead: few context switches, trivial bookkeeping.

  • Does not need to know burst times in advance (SJF does).

Disadvantages

  • Convoy effect: short jobs stuck behind long ones.

  • High and unpredictable average waiting time.

  • No preemption: a process stuck in a long computation (or an infinite loop) holds the CPU until it ends or blocks, which is unacceptable for interactive use.

  • Treats all processes equally, with no notion of importance or priority.


Where Is FCFS Used in Real Systems?

Pure FCFS is rarely the main CPU scheduler on a desktop or phone, but the idea appears everywhere:

  • Tie-breaking: SJF, Priority and other algorithms use arrival order when two processes are equal.

  • Round Robin is FCFS plus a time limit. If the time quantum is very large, Round Robin becomes FCFS.

  • Linux SCHED_FIFO: a real-time policy where threads of the same priority are served first-in, first-out and run until they block, yield, or a higher-priority thread arrives. So it is FCFS within one priority level.

  • Lowest queue of a multilevel scheduler: long background jobs are often served FCFS (see Multilevel Queue & Feedback Queue Scheduling).

  • Outside the CPU: printer queues, simple disk request queues (the FCFS disk scheduling algorithm in Disk Structure & Disk Scheduling), and network packet queues in routers.


Common Mistakes

  • Scheduling by process number instead of arrival time. Always sort by AT first (Example 4).

  • Forgetting idle time. If the next process has not arrived, the CPU waits. The next process starts at its arrival time, not at the previous completion time (Example 3).

  • Using CT - BT as waiting time. That is only correct when AT = 0. The general formula is WT = CT - AT - BT.

  • Thinking FCFS can preempt. It cannot. A newly arrived process always waits, even if it is tiny.

  • Saying "FCFS causes starvation". It does not. Long waits are not the same as starvation; in FCFS every process is guaranteed to run eventually.

  • Counting a context switch before the first process when the question does not say so. Read the question carefully: most count switches only between processes.


Interview Questions

Is FCFS preemptive or non-preemptive?

Non-preemptive. A process keeps the CPU until it finishes its burst or blocks.

What is the convoy effect?

Many short (often I/O-bound) processes wait behind one long CPU-bound process. The CPU and the I/O devices take turns being idle, so overall utilization drops.

Can FCFS cause starvation?

No. Every process reaches the front of the FIFO queue after a finite time, provided every burst eventually ends.

Why is the average waiting time of FCFS order-dependent?

Each process waits for the sum of the bursts ahead of it. A long burst early in the queue adds a large amount to every later process's waiting time.

Why are waiting time and response time equal in FCFS?

Because a process never gets interrupted. All its waiting happens before its first (and only) run, so the time to first response is the total waiting time.

How does FCFS relate to Round Robin?

Round Robin is FCFS with a time quantum. When the quantum is larger than every burst, Round Robin behaves exactly like FCFS.

Why is FCFS a poor choice for a time-sharing system?

Interactive users need quick responses. With FCFS, one long job can block everyone for a long time, and there is no way to take the CPU away from it.


The Main Idea

FCFS runs processes in the order they arrive, using a simple FIFO ready queue, and never interrupts a running process.

Sort by arrival time
      ↓
Run the head of the queue to completion
      ↓
CPU idle if nobody has arrived
      ↓
Repeat

Key facts to remember:

Type          → Non-preemptive
Starvation    → No
Overhead      → Lowest (one switch per process)
Weakness      → Convoy effect, high average waiting time
WT            → equals RT for every process

FCFS is fair and simple, but a single long job at the front of the queue makes everyone else wait.

In the next chapter, SJF & SRTF Scheduling, we fix the convoy problem by letting the shortest job go first, and we will prove that this gives the lowest possible average waiting time.