Scheduling Algorithms

There are various algorithms which are used by the Operating System to schedule the processes on the processor in an efficient way. 

The Purpose of a Scheduling algorithm

 1. Maximum CPU utilization

 2. Fare allocation of CPU  

3. Maximum throughput 

4. Minimum turnaround time 

5. Minimum waiting time

 6. Minimum response time

 There are the following algorithms which can be used to schedule the jobs. 

1. First Come First Serve

 It is the simplest algorithm to implement. The process with the minimal arrival time will get the CPU first. The lesser the arrival time, the sooner will the process gets the CPU. It is the non-preemptive type of scheduling.

 2. Round Robin

 In the Round Robin scheduling algorithm, the OS defines a time quantum (slice). All the processes will get executed in the cyclic way. Each of the process will get the CPU for a small amount of time (called time quantum) and then get back to the ready queue to wait for its next turn. It is a preemptive type of scheduling. 

3. Shortest Job First 

The job with the shortest burst time will get the CPU first. The lesser the burst time, the sooner will the process get the CPU. It is the non-preemptive type of scheduling. 

4. Shortest remaining time first 

It is the preemptive form of SJF. In this algorithm, the OS schedules the Job according to the remaining time of the execution.

5. Priority based scheduling 

In this algorithm, the priority will be assigned to each of the processes. The higher the priority, the sooner will the process get the CPU. If the priority of the two processes is same then they will be scheduled according to their arrival time. 

6. Highest Response Ratio Next

 In this scheduling Algorithm, the process with highest response ratio will be scheduled next. This reduces the starvation in the system.

FCFS Scheduling

 First come first serve (FCFS) scheduling algorithm simply schedules the jobs according to their arrival time. The job which comes first in the ready queue will get the CPU first. The lesser the arrival time of the job, the sooner will the job get the CPU. FCFS scheduling may cause the problem of starvation if the burst time of the first process is the longest among all the jobs.

Advantages of FCFS 

o Simple

 o Easy 

 o First come, First serv

Disadvantages of FCFS 

1. The scheduling method is non preemptive, the process will run to the completion. 

2. Due to the non-preemptive nature of the algorithm, the problem of starvation may occur. 

3. Although it is easy to implement, but it is poor in performance since the average waiting time is higher as compare to other scheduling algorithms.


Example Let's take an example of The FCFS scheduling algorithm.

 In the Following schedule, there are 5 processes with process ID P0, P1, P2, P3 and P4. P0 arrives at time 0, P1 at time 1, P2 at time 2, P3 arrives at time 3 and Process P4 arrives at time 4 in the ready queue. The processes and their respective Arrival and Burst time are given in the following table.

 The Turnaround time and the waiting time are calculated by using the following formula.

 1. Turn Around Time = Completion Time - Arrival Time 

2. Waiting Time = Turnaround time - Burst Time 

The average waiting Time is determined by summing the respective waiting time of all the processes and divided the sum by the total number of processes.