第二讲作业调度算法主讲教师：张新彩
3.2 作业调度算法
3.2.1 先来先服务算法
3.2.2 短作业 / 进程优先算法
3.2.3 优先级调度算法
3.2.4 高响应比优先调度算法
3.2.1 先来先服务算法
▪适用于作业调度
•从后备作业队列中选择一个或多个最先进入的作业，将
它们调入内存，为它们分配资源、创建进程，然后放入
就绪队列。

▪适用于进程调度
•从就绪进程队列中选择一个最先进入的进程，为之分配
处理机，使之投入运行；直到运行完成或阻塞，才会让
出处理机。

3.2.1 先来先服务算法
4
平均周转时间为（4+6+10+11+14）/5=9
作业A 、B 、C 、D 、E 分别在0、1、2、3、4时刻到达，需要的服务时间分别为4、3、5、2、4。

请用先来先服务算法计算它们的完成时间、周转时间、带权周转时间和平均周转时间。

作业 名 到达 时间 服务 时间 开始执 行时间 完成 时间 周转 时间 带权周 转时间
A
4
B 1 3
C 2 5
D 3 2
E 4 4 4 7 12 14 1
2 2 5.5 0 4 7 12 4 6 10 11 18 3.5 14
14 简单易实现，有利于长作业，不利于短作业
3.2.2 短作业 / 进程优先算法
▪短作业优先（SJF）
•从后备队列中选择一个或多个估计运行时间最短的作业
调入内存。

▪短进程优先（SPF）
•从就绪队列中选出一个估计运行时间最短的进程，将处
理机分配给它，使它立即执行。

3.2.2 短作业 / 进程优先算法
6
平均周转时间为（4+3+8+9+16）/5=8
作业 名
到达 时间
服务 时间
开始执 行时间
完成 时间
周转 时间
带权周 转时间
作业A 、B 、C 、D 、E 分别在0、1、2、3、4时刻到达，需要的服务时间分别为4、3、5、2、4。

请用短作业优先算法计算它们的完成时间、周转时间、带权周转时间和平均周转时间。

4 1 0 4 6 1.
5 4 3 9
8/3 6 8 13 9/4 9 9 18 16/5
13 16 D 3 2 B 1 3 E 4 4
C 2 5 A 0 4
3.2.3 优先级调度算法
▪适用于作业调度
•从后备队列中选择若干个优先权最高的作业装入内存。

▪适用于进程调度
•根据进程的紧迫程度赋予每个进程一个优先权，选择就
绪队列中一个优先权最高的进程投入执行。

3.2.3 优先级调度算法
▪1. 优先级调度算法的类型
•（1）非抢占式优先权调度算法
▪把CPU分配给优先权最高的进程后，运行直至完成或发生某事件
而阻塞时，才将CPU分配给其他进程。

•（2）抢占式优先权调度算法
▪在执行期间出现了优先权更高的进程，系统将暂停当前进程，并
将CPU分配给新到的优先权最高的进程。

3.2.3 优先级调度算法
抢占的原则有：
•优先权原则
•短作业（进程）优先原则
•时间片原则
▪2. 优先权的类型
•（1）静态优先权
▪是在创建进程时确定的，且在进程的整个运行期间保持不变。

•（2）动态优先权
▪优先权可以随进程的推进或等待时间的增加而改变。

3.2.3 优先级调度算法
t(等待)
优先权
t(运行)
优先权
3.2.3 优先级调度算法
平均周转时间为（4+4+11+15+15）/5=49/4 进程A 、B 、C 、D 、E 分别在0、1、2、3、4时刻到达，需要的服务时间分别为4、3、5、2、4，优先数分别为2、4、3、5、1，规定优先数越小，优先级越高，请用非抢占式优先级算法计算各进程的完成时间、周转时间和平均周转时间。

进程 名 到达 时间 服务 时间 开始执 行时间 完成 时间 周转
时间
4
16
13
18 0 13 8 16 4 15 11 15
8
4 4 A 0 4 E 4 4 C 2
5 B 1 3 D 3 2
▪思想：优先级随着等待时间的增加而提高。

▪优先级的变化规律为：
▪优点：照顾短作业（进程）；考虑到达次序；兼顾长作业（进程）
3.2.4 高响应比优先调度算法
服务时间服务时间等待时间响应比+=
3.2.4 高响应比优先调度算法
进程A 、B 、C 、D 、E 分别在0、1、2、3、4时刻到达，需要的服务时间分别为4、3、5、2、4。

请用高响应比优先调度算法计算各进程的完成时间、周转时间和平均周转时间。

平均周转时间为（4+6+6+12+14）/5=42/5 进程
名 到达 时间 服务 时间 开始执 行时间 完成 时间 周转 时间
4
14 9
18 0 9 7 14 4 12 6 14
7
4 6 A 0 4 B 1 3 D 3 2 C 2
5 E 4 4
本节小结
▪1.理解每种调度算法的思想、特点
▪2.掌握使用各种调度算法完成调度的计算
思考
静态优先级和动态优先级的优缺点？。