进程 完成时间 FB(q=2i-1) 周转时间 （非抢占） 带权周转 A 3 3 1 B 17 15 2.5 C 18 14 3.5 D 20 14 2.8 E 14 6 3
9
2014-12-28
答案
进程调度顺序为： A,A,B,A,C,B,D,C,E,B,B,D,D,C,C,E,B,B,D,D
进程 完成时间 周转时间 带权周转 A 4 4 1.33 B 18 16 2.67 C 15 11 2.75 D 20 14 2.8 E 16 8 4
5
到达 时间 0 2 4 6 8
服务 时间 3 6 4 5 2
2014-12-28
答案
进程调度顺序为：A、B、E、C、D
进程 完成时间 SPF(非抢占) 周转时间 带权周转 A 3 3 1 B 9 7 1.17 C 15 11 2.75 D 20 14 2.8 E 11 3 1.5
6
2014-12-28
12
2014-12-28
单项选择题
下列选项中，满足短任务优先且不会发生饥 饿现象的调度算法是（ B ）【2011年】
A、先来先服务 C、时间片轮转 B、高响应比优先 D、非抢占式短任务优先
此题考察多种作业调度算法的特点。 响应比=（执行时间+等待时间）/执行时间 高响应比算法中，作业执行时间越短其响应比越高，满足短任务优 先；而随着等待时间的增加，长期等待的作业的响应比增加，优先 级提高，可获得执行，避免饥饿。
FB(q=2i-1) (立即抢占)
10
2014-12-28
综合题
设某计算机系统具有如下的性能特征：处理 一次中断，平均耗时1ms；一次进程调度耗 时2ms；将CPU分派给选中进程耗时1ms； 定时器芯片每秒产生100次中断，请问：
1）OS将百分之几的CPU时间用于处理时钟中断？ 2）若OS采用时间片轮转调度算法，且10个时钟中 断为一个时间片，则此OS将百分之几的CPU时 间用于进程调度（包括调度、CPU分派和引起调 度的时钟中断处理时间）？
几种常见调度算法的特点
先来先服务 是否抢占 非抢占
公平，实现 简单
短作业优先 均可
平均等待时 间最少，效 率最高 长作业会饥 饿，估计时 间不易确定 作业调度， 批处理系统
高响应比 均多级反馈队列 抢占 队列内算法不 一定
优点
兼顾长短作业， 兼顾长短作 有较好的响应 业 时间，可行性 强 平均等待时 间较长，上 下文切换费 时 分时系统 无
答案
进程调度顺序为： A,A,B,A,B,C,B,D,C,B,E,D,C,B,E,D,C,B,D,D
进程 完成时间 周转时间 带权周转 A 4 4 1.33 B 18 16 2.67 C 17 13 3.25 D 20 14 2.8 E 15 7 3.5
RR
8
2014-12-28
答案
进程调度顺序为： A,A,A,B,C,B,B,D,E,C,C,D,D,E,B,B,B,C,D,D
缺点
不利于短作 业 均可
计算响应比 开销大 均可
适用
相当通用
4
2014-12-28
综合题
设某系统中有5个进程，它们的 到达时间和服务时间如下表所 进程 示，忽略I/O以及其他开销时间， A 若分别按非抢占的短进程优先 B （SPF）、高响应比优先 （HRRN）、时间片轮转（RR， C D 时间片=1）、非抢占的多级反 E 馈队列（FB，第i级队列的时间 片=2i-1）以及立即抢占的多级反 馈队列（ FB，第i级队列的时间 片=2i-1 ）调度算法进行CPU调 度，请给出各进程的完成时间、 周转时间、带权周转时间。
调度算法练习
Operating System
单项选择题
下列选项中，降低进程优先级的合理时机是 （ A ）【2010年】
A、进程的时间片用完 B、进程刚完成I/O，进入就绪队列 C、进程长期处于就绪队列 D、进程从就绪态转为运行态
A、进程时间片用完，进入就绪队列的队尾，优先级最低，另外在 使用多级反馈队列算法的系统中，时间片用完后应降级再放入下一 个队列 B、刚完成I/O的进程本来就进入了就绪队列的末尾，即优先级最低， 因此不可再降 C、长期处于就绪队列的进程要避免饥饿，应适当提升优先级 D、处于运行态的进程不能改变优先级
答案
进程调度顺序为：A、B、C、E、D
进程 完成时间 周转时间 带权周转 A 3 3 1 B 9 7 1.17 C 13 9 2.25 D 20 14 2.8 E 15 7 3.5
HRRN
Rp =(tw+ts)/ts 其中，tw为等待时间，ts为预估的服务时间， Rp称为响应比
7 2014-12-28
11 2014-12-28
答案
1）每秒产生100次中断，则一次中断间隔10ms， 则处理中断所占比例为1/10=10%，即10ms中有 1ms用于中断处理 2）处理进程调度的时间为（1+2+1）/100=4%， 其中（1+2+1）表示调度时间2ms、中断处理时 间1ms、CPU分派1ms所耗时总和，100表示10 个10ms长的时钟中断组合成的时间片的总长度