Highest Response Ratio Next (HRRN) Scheduling
Highest Response Ratio Next (HRRN) Scheduling: It is non-preemptive scheduling algorithm. This select the process with highest ration of response and burst time. It minimizes the turn around time.
Response Time = (Latest response time) - (Arrival Time)
Response Ratio = Response time(or Turn around time) / Burst Time = (WT + BT) / BT
Example: Consider the following table:
Process no. |
Arrival Time |
Burst Time |
P1 |
0 |
6 |
P2 |
2 |
1 |
P3 |
4 |
4 |
P4 |
5 |
3 |
Find the average waiting time and average turn around time using HRRN algorithm?
Solution: Using HRRN algorithm, response ratio for first term (only one process ready to execute):
Response ratio (RR) = (WT1 + BT1) / (BT1) = (0 + 6)/6 = 1
Response ratio for second term:
RR2 = (4 + 1)/1 = 5
RR3 = (2 + 4)/4 = 1.5
RR4 = (1 + 3)/3 = 1.33
HRRN algorithm selects process with highest RR P2:
Response ratio for third term:
RR3 = (3 + 4)/4 = 1.75
RR4 = (2 +3)/3 = 1.67
HRRN algorithm selects process with highest RR P3:
At the last, HRRN selects final process to executes:
Therefore,
Waiting Time |
Turn Around Time |
Completion Time |
Process No. |
Arrival Time |
Burst Time |
6 - 6 = 0 |
6 - 0 = 6 |
6 |
P1 |
0 |
6 |
5 - 1 = 4 |
7 - 2 = 5 |
7 |
P2 |
2 |
1 |
7 - 4 = 3 |
11 - 4 = 7 |
11 |
P3 |
4 |
4 |
9 - 3 = 6 |
14 - 5 = 9 |
14 |
P4 |
5 |
3 |
Average Turn Arround Time = (6 + 5 + 7 + 9) / 4 = 6.75
Average Waiting Time = (0 + 4 + 3 + 6) / 4 = 3.25