In this tutorial, we will learn about first come first serve scheduling (FCFS) algorithm in operating system. We have already learnt about basics terms, formulas of CPU Scheduling in previous post.

As the name suggests, the process which comes first in the ready queue will be executed first, in first come first serve scheduling algorithm. FCFS is a non-preemptive scheduling. So, when the first process completes its execution, then, next process will be allocated to CPU. Its implementation is based on FIFO queue data structure.

In simple words, the process which requests the CPU first will be allocated to CPU first. It is easier to understand and implement comparing to any other scheduling algorithms. The perfect real life example of FCFS scheduling is queue at bank counter for money withdraw.

Let us take an example to understand this:

Assume we have 4 processes with process id, burst time and arrival time given below –

Now, we will calculate average waiting time, turn around time for each process.

Solution –

We can represent the processes’s execution using GANTT chart as shown below –

Gantt Chart FCFS Example

Explanation –
Arrival time of all processes is 0. So, all processes will be present in ready queue ( in order P1, P2, P3, P4).
At Arrival time = 0, P1 process is picked from the ready queue. So, P1 will be executed first. It will take 2 unit time for complete execution.
After completion of P1 process, P2 will be executed. It takes 1 unit time for complete execution. The completion time for P2 will be 3 ( = 2+1).
Now, P3 will be executed. It will take 6 unit time. So, completion time of P3 is 9 ( = 3 + 6).
Now, P4 will be executed for 5 unit time. So, completion time for P4 is 14 ( = 9 + 5).

Now, let’s calculate turnaround time and waiting time.

Turnaround time = (Completion time – Arrival time)
P1 = 2-0 = 2,
P2 = 3-0 = 3,
P3 = 6-0 = 6,
P4 = 5-0 = 5

Waiting time = (Turnaround time – Burst time)
P1 = 2-2 = 0,
P2 = 3-1 = 2,
P3 = 9-6 = 3,
P4 = 14 – 5 = 9

Average waiting time = (Total waiting time) / (number of processes) = (0+2+3+9) / 4 = 14/4 = 3.25 ms

Disadvantages of First Come First Serve (FCFS)

– In FCFS, Average waiting time is high which makes it poor in performance.
– It causes convoy effect.

Convoy Effect in FCFS

When a process with high burst time arrives first, it takes lot of time to finish due to which all the other processes will be blocked. This is called convoy effect in operating system. It is the disadvantage of FCFS scheduling algorithm.

A real life example of convoy effect is a big truck passing through the road because of this small vehicle following it gets blocked.

Convoy Effect Example

Example to Demonstrate Convoy Effect

Let’s assume we have three processes P1, P2 and P3 with burst time and arrival time as shown below

Now, we will calculate average waiting time for above processes.

Solution –
You can represent the above scenarios using GANTT Chart as shown below –

FCFS Example

Here, P1 process is executed first. All other process can get access to CPU only after it’s completion. Now, P1 process has high burst time. So, Processes P2 and P3 have to wait for longer period to get access to CPU. So, P2, P3 process suffers from starvation.

P1 gets access to CPU first. So, waiting time is 0.
Then, P2 waits for 40 unit of time to get access to CPU.
Then, P3 waits for 42 unit of time to get access to CPU.

So, Average waiting time = (0 + 40 + 42) / 3 = (82 / 3) = 27.333 unit of time.

Can you calculate average waiting time if either process P2 or P3 gets access to CPU first?

It’s definitely less than what we got in earlier case.

In first come first serve (FCFS) scheduling, we can see that the average waiting time will be very high.

So, the effect caused by FCFS scheduling in which other processes suffers from starvation due to high burst time of one process is called convoy effect.

In this tutorial, we have studied about first come first Serve (FCFS) algorithm and it’s convoy effect. In the next tutorial, we will study about round robin scheduling algorithm.