Scheduling Algorithms in Operating System

Scheduling algorithms schedule processes on the processor in an efficient and effective manner. This scheduling is done by a Process Scheduler. It maximizes CPU utilization by increasing throughput.

Following are the popular process scheduling algorithms about which we are going to talk in this chapter:
1. First-Come, First-Served (FCFS) Scheduling
2. Shortest-Job-Next (SJN) Scheduling
3. Priority Scheduling
4. Shortest Remaining Time
5. Round Robin(RR) Scheduling
6. Multiple-Level Queues Scheduling
7. Multilevel Feedback Queues Scheduling
8. Highest Response Ratio Next

1. First-Come, First-Served (FCFS)

In this scheduling algorithm, jobs are executed on a first come, first serve basis irrespective of burst time or priority. It is both a preemptive and non-preemptive scheduling algorithm. It is based on the First In First Out (FIFO) queue.

Waiting time of each process:

Process	Waiting Time = Service Time – Arrival Time
P0	0 – 0 = 0
P1	5 – 1 = 4
P2	8 – 2 = 6
P3	16 – 3 = 13

Average Waiting Time = (0+4+6+13) / 4 = 5.75

Advantages of FCFS:

• It is simple and easy to implement.

Disadvantages of FCFS:

• Inefficient throughput
• If a process has a very high burst time and is coming first, then it will be executed first even if another process with a lesser time is present in the ready state.

2. Shortest Job Next (SJN)

Also known as shortest job first (SJF), this scheduling algorithm is both a non-preemptive and preemptive scheduling algorithm. Process with the minimum burst time at an instance executes first. It is very efficient in minimizing the waiting time and is easy to implement in Batch systems. It cannot be implemented if the required CPU time is not known in advance.

Process	Arrival Time	Execution Time	Service Time
P0	0	5	0
P1	1	3	5
P2	2	8	14
P3	3	6	8

Waiting time of each process:

Process	Waiting Time = Service Time – Arrival Time
P0	0 – 0 = 0
P1	5 – 1 = 4
P2	14 – 2 = 12
P3	8 – 3 = 5

Average Waiting Time = (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Advantages:

• Short processes execute first.

Disadvantages:

• There is a chance of starvation if short processes keep coming in the ready state.

3. Priority Scheduling

This scheduling algorithm is commonly used in batch systems and is a non-preemptive scheduling algorithm. In this each process is assigned a priority and the process with the highest priority executes first followed by the ones lower in priority. If two processes share the same priority then execution is done on a first come first served basis. Priority is decided based on memory requirements, time requirements, or any other resource requirement.

Process	Arrival Time	Execution Time	Priority	Service Time
P0	0	5	1	0
P1	1	3	2	11
P2	2	8	1	14
P3	3	6	3	5

Waiting time of each process:

Process	Waiting Time
P0	0 – 0 = 0
P1	11 – 1 = 10
P2	14 – 2 = 12
P3	5 – 3 = 2

Average Waiting Time = (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Advantages:

• Higher priority processes execute first.

Disadvantages:

• There is a chance of starvation if only higher priority processes keep coming in the ready state
• If two processes have the same priorities, then some other scheduling algorithm needs to be used.

4. Shortest Remaining Time (SRT)

This scheduling algorithm is the preemptive version of the SJN algorithm. The OS allocates the processor to the job that is closest to completion. Though there is a chance of this job being preempted, if another job is ready with a shorter time to completion. It is used in batch environments where short jobs are given preference and cannot be implemented in interactive systems where required CPU time is unknown.

5. Round Robin (RR)

This scheduling algorithm is a preemptive process scheduling algorithm where each process is provided a fixed time to execute. This fixed time is called a quantum.It uses context switching to save states of preempted processes. Once a process is done executing for a given time period, it is preempted and another process executes for a given time period.

Waiting time of each process:

Process	Waiting 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 Waiting Time = (9+2+12+11) / 4 = 8.5

Advantages:

• No starvation as every process gets a chance for its execution.
• Used in time-sharing systems.

Disadvantages:

• The CPU is left idle due to a lot of context switching.

6. Multiple-Level Queues

In this scheduling algorithm multiple algorithms with common characteristics come together to form a group and then schedule jobs as a whole. Thus, it is not an independent scheduling algorithm. There are multiple queues for processes with common characteristics and each queue has its own scheduling algorithms. The OS assigns priorities to each queue.

7. Multilevel Feedback Queue

This scheduling algorithm is similar to multilevel queue scheduling except that the processes here can change their queue too i.e., if a process is in queue1, then after partial execution, it can switch to queue2.

There is a list of queues with different priorities and one with a higher priority queue executes first. During execution of a process with a higher priority queue comes, then the execution of the lower priority queue stops and the one with higher priority queue replaces it. There is a chance of starvation if the higher priority queue keeps coming in the ready state and the lower priority queue keeps waiting for its turn.

8. Highest Response Ratio Next

In this scheduling algorithm, scheduling is done on the basis of response ratio. The process with the highest response ratio is scheduled next which reduces starvation in the system.

Purpose of a Scheduling algorithm

The purpose of a scheduling algorithm is to provide:

• Maximum CPU utilization
• Minimum turnaround time
• Fair allocation of CPU
• Maximum throughput
• Minimum waiting time
• Minimum response time

Summary

Scheduling algorithm schedules jobs. There are six types of algorithms that we have seen in this tutorial. Hope you liked it.