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

HRRN Scheduling

Author Ankit Kumar
1 upvote
gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up
Operating System

Introduction

Nowadays, we all are surrounded by multiprogramming operating systems. These operating systems are fast and very efficient in handling so many processes at a single time without fail. If you do not understand multitasking or multiprogramming, pause and check out your mobile phone. Bingo! You just did multitasking 😂😂. At the same time, you checked your phone and read this blog. 

Our brain is the smartest thing on the planet so we can perform multitasking without any scheduling algorithm, but operating systems need a set of rules or algorithms to decide which processes are to be executed and when.

This set of algorithms is called scheduling algorithms, and in this article, we will discuss one of the most optimal scheduling algorithms known as HRRN scheduling.

The highest response ratio next or the HRRN scheduling algorithm is a non-preemptive kind of algorithm, which runs on the dependency of the response ratio of a process. Let us discuss the response ratio in the next section.

Recommended Topic, FCFS Scheduling Algorithm, Multiprogramming vs Multitasking

Response ratio

As the name suggests, it must be a ratio of two things. The two things are the process's waiting time and the burst/execution time. We have a direct formula to determine the response ratio for a process.

Response ratio = (W+S)/S,

Where W is the waiting time of the process in the ready queue and S is the total time needed by the process to complete its execution.

The above formula shows that the process with a low burst time will have a higher response ratio, increasing the priority of the process to get executed by the CPU. 

With every increment in the waiting time of the process, the response ratio will increase and thus making the process more probable to be completed as soon as the CPU is free.

With the above theory, we can derive the following conclusions in the context of response ratio.

  1. The response ratio is directly proportional to the waiting time of the process.
  2. The response ratio is inversely proportional to the burst/execution time of the process.

Let us understand in brief the working of this algorithm.

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

Working

The Highest response ratio is a non-preemptive algorithm that does not interrupt any process in the execution until it is terminated or requires an input/output operation.

Now the question arises whether the CPU will execute which process first if the CPU is following the HRRN scheduling algorithm.

At first, the CPU will calculate the response ratio with the help of the formula mentioned above for every process that is present in the ready queue or is simply ready to be executed. 

Then the CPU will send the process with the highest response ratio for the execution, and this will continue until the ready queue is empty.

Was it not simple? I hope It was, and this was all about one of the most optimal scheduling algorithms known as the HRRN Scheduling.

Let us now discuss an example of it in the next section.

Example of HRRN Scheduling.

Let us consider the following table, which has three processes to be executed, and see which order they will get executed.

Process ID Arrival time Execution/Burst time
0 0 3
1 1 2
2 3 2

When the CPU starts executing the process, then at time 0, we only have one process available, so without any second thought, the CPU will start executing the P0.

Now the P0 is executed for three units of time.

When P0 is completed, two new processes, P1 and P2, arrive. According to the HRRN scheduling algorithm, we will calculate the response ratio of these two processes, and the process with the higher response ratio will be scheduled for its execution.

The process P1 arrived at one unit of time and had to wait for two units until the execution of process P0. Hence the waiting time for P1 becomes two units.

Response ratio for P1 = (2+2/2) = 2

Since the process P2 arrived at the units of time and didn't wait, the waiting time becomes zero.

Response ratio for P2 = (0+2/2) = 1

As the response ratio for P1 is greater than P2, the CPU will execute the process P1 first. Hence the order of execution becomes 

P0 → P1 → P2.

I hope you understood this explanation of HRRN scheduling clearly, and let us now discuss some of the FAQs related to this.

You can also read about layered structure of operating system, and Open Source Operating System

Frequently Asked Questions

What is the full form of HRRN scheduling?

HRNN is the Highest response ratio next scheduling algorithm.

Is HRNN a preemptive scheduling algorithm?

No! HRNN is not preemptive. It is a non-preemptive type of scheduling algorithm. This means it cannot interrupt the process in between its execution.

What is the response ratio?

Response ratio is simply the ratio of wait time-burst time divided by the burst time of the process.
It is calculated by the following formula.
Response ratio = (W+S)/S.
Where W is the wait time, and S is the burst/execution time of the process.

What is the dependency of waiting time and burst time on the response ratio?

The response ratio is directly proportional to the wait time and inversely proportional to the burst time of the process.

What are some of the non-preemptive scheduling algorithms?

The following algorithms are non-preemptive.
FCFS - First come, first serve.
Priority scheduling
HRRN scheduling

Let us now summarize our learnings.

Conclusion

In this article, we extensively discussed one of the most important scheduling algorithms named HRNN, or the Highest response ratio scheduling algorithm. We discussed its working in detail and also got through an example of it.

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.

Previous article
Round Robin CPU Scheduling Algorithm
Next article
Multilevel Queue Scheduling
Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass