FCFS Scheduling in OS
Introduction
FCFS (First-Come, First-Served) is the simplest CPU scheduling algorithm, where processes are executed in the order they arrive – just like a queue at a grocery store! 🛒
- Non-preemptive: Once a process starts, it runs to completion.
- Fair but inefficient: Long processes can block shorter ones (called the Convoy Effect).
- Criteria : Arrival Time
Key Characteristics
- Processes are served in arrival time order.
- Uses a FIFO (First-In, First-Out) queue.
- Easy to implement but often results in poor average waiting time.
Real-Life Analogy
Imagine three customers arriving at a bank:
- Customer A arrives first and takes 10 minutes.
- Customer B arrives next but waits until A finishes.
- Customer C arrives last and waits for both A and B.
This is exactly how FCFS works!
Problem Statement
Calculate the average waiting time and average turnaround time for three processes:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
Step 1: Determine Execution Order
Processes execute in arrival order: P1 → P2 → P3.
Step 2: Calculate Completion Times
P1:
- Starts at 0 (no waiting).
- Completes at 0 + 5 = 5.
P2:
- Arrives at 1 but waits until P1 finishes at 5.
- Starts at 5.
- Completes at 5 + 3 = 8.
P3:
- Arrives at 2 but waits until P2 finishes at 8.
- Starts at 8.
- Completes at 8 + 8 = 16.
Step 3: Calculate Turnaround Time
\[ \text{Turnaround Time} = \text{Completion Time} - \text{Arrival Time} \]
| Process | Turnaround Time |
|---|---|
| P1 | 5 - 0 = 5 |
| P2 | 8 - 1 = 7 |
| P3 | 16 - 2 = 14 |
Average Turnaround Time = \( \frac{5 + 7 + 14}{3} = 8.67 \)
Step 4: Calculate Waiting Time
\[ \text{Waiting Time} = \text{Turnaround Time} - \text{Burst Time} \]
| Process | Waiting Time |
|---|---|
| P1 | 5 - 5 = 0 |
| P2 | 7 - 3 = 4 |
| P3 | 14 - 8 = 6 |
Average Waiting Time = \( \frac{0 + 4 + 6}{3} = 3.33 \)
Final Timeline
Figure 1: Gantt Chart for FCFS Scheduling
FCFS C Program: Implementation
Below is a complete C program that simulates First-Come, First-Served (FCFS) scheduling.
#include <stdio.h>
struct Process {
int pid;
int arrival;
int burst;
int start;
int waiting;
int turnaround;
int completion;
};
void sortByArrival(struct Process p[], int n) {
struct Process temp;
for (int i = 0; i < n-1; i++) {
for (int 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;
}
}
}
}
void calculateTimes(struct Process p[], int n) {
int currentTime = 0;
for (int i = 0; i < n; i++) {
if (currentTime < p[i].arrival)
currentTime = p[i].arrival; // CPU is idle
p[i].start = currentTime;
p[i].waiting = p[i].start - p[i].arrival;
p[i].completion = p[i].start + p[i].burst;
p[i].turnaround = p[i].completion - p[i].arrival;
currentTime = p[i].completion;
}
}
void printTable(struct Process p[], int n) {
float total_waiting = 0, total_turnaround = 0;
printf("\n%-5s %-10s %-10s %-10s %-15s %-15s %-15s\n",
"PID", "Arrival", "Burst", "Start", "Waiting Time", "Turnaround Time", "Completion Time");
for (int i = 0; i < n; i++) {
printf("P%-4d %-10d %-10d %-10d %-15d %-15d %-15d\n",
p[i].pid, p[i].arrival, p[i].burst, p[i].start,
p[i].waiting, p[i].turnaround, p[i].completion);
total_waiting += p[i].waiting;
total_turnaround += p[i].turnaround;
}
printf("\nAverage Waiting Time = %.2f", total_waiting / n);
printf("\nAverage Turnaround Time = %.2f\n", total_turnaround / n);
}
void printGanttChart(struct Process p[], int n) {
printf("\nGantt Chart:\n ");
// Top bar
for (int i = 0; i < n; i++) {
printf("---------");
}
printf("-\n|");
// Process names
for (int i = 0; i < n; i++) {
printf(" P%-2d |", p[i].pid);
}
// Bottom bar
printf("\n ");
for (int i = 0; i < n; i++) {
printf("---------");
}
printf("-\n");
// Time values
printf("0");
for (int i = 0; i < n; i++) {
printf(" %2d", p[i].completion);
}
printf("\n");
}
int main() {
int n;
printf("Enter number of processes: ");
scanf("%d", &n);
struct Process p[n];
for (int i = 0; i < n; i++) {
p[i].pid = i + 1;
printf("Enter Arrival and Burst Time for P%d: ", p[i].pid);
scanf("%d %d", &p[i].arrival, &p[i].burst);
}
sortByArrival(p, n);
calculateTimes(p, n);
printTable(p, n);
printGanttChart(p, n);
return 0;
}Sample Output
Let’s run the program with the following input:
Enter number of processes: 3
Enter Arrival and Burst Time for P1: 0 5
Enter Arrival and Burst Time for P2: 1 3
Enter Arrival and Burst Time for P3: 2 8And the output will be:
PID Arrival Burst Start Waiting Time Turnaround Time Completion Time
P1 0 5 0 0 5 5
P2 1 3 5 4 7 8
P3 2 8 8 6 14 16
Average Waiting Time = 3.33
Average Turnaround Time = 8.67
Gantt Chart:
---------------------------------
| P1 | P2 | P3 |
---------------------------------
0 5 8 16Pros & Cons of FCFS
Advantages
- Simple to implement (no complex logic).
- No starvation: Every process gets a fair chance.
- Predictable execution order.
Disadvantages
- Convoy Effect: Short processes stuck behind long ones.
- Poor performance for short processes.
- High average waiting time in mixed workloads.
When to Use FCFS
- Batch processing systems (e.g., payroll).
- Situations where simplicity is prioritized over efficiency.
FAQ
Q: Is FCFS preemptive?
No! Once a process starts, it runs to completion.
Q: What if two processes have the same arrival time?
They are scheduled in the order they were submitted (e.g., P1 before P2 if entered first).
Q: Why is the average waiting time high here?
Because P3 (burst time 8) had to wait for P1 and P2 to finish.
Conclusion
FCFS is like a strict queue manager:
- Fair: First come, first served.
- Inefficient: Not ideal for systems with mixed process sizes.