Operating System

FCFS Scheduling : Explained

Abstract

  • In FCFS, the process that requires CPU first is allocated CPU first. 
  • It is a non-preemptive scheduling algorithm.

Scope

This article talks about FCFS scheduling in detail.

Definition

FCFS (First-Come-First-Serve) is the simplest scheduling algorithm. The basic idea is the process that comes first is scheduled first. It follows the principle of FIFO (First-in-First-Out). It is a non-preemptive algorithm.

Let’s look at this problem

           PROCESS          ARRIVAL TIME          BURST TIME
              P0                  0                    10
              P1                  1                    6
              P2                  3                    2
              P3                  5                    4

Only the processes in the ready queue are to be considered. Since there is no preemption, once the job starts it is going to run until its completion. Now let’s look at the Gantt chart:

Now let’s compute each type of time using concepts and formulae.

PROCESSARRIVAL TIMEBURST TIMECOMPLETION         TIMETURN AROUND TIMEWAITING TIME
    P0        0        10          10        10          0
    P1        1        6          16        15          9
    P2        3        2          18        15          13
    P3        5        4          22        17          13

*Turnaround time = Completion time – Arrival time

*Waiting time = Turnaround time – Burst time 

So average turnaround time is = (10+15+15+17)/4  = 57/4 = 14.25

Average waiting time = (0+9+13+13)/4 = 35/4 = 8.75

Note :

  1. The lower the average turnaround time, the better it is.
  2. The lower the average waiting time, the better it is.
  3. The higher the CPU utilization, the better it is.
  4. The higher the throughput, the better it is
  5. The average waiting time under FCFS policy is generally not minimal.

Some important points :

  1. It is very simple and easy to implement.
  2. It is non-preemptive. Once you assign a process to a processor you cannot take the processor back.
  3. It results in a convoy effect. Suppose there are many IO-bound processes and one CPU-bound process. The IO-bound process has to wait for the CPU-bound process when the CPU-bound process acquires the CPU. This slows down the operating system. Each process should get a CPU for an equal amount of time but this algorithm does not follow this principle. 
  4. The average waiting time is not optimal.

Summary

  • FCFS is the simplest scheduling algorithm. The implementation of the FCFS policy is easily managed with the FIFO queue.
  • It is a non-preemptive scheduling algorithm. It results in poor performance and low throughput.

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article