Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

FCFS Scheduling Algorithm in Operating System (OS)

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.

ProcessBurst TimeArrival OrderArrival Time
P11210
P2720
P3230
P4540
  1. Turn Around Time = Completion Time – Arrival Time   
  2.     Waiting Time = Turnaround time – Burst Time 

Lets make a gantt Chart for this first.

FCFS Scheduling in Operating System

Waiting time – 

  1. P1 waiting time – 0ms
  2. P2 waiting time – 12ms
  3. P3 waiting time – 19ms
  4. 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 

  1. P1 turn around time – (12 – 0) ms
  2. P2 turn around time – (19 – 0) ms
  3. P3 turn around time – (21 – 0) ms
  4. 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.

ProcessBurst TimeArrival OrderArrival Time
P1510
P2924
P3436
P48413

In this case the Gantt Chart looks like

first come first serve algorithm in Operating System

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 – 

  1. P1 arrival time – 0 ms
  2. P2 arrival time – 4 ms
  3. P3 arrival time – 6 ms
  4. P4 arrival time – 13 ms

Waiting time –

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

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

Turn Around time –

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

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