Operating System Tutorial

What is Operating System Evolution of Operating System Types of Operating System Functions of Operating System What is Kernel and Types of Kernel Operating System Properties Operating System Services Components of Operating System Needs of the Operating System Linux Operating System Unix Operating System Ubuntu Operating System What is DOS Operating System Difference Between Multi-programming and Multitasking What is Thread and Types of Thread Process Management Process State What is Process Scheduler and Process Queue What is Context Switching What is CPU Scheduling Scheduling Algorithm FCFS (First-come-First-Serve) Scheduling SJF (Shortest Job First) Scheduling Round-Robin CPU Scheduling Priority Based Scheduling HRRN (Highest Response Ratio Next) Scheduling Process Synchronization Lock Variable Mechanism TSL Mechanism Turn Variable Mechanism Interested Variable Mechanism What is Producer-Consumer Problem What is Semaphore in Operating System Monitors in Operating System What is Deadlock Deadlock Avoidance Strategies for Handling Deadlock Deadlock Prevention Deadlock Detection and Recovery Resource Allocation Graph Banker’s Algorithm in Operating System Fixed Partitioning and Dynamic Partitioning Partitioning Algorithms What is Paging and Segmentation What is Demand Paging What is Virtual Memory Disk Scheduling Algorithms FCFS and SSTF Disk Scheduling Algorithm SCAN and C-SCAN Disk Scheduling Algorithm Look and C-Look Disk Scheduling Algorithm File in Operating System File Access Methods in Operating System File Allocation Method Directory Structure in Operating System Difference between C-LOOK and C-SCAN Difference between Rotational Latency and Disk Assess Time Trap vs Interrupt How to implement Monitors using Semaphores N-Step-SCAN Disk Scheduling Why is it critical for the Scheduler to distinguish between I/O-bound and CPU-bound programs Difference between C-SCAN and SSTF Difference between SCAN and FCFS Difference between Seek Time and Disk Access Time Difference between SSTF and LOOK

HRRN Scheduling in OS

Highest Response Ratio Next (HRRN) Scheduling in OS

Highest Response Ratio Next Scheduling is a Non-Preemptive Scheduling algorithm. This algorithm provides the benefits of the shortest job first scheduling algorithm and also removes the limits of the shortest job first scheduling algorithm.

It is one of the most optimal scheduling algorithms among all other scheduling algorithms. In Highest Response Ratio, scheduling of the jobs is implemented on the basis of an additional parameter, which is called Response Ratio. We calculate the response ratio for every available process, and the process, which has the highest response ratio holds the highest priority among all the processes.

Response Ratio is calculated with the help of given formula:

          Response Ratio = (W+S)/S


         W is a Waiting Time

          S is a Service Time or Burst Time

In the following example, we have 5 processes with process ID P1, P2, P3, P4, and P5. The arrival time and burst time of the processes are given in the following table.

      Process ID    Arrival Time     Burst Time
              P1             0                 3
              P2             2                 7
              P3             4                 5
              P4             6                 2
              P5              8                 4

Gantt Chart

HRRN Scheduling in OS


  • Initially, at time=0, the process P1 was in the ready queue. So, the process P1 completes its execution.
  • After the process P1, at time=3, only the process P2 arrived, so the process P2 executed because the operating system did not had any other option.
  • At time=10, the processes P3, P4, and P5 were in ready queue. So, to schedule the next process after P2, we had calculated the response ratio.
  • Next we calculated the response ratio for P3, P4, and P5.

Response Ratio = W+S/S

  RR(P3) = [(10-4) +5]/5

               = 2.2    

  RR(P4) = [(10-6) +2]/2

                = 3

  RR(P5) = [(10-8) +4]/4

               = 1.5

As it is clear that the Process P4 has the Highest Response ratio, so the Process P4 was scheduled after P2.

  • Then, we had two processes i.e., P3 and P5, which are in the ready queue.

         So, we again calculate the Response Ratio for the Process P3 and P5.

          RR (P3) = [(12-6) +2]/2


          RR (P5) = [(12-8) +4]/4


       Process P3 has the Highest Response Ratio so, next Process P3 was executed.

  • After the Process P3 completed its execution, the Process P5 was only left in the ready queue. So, the Process P3 was executed next.      

The waiting Time and Turnaround Time were calculated with the help of the following formula.

         Waiting Time = Turnaround time – Burst Time

          Turnaround Time = Completion time – Arrival time 

   Process ID   Arriving Time          Burst Time  Completion Time Turnaround Time Waiting Time
          P1            0           3               3            3         0
          P2            2          7               10            8         1
          P3            4          5               17           13         8
          P4            6          2               12             6          4
          P5            8           4                21              13           9

Average Waiting Time= 0+1+8+4+9/5

                                       = 4.4

Average Turnaround Time = 3+8+13+6+13/5

                                               = 8.6

Advantages of Highest Response Ratio Next Scheduling

The advantages of Highest Response Ratio Next Scheduling are:

  1. The Performance of HRRN Scheduling is better than the shortest job first Scheduling.
  2.  HRRN Scheduling reduces the longer job waiting time and also encourages shorter jobs.
  3. Increase throughput.

Disadvantage of Highest Response Ratio Next Scheduling

The disadvantages of Highest Response Ration Next Scheduling are:

  1. Practical implementation is not possible in HRRN Scheduling because we cannot know the burst time of every process in advance.
  2. In HRRN Scheduling, overhead on processors may occur.