Scheduling Algorithms in Operating System

7 min readDec 25, 2020

What is CPU Scheduling?

CPU Scheduling is the process which determines the process which will own the CPU for execution while other processes are in the queue. Whenever the CPU is idle, the Operating System selects one of the process which is ready in the queue. This task is carried out by CPU scheduler which selects one of the processes in memory that is ready for execution. Scheduling is used to increase the efficiency of CPU. CPU Scheduling is implemented to minimize Waiting Time, Response Time, and turnaround time and maximize CPU utilization and Throughput.

Types of CPU Scheduling

There are 2 types of CPU Scheduling:

1. Pre-emptive Scheduling

2. Non Pre-emptive Scheduling

Pre-emptive Scheduling:

Pre-emptive Scheduling is a priority based. Sometimes a higher priority task needs to be executed before any next lower priority task is selected. Even sometimes lower priority task need to be on hold for sometime till the higher priority task completes its execution.

Non Pre-emptive Scheduling:

Non Pre-emptive Scheduling has CPU allocated to a process. This process keeps CPU busy and can only released by context switching or terminating. Hence, it does not need special hardware like timer, as in Pre-emptive Scheduling.

Important Scheduling Terminologies:

CPU Time: It is the time taken by CPU to execute the process.

I/O Time: It is the time taken by process to execute I/O operations.

Burst Time: It can also be referred as Execution Time. It is the time taken by process to complete its execution on CPU.

Arrival Time: It is the time when a process enters in ready state or is ready for execution.

Exit Time/Completion Time: It is the time when system complete its execution and exits from the system.

Response Time: It is the time taken when the process is in the ready state and gets the CPU for first time.

Waiting Time: It is the total time passed waiting for CPU, in ready state.

Note: There is a difference between Response time and Waiting time. Response time is the time needed between ready state and getting the CPU first time. While Waiting time is time taken by process in ready state.

Turnaround Time: It is the total time taken by a process from coming into ready state till the complete execution. It can be calculated as-

Turnaround Time = Burst Time + Waiting Time

It can also be calculated as: Turnaround Time = Exit Time — Arrival Time

Throughput: It can be defined as the number of processes executed by CPU in a given amount of time.

Types of CPU Scheduling Algorithm:

There are 6 types of Scheduling Algorithms:

1. FCFS (First Come First Serve)

2. SJF (Shortest Job First)

3. SRT (Shortest Remaining Time)

4. RR (Round Robin Scheduling)

5. Priority Scheduling

6. Multiple level Queue Scheduling

First Come First Serve Scheduling

It is the easy and simple CPU Scheduling Algorithm. In this algorithm, the process which requests the CPU first, gets the CPU first for execution. It can be implemented using FIFO (First-In, First-Out) Queue method.

Characteristics:

1. It is easy to implement.

2. CPU is always allotted on the basis of First-come and First-serve.

3. But, this algorithm is poor in performance as the average waiting time is quite high.

Gantt Chart:

Gantt Chart for FCFS Scheduling

Shortest Job First Scheduling

In this algorithm, the process with minimum Burst Time is selected for the executing next. It significantly reduces the average waiting time for the other waiting processes. It provides Non pre-emptive, Pre-emptive methods.

Characteristics:

1. This algorithm is easy to implement in system where CPU time is known in advance.

2. In this algorithm, waiting for complete execution is not critical.

3. It is impossible to implement if CPU time is not known.

Gantt Chart:

Gantt Chart for SJF Scheduling

Shortest Remaining Time Scheduling

This algorithm is pre-emptive version of SJF algorithm. In this algorithm, the process will be allocated which is near to its completion. This does not allow new, ready processes to hold the completion of older processes.

Characteristics:

1. This algorithm is applied where short jobs are needed to be given preference.

2. A process closer to completion is allocated, but it can be preempted by a newly ready process, with less completion time.

3. Impossible to implement if CPU Time is not known.

Gantt Chart:

Gantt Chart for SRTF Scheduling

Round Robin Scheduling

Round Robin Scheduling is also a simple scheduling algorithm. Like the Round-Robin principle, where each person gets equal share of something, here each process is given a fixed amount of time (called as quantum). This algorithm is mainly used in Multitasking.

Characteristics:

1. As Round Robin is cyclic in nature, so there is no starvation of processes.

2. Setting the quantum too short may lower the efficiency of CPU. And setting it too long may cause poor response to other processes.

3. In this type of scheduling, average waiting time is often longer.

Time Quantum = 2

Gantt Chart:

Gantt Chart for Round Robin Scheduling

Priority Scheduling

This is the type of scheduling which is based on priorities, as name suggests. In this algorithm, process with highest priority is executed first. Same or equal priority processes are executed on RR or FCFS basis. Priority can be decided on various parameters like memory requirement, time requirement or any other criteria.

Characteristics:

1. Here, the relative importance of processes is precisely defined and executed.

2. If higher priority process take a lot of time, then other lower priority have possibility of starvation.

3. Another problem is decision of priority of the processes.

Gantt Chart:

Gantt Chart for Priority Scheduling

Multiple Level Queue Scheduling

This algorithm uses other scheduling algorithms to schedule the processes. Hence, it is not a independent process. In this algorithm, the ready queue is divided into separate queue levels with different priorities. Each of these queues can have its separate scheduling algorithm. There are multiple queues of different levels (here, highest to lowest priority) system processes, interactive processes and batch processes.

Characteristics:

Applications with various algorithms are possible.
Drawback is, a highest priority process is executed first and after its complete execution, a lower priority process get chance. It leads to starvation of lower priority processes.
Multilevel feedback queue scheduling is the solution to overcome the drawback of this algorithm.

Summary:

CPU Scheduling is the process which determines the process which will own the CPU for execution while other processes are in the queue.
Pre-emptive Scheduling is a priority based. Sometimes a higher priority task needs to be executed before any next lower priority task is selected.
In Non Pre-emptive Scheduling the running process keeps CPU busy and can only released by context switching or terminating.
Six types of Scheduling Algorithms are: 1. FCFS (First Come First Serve), 2. SJF (Shortest Job First), 3. SRT (Shortest Remaining Time), 4. RR (Round Robin Scheduling), 5. Priority Scheduling, 6. Multiple level Queue Scheduling
In FCFS algorithm, the process which requests the CPU first, gets the CPU first for execution.
In SJF algorithm, the process with minimum Burst Time is selected for the executing next.
In SRT algorithm, the process will be allocated which is near to its completion.
In RR algorithm, each process is given a fixed amount of time (called as quantum).
In Priority algorithm, process with highest priority is executed first.
In Multi-level queue algorithm, the ready queue is divided into separate queues with different priorities.
Scheduling is needed to increase the efficiency of the CPU.

REFERENCES