Today we are going to look at the various scheduling algorithms in Operating Systems.

Different Scheduling Algorithms in Operating Systems:

In the previous section we learned about the queues and their types. Also we discussed the two state process model and three different types of schedulers including long-term, short-term and medium-term schedulers. In the end context switching is covered with respect to scheduling.

Process Scheduler:

On the base of particular scheduling algorithms, different processes are assigned to CPU by process scheduler. Following are the six popular scheduling algorithms which will be discussed in this chapter,

  • First-Come, First-Served (FCFS) Scheduling
  • Shortest-Job-Next (SJN) Scheduling
  • Priority Scheduling
  • Shortest Remaining Time
  • Round Robin(RR) Scheduling
  • Multiple-Level Queues Scheduling

Now it is important to mention at this point that the above mentioned six scheduling algorithms in operating systems are divided into two main categories/types:

  • Preemptive Algorithms
  • Non-Preemptive Algorithms

Preemptive Algorithms:

This algorithms work on the base of priority scheduling. A high priority process entering into ready state can snatch control from a low priority process that was already in execution.

Non-Preemptive Algorithms:

In these algorithms, we the system cannot take out a process from its running state until or unless it completes its allotted time in that state, independent of low or high priority process residing in the ready state.


First Come First Serve (FCFS):

  • The job which comes first is served first and all the jobs are done in this manner.
  • It is a non-preemptive, pre-emptive scheduling algorithm.
  • Implementing and understanding FCFS is easy.
  • FCFS works on FIFO (First in First out) technique.
  • Average wait time is large so performance is poor.

Waiting time of each process is as follows:

ProcessWait Time : Service Time – Arrival Time
P00 – 0 = 0
P15 – 1 = 4
P28 – 2 = 6
P316 – 3 = 13

 

 


 

Shortest Job Next:

  • Shortest Job First (SJF) is another name of SJN.
  • It is a non-preemptive, pre-emptive scheduling algorithm.
  • Reduces the Waiting time for different processes.
  • In batch systems, we already know the CPU time so Shortest Job First (SJF) is easy to implement.
  • Implementation is impossible in systems in which required CPU time is unknown e.g. interactive systems.
  • The processor must know in advance the amount of time a process will take for it’s execution.

Waiting time of each process is as follows,

ProcessWait Time : Service Time – Arrival Time
P03 – 0 = 3
P10 – 0 = 0
P216 – 2 = 14
P38 – 3 = 5

Average Wait Time: (3+0+14+5) / 4 = 5.50


 

Priority Based Scheduling:

  • In batch systems priority scheduling is the most common algorithm and it is non-preemptive.
  • It assigns priorities to each process. Priority Based Scheduling then starts execution from Highest priority process and gradually move to lower priority processes.
  • We use FCFS to execute those processes which have same priority.
  • Decision of priority can be taken on the following basis:
    • Memory requirement
    • Time requirement
    • Other resource requirement

Waiting time of each process is as follows:

ProcessWait Time : Service Time – Arrival Time
P09 – 0 = 9
P16 – 1 = 5
P214 – 2 = 12
P30 – 0 = 0

Average Wait Time: (9+5+12+0) / 4 = 6.5


 

Shortest Remaining Time:

  1. The preemptive version of shortest job first (SJN) algorithm is actually shortest remaining time (SRT).
  2. Shortest Remaining Time always selects a job with the smallest time remaining till it’s completion.
  3. In interactive systems CPU time is unknown, so SRT is impossible to implement.
  4. Batch environments use SRT because short jobs require preference.

 

Round Robin Scheduling:

  1. It resides in the category of preemptive process scheduling algorithms.
  2. It provides a fixed time to every process in which the process has to complete its execution. This time is called Quantum.
  3. Once a process has run for a given time period, Round Robin preempts this process and allows some other process to execute for a given time period.
  4. Round Robin saves the states of the preempted processes with the help of context switching.

 

Waiting time of each process is as follows:

ProcessWait Time : Service Time – Arrival Time
P0(0 – 0) + (12 – 3) = 9
P1(3 – 1) = 2
P2(6 – 2) + (14 – 9) + (20 – 17) = 12
P3(9 – 3) + (17 – 12) = 11

Average Wait Time: (9+2+12+11) / 4 = 8.5


 

Multiple-Level Queues Scheduling:

Multiple-level queues are dependent scheduling algorithms. Multi-level Queue Scheduling uses other existing algorithms by grouping and scheduling jobs with common characteristics.

  • It maintains multiple queues for processes with multiple characteristics.
  • Each queue maintains a specific scheduling algorithm.
  • A certain priority is then given to each queue.

Example of Multi-Level Queue Scheduling:

For example, say there are two types of jobs/processes waiting for their execution. If there are CPU-bound jobs and I/O bound jobs then multi-level queue schedules both jobs in different queues. The Process Scheduler then alternately selects jobs from each queue and assigns them to the CPU based on the algorithm assigned to the queue.


And that is all about the different types of scheduling algorithms in Operating Systems. We hope you liked our article.