《操作系统教程》（第三版）CH1应用题参考答案
11
有5个批处理作业A到E均已到达计算中心，其运行时间分别10、6、2、4和8
分钟；各自的优先级分别被规定为3、5、2、1和4，这里5为最高级。若不考虑系统切换开销，计算出平均作业周转时间。（1）FCFS(按A、B、C、D、E)；(2)优先级调度算法，(3)时间片轮转法(每个作业获得相同的2分钟长的时间片)。
答：
(1)FCFS调度算法
执行次序 执行时间 等待时间 周转时间 带权周转时间
A 10 0 10 1 B 6 10 16 2.66 C 2 16 18 9 D 4 18 22 5.5 E 8 22 30 3.75 作业平均周转时间 T=(10+16+18+22+30)/5=19.2 作业平均带权周转时间 W=(1+2.66+9+5.5+3.75)/5=4.38
(2)优先级调度算法
执行次序 执行时间 等待时间 周转时间 带权周转时间
B 6 0 6 1 E 8 6 14 1.75 A 10 14 24 2.4
C 2 24 26 13
D 4 26 30 7.5 作业平均周转时间 T=(6+14+24+26+30)/5=20 作业平均带权周转时间 W=(1+1.75+2.4+13+7.5)/5=5.13
(3)时间片轮转法
按次序A B C D E A B D E A B E A E A轮转执行。
作业 执行时间 等待时间 周转时间 带权周转时间
A 10 20 30 3 B 6 16 22 3.66 C 2 4 6 3
D 4 12 16 4
E 8 20 28 3.5 作业平均周转时间 T=(30+22+6+16+28)/5=20.4 作业平均带权周转时间 W=(3+3.66+3+4+3.5)/5=3.43
12 (1)假定一个处理器正在执行两道作业，一道以计算为主，另一道以输入输出为主，
11
《操作系统教程》（第三版）CH1应用题参考答案
你将怎样赋予它们占有处理器的优先级?为什么?
(2)假定一个处理器正在执行三道作业，一道以计算为主，第二道以输入输出为主，第三道为计算与输入输出均匀。应该如何赋予它们占有处理器的优先级使得系统效率较高？
答：处理器调度算法会考虑以下因素：作业响应时间要求；让CPU尽量和外围设备并行工作；限制一个计算进程长时间霸占处理器。因而，(1)I/O为主作业优先级高。(2) 输入输出为主作业优先级最高，输入输出均匀的作业其次，而计算为主作业的优先级最低。 13
请你设计一种先进的计算机体系结构，它使用硬件而不是中断来完成进程切换，则CPU需要哪些信息? 请描述用硬件完成进程切换的工作过程。
答：该计算机有一个专用硬件寄存器，它始终存放指向当前运行进程的PCB的指针。当系统中发生了一个事件，如I/O结束事件，CPU便可把运行进程的上下文保存到专用硬件寄存器指针指向的PCB中保护起来，然后，CPU转向中断向量表，找到设备中断处理程序入口，让专用硬件寄存器指针指向(设备)中断服务例程，于是，便可启动中断服务例程工作。 14
单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪一种算法性能较好？请完成下表： 作业 1 2 3 提交时间 运行时间 开始 时间 完成 时间 周转 时间 带权周 转时间 10∶00 2∶00 10∶10 1∶00 10∶25 0∶25 平均作业周转时间＝ 平均作业带权周转时间W=
答： FIFO 作业 1 2 3 提交时间 10∶00 10∶10 10∶25 运行时间 2∶00 1∶00 0∶25 开始 时间 10:00 12:00 13:00 完成 时间 12:00 13:00 13:25 周转 时间 2 2:50 3 带权周 转时间 120/120 145/60 180/25 12
《操作系统教程》（第三版）CH1应用题参考答案
平均作业周转时间＝2.61 平均作业带权周转时间W=3.54 HRRF 作业 提交时间 运行时间 开始 时间 10:00 12:25 12:00 完成 时间 12:00 13:25 12:25 周转 时间 2 3:15 2 带权周 转时间 120/120 195/60 120/25 1 10∶00 2∶00 2 10∶10 1∶00 3 10∶25 0∶25 平均作业周转时间＝2.41 平均作业带权周转时间W=3.02 可见HRRF比FIFO要好。
15
若有如表所示四个作业进入系统，分别计算在FCFS、SJF和HRRF算法下的平均周转时间与带权平均周转时间。(时间以十进制表示)
作业 提交时间(时) 估计运行时间(小时) 开始执行时间(时) 1 8.00 2.00 8.00 2 8.50 0.50 10.30 3 9.00 0.10 10.00 4 9.50 0.20 10.10 答：
FCFS SJF HRRF 作业 开始 完成 周转 开始 完成 周转 开始 完成 周转 时间 时间 时间 时间 时间 时间 时间 时间 时间 1 8.00 10.00 2.00 8.00 10.00 2.00 8.00 10.00 2.00 2 10.00 10.50 2.00 10.30 10.80 2.30 10.10 10.60 2.10 3 10.50 10.60 1.60 10.00 10.10 1.10 10.00 10.10 1.10 4 10.60 10.80 1.30 10.10 10.30 0.80 10.60 10.80 1.30 平均周 T=1.725 T=1.55 T=1.625 转时间= 带权平均 W=6.875 W=5.15 W=5.675 周转时间=
13
《操作系统教程》（第三版）CH1应用题参考答案
16
Kleinrock提出一种动态优先权算法：进程在就绪队列等待时，其优先权以速率α变化； 当进程在处理器上运行，时其优先权以速率β变化。给参数α、β赋以不同值可得到不同算法。(1)若α>β>0是什么算法？(2) 若α<β<0是什么算法
(1)
是先进先出算法。因为在就绪队列中的进程比在CPU上运行的进程的优先数提高得快，故进程切换时，先进入就绪队列的进程优先权就越高。
是后进先出算法。因为在就绪队列中的进程比在CPU上运行的进程的优先权下降得快，故后进入就绪队列的进程此先进入的进程的优先权高。
答：
(2)
17
17 有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运行时间由下表给出：
作业 提交时间 估计运行时间(分钟) 1 8：00 60 2 8：20 35 3 8：25 20 4 8：30 25 5 8：35 5 6 8：40 10 系统采用SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被更短作业抢占。(1)分别给出6个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。(2)计算平均作业周转时间。 答：
执行次序 提交时间 执行时间 开始时间 完成时间 周转时间 J1 8:00 60 8:00 9:00 60 J5 8:35 5 9:00 9:05 30 J6 8:40 10 9:05 9:15 35 J3 8:25 20 9:15 9:35 70 J4 8:30 25 9:35 10:00 90 J2 8:20 35 10:00 10:35 135 作业平均周转时间T=(60+30+35+70+90+135)/6=70 14
《操作系统教程》（第三版）CH1应用题参考答案
注意，J1被调度运行后，直到它执行结束，才会引出作业调度程序工作。所
以，J2至J6虽在J1执行期间进入，但未被调度，均在等待。当J1撤离后，作业调度程序工作，按SJF算法，显然有执行次序：J5、J6、J3、J4、和J2。
18 有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程
调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。
作业名 到达时间 估计运行时间 优先数
A 10：00 40分 5
B 10：20 30分 3
C 10：30 50分 4
D 10：50 20分 6
(1)列出所有作业进入内存时间及结束时间。 (2)计算平均周转时间。 答：
每个作业运行将经过两个阶段：作业调度(SJF算法)和进程调度(优先数抢占式)。另外，批处理最多容纳2道作业，更多的作业将在后备队列等待。
时间(分钟) 10:00 10:20 10:30 10:50 11:10 12:00 12:20 A B A C D CPU A D D 进程就绪队列 C 作业后备队列
(1) 10:00，作业A到达并投入运行。
(2) 10:20，作业B到达且优先权高于作业A，故作业B投入运行而作业A在就绪队
列等待。
(3) 10:30，作业C到达，因内存中已有两道作业，故作业C进入作业后备队列等待。 (4) 10:50，作业B运行结束，作业D到达，按SJF短作业优先算法，作业D被装入
内存进入就绪队列。而由于作业A的优先级高于作业D，故作业A投入运行。 (5) 11:10，作业A运行结束，作业C被调入内存，且作业C的优先级高于作业D，
故作业C投入运行。
(6) 12:00，作业C运行结束，作业D投入运行。 (7) 12:20，作业D运行结束。
作业 进入内存时间 运行结束时间
A 10:00 11:10
B 10:20 10;50 C 11:10 12:00 15 D 10:50 12:20