Highest Response Ratio Next (HRRN) Scheduling with Examples and Programs

HRRN (Highest Response Ratio Next) scheduling is a CPU scheduling algorithm that prioritizes processes based on their response ratio, which is the ratio of waiting time and estimated processing time. Now, here we will explain about what is Highest Response Ratio Next scheduling algorithm; involving with HRRN scheduling examples and programs with their outputs. Therefore, at the end of this article; you will definitely fully educate about HRRN Scheduling Algorithm without any problem.

What is HRRN Scheduling in OS?

HRRN (Highest Response Ratio Next) scheduling is a type of process scheduling algorithm that is used by operating systems to determine the order in which processes are executed. It is a non-pre-emptive scheduling algorithm, which means that once a process has started execution, it will continue to run until it completes, or until it voluntarily yields the CPU.

Highest-Response-Ratio-Next-scheduling

In HRRN scheduling, the process with the highest response ratio (which is the ratio of its waiting time to its estimated run time) is given priority. The idea behind this algorithm is that it tries to balance the turnaround time of a process with the amount of time it has already waited to execute.

HRRN scheduling is an improvement over other scheduling algorithms like FCFS (First-Come, First-Serve) and SJF (Shortest Job First) as it takes into account both the waiting time and the estimated run time of a process. However, it may not be suitable for real-time systems where the response time is critical, as it may lead to long response times for some processes.

‘HRRN Scheduling’ Tutorial Headlines:

In this section, we will show you all headlines about this entire article; you can check them as your choice; below shown all:

  1. What is HRRN Scheduling in OS?
  2. What is Response Ratio in OS?
  3. How to Calculate Response Ratio?
  4. HRRN Scheduling Algorithm Implementation
  5. HRRN Scheduling Example with Gantt Chart
  6. What is the Real Life Example of HRRN Scheduling?
  7. Advantages of HRRN CPU Scheduling
  8. Disadvantages of HRRN CPU Scheduling
  9. Characteristics of HRRN CPU Scheduling
  10. HRRN Scheduling Program in C
  11. HRRN Scheduling Program in C++

Let’s Get Started!!

What is Response Ratio in OS?

The response ratio is calculated as the sum of the waiting time and service time divided by the service time of a process.

The response ratio in HRRN scheduling is used to prioritize the execution of processes, the higher the response ratio, and higher the priority of the process. When a new process arrives, the HRRN algorithm calculates its response ratio and compares it to the response ratios of the currently running processes. If the new process has a higher response ratio, it is given priority and scheduled for execution.

The response ratio can be used as a measure of how long a process has been waiting for CPU time. Processes that have been waiting for a long time will have a higher response ratio and will be given priority over processes that have just arrived or have been waiting for a shorter period.

The HRRN scheduling algorithm is designed to minimize the average response time of processes, which is the time it takes for a process to receive a response to its request for CPU time. By prioritizing processes with higher response ratios, the algorithm aims to reduce the average response time and improve overall system performance.

How to Calculate Response Ratio?

To calculate the response ratio in HRRN scheduling, you need to know the waiting time and service time of the process. The response ratio is then calculated as the sum of the waiting time and service time divided by the service time of the process.

Also Read: Longest Remaining Time First (LRTF) Scheduling with Examples & Programs

The formula for calculating the response ratio is:

Response Ratio = (Waiting Time + Service Time) / Service Time

The waiting time is the time a process has spent waiting in the ready queue before it starts executing, and the service time is the time the process requires to complete its execution.

Let’s take an example to understand this better. Suppose we have three processes P1, P2, and P3, with the following characteristics:

Process P1: Service Time = 4, Waiting Time = 6

Process P2: Service Time = 3, Waiting Time = 3

Process P3: Service Time = 5, Waiting Time = 2

To calculate the response ratio for each process, we use the formula:

Response Ratio P1 = (Waiting Time P1 + Service Time P1) / Service Time P1 = (6 + 4) / 4 = 2.5

Response Ratio P2 = (Waiting Time P2 + Service Time P2) / Service Time P2 = (3 + 3) / 3 = 2

Response Ratio P3 = (Waiting Time P3 + Service Time P3) / Service Time P3 = (2 + 5) / 5 = 1.4

From the above example, we can see that the process with the highest response ratio is P1, followed by P2 and P3. Therefore, in HRRN scheduling, P1 will be given the highest priority, followed by P2 and P3.

HRRN Scheduling Algorithm Implementation

Here, we will show you a flowchart for implementing HRRN (Highest Response Ratio Next) scheduling algorithm:

Also Read: Shortest Remaining Time First (SRTF) Scheduling Examples & Programs

Start

  1. Initialize the ready queue
  2. Check if there are any processes in the ready queue
  3. If there are no processes, go to step 8
  4. Calculate the response ratio for each process in the ready queue using the formula:
  5. Response ratio = (waiting time + service time) / service time
  6. Select the process with the highest response ratio
  7. Execute the selected process for a time slice
  8. Check if all processes have been executed
  9. If not, go to step 3

End

Note: The waiting time is the time a process has been waiting in the ready queue, and the service time is the amount of time required by a process to complete its execution. In step 7, the process is executed for a predefined time slice before being pre-empted to allow other processes to execute.

HRRN Scheduling Example with Gantt Chart

Sure, let’s take an example to illustrate the HRRN (Highest Response Ratio Next) scheduling algorithm and create a Gantt chart for it.

Assume we have four processes with the following information:

Process         Arrival Time    Burst Time

P1                           0                   4

P2                           2                   6

P3                           4                   2

P4                           6                   4

The Highest Response Ratio Next (HRRN) scheduling algorithm selects the process with the highest response ratio, where the response ratio is defined as (wait time + burst time) / burst time. In other words, HRRN selects the process that has been waiting the longest, relative to its burst time.

To illustrate the HRRN algorithm, we’ll use the following steps:

Calculate the response ratio for each process.

  • Select the process with the highest response ratio to run next.
  • Execute the process for one time unit.
  • Update the wait time for all the remaining processes.
  • Repeat steps 1-4 until all processes are completed.

Here’s the calculation of response ratios for each process:

Process    Arrival Time    Burst Time   Wait Time    Response Ratio

P1                           0                     4                   0                1.00

P2                           2                    6                    0                1.33

P3                           4                     2                   0                 2.00

P4                           6                     4                   0                 2.50

At time 0, the only process that has arrived is P1, so we’ll run it:

Time      Running Process

0                    P1

After running P1 for one time unit, we update the wait time for the remaining processes:

Process    Arrival Time    Burst Time    Wait Time    Response Ratio

P1                     0                     4                       1                       1.25

P2                     2                      6                      0                        1.33

P3                     4                      2                      1                        2.50

P4                     6                      4                      0                        2.50

At time 1, we have two processes with the highest response ratio, P2 and P3. Since P2 arrived first, we’ll run it:

Time      Running Process

0                      P1

1                      P2

After running P2 for one time unit, we update the wait time for the remaining processes:

Process    Arrival Time    Burst Time    Wait Time    Response Ratio

P1                    0                     4                          2                     1.50

P2                    2                     6                          1                     1.50

P3                    4                     2                          2                     3.00

P4                    6                     4                          0                     2.50

At time 2, we have two processes with the highest response ratio, P1 and P2. Since P1 arrived first, we’ll run it:

Time      Running Process

0                      P1

1                      P2

2                      P1

After running P1 for one time unit, we update the wait time for the remaining processes:

Process    Arrival Time    Burst Time    Wait Time    Response Ratio

P1               0                    4                           3                           1.75

P2               2                    6                           2                           2.00

P3               4                    2                           3                           4.50

P4               6                    4                           0                           2.50

At time 3, we have two processes with the highest response ratio, P1 and P2. Since P1 arrived first, we’ll run it:

Time      Running Process

0              P1

1              P2

2              P1

3              P1

After running P1 for one time unit, we update the wait time for the remaining processes:

Process    Arrival Time    Burst Time    Wait Time    Response Ratio

P1                0                      4                      4                             2.00

P2                2                      6                      3                             2.50

P3                4                      2                      4                             6.00

P4                 6                      4                      0                             2.50

Finally, at time 4, we only have one process remaining, P2, so we’ll run it until completion:

Time      Running Process

0                              P1

1                              P2

2                              P1

3                              P1

4                              P2

5                              P2

6                              P2

Now that all processes are completed, let’s create the Gantt chart:

Process  Time 0 Time 1  Time 2  Time 3  Time 4  Time 5  Time 6

P1               P1          P2           P1           P1                                       

P2                                                                                P2          P2          P2

P3                                                                                                          

P4

The above Gantt chart shows that P1 is executed for the first time at time 0, followed by P2 at time 1. Then, P1 executes again at time 2 and 3. Finally, P2 executes for the remaining time slots from time 4 to 6. Note that P3 and P4 are not executed at all in this example.

What is the Real Life Example of HRRN Scheduling?

One real-life example of HRRN scheduling is in a restaurant where the chef has to prioritize the cooking of dishes based on their waiting time and cooking time. Suppose there are three dishes: A, B, and C, with cooking times of 10, 20, and 30 minutes, respectively. If dish A has been waiting for 5 minutes, dish B has been waiting for 10 minutes, and dish C has been waiting for 15 minutes, the chef can use the HRRN scheduling algorithm to decide which dish to cook next.

Also Read: Multilevel Queue (MLQ) Scheduling with Examples and Programs!!

Using the HRRN scheduling algorithm, the response ratios for dishes A, B, and C can be calculated as follows:

Response ratio for dish A = (5 + 10) / 10 = 1.5

Response ratio for dish B = (10 + 20) / 20 = 1.5

Response ratio for dish C = (15 + 30) / 30 = 1.5

Since all three dishes have the same response ratio, the chef can select the dish with the shortest cooking time, which is dish A. After dish A is cooked, the chef can recalculate the response ratios for dishes B and C and select the next dish to cook based on the new ratios. This process continues until all dishes are cooked.

Advantages of HRRN CPU Scheduling

Here are some advantages of HRRN CPU scheduling:

Also Read: Multilevel Feedback Queue Scheduling (MLFQ) Algorithm with Examples & Programs!!

Higher Throughput: HRRN CPU scheduling algorithm is designed to maximize the throughput by selecting the process with the highest response ratio. As a result, it can achieve a higher throughput compared to other scheduling algorithms.

Better Turnaround Time: HRRN scheduling algorithm gives priority to the process with a higher response ratio. This helps in reducing the waiting time of the process and improves the turnaround time.

Better Utilization of CPU: HRRN scheduling algorithm ensures that the CPU is used efficiently by selecting the process with the highest response ratio. This reduces the idle time of the CPU and increases its utilization.

No Starvation: In HRRN scheduling algorithm, all processes are given a chance to execute, and no process is left waiting indefinitely. This ensures that there is no starvation of any process in the system.

Fairness: HRRN scheduling algorithm is fair in terms of giving priority to processes based on their response ratio. This ensures that all processes are treated equally and there is no bias towards any particular process.

Dynamic: HRRN scheduling algorithm is dynamic, meaning that it adapts to the changing system state. It constantly evaluates the response ratio of each process and selects the one with the highest ratio. This helps in handling the workload in a dynamic system and ensures that the scheduling algorithm is always optimized.

Simple Implementation: HRRN scheduling algorithm is relatively easy to implement compared to other scheduling algorithms such as Round Robin or Priority scheduling. It requires only a few computations to calculate the response ratio and select the process with the highest ratio.

Low Latency: HRRN scheduling algorithm has low latency since it selects the process with the highest response ratio, which means that the selected process is likely to be the one that is most ready to run. This reduces the waiting time for the process and improves the overall system performance.

Efficient Use of Resources: HRRN scheduling algorithm ensures that the resources are used efficiently by selecting the process with the highest response ratio. This reduces the number of context switches and ensures that the CPU is not wasted on processes that are not ready to run.

Hence, HRRN CPU scheduling algorithm is a good choice for systems that require high throughput, low waiting time, and efficient use of resources. It is dynamic, simple to implement, and ensures fairness among processes.

Disadvantages of HRRN CPU Scheduling

While HRRN scheduling has some advantages, such as maximizing the overall throughput of the system and reducing the average waiting time of processes, it also has some disadvantages, including:

Also Read: Shortest Job First (SJF) Scheduling with Examples and Programs!!

Starvation: In some cases, a long-running process with a low response ratio can be starved of CPU time as the scheduler always favors processes with a high response ratio. This can lead to unfairness and reduced overall performance.

Computational Overhead: The HRRN algorithm requires calculating the response ratio for each process, which can be computationally expensive, especially in systems with a large number of processes.

Lack of Predictability: The execution time of a process can vary greatly, making it difficult to predict the response ratio accurately. This can lead to unpredictable behavior and make it challenging to plan and optimize system resources.

Non Pre-emptive Nature: HRRN is a non-preemptive scheduling algorithm, which means that once a process starts executing, it cannot be interrupted or pre-empted by another process. This can lead to increased waiting times for higher-priority processes and reduced overall system responsiveness.

Inefficient for Interactive Systems: HRRN scheduling is not well suited for interactive systems where users expect a quick response time. This is because processes with long execution times will be given a higher response ratio, which can lead to poor system responsiveness and user dissatisfaction.

Inability to Handle Dynamic Workloads: HRRN scheduling does not adapt well to changing workloads. If a system experiences a sudden increase in the number of processes, the response ratio of existing processes may decrease, leading to longer waiting times and reduced system performance.

Complexity: HRRN scheduling can be a complex algorithm to implement and maintain, especially in large and complex systems. The algorithm requires maintaining a priority queue and calculating response ratios, which can be challenging to implement efficiently.

Bias Towards Shorter Processes: HRRN scheduling tends to favor shorter processes over longer ones, which can lead to longer waiting times for long-running processes. This can be especially problematic in systems with a mix of short and long-running processes.

Characteristics of HRRN CPU Scheduling

Non Pre-emptive: HRRN scheduling is a non-preemptive algorithm, meaning that once a process is assigned the CPU, it will continue to run until it completes or voluntarily yields the CPU.

Response Ratio: The response ratio of a process is the primary factor that determines its priority for execution. The response ratio depends on both the waiting time and the service time of the process, so processes that have been waiting for a long time will have a higher priority.

Overhead: The response ratio calculation for each process can be computationally expensive, especially if there are a large number of processes in the system. This overhead can impact the overall performance of the system.

Performance: HRRN scheduling can achieve good performance in terms of average waiting time and turnaround time, especially in systems with a mix of short and long-running processes. However, it may not be as efficient as other scheduling algorithms in systems with a high degree of concurrency.

Deterministic: HRRN scheduling is a deterministic algorithm, meaning that if the same set of processes arrives at the scheduler in the same order multiple times, the same sequence of process execution will be generated each time.

Context Switching: Context switching in HRRN scheduling is infrequent, as the algorithm is non-preemptive. However, if a process with a higher response ratio arrives while another process is executing, a context switch will occur.

Low Burst Time Processes: HRRN scheduling is particularly suitable for systems with a mix of long and short-running processes. However, it may not be as effective in systems with many short burst time processes, as the response ratio calculation will heavily prioritize long-running processes.

HRRN Scheduling Program in C

Here is an example program that implements the Highest Response Ratio Next (HRRN) scheduling algorithm in C:

#include<stdio.h>

struct process {

    int pid;

    int arrival_time;

    int burst_time;

    int wait_time;

    int turnaround_time;

    float response_ratio;

};

void hrrn(struct process proc[], int n) {

    int i, j;

    float max_ratio, sum_wait_time = 0, sum_turnaround_time = 0;

    struct process temp;

    // calculate response ratio for each process

    for(i = 0; i < n; i++) {

        proc[i].response_ratio = 1 + (float)(proc[i].wait_time) / (float)(proc[i].burst_time);

    }

    // sort processes in descending order of response ratio

    for(i = 0; i < n – 1; i++) {

        for(j = i + 1; j < n; j++) {

            if(proc[i].response_ratio < proc[j].response_ratio) {

                temp = proc[i];

                proc[i] = proc[j];

                proc[j] = temp;

            }

        }

    }

    printf(“\nProcess\tArrival Time\tBurst Time\tWait Time\tTurnaround Time\tResponse Ratio”);

    // calculate wait time, turnaround time, and print results

    for(i = 0; i < n; i++) {

        proc[i].wait_time = (i == 0) ? 0 : (proc[i – 1].burst_time + proc[i – 1].wait_time);

        proc[i].turnaround_time = proc[i].burst_time + proc[i].wait_time;

        sum_wait_time += proc[i].wait_time;

        sum_turnaround_time += proc[i].turnaround_time;

        printf(“\n%d\t%d\t\t%d\t\t%d\t\t%d\t\t\t%.2f”, proc[i].pid, proc[i].arrival_time,          proc[i].burst_time, proc[i].wait_time, proc[i].turnaround_time, proc[i].response_ratio);

    }

    printf(“\n\nAverage wait time: %.2f”, sum_wait_time / n);

    printf(“\nAverage turnaround time: %.2f”, sum_turnaround_time / n);

}

int main() {

    int n, i;

    printf(“Enter number of processes: “);

    scanf(“%d”, &n);

    struct process proc[n];

    for(i = 0; i < n; i++) {

        printf(“\nProcess %d:\n”, i + 1);

        proc[i].pid = i + 1;

        printf(“Arrival time: “);

        scanf(“%d”, &proc[i].arrival_time);

        printf(“Burst time: “);

        scanf(“%d”, &proc[i].burst_time);

    }

    hrrn(proc, n);

    return 0;

}

In this program, the struct process represents a process with its pid, arrival_time, burst_time, wait_time, turnaround_time, and response_ratio. The hrrn function implements the HRRN scheduling algorithm, which first calculates the response ratio for each process and then sorts the processes in descending order of their response ratios. The function then calculates the wait time and turnaround time for each process, and prints the results. Finally, the main function reads in the number of processes and their arrival and burst times, and calls the hrrn function to schedule the processes.

HRRN Scheduling Program in C++

Here’s an example program in C++ that implements the Highest Response Ratio Next (HRRN) scheduling algorithm. The program assumes that the arrival time of all the processes is 0.

#include <iostream>

#include <queue>

#include <algorithm>

using namespace std;

struct Process {

    int pid;

    int burst_time;

    int waiting_time;

    int response_ratio;

    Process(int pid, int burst_time) {

        this->pid = pid;

        this->burst_time = burst_time;

        this->waiting_time = 0;

        this->response_ratio = 0;

    }

};

bool operator<(const Process& a, const Process& b) {

    return a.response_ratio < b.response_ratio;

}

void HRRN(vector<Process>& processes) {

    int n = processes.size();

    int total_waiting_time = 0;

    int total_turnaround_time = 0;

    sort(processes.begin(), processes.end(), [](const Process& a, const Process& b) {

        return a.burst_time < b.burst_time;

    });

    priority_queue<Process> pq;

    int current_time = 0;

    while (!pq.empty() || !processes.empty()) {

        while (!processes.empty() && processes.front().burst_time <= current_time) {

            pq.push(processes.front());

            processes.erase(processes.begin());

        }

        if (!pq.empty()) {

            Process current_process = pq.top();

            pq.pop();

            current_process.waiting_time = current_time;

            total_waiting_time += current_process.waiting_time;

            total_turnaround_time += current_time + current_process.burst_time;

            current_time += current_process.burst_time;

        } else {

            current_time = processes.front().burst_time;

        }

        for (Process& p : processes) {

            p.response_ratio = (current_time – p.waiting_time) / p.burst_time;

        }

        sort(processes.begin(), processes.end());

    }

    double avg_waiting_time = (double) total_waiting_time / n;

    double avg_turnaround_time = (double) total_turnaround_time / n;

    cout << “Average waiting time: ” << avg_waiting_time << endl;

    cout << “Average turnaround time: ” << avg_turnaround_time << endl;

}

int main() {

    vector<Process> processes = {

        {1, 6},

        {2, 8},

        {3, 7},

        {4, 3},

        {5, 4},

        {6, 5},

        {7, 2},

        {8, 1},

        {9, 5},

        {10, 3}

    };

    HRRN(processes);

    return 0;

}

The program defines a Process struct to store information about each process, including its process ID (pid), burst time (burst_time), waiting time (waiting_time), and response ratio (response_ratio). The < operator is overloaded to compare processes based on their response ratio.

The HRRN function takes a vector of Process objects as input and implements the HRRN scheduling algorithm. It first sorts the processes in ascending order of burst time. It then initializes a priority queue to store the processes that are ready to run. The algorithm iterates until all processes have completed their execution or are in the priority queue.

During each iteration, the algorithm checks for processes that have arrived and adds them to the priority queue. It then checks for the process with the highest response ratio in the priority queue and executes it. The waiting time and turnaround time of the executed process are calculated and added to the total waiting time and total turnaround time

Wrapping Up

Now we can hope that you have been fully aware about what is Highest Response Ratio Next scheduling algorithm; involving with HRRN scheduling examples and programs with their outputs. If this content is helpful for you, then please share it along with your friends, family members or relatives over social media platforms like as Facebook, Instagram, Linked In, Twitter, and more.

Also Read: Process Life Cycle in Operating System | Process State in OS

If you have any experience, tips, tricks, or query regarding this issue? You can drop a comment!

Thanks for Reading!!

Leave a Reply

Your email address will not be published. Required fields are marked *