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

 

25.jpg

 

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:

 

  26.jpg

 

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:

 

27.jpg

 

At the last, HRRN selects final process to executes:

 

  28.jpg

 

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

Contributor's Info

Created:
0Comment