介绍

最高响应比优先算法(Highest Response Rate First，HRRF) 是一种对CPU中央控制器响应比的分配的一种算法。是介于先来先服务和最短进程优先算法之间的折中算法

算法思想

总是调度响应比最大的进程

性能

先来先服务和最短进程优先算法的折中

响应比

响应比Rp =  (等待时间 + 预计运行时间)/预计运行时间 = 1 + 等待时间/预计运行时间 = 周转时间/预计运行时间

周转时间

周转时间 =  完成时间 - 到达时间

带权周转时间

带权周转时间 = 周转时间 / 运行时间

平均周转时间

平均周转时间 =  进程周转总时间 / 进程个数

平均带权周转时间

平均周转时间 =  进程带权周转总时间 / 进程个数

等待时间

等待时间 = 最后一个的完成时间 - 该进程的到达时间 

例题1

采用： 1 + (等待时间 / 运行时间) = 响应比

先执行P1

响应比：
P2 = 1 + (12.0 - 10.2) / 1.0 = 2.8
P3 = 1 + (12.0 - 10.4) / 0.5 = 4.2
P4 = 1 + (12.0 - 10.5) / 0.3 = 6
所以P4先执行

响应比：
P2：1 + (12.3 - 10.2) / 1.0 = 3.1
P3：1 + (12.3 - 10.4) / 0.5 = 4.8
P3先执行

例题2

先执行P1

响应比：
8 : 50 = 8 : 00 + (50 / 60) = 8 : 83
P2：1 + (10 : 00 - 8 : 83) / 0.5 = 3.34
P3: 1 + (10 : 00 - 9 : 00) / 0.1 = 11
P4: 1 + (10 ：00 - 9 ：83) / 0.2 = 1.85
P3先执行

响应比：
P2：1 + (10 : 06 - 8 : 50) / 0.5 = 4.12
P3: 1 + (10 : 06 - 9 : 50) / 0.2 = 3.18
P2先执行

例题3

采用：等待时间 + 运行时间 / 运行时间 = 响应比

响应比：
P2：(9 + 1) / 1 = 10
P3: (8 + 2) / 2 = 5
P4: (7 + 1) / 1 = 8
P5: (6 + 5) / 5 = 2.2
P2先执行

响应比：
P3: (9 + 2) / 2 = 5.5
P4: (8 + 1) / 1 = 9
P5: (7 + 5) / 5 = 2.4
P4先执行

响应比：
P3: (10 + 2) / 2 = 6
P5: (8 + 5) / 5 = 2.6
P3先执行

参考

• 全洛-高响应比优先调度算法（HRRN）例题详解
• 我叫RT-例题：最高响应比优先调度算法