Operating System - FCFS Scheduling Algorithm
First Come First Serve (FCFS) is the simplest CPU Scheduling algorithm.
What is FCFS Algorithm?
When a process requests the CPU first before other processes, then the CPU time will be first provided to that process.
That is, process will get the CPU time based on where it stands in the queue of processes waiting for CPU to execute it.
This algorithm uses the FIFO queue for ready queue management.
Algorithm is the simplest to write and has lesser complexity.
FCFS - Scheduling Type
This algorithm follows the non-preemptive scheduling.
FCFS - For Processes Arriving At Almost Same Time
Let us see how this works. Consider the set of processes that arrive at the same time 0 and CPU-burst time in millisecond as shown below:
| Process | CPU-Burst Time |
|---|---|
| P1 | 20 |
| P2 | 4 |
| P3 | 3 |
If the processes P1, P2, P3 arrive in order with negligible time difference, then the processes will be executed as shown below.
| P1 | ||
|---|---|---|
| 20 | P2 | |
| 4 | P3 | |
| 3 | ||
Waiting time for each process will be the time taken from its arrival on the process queue until it is processed. It is calculated by the sum of time taken by all processes before it minus the time at which it arrived
Process | Arrival Time | CPU Burst | Waiting Time | Turn around time |
|---|---|---|---|---|
| P1 | 0 | 20 | 0 | 20 |
| P2 | 0 | 4 | 20 | 24 |
| P3 | 0 | 3 | 24 | 27 |
FCFS - For Processes Arriving At Different Times
Suppose, the processes arrive in the different arrival time, then these processes will be served in FCFS order.
| Process | Arrival Time | CPU-Burst Time |
|---|---|---|
| P1 | 0 | 20 |
| P2 | 1 | 4 |
| P3 | 3 | 3 |
Processes will be executed as shown below
| P1 | ||
|---|---|---|
| 20 | P2 | |
| 4 | P3 | |
| 3 | ||
The waiting time, finish time and turn around time for each process will be as shown below:
Process | Arrival Time | CPU Burst | Start Time | Waiting Time = Start Time - Arrival Time | Finish Time | Turnaround time= Finish Time - Arrival Time |
|---|---|---|---|---|---|---|
| P1 | 0 | 20 | 0 | 0-0=0 | 20 | 20-0=20 |
| P2 | 1 | 4 | 20 | 20-1=19 | 24 | 24-1=23 |
| P3 | 3 | 3 | 24 | 24-3=21 | 27 | 27-3=24 |
Average Waiting Time = (0+19+21)/3 = 16.333 ms
Average Turnaround Time = (20+23+24)/3 = 22.333 ms
FCFS - Advantages
- There is no issue in switching context between processes. Once one process completes or terminates, next one is automatically chosen
- There is no need to maintain priority of processes.
- As long processes get terminated one by one, there is lesser risk of process hanging without being run for an unknown time. A process in queue, will always run provided its previous processes, were terminated
FCFS - Disadvantages
- Priorities cannot be set. Hence, a higher priority process that starts late wonuld still have to wait for CPU time just like other processes
- If a process pauses without terminating, no other process would run
FCFS - Performance of Algorithm
For the OS implementing this algorithm, the average waiting time for a process to get CPU time is quite long.
Performance of this algorithm is very low. Hence, it is rarely used in Modern Operating Systems.
<<Previous - CPU Scheduling Algorithms
First Come First Serve - FCFS example put in a different way
