FCFS Scheduling Algorithm in Operating System (OS)

April 18, 2021

First Come First Served Scheduling Algorithm in Operating System

This is the most basic algorithm in Operating System, as the name suggests, first come first serve (FCFS) the process which enters the system first gets the CPU time first.

Consider the following scenario –

Lets say you’re waiting at a railway station’s ticket counter at the front of the queue the person who arrived first will be given chance to buy the ticket, and you will have to wait for your turn until all the people in front of you in the queue or those who have arrived earlier have bought tickets.

These are the traits of FCFS algorithm –

It is parallel to how FIFO in stack is
Process which arrives firsts gets CPU time first
It is a non preemptive type of algorithm

Let us try to understand FCFS Scheduling with the help of an example –

Note – If order and arrival time is not given then consider the order as is and arrival time to be 0 for all the processes.

Process	Burst Time	Arrival Order
P1	12	1
P2	7	2
P3	2	3
P4	5	4

Turn Around Time = Completion Time – Arrival Time
Waiting Time = Turnaround time – Burst Time

Lets make a gantt Chart for this first.

Waiting time –

P1 waiting time – 0ms
P2 waiting time – 12ms
P3 waiting time – 19ms
P4 waiting time – 21ms

Thus, average waiting time – (0 + 12 + 19 + 21)/4 = 13ms

Turn around time – Time when process entered the system and when its out of the system

P1 turn around time – (12 – 0) ms
P2 turn around time – (19 – 0) ms
P3 turn around time – (21 – 0) ms
P4 turn around time – (26 – 0) ms

Average turn around time (12 + 19 + 21 + 26)/4 = 19.5 ms

Disadvantages of FCFS Algorithm

Since, its a non preemptive algorithm thus, there is no intelligence applied and no priority can be given to processes.
If critical system process arrives it may have to wait for a process like calculator.
Waiting time may get too high, along with the turn around time.
Causes convoy effect

What is convoy effect?

FCFS may suffer from the convoy effect if the burst time of the first job is the highest among all. As in the real life, if a convoy is passing through the road then the other persons may get blocked until it passes completely. This can be simulated in the Operating System also.

If the CPU gets the processes of the higher burst time at the front end of the ready queue then the processes of lower burst time may get blocked which means they may never get the CPU if the job in the execution has a very high burst time. This is called convoy effect or starvation.

Let us take one more example a little more complicated.

In the previous example all the processes had arrived at the same time however, in a real time environment this is hardly the case.

Process	Burst Time	Arrival Order	Arrival Time
P1	5	1	0
P2	9	2	4
P3	4	3	6
P4	8	4	13

In this case the Gantt Chart looks like

The 2 seconds in the start can be avoided as the system only starts at 2 ms when the first process arrives.

Here have close watch on the arrival time for each process –

arrival time –

P1 arrival time – 0 ms
P2 arrival time – 4 ms
P3 arrival time – 6 ms
P4 arrival time – 13 ms

Waiting time –

P1 waiting time – 0 ms
P2 waiting time – (5 – 4) = 1 ms
P3 waiting time – (14 – 6) = 8 ms
P4 waiting time – (18 – 13) = 5 ms

Thus, average waiting time – (0 + 1 + 8 + 5)/4 = 3.50ms

Turn Around time –

P1 turn around time – 5 ms
P2 turn around time – (14 – 4) = 10 ms
P3 turn around time – (18 – 6) = 12 ms
P4 turn around time – (26 – 13) = 13 ms

Thus, average Turn Around time – (5 + 10 + 12 + 13)/4 = 12.5 ms

FCFS Scheduling Algorithm in Operating System (OS)

First Come First Served Scheduling Algorithm in Operating System

Disadvantages of FCFS Algorithm

Read More