操作系统之HRRN - 最高响应比调度
一、简述
最高响应比调度的含义:
(1)最高响应比优先调度算法(Highest Response Ratio Next)是一种对CPU中央控制器响应比的分配的一种算法。HRRN是介于FCFS(先来先服务算法)与SJF(短作业优先算法)之间的折中算法,既考虑作业等待时间又考虑作业运行时间,既照顾短作业又不使长作业等待时间过长,改进了调度性能。
(2)高响应比优先调度算法的基本思想是把CPU分配给就绪队列中响应比最高的进程。
调度算法的适用场景:
- 批处理系统,主要用于作业调度
二、例题
在道数不受限制的多道程序系统中,作业进入系统的后备队列时立即进行作业调度。现有4个作业进入系统,有关信息为:
作业名 | 提交时刻(进入后备队列时刻) | 运行时间(执行时间/min) |
---|---|---|
p1 | 8.8 | 1.5 |
p2 | 9.0 | 0.4 |
p3 | 9.5 | 1.0 |
(1)按顺序到达
-
p1最先进入队列,p1先执行,执行1.5,到8.8+1.5=10.3,此时p1执行完,p2、p3也全部进入队列且待执行,计算响应比p2=1+((10.3-9.0)/0.4)=3.25,p3=((10.3-9.5)/1.0)=0.8,p2的响应比大,p2先执行,再执行p3
-
p2执行,开始时间为上一个进程的完成时间为10.3,执行0.4,到10.7
-
p3执行,开始时间为上一个进程的完成时间为10.7,执行1.0,到11.7
答:
作业名 | 提交时刻 | 运行时间 | 开始时刻 | 完成时刻 | 周转时间 | 带权周转时间 |
---|---|---|---|---|---|---|
p1 | 8.8 | 1.5 | 8.8 | 10.3 | 1.5 | 1 |
p2 | 9.0 | 0.4 | 10.3 | 10.7 | 1.7 | 4.25 |
p3 | 9.5 | 1.0 | 10.7 | 11.7 | 2.2 | 2.2 |
平均周转时间T = (1.5+1.2+2.2)/3=1.63
平均带权周转时间T = (1+4.25+2.2)/3=2.48
(2)全部到达
-
全部到达则全部计算响应比再执行
响应比p1=1+(9.5-8.8)/1.5=1.46 响应比p2=1+(9.5-9.0)/1.5=2.25 响应比p3=1+(9.5-9.5)/1.5=1
p2先执行,执行0.4,执行到9.9,此时计算p1,p3的响应比
响应比p1=(9.9-8.8)/1.5+1=1.73 响应比p3=(9.9-9.5)/1+1=1.4
p1先执行,执行1.5,执行到11.4
p3执行,执行1.0,执行到12.4
-
222
答:
作业名 | 提交时刻 | 运行时间 | 开始时刻 | 完成时刻 | 周转时间 | 带权周转时间 |
---|---|---|---|---|---|---|
p1 | 8.8 | 1.5 | 9.9 | 11.4 | 2.6 | 1.73 |
p2 | 9.0 | 0.4 | 9.5 | 9.9 | 0.9 | 2.25 |
p3 | 9.5 | 1.0 | 11.4 | 12.4 | 2.9 | 2.9 |
平均周转时间T = (2.6+0.9+2.9)/3=2.13
平均带权周转时间T = (1.73+2.25+2.9)/3=2.29
三、公式
-
完成时刻 = 开始时刻 + 运行时间
-
周转时间 = 完成时间 - 到达时间(进入时间 / 提交时刻)
-
带权周转时间 = 周转时间 / 运行时间
-
响应比 =(等待时间+运行时间)/ 运行时间
-
按顺序到达:
响应比=1+等待时间/运行时间 等待时间=前一个进程的完成时间-当前线程的提交时刻 响应比=1+(finishTime-enterTime)/runningTime
-
全部到达
响应比=1+等待时间/运行时间 等待时间=最后一个的提交时间-该作业到达的时刻 响应比=1+(finishTime-enterTime)/runningTime
-