Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Easy

Scheduling Algorithms in Operating Systems

Author Yashesvinee V
0 upvote
gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up

Introduction

The Operating system runs various processes and programs to ensure the proper functioning of the computer. Since many processes run and execute concurrently, there is a high demand for CPU and other resources. Hence, the concept of Scheduling comes into play. Scheduling is a task carried out by the OS to efficiently allocate CPU time to executing processes. The scheduling process can be done using the different types of scheduling algorithms in Operating systems.

Scheduling Algorithms in Operating Systems

Also See, FCFS Scheduling Algorithm, Multiprogramming vs Multitasking

Scheduling algorithms

Scheduling Algorithms define the different ways of scheduling processes to ensure maximum and efficient utilization of the CPU. The process scheduler uses these algorithms to determine the sequence of processes to be executed or removed. Scheduling algorithms in operating systems can be Preemptive or non-preemptive.

Preemptive Scheduling algorithms

Preemptive scheduling algorithms in operating systems schedule processes based on a priority order. The process with higher priority can interrupt the execution of the one with lower priority and be executed first. This is the preemptive way of scheduling processes.

Non-Preemptive Scheduling algorithms

Non-preemptive scheduling algorithms in operating systems do not support the preempting of a process. It does not take into account the priority of a process. A process may release the CPU only after its termination and can not be interrupted during execution.

Terminology

  • Throughput - The number of processes that complete their execution per unit time.
     
  • Arrival time - The time at which a process enters the Ready queue.
     
  • Completion time - The time at which a process completes its execution.
     
  • Burst time - The time takes to execute a process in the CPU.
     
  • Turnaround time - The time difference between completion time and arrival time. It is the time interval between the submission and completion of a process.
     
  • Waiting time - The time difference between turnaround time and burst time. It is the amount of time a process spends in the ready queue waiting for its turn with the CPU.

Need for scheduling 

Scheduling algorithms in operating systems play a vital role in determining the performance and efficiency of a computer. Scheduling helps maximize CPU utilization and keeps the CPU up and running at all times. It also ensures that all processes get a fair share of CPU time for their execution. Scheduling can also help minimize the turnaround time and waiting time. It also helps maximize the total number of processes executed in unit time.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

List of Scheduling algorithms

All scheduling algorithms in operating systems are either preemptive or non-preemptive. Following is the list of the most frequently used scheduling algorithms.

First Come First Serve (FCFS)

It is the simplest scheduling algorithm that schedules processes based on their arrival time. A process that arrives first is executed first, followed by the next. It is a non-preemptive scheduling algorithm that does not prioritize one process over another. They are executed in the order of their arrival at the CPU. FCFS uses the concept of First-in-First-out (FIFO).

Advantages

  • It uses simple logic and is easy to implement. 
  • The chances of starvation are highly unlikely.
  • Ensures that every process gets a chance to execute, preventing starvation.
  • Low overhead in terms of implementation and system resources.

Disadvantages

  • It consumes a lot of time and tends to minimize CPU utilization. 
  • It reduces performance as the average wait time is high.
  • Inefficient when tasks have varying burst times, as short jobs wait behind long ones.
  • Can result in higher turnaround time, especially with a mix of short and long jobs.

Shortest Job First (SJF)

This algorithm schedules processes based on their burst time. The process having the shortest burst time is scheduled first, provided that all the processes in the queue arrive at the same time. It is also known as the Shortest Job Next algorithm. SJF is a non-preemptive algorithm that requires the processor to know the burst time of all the processes in advance. If two or more processes have the same burst time, the FCFS is used to schedule them further.

Advantages

  • Increased throughput and shorter turnaround time. 
  • It minimizes waiting time for processes that are ready for execution.
  • Effective in batch processing where job lengths are known in advance.
  • Provides predictable and deterministic performance.

Disadvantages

  • It may lead to starvation, as longer processes have to wait for their turn until the shorter processes have been executed.
  • Accurate prediction of job lengths is often challenging.
  • Requires continuous monitoring of job lengths, adding complexity.
  • A long job may need to wait indefinitely if shorter jobs keep arriving.

Longest Job First (LJF)

This algorithm works very much like the Shortest Job First Algorithm, the only difference being that LJF schedules processes with the longest burst time first.

Shortest Remaining Job First (SRJF)

Shortest Remaining Job First is the preemptive version of the Shortest Job First algorithm. Processes are scheduled according to the shortest remaining time. The process with the shortest burst time is scheduled to execute first. The arrival time of all processes need not be the same. If a process with the shortest burst time arrives during the execution of another process, then it will be preempted, and the newly arrived job is executed first.

Advantages 

  • Processes are executed at a much faster rate compared to the SJF algorithm.
  • Effective in batch processing environments where job characteristics are known in advance.
  • Leads to low turnaround time as short jobs are quickly executed.
  • Tasks with shorter remaining execution times are scheduled first, minimizing overall waiting time.

Disadvantages 

  • It is impossible to implement it in systems where the required CPU time is unknown. It may lead to starvation and increased overhead.
  • Accurately predicting the remaining execution time of each task is difficult.
  • Long tasks may face starvation if constantly preempted by shorter tasks.
  • Frequent preemption and context switching introduce overhead.

Longest Remaining Job First (LRJF)

The Longest Remaining Job First algorithm is similar to the SRJF algorithm. The only difference between the two is that the process with the longest burst time is scheduled to execute first.

Priority Scheduling

Priority Scheduling is a  non-preemptive scheduling algorithm in which each process is assigned a priority. The process with the highest priority is scheduled first, followed by the ones with lower priority. Processes are given their priority based on memory, time and resource requirements.

Advantages 

  • Processes with high priority need not wait for long. Hence, it is suitable for applications with fluctuating time and resource requirements.
  • Priorities can be adjusted based on the specific requirements of the system or application.
  • High-priority tasks are executed promptly, leading to efficient resource utilization.
  • Processes are assigned priority levels, allowing for the execution of higher-priority tasks first.

Disadvantages 

  • Since higher priority processes take over the majority of the CPU time, it leads to starvation of lower priority processes.
  • Priority inversion can occur, where a low-priority task holds a resource needed by a higher-priority task.
  • The need for dynamic adjustments to priorities adds complexity to the scheduling algorithm.
  • Assigning accurate and meaningful priorities to diverse processes can be challenging.

Round Robin Scheduling

Round robin scheduling is a preemptive scheduling algorithm in which a process gets executed cyclically. Every process in the Ready queue has a time slice allotted to it. This is known as the time quantum. The CPU is assigned to the process for that time quantum. A process that completes the execution within the time quantum is terminated. If a process cannot complete its execution within the time quantum, it is suspended and added to the ready queue again. This algorithm is primarily used in time-sharing systems.

Advantages

  • All processes have the same priority and are given an equal share of CPU time. 
  • There is no starvation and no process is left unattended.
  • Short processes generally experience lower waiting times compared to some other scheduling algorithms.
  • It is a straightforward and easy-to-implement scheduling algorithm.

Disadvantages

  • It has a long average waiting time. 
  • Setting a short time quantum can reduce CPU utilization and reduce performance.
  • The algorithm may result in lower throughput compared to other scheduling algorithms, especially when processes have varying burst times.
  • Short processes can get stuck waiting behind a long process, leading to a convoy effect where short processes are delayed.

Highest Response Ratio Next (HRRN)

It is a non-preemptive scheduling algorithm that schedules processes based on a response ratio. The process with the highest response ratio is scheduled first. This helps reduce starvation in the system. The response ratio is calculated using the following formula.

Response ratio = (Waiting time + Burst time) / Burst time

Multiple-Level Queues Scheduling

In this algorithm, multiple algorithms with common characteristics combine to form a group and are scheduled as a whole. Multiple queues are made to store processes based on similar characteristics, and each queue has its own scheduling algorithm. The operating system assigns priority to every queue.

Multilevel Feedback Queues Scheduling

This algorithm is similar to multilevel queue scheduling, except that the processes can change their queue after partial execution. Higher priority queues can preempt lower priority queues. If a process uses too much CPU time, it moves to a lower priority queue.

You can also read about layered structure of operating system.

Must Read Evolution of Operating System

Frequently Asked Questions

What is scheduling algorithms in operating system?

Scheduling algorithms manage the order in which processes execute in an operating system. They determine which process to run next and for how long.

What are the 5 scheduling algorithm types?

The 5 scheduling algorithm types include First-Come, First-Served (FCFS), Shortest Job Next (SJN), Priority Scheduling, Round Robin, and Multilevel Queue Scheduling.

What are the 3 types of scheduling in operating system?

The three main types of scheduling in an operating system are short-term scheduling (CPU scheduling), medium-term scheduling (Swapping), and long-term scheduling (Job Scheduling).

Conclusion

In this article, we have extensively discussed Scheduling algorithms in Operating Systems. We started with a brief introduction to Scheduling algorithms and then moved on the see their types. We also explored the various scheduling algorithms in operating systems that are currently in use.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Upvote our blogs if you find them insightful and engaging! Happy Learning!

Previous article
First In First Out (FIFO) Algorithm in OS
Next article
How Is Shortest Job First Scheduling Performed In Operating Systems?
Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass