First Come First Served (FCFS) is the simplest CPU scheduling algorithm used by an operating system — processes are executed strictly in the order they arrive, with no interruption once a process starts running. It works exactly like a queue at a ticket counter: whoever arrives first gets served first, and everyone else waits their turn.
FCFS is non-preemptive, easy to implement, and fair in the sense that no process can jump the queue — but it can cause long average wait times when a short process gets stuck behind a long one (the “convoy effect”). This page covers the algorithm, a complete C program, a worked trace, and its complexity.
How FCFS Works
- Sort all processes by arrival time.
- Pick the process with the earliest arrival time that hasn’t run yet.
- Run it to completion — FCFS is non-preemptive, so once started, a process is never interrupted.
- Compute its completion time, turnaround time (completion − arrival), and waiting time (turnaround − burst).
- Move the CPU clock forward and repeat for the next process in arrival order.
Step-by-step trace
Three processes arrive at different times with different burst (execution) times:
Process Arrival Burst P1 0 5 P2 1 3 P3 2 8 Clock = 0 P1 arrives at 0, CPU is free → runs 0 to 5. Completion = 5 P2 arrived at 1, waits until P1 finishes → runs 5 to 8. Completion = 8 P3 arrived at 2, waits until P2 finishes → runs 8 to 16. Completion = 16
C Program for FCFS Scheduling
/* FCFS CPU Scheduling in C
* Compile: gcc -ansi -Wall -Wextra fcfs.c -o fcfs */
#include <stdio.h>
#define MAX 20
struct Process {
int pid;
int arrival;
int burst;
int completion;
int turnaround;
int waiting;
};
void sort_by_arrival(struct Process p[], int n)
{
int i, j;
struct Process temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (p[j].arrival > p[j + 1].arrival) {
temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;
}
}
}
}
int main(void)
{
struct Process p[MAX];
int n, i, clock_time;
double total_wt = 0.0, total_tat = 0.0;
printf("Enter number of processes: ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
p[i].pid = i + 1;
printf("Process %d - Arrival Time: ", p[i].pid);
scanf("%d", &p[i].arrival);
printf("Process %d - Burst Time: ", p[i].pid);
scanf("%d", &p[i].burst);
}
sort_by_arrival(p, n);
clock_time = 0;
for (i = 0; i < n; i++) {
if (clock_time < p[i].arrival)
clock_time = p[i].arrival;
clock_time += p[i].burst;
p[i].completion = clock_time;
p[i].turnaround = p[i].completion - p[i].arrival;
p[i].waiting = p[i].turnaround - p[i].burst;
total_wt += p[i].waiting;
total_tat += p[i].turnaround;
}
printf("\nPID\tArrival\tBurst\tCompletion\tTurnaround\tWaiting\n");
for (i = 0; i < n; i++) {
printf("%d\t%d\t%d\t%d\t\t%d\t\t%d\n",
p[i].pid, p[i].arrival, p[i].burst,
p[i].completion, p[i].turnaround, p[i].waiting);
}
printf("\nAverage Waiting Time = %.2f\n", total_wt / n);
printf("Average Turnaround Time = %.2f\n", total_tat / n);
return 0;
}
How to Compile and Run
gcc -ansi -Wall -Wextra fcfs.c -o fcfs ./fcfs
Sample Input and Output — Test 1
Enter number of processes: 3 Process 1 - Arrival Time: 0 Process 1 - Burst Time: 5 Process 2 - Arrival Time: 1 Process 2 - Burst Time: 3 Process 3 - Arrival Time: 2 Process 3 - Burst Time: 8 PID Arrival Burst Completion Turnaround Waiting 1 0 5 5 5 0 2 1 3 8 7 4 3 2 8 16 14 6 Average Waiting Time = 3.33 Average Turnaround Time = 8.67
Sample Input and Output — Test 2 (unsorted input)
Processes are entered out of arrival order to confirm the sort step works correctly:
Enter number of processes: 3 Process 1 - Arrival Time: 2 Process 1 - Burst Time: 4 Process 2 - Arrival Time: 0 Process 2 - Burst Time: 3 Process 3 - Arrival Time: 4 Process 3 - Burst Time: 2 PID Arrival Burst Completion Turnaround Waiting 2 0 3 3 3 0 1 2 4 7 5 1 3 4 2 9 5 3 Average Waiting Time = 1.33 Average Turnaround Time = 4.33
Code Explanation
- sort_by_arrival() — a simple bubble sort that reorders processes by arrival time. This is essential: FCFS is defined by arrival order, not input order, so process 1 in your input might not be the first to run.
- clock_time — models the CPU’s current time. If the next process hasn’t arrived yet when the CPU goes idle, the clock jumps forward to that process’s arrival time (
if (clock_time < p[i].arrival)) instead of running at time 0. - waiting = turnaround − burst — waiting time is how long a process sat in the ready queue doing nothing, which is turnaround time minus the time it actually spent running.
- Edge case — if two processes arrive at the same time, the bubble sort here is stable, so they keep their original relative (PID) order, matching standard FCFS tie-breaking.
Time and Space Complexity
| Step | Time | Space |
|---|---|---|
| Sorting by arrival time | O(n²) (bubble sort) | O(1) extra |
| Computing completion/turnaround/waiting | O(n) | O(n) for process array |
| Overall | O(n²) | O(n) |
The O(n²) cost comes entirely from the bubble sort; swapping it for a faster sort (e.g. qsort) brings the whole algorithm down to O(n log n), which matters once n is large.
Advantages and Disadvantages of FCFS
| Advantages | Disadvantages |
|---|---|
| Simple to understand and implement | Convoy effect — a long process delays every process behind it |
| No starvation — every process eventually runs | High average waiting time compared to SJF or Round Robin |
| Fair in arrival order, no priority tricks | Not suitable for interactive or time-sharing systems |
Related Programs
- Round Robin CPU Scheduling in C
- SJF (Shortest Job First) Scheduling in C
- Priority Queue in C
- Structures in C – Complete Guide
- Dining Philosophers Problem in C
Recommended Books
- The C Programming Language – Kernighan & Ritchie (India) | Amazon.com
- C Programming: A Modern Approach – K.N. King (India) | Amazon.com
Practice OS scheduling and C fundamentals with the C Programming Quiz App — 500+ MCQs covering scheduling, pointers, sorting, and more.
Download on Google Play →