Scheduling Algorithms In Operating System Explained!

11 min readMar 10, 2022

Table of content:

Preemptive and Non-preemptive Algorithms
Goals of Scheduling
First Come First Serve
Shortest Job First
Longest Job First
Shortest Remaining Time First
Longest Remaining Time First
Priority Based Scheduling
Round Robin Scheduling
Multiple Level Queues Scheduling

The job of an operating system is to provide an interface for a user to effectively interact with a computer. However, an operating system needs to handle multiple processes and requests at any given time. This causes an increase in complexity since there needs to be an efficient method through which the operating system can cater to each and every process without running into problems. This is where scheduling algorithms come into play. They are used to maximize throughput and also ensure maximum utilization of the CPU, through the clever allocation of CPU resources.

Preemptive and Non-preemptive Algorithms

There are mainly two types of scheduling algorithms used, pre-emptive and non-preemptive. A non-preemptive algorithm will not pause or stall a process once it starts executing. On the other hand, in preemptive mode, a certain process can be preempted to allow another process to execute. Preempting means to take some action to prevent something, so in this context, one process is preempted to allow another to go on.

Goals of Scheduling

Scheduling algorithms have to be used to provide a systematic order of process execution in computing systems. The objective of CPU scheduling is to-

Provide maximum throughput
Pushing for maximum utilization of the CPU for the execution of tasks
Minimise the response time
Reduce the average turnaround time
Ensure Minimum waiting time

The following terminologies need to be defined to understand CPU Scheduling algorithms-

Arrival Time: It is the time at which a process arrives in the ready to execute queue or the ready queue.
Burst Time: It is the time required by the process to finish its execution. It is also called service time.
Completion Time: This is the time at which a process completes its execution.
Turnaround Time: This is the difference in time between the completion and arrival time.
Waiting Time: This is the amount of time that a process needs to wait before starting its execution. It may be due to other processes further ahead in line or due to a lack of available resources.

Some of the most popular scheduling algorithms are discussed here.

1. First Come First Serve (FCFS)

This is one of the simplest scheduling algorithms that can be implemented. It is a non-preemptive scheduling method. It uses a queue data structure, which works on the first in first out principle. What this implies is that in this algorithm, whichever process comes first to the OS, will get executed first. It is analogous to a queue of people waiting to buy ice cream. The person who stands first in the queue gets their chance to buy ice cream first. Then the second person in line gets their chance and so forth.

Let’s take up an example for FCFS-

We have 5 processes that arrive at the CPU at different times. The process with the minimal arrival time goes first. Since the first process has a burst time of 3, the CPU will remain busy for 3 units of time, which indicates that the second process will have to wait for 1 unit of time since it arrives at T=2.

In this way, the waiting and turnaround times for all processes can be calculated. This also gives the average waiting time and the average turnaround time. We can contrast this with other algorithms for the same set of processes.

Using a queue for the execution of processes is helpful in keeping track of which process comes at what stage. Although this is one of the simplest CPU scheduling algorithms, it suffers from the convoy effect. This occurs when multiple smaller processes get stuck behind a large process. This is similar to multiple cars stuck behind a slow-moving truck on a single lane road. This makes the average wait time quite high.

Advantages of FCFS

It’s simple and straightforward to implement and put into execution
Every process gets its chance to execute
Uses a simple data structure, that is, a FIFO-based queue.

Disadvantages of FCFS

May cause convoy effect which causes high wait time.
High average waiting time
Inefficient CPU utilization

2. Shortest Job First (SJF)

To improve upon FCFS, the Shortest Job Next algorithm employs the idea of allowing the process with the shortest execution time to go first. All the incoming processes are sorted on the basis of their burst time in increasing order. Shorter processes can execute quickly and free up the CPU for longer and more complex processes. This scheduling approach provides a good way to minimize waiting time.

Let’s continue with the same example for SJF-

Here, the first 2 processes execute as they come, but then the 5th process gets to go since it’s the shortest among all others. The turnaround time and waiting time is calculated. It’s visible that as an improvement over FCFS, we get reduced average waiting time as well as reduced average turnaround time.

This algorithm is especially useful in cases where there are multiple incoming processes and their burst time is known in advance. The average waiting time obtained is lower as compared to the first-come-first-served scheduling algorithm.

Advantages of SJF

Usually leads to reduced turnaround time
Useful for batch processes
Helps in reducing the wait time as well

Disadvantages of SJF

Longer processes may never get a chance if smaller ones keep coming
The burst time has to be known beforehand, which may not always be possible

3. Longest Job First (LJF)

Contrary to SJF, the Longest Job First works on the principle of allowing the process with the longest time period of execution to go first. It is also a non-preemptive scheduling algorithm. All the incoming processes are sorted on the basis of their burst time in descending order. Then the process with the longest burst time is chosen and executed.

Consider this as an example-

The first process executes first, then there is a choice between selecting the second or third process. The third one is selected since it has a higher burst time. Then the fourth one gets executed since it also has a higher burst time than the second process. Finally, the second process gets it chance to go.

This approach of CPU scheduling leads to very high waiting times since shorter processes might have to wait a lot to finally get a chance to get executed. This also causes the aforementioned convoy effect.

Advantages of LJF

More important and longer processes execute first, allowing minor ones to go later

Disadvantages of LJF

Shorter processes may not get a chance to execute if longer ones keep coming
Quite high waiting times, since all long processes go first
Burst time has to be known beforehand.

4. Shortest Remaining Time First

This algorithm is a preemptive scheduling method. The incoming processes are sorted on the basis of their CPU-burst time. The process which requires the least burst time is executed first, but if another process arrives that has an even lesser burst time, then the former process will get preempted for the latter. A certain process is executed for some specific unit of time and then the scheduler checks if any new processes with even shorter burst time have arrived. If there is one, the current process is preempted.

The following is an example for the same-

Here, the first process starts first and then the second process executes for 1 unit of time. It is then preempted by the arrival of the third process that has a lower service time. This goes on until the ready queue is empty and all processes are done executing.

It can also be called the preemptive version of the SJF algorithm.

Advantages of SRTF

The preemptive version of the SJF algorithm hence is more efficient.
Useful for batch processes
Helps in reducing the wait time as well

Disadvantages of SRTF

Longer processes may never get a chance if smaller ones keep coming
The burst time has to be known beforehand, which may not always be possible

5. Longest Remaining Time First

Like the previous approach, this is also preemptive. The incoming processes are sorted on the basis of their burst time. A certain process is executed for some specific time interval and then the CPU scheduler checks if any new process with a long burst time has arrived. If there is one, the current process is preempted and the new process starts executing for the next unit of time.

Consider this as an example-

The first process executes for one unit before being preempted by the second process. That, in turn, is preempted by the third process which is also preempted by the fourth process. After the longest process is done, the others get executed.

It can also be called the preemptive version of the LJF algorithm.

Advantages of LRTF

The preemptive version of the LJF algorithm hence is more efficient.
More important and longer processes execute first, allowing minor ones to go later

Disadvantages of LRTF

Shorter processes may not get a chance to execute if longer ones keep coming
Quite high waiting times, since all long processes go first
Burst time has to be known beforehand.

6. Priority Based Scheduling

In order to do away with selecting the shortest or longest processes, this algorithm is used to assign priorities to different processes. The process with the highest priority goes first, and the one with the lowest priority gets to go at the end. Hence the priority of process will determine the order. It uses a non-preemptive scheduling approach.

If two processes have the same priority, then the one which comes first will be executed first. The priority of a process can depend on multiple factors ranging from memory requirements to required CPU time.

The example below illustrates the concept better-

Here, different priorities are assigned to the incoming processes. The lower the number, the higher the priority. The 1st process to be executed is the second one, since it has higher priority than the first process. Then the fourth process gets its turn. This is known as Priority Scheduling. The calculated times may not be the lowest but it helps to prioritise important processes over others.

Advantages of PBS

Priorities help in sorting the incoming processes.
Works well for static and dynamic environments.

Disadvantages of PBS

Processes with lower priority may get stuck for a long time.
Turnaround time may be higher than other algorithms.

7. Round Robin Scheduling

The Round Robin Scheduling algorithm is a preemptive scheduling algorithm. A finite unit of time, known as a time quantum or time slice is provided to the processes for execution. Each process is allowed to execute for the given quantum of time, before which the execution of another process takes over for the next time quantum. This change happens through context switching. Once a process begins executing, it is preempted after one quantum of time.

As seen from the figure, the scheduler executes the 3 incoming processes part by part.

This can also be understood by using an example-

Let’s take a quantum time of 4 units. The first process will execute and get completed. After a gap of 1 unit, the second process executes for 4 units. Then the third one executes since it has also arrived in the ready queue. After 4 units, the fourth process executes.

This process keeps going until all processes are done. It is worth noting that the minimum average waiting time is higher than some of the other algorithms. While it is true that this approach requires a higher turnaround time, it can be used in multitasking environments.

Advantages of RRS

All processes are given the same priority
Starvation doesn’t take place
Efficient CPU utilization

Disadvantages of RRS

Higher waiting time as compared to other algorithms
Context switching leads to the addition of overhead time, which increases the execution time.
Choosing the correct time quantum is not a simple task

8. Multiple Level Queues Scheduling

The multilevel queue scheduling approach makes use of multiple queues to separate the processes which are in the ready queue. Once this separation is done, different queues can use different algorithms such as FCFS, SJF and so on to execute the processes in line. Hence the multilevel queue scheduling algorithm is essentially a technique by which processes can be separated on the basis of their time requirements and then get executed depending on the algorithm used.

The figure above displays how processes are separated on the basis of their priority and executed. Depending on the type of the process, such as system, interactive or batch, different algorithms are used. These can be FCFS, SJF or the Round-Robin (RR) scheduling technique.

Advantages of MLQS

Uses a combination of algorithms to provide the best results
The overhead time is less

Disadvantages of MLQS

Implementation of this algorithm is not simple
Requires sorting and selecting different processes for different algorithms.

In conclusion, the goal of scheduling algorithms is to provide efficient execution of the various processes within an operating system and to achieve maximum CPU utilization. The overall throughput and CPU utilization will depend on the type of scheduling algorithm that is implemented.

You might also be interested in reading: