进程调度算法-高响应比优先调度算法（HRRN）

定义

为每一个作业引入一个动态优先级，即优先级是可以改变的。它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。

变化规律

Tw为等待时间，TR为服务时间。

从上式可以看出:

1. 等待时间相同，则短作业优先权高，有利于短作业。

2. 服务时间相同，等待时间越长，其优先权越高，相当于先来先服务。

3. 服务时间相对较长的作业，当其等待足够长时，便可获得处理机运行。

算法性能

优势

既考虑了作业到达的先后次序，又照顾了短作业，不会使长作业长期得

不到服务。

不足

每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。

案例

进程名	到达时间	服务时间	优先数
A	10	3
B	1	1	1
C	2	2	4
D	3	1	5
E	4	5	2

系统有如图进程，采用抢占式和非抢占式调度方法来计算平均周转时间和平均带权周转时间。（优先数越小，优先级越高。）

1. 周转时间=完成时间-到达时间
2. 平均周转时间：周转时间/进程数
3. 带权周转时间：周转时间/服务时间
4. 平均带权周转时间：带权周转时间/进程数

非抢占式

非抢占式调度(Non-preemptiveMode)进程一旦获得处理机，只有在该进程任务完成或因某事件而阻塞时，才让出处理机，决不允许某进程抢占已经分配出去的处理机。

方法

1. 最先到达的进程开始运行(A)；
2. 根据上一进程的完成时间，找到在这个完成时间内所有到达的进程，运行这些进程中**优先级最高（B>E>A>C>D）**的那个；
3. 重复2直至完成所有进程。

   

进程名	到达时间	结束时间	周转时间
A	10	10
B	1	11	10
C	2	18	16
D	3	19	16
E	4	16	12

平均周转时间：（10+10+16+16+12）/5=12.8

平均带权周转时间：（1+10+8+16+2.4）/4 =7.48

抢占式

抢占式调度(PreemptiveMode)允许调度程序根据某种原则，暂停某个占用处理机的进程，抢占已经分配出去的处理机。抢占的原则有优先权原则、短作业优先原则和时间片原则。

方法

1. 最先到达的进程开始运行(A)；
2. 在运行过程中，若后续到来的进程的优先级比该进程高，则暂时中断该进程。开始运行 优先级较高的进程；
3. 重复2直至完成所有进程。

   

进程名	到达时间	结束时间	周转时间
A	16	16
B	1	2	1
C	2	18	16
D	3	19	16
E	4	9	5

平均周转时间：（16+1+16+16+5）/5=10.8

平均带权周转时间：（1.6+1+8+16+1）/5 =5.52