Scheduling Algorithms in Operating Systems - Part 1 - First Come First Serve (FCFS)

Like humans, the operating system needs to plan its activities. These activities are the various processes that need to be executed by the OS. The OS needs to schedule all its processes properly to ensure that they get executed without any problems and in minimal time.

For this purpose, there are many scheduling algorithms like the First Come First Serve (FCFS) algorithm, Shortest Job First (SJF) algorithm, etc. We will be discussing these algorithms in detail but before that, we need to understand some terms.

1. Arrival Time: The time at which the process arrives in the processor for execution.

2. Waiting Time: The time for which a process has to wait before it starts executing. A process may have to wait if some other process is being executed (in a uniprocessor environment) or when the resources required by the process are not available, etc. It is calculated as :

   Waiting time = Completion Time- Arrival Time- Service Time

   1. Service Time/ Burst time: The time required by the process to complete its execution.
   2. Turnaround Time: The interval between the time at which the process starts executing and the arrival time of the process. It is calculated using the formula: > Turnaround Time = Service Time + Waiting Time

Now, let us have a look at the First Come First serve scheduling algorithm :

First Come First Serve (Also called FCFS or FIFO or non-preemptive) algorithm :

In this algorithm, the processes are executed in the order they enter the processor.

Consider the example,

Here, there are 5 processes A, B, C, D, E with their arrival time and service time.

From the given arrival times, we can see that process A is the first one to arrive at 0ms (milliseconds). So that process starts executing.

This is the execution queue. Process A starts executing at 0 and continues till 3 i.e. executes completely. Meanwhile, process B arrives at 2ms and is added to the waiting queue. Note: The value in the brackets ‘()’ denotes the service time/burst time required by the process.

Next, process B is removed from the waiting queue and starts executing:

Process B executes till 9ms. Meanwhile processes C, D, E arrive and are added to the waiting queue.

C being first in the queue starts executing next.

It executes for 4ms. No new process is added to the waiting queue. The next process to be executed is D.

D executes for 5ms from 13 through 18. After that E is the only process left to be executed. So, E executes next.

As you can see all the processes are successfully executed. Now let us calculate the waiting time and the turnaround time using the formulae mentioned above.

These are the results obtained:

So, this is the FCFS algorithm.

Advantages :

It is very simple.

Disadvantages :

1. Favors CPU bound processes over I/O bound processes.

2. If a longer process starts executing, the shorter processes have to wait for long which leads to the starvation of the shorter processes.

To overcome this disadvantage, we have the Shortest Job First algorithm.

Hope this helps you!

Have a nice day!!