操作系统 孙钟秀课后答案

《操作系统教程》（第三版）CH1应用题参考答案

CH1 应用题参考答案

1 有一台计算机，具有1MB内存，操作系统占用200KB，每个用户进程各占200KB。

如果用户进程等待I/O的时间为80%，若增加1MB内存，则CPU的利用率提高多少？ 答：设每个进程等待I/O的百分比为P，则n个进程同时等待I/O的概率是Pn ，当n个

进程同时等待I/O期间CPU是空闲的，故CPU的利用率为1-Pn 。由题意可知，除去操作系统，内存还能容纳4个用户进程，由于每个用户进程等待I/O的时间为80%，故：

CPU利用率=1-(80%)4 =0.59

若再增加1MB内存，系统中可同时运行9个用户进程，此时： CPU利用率=1-(80%)9 =0.87 故增加1MB内存使CPU的利用率提高了47%： 87%÷59%=147% 147%-100%=47%

2 一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A

先开始做，程序B后开始运行。程序A的运行轨迹为：计算50ms、打印100ms、再计算50ms、打印100ms，结束。程序B的运行轨迹为：计算50ms、输入80ms、再计算100ms，结束。试说明(1)两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？为什么会等待？(2)程序A、B有无等待CPU的情况？若有，指出发生等待的时刻。 答：画出两道程序并发执行图如下：

A计算 B计算 A计算 B计算 处理器 B输入 输入机

A打印 A打印 打印机

计算 打印 计算 打印 程序A

计算 输入 计算 程序B 一 时间(ms)

0 50 100 150 180 200 250 300

(1) 两道程序运行期间，CPU存在空闲等待，时间为100至150ms之间(见图中有色部

分)。

(2) 程序A无等待现象，但程序B有等待。程序B有等待时间段为180ms至200ms间(见

图中有色部分)。

1

《操作系统教程》（第三版）CH1应用题参考答案

3 设有三道程序，按A、B、C优先次序运行，其内部计算和I/O操作时间由图给出。

A B C C11＝30ms C21=60ms C31=20ms

∣ ∣ ∣ I12＝40ms I22=30ms I32=40ms

∣ ∣ ∣ C13＝10ms C23=10ms C33=20ms

试画出按多道运行的时间关系图（忽略调度执行时间）。完成三道程序共花多少时间？比单道运行节省了多少时间？若处理器调度程序每次进行程序转换化时1ms，试画出各程序状态转换的时间关系图。

答：

1） 忽略调度执行时间，多道运行方式（抢占式）：

时间 0 3 7 8 10 12 13 14 17 19 单位10 ms

I/O I12 I22 I32 CPU C11 C21 C13 C21 C31 C23 C33

抢占式共用去190ms，单道完成需要260ms， 节省70ms。

忽略调度执行时间，多道运行方式（非抢占式）：

时间 0 3 7 9 10 12 13 14 16 18 单位10 ms

I/O I12 I22 I32 CPU C11 C21 C13 C31 C23 C33

非抢占式共用去180ms，单道完成需要260ms， 节省80ms。

2） 调度执行时间1ms，多道运行方式（抢占式）：

时间 0 303132 71727374 8485 105107 127 136137 147 177178 198 单位1ms

I/O I12 I22 I32 CPU C11 C21 C13 C21 C31 C23 C33

OS

调度执行时间1ms，多道运行方式（非抢占式）：

时间 0 303132 7172 939495 105106 124125127129 139 168169 189 单位1ms

I/O I12 I22 I32 CPU C11 C21 C21 C13 C31 C31 C23 C33 OS

4 在单CPU和两台I/O(I1,I2)设备的多道程序设计环境下，同时投入三个作业运行。它

2

《操作系统教程》（第三版）CH1应用题参考答案

们的执行轨迹如下：

Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)、I2(20ms) Job2：I1(20ms)、CPU(20ms)、I2(40ms)

Job3：CPU(30ms)、I1(20ms)、CPU(10ms)、I1(10ms)

如果CPU、I1和I2都能并行工作，优先级从高到低为Job1、Job2和Job3，优先级高的作业可以抢占优先级低的作业的CPU，但不抢占I1和I2。试求：(1)每个作业从投入到完成分别所需的时间。(2) 从投入到完成CPU的利用率。(3)I/O设备利用率。 答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)： U CP Job3 Job2 Job1 Job2 Job3 Job1 Job3 I1 Job2 Job1 Job3 Job3 I2 Job1 Job2 Job1 Job1 I2 CPU I1 CPU I2 I1 Job2CPU CPU I2 Job3 CPU CPU I1 CPU I1 时间 (ms) 0 10 20 30 40 50 60 70 80 90 100 110 (1) Job1从投入到运行完成需110ms，Job2从投入到运行完成需90ms，Job3从投入到

运行完成需110ms。

(2) CPU空闲时间段为：60ms至70ms，80ms至90ms，100ms至110ms。所以CPU利

用率为(110-30)/110=72.7%。

(3) 设备I1空闲时间段为：20ms至40ms，90ms至100ms，故I1的利用率为

(110-30)/110=72.7%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(110-20)/110=81.8%。

5 在单CPU和两台I/O(I1,I2)设备的多道程序设计环境下，同时投入三个作业运行。它

们的执行轨迹如下：

Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms) Job2：I1(20ms)、CPU(20ms)、I2(40ms) Job3：CPU(30ms)、I1(20ms)

如果CPU、I1和I2都能并行工作，优先级从高到低为Job1、Job2和Job3，优先级高的作业可以抢占优先级低的作业的CPU。试求：(1)每个作业从投入到完成分别所需的时间。(2) 每个作业投入到完成CPU的利用率。(3)I/O设备利用率。 答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：

3

《操作系统教程》（第三版）CH1应用题参考答案

CPU I1 I2 Job1 Job2 Job3 时间(ms) Job3 Job2 Job1 I2 I1 CPU Job2 Job1 Job2 Job3 Job1 Job3 Job1 Job2 CPU CPU I1 CPU I2 CPU CPU I1 0 10 20 30 40 50 60 70 80 90

(1) Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运

行完成需90ms。

(2) CPU空闲时间段为：60ms至70ms，80ms至90ms。所以CPU利用率为

(90-20)/90=77.78%。

(3) 设备I1空闲时间段为：20ms至40ms，故I1的利用率为(90-20)/90=77.78%。设备I2

空闲时间段为：30ms至50ms，故I2的利用率为(90-20)/90=77.78%。

6 若内存中有3道程序A、B、C，它们按A、B、C优先次序运行。各程序的计算轨

迹为：

A：计算(20)、I/O(30)、计算(10) B：计算(40)、I/O(20)、计算(10) C：计算(10)、I/O(30)、计算(20)

如果三道程序都使用相同设备进行I/O(即程序用串行方式使用设备，调度开销忽略不计)。试分别画出单道和多道运行的时间关系图。两种情况下，CPU的平均利用率各为多少?

答：分别画出单道和多道运行的时间图 (1) 单道运行时间关系图

I/O A B C CPU A A B B C C 时间 (ms) 0 20 40 50 60 80 100 120 140 160 180 190 单道总运行时间为190ms。CPU利用率为(190-80)/190=57.9% (1) 单道运行时间关系图

4

《操作系统教程》（第三版）CH1应用题参考答案

I/O A B C CPU A B A B C B C 时间 (ms) 0 20 40 50 60 80 100 120 140

多道总运行时间为140ms。CPU利用率为(140-30)/140=78.6%

7 若内存中有3道程序A、B、C，优先级从高到低为A、B和C，它们单独运行时的

CPU和I/O占用时间为：

程序A： 60 20 30 10 40 20 20 (ms)

I/O2 CPU I/O1 CPU I/O1 CPU I/O1 程序B： 30 40 70 30 30 (ms)

I/O1 CPU I/O2 CPU I/O2 程序C： 40 60 30 70 (ms) CPU I/O1 CPU I/O2

如果三道程序同时并发执行，调度开销忽略不计，但优先级高的程序可中断优先级低的程序，优先级与I/O设备无关。试画出多道运行的时间关系图，并问最早与最迟结束的程序是哪个？每道程序执行到结束分别用了多少时间？计算三个程序全部运算结束时的CPU利用率?

答：画出三个作业并发执行的时间图： A B C A CPU I01 I02 A B C 时间(ms) C B A B B C A C A C A B cpu A B C I02 cpu I01 cpu cpu I02 I01 cpu I01 cpu I01 cpu I02 cpu cpu I01 cpu cpu I02 0 30 60 90 120 150 180 210 240 270 300 330 (1) 最早结束的程序为B，最后结束的程序为C。

(2) 程序A为250ms。程序B为220ms。程序C为310ms。 (3) CPU利用率为(310-120)/310=61.3%

5

《操作系统教程》（第三版）CH1应用题参考答案

8 有两个程序，A程序按顺序使用：(CPU)10秒、(设备甲)5秒、(CPU)5秒、(设备乙)10

秒、(CPU)10秒。B程序按顺序使用：(设备甲)10秒、(CPU)10秒、(设备乙)5秒、(CPU)5秒、(设备乙)10秒。在顺序环境下先执行A，再执行B，求出总的CPU利用率为多少? 答：程序A执行了40秒，其中CPU用了25秒。程序B执行了40秒，其中CPU用了15秒。两个程序共用了80秒，CPU化了40秒。故CPU利用率为40/80=50%。

9 在某计算机系统中，时钟中断处理程序每次执行的时间为2ms（包括进程切换开

销）。若时钟中断频率为60HZ，试问CPU用于时钟中断处理的时间比率为多少? 答：因时钟中断频率为60HZ，所以，时钟周期为：1/60s=50/3ms。在每个时钟周期中，CPU花2ms执行中断任务。所以，CPU用于时钟中断处理的时间比率为：2(50/3)=6/50=12%。

CH2 应用题参考答案

1

下列指令中哪些只能在核心态运行? (1) 读时钟日期；（2）访管指令；（3）设时钟日期；（4）加载PSW；（5）置特殊

寄存器；(6) 改变存储器映象图；(7) 启动I/O指令。

答：(3)，(4)，(5)，(6)，(7)。 2

假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。

答：因为I/O繁忙型作业忙于I/O，所以它CPU用得少，按调度策略能优先执行。同样原因一个进程等待CPU足够久时，由于它是“最近使用处理器较少的进程”，就能被优先调度，故不会饥饿。 3

并发进程之间有什么样的相互制约关系?下列日常生活中的活动是属哪种制约关系：(1)踢足球，(2)吃自助餐，(3)图书馆借书，(4)电视机生产流水线工序。

答：并发进程之间的基本相互制约关系有互斥和同步两种。其中(1)、(3)为互斥问题。(2)、(4)为同步问题。 4

在按动态优先数调度进程的系统中，每个进程的优先数需定时重新计算。在处理器不断地在进程之间交替的情况下，重新计算进程优先数的时间从何而来?

答：许多操作系统重新计算进程的优先数在时钟中断处理例程中进行，由于中断是随机的，碰到哪个进程，就插入哪个进程中运行处理程序，并把处理时间记在这个进程的账上。

6

《操作系统教程》（第三版）CH1应用题参考答案

5

若后备作业队列中等待运行的同时有三个作业J1、J2、J3，已知它们各自的运行时间为a、b、c，且满足a

答：采用短作业优先算法调度时，三个作业的总周转时间为：

T1=a+(a+b)+(a+b+c)=3a+2b+c ①

若不按短作业优先算法调度，不失一般性，设调度次序为：J2、J1、J3。则三个作业的总周转时间为：

T2=b+(b+a)+(b+a+c)=3b+2a+c ②

令②-①式得到：

T2-T1=b-a>0

可见，采用短作业优先算法调度才能获得最小平均作业周转时间。 6 若有一组作业J1，?，Jn，其执行时间依次为S1，?，Sn。如果这些作业同时到

达系统，并在一台单CPU处理器上按单道方式执行。试找出一种作业调度算法，使得平均作业周转时间最短。 答：首先，对n个作业按执行时间从小到大重新进行排序，则对n个作业：J1’，?，Jn’，它们的运行时间满足：S1’≤ S2’≤? ≤S(n-1)’≤Sn’。那么有：

T=[S1’ +( S1’+S2’)+ (S1’ + S2’+ S3’)+?+(S1’ + S2’+ S3’+?+ Sn’)]/n =[n×S1’ +( n-1)×S2’+ (n-3)×S3’]+?+ Sn’]]/n

=(S1’ + S2’+ S3’+?+ Sn’)-[0×S1’+1×S2 ’ +2×S3’ +?+(n-1) Sn’]/n

由于任何调度方式下，S1’ + S2’+ S3’+?+ Sn’为一个确定的数，而当S1’≤ S2’≤? ≤S(n-1)’≤Sn’ 时才有：0×S1’+1×S2 ’ +2×S3’ +?+(n-1) Sn’的值最大，也就是说，此时T值最小。所以，按短作业优先调度算法调度时，使得平均作业周转时间最短。 7 假定执行表中所列作业，作业号即为到达顺序，依次在时刻0按次序1、2、3、4、

5进入单处理器系统。

1） 分别用先来先服务调度算法、时间片轮转算法、短作业优先算法及非强占优先权调度算法算出各作业的执行先后次序(注意优先权高的数值小)； 2） 计算每种情况下作业的平均周转时间和平均带权周转时间。

作业号 1 2 3 4 5 答：

执行时间 10 1 2 1 5 优先权 3 1 3 4 2 7

《操作系统教程》（第三版）CH1应用题参考答案

(1) 采用FCFS算法调度作业，运作情况：

执行次序 执行时间 等待时间 开始时间 完成时间 周转时间 带权周转时间 1 10 0 0 10 10 1 2 1 10 10 11 11 11 3 2 11 11 13 13 6.5 4 1 13 13 14 14 14 5 5 14 14 19 19 3.8 作业平均周转时间 T=(10+11+13+14+19)/5=13.4 作业平均带权周转时间 W=(1+11+6.5+14+3.8)/5=7.26

(2) 采用RR算法调度作业，若令时间片长=1，各作业执行情况为：1、2、3、4、5、

1、3、5、1、5、1、5、1、5、1、1、1、1、1。

作业 执行时间 提交时间 完成时间 周转时间 带权周转时间 1 10 0 19 19 1.9 2 1 0 2 2 2 3 2 0 7 7 3.5 4 1 0 4 4 4 5 5 0 14 14 2.8 作业平均周转时间 T=(19+2+7+4+14)/5=9.2 作业平均带权周转时间 W=(1.9+2+3.5+4+2.8)/5=2.84

(3) 采用SJF算法调度作业，运作情况：

执行次序 执行时间 等待时间 开始时间 完成时间 周转时间 带权周转时间 2 1 0 0 1 1 1 4 1 1 1 2 2 2 3 2 2 2 4 4 2 5 5 4 4 9 9 1.8 1 10 9 9 19 19 1.9 作业平均周转时间 T=(1+2+4+9+19)/5=7 作业平均带权周转时间 W=(1+2+2+1.8+1.9)/5=1.74

(4) 采用非剥夺优先权算法调度作业，运作情况：

8

《操作系统教程》（第三版）CH1应用题参考答案

执行次序 优先数 执行时间 等待时间 周转时间 带权周转时间 2 1 1 0 1 1 5 2 5 1 6 1.2 1 3 10 6 16 1.6 3 3 2 16 18 9 4 4 1 18 19 19 作业平均周转时间 T=(1+6+16+18+19)/5=12 作业平均带权周转时间 W=(1+1.2+1.6+9+19)/5=6.36 8

对某系统进行监测后表明平均每个进程在I/O阻塞之前的运行时间为T。一次进程切换的系统开销时间为S。若采用时间片长度为Q的时向片轮转法，对下列各种情况算出CPU利用率。

1）Q＝∞ 2）Q＞T 3）S＜Q＜T 4＝Q＝S 5＝Q接近于0 答：

1）Q=∞ CPU利用率=T/（T+S） 2）Q>T CPU利用率=T/（T+S） 3）T>Q>S CPU利用率=Q/（Q+S） 4) Q=S CPU利用率=50% 5) Q→0 CPU利用率→0

9

有5个待运行的作业，各自预计运行时间分别是：9、6、3、5和x，采用哪种运行次序使得平均响应时间最短？

答：按照最短作业优先的算法可以使平均响应时间最短。X取值不定，按照以下情况讨论：

1） x≤3 次序为：x，3，5，6，9 2） 3

10

有5个批处理作业A到E均已到达计算中心，其运行时间分别2、4、6、8和10分钟；各自的优先级分别被规定为1、2、3、4和5，这里5为最高级。对于1）时间片轮转算法、2）优先数法、3）短作业优先算法、4）先来先服务调度算法(按到达次序C、D、B、E、A)，在忽略进程切换时间的前提下，计算出平均作业周转时间。（对1）每个作业获得相同的2分钟长的时间片；对2）到4）采用单道运行，直到结束。） 答：

(1)FCFS调度算法 执行次序 执行时间 等待时间 周转时间 带权周转时间 C 6 0 6 1

D 8 6 9 14 1.75 B 4 14 18 4.5 E 10 18 28 2.8 A 2 28 30 15 《操作系统教程》（第三版）CH1应用题参考答案

(2)优先级调度算法

执行次序 执行时间 等待时间 周转时间 带权周转时间 E 10 0 10 1 D 8 10 18 2.25

C 6 18 24 4

B 4 24 28 7 A 2 28 30 15 作业平均周转时间 T=(10+18+24+28+30)/5=22

作业平均带权周转时间 W=(1+2.25+4+7+15)/5=5.85

(3)时间片轮转法 按次序A B C D E B C D EC D E D E E轮转执行。

作业 执行时间 等待时间 周转时间 带权周转时间

A 2 0 2 1 B 4 8 12 3 C 6 14 20 3.33

D 8 18 26 3.25

E 10 20 30 3 作业平均周转时间 T=(2+12+20+26+30)/5=18 作业平均带权周转时间 W=(1+3+3.33+3.25+3)/5=2.71

(4)SJF调度算法

作业 执行时间 等待时间 周转时间 带权周转时间

A 2 0 2 1 B 4 2 6 1.5 C 6 6 12 2

D 8 12 20 2.5

E 10 20 30 3 作业平均周转时间 T=(2+6+12+20+30)/5=14 作业平均带权周转时间 W=(1+1.5+2+2.5+3)/5=2

10

《操作系统教程》（第三版）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

11

《操作系统教程》（第三版）CH1应用题参考答案

12

(1)假定一个处理器正在执行两道作业，一道以计算为主，另一道以输入输出为主，

你将怎样赋予它们占有处理器的优先级?为什么?

(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 CPU 进程就绪队列 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 B A C D A D D 作业 进入内存时间 运行结束时间 A 10:00 11:10 B 10:20 10;50 C 11:10 12:00 15 D 10:50 12:20

《操作系统教程》（第三版）CH1应用题参考答案

各作业周转时间为：作业A 70，作业B 30，作业C 90，作业D 90。平均作业周转时间为70分钟。

19

某多道程序设计系统供用户使用的主存为100K，磁带机2台，打印机1台。采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业I/O时间。现有作业序列如下：

作业号 进入输入井时间 运行时间 主存需求量 磁带需求 打印机需求

1 8:00 25分钟 15K 1 1

2 8:20 10分钟 30K 0 1

3 8:20 20分钟 60K 1 0

4 8:30 20分钟 20K 1 0 5 8:35 15分钟 10K 1 1

作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业，在主

存中的各作业平分CPU时间。现求：(1)作业被调度的先后次序?(2)全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周转时间为多少?

答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。 (2)全部作业运行结束的时间9:30。

(3)周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4为

40分钟和作业5为55分钟。 (4)平均作业周转时间=44分钟。 (5) )最大作业周转时间为55分钟。

20

某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200K，磁带机5台。采用静态方式分配外围设备，且不能移动在主存中的作业，忽略用户作业I/O时间。现有作业序列如下：

作业号 进入输入井时间 运行时间 主存需求量 磁带需求

A 8:30 40分钟 30K 3

B 8:50 25分钟 120K 1

C 9:00 35分钟 100K 2

D 9:05 20分钟 20K 3 E 9:10 10分钟 60K 1

现求：(1)FIFO算法选中作业执行的次序及作业平均周转时间?(2)SJF算法选中作业执

行的次序及作业平均周转时间? 答：

(1) FIFO算法选中作业执行的次序为：A、B、D、C和E。作业平均周转时间为63分钟。 (2) SJF算法选中作业执行的次序为：A、B、D、E和C。作业平均周转时间为58分钟。

16

《操作系统教程》（第三版）CH1应用题参考答案

CH3 应用题参考答案

1

有三个并发进程：R负责从输入设备读入信息块，M负责对信息块加工处理；P负责打印输出信息块。今提供；

1） 一个缓冲区，可放置K个信息块； 2） 二个缓冲区，每个可放置K个信息块；

试用信号量和P、V操作写出三个进程正确工作的流程。 答：

1） var B : array[0,k-1] of item ;

sread : semaphore := k ;

smanage : semaphore := 0 ;

swrite : semaphore := 0; rptr : integer := 0 ; mptr : integer := 0 ; wptr : integer := 0 ; x : item

cobegin

process reader ;

process manager;

begin begin

L1: read a message into x ; L2: P(smanage) ; P(sread) ;

x := B[mptr] ;

B[rptr]:= x ;

mptr :=(mptr+1) mod k; rptr := ( rptr+1) mod k; manage the message in x ; V(smanage) ; B[mptr] := x; goto L1 ; V(swrite) ; end ; goto L2;

end ;

coend

2） var A, B : array [0,k-1] of item ;

sput1 : semaphore := k ;

sput2 : semaphore := k ; sget1 : semaphore := 0 ; sget2 : semaphore := 0 ; put1 : integer := 0 ; put2 : integer := 0 ; get1 : integer := 0 ; get2 : integer := 0 ; cobegin

process reader ; process manager ; begin begin

L1: read a message into x ; L2: P(sget1) ; P(sput1) ; x :=A[get1];

A[put1] := x ;

get1 :=(get1+1) mod k;

17

process writer ; begin

L3: P(swrite) ; x := B[wptr] ;

wptr :=(wptr +1) mod k; V(sread) ;

Print the message in x ; goto L3 ; end ;

process writer ; begin

L3 : P(sget2) ;

x :=B[get2] ;

get2 :=(get2+1) mod k;

《操作系统教程》（第三版）CH1应用题参考答案

put1 := (put1+1) mod k ; V(sput1) ; V(sget1) ;

Goto L1 ; end ;

V(sput2) ;

Manage the message into x; Print the message in x ; P(sput2) ; Goto L3 ; B[put2] := x ; end ; put2 := (put2+1) mod k ;

V(sget2) ; Goto L2 ; end ;

coend

2

设有n个进程共享一个互斥段，如果： (1)每次只允许一个进程进入互斥段；

(2)每次最多允许m个进程（m≤n）同时进入互斥段。

试问：所采用的信号量初值是否相同？信号量值的变化范围如何？

答：所采用的互斥信号量初值不同。

1） 互斥信号量初值为1，变化范围为 [-n+1 ，1]。

当没有进程进入互斥段时，信号量值为1；当有1个进程进入互斥段但没有进程等待进入互

斥段时，信号量值为0；当有1个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-1个进程等待进入互斥段，故此时信号量的值应为-(n-1)也就是-n+1。

2） 互斥信号量初值为m，变化范围为 [-n+m ，m]。

当没有进程进入互斥段时，信号量值为m；当有1个进程进入互斥段但没有进程等待进入互

斥段时，信号量值为m-1；当有m个进程进入互斥段且没有一个进程等待进入互斥段时，信号量值为0；当有m个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-m个进程等待进入互斥段，故此时信号量的值应为-(n-m)也就是-n+m。 3

有两个优先级相同的进程P1和P2，各自执行的操作如下，信号量S1和S2初值均为0。试问P1、P2并发执行后，x、y、z的值各为多少？

P1： P2： begin begin

y:=1; x:=1; y:=y+3; x:=x+5; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.

答：现对进程语句进行编号，以方便描述。

P1： P2： begin begin

y:=1; ① x:=1; ⑤ y:=y+3; ② x:=x+5; ⑥ V(S1); P(S1);

z:=y+1; ③ x:=x+y; ⑦

18

《操作系统教程》（第三版）CH1应用题参考答案

P(S2); V(S2);

y:=z+y ④ z:=z+x; ⑧ end. end.

①、②、⑤和⑥是不相交语句，可以任何次序交错执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到语句⑦时，可以得到x=10，y=4。按Bernstein条件，语句③的执行结果不受语句⑦的影响，故语句③执行后得到z=5。最后，语句④和⑧并发执行，最后结果为：

语句④先执行：x=10，y=9，z=15。 语句⑧先执行：x=10，y=19，z=15。

4

有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100个座位。试用：1）信号量和P、V操作；2）管程，来实现用户进程的同步算法。

答：1) 使用信号量和P、V操作：

var name: array[1..100] of A;

A=record number:integer; name:string; end

for i:=1 to 100 do {A[i].number:=i; A[i].name:=null;} mutex,seatcount:semaphore; i:integer;mutex:=1;seatcount:=100; cobegin {

process readeri(var readername:string)(i=1,2,?) {

P(seatcount); P(mutex);

for i:=1 to 100 do i++

if A[i].name=null then A[i].name:=readername;

reader get the seat number =i; /*A[i].number V(mutex)

进入阅览室，座位号i，座下读书;

P(mutex);

A[i] name:=null; V(mutex); V(seatcount); 离开阅览室; } } coend.

19

《操作系统教程》（第三版）CH1应用题参考答案

5 在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1和P2，其中P1拣白子；P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出两进程P1和P2能并发正确执行的程序。

答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一

般性，若令先拣白子。

var S1,S2:semaphore;

S1:=1;S2:=0; cobegin {

process P1 begin repeat P(S1); 拣白子

V(S2); until false; end

process P2 begin repeat P(S2); 拣黑子

V(S1); until false;

end } coend.

6 设公共汽车上，司机和售票员的活动分别如下：

司机的活动：启动车辆：正常行车；到站停车。 售票员的活动：关车门；售票；开车门。

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。

答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。

20

《操作系统教程》（第三版）CH1应用题参考答案

答：(1)系统四个进程需要使用的资源数为R1各2台，R2各1台。可见资源数不足，同时

各进程申请资源在先，有可能产生死锁发生的四个条件，故系统可能产生死锁。

(2) 当三个进程执行完申请资源R1，开始执行申请资源R2时，第四个进程会因没有资

源R1而被阻塞。当三个进程执行完申请资源R2后，系统还剩1个R2资源。而这三个进程因执行申请第二个资源R1而全部被阻塞，系统进入死锁。

P1 P2 ● ● ● ●●●● P3

P4 16 假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位，R2有一个单位），它们被进程P1，P2所共享，且已知两个进程均以下列顺序使用两类资源。 →申请R1→申请R2→申请R1→释放R1→释放R2→释放R1→

试求出系统运行过程中可能到达的死锁点，并画出死锁点的资源分配图（或称进程－资源图）。 答：当两个进程都执行完第一步(都占用R1) 时，系统进入不安全状态。这时无论哪个进程执行完第二步，死锁都会发生。可能到达的死锁点：进程P1占有一个R1和一个R2，而进程P2占有一个R1。或者相反。这时己形成死锁。进程---资源图为：

P1 P1 ． ． P1

P1 17 桌上有一只盘子，最多可以容纳两个水果，每次仅能放入或取出一个水果。爸爸向盘子

中放苹果(apple)，妈妈向盘子中放桔子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。试用：(1)信号量和P、V操作，(2)管程，来实现爸爸、妈妈、

26

《操作系统教程》（第三版）CH1应用题参考答案

儿子、女儿间的同步与互斥关系。

答：(1)用信号量和P、V操作。

类似于课文中的答案，扩充如下：1) 同步信号量初值为2；2) 要引进一个互斥信号量mutex，用于对盘子进行互斥；3)盘子中每一项用橘子、苹果2个枚举值。

var

plate ARRAY[0,1] of (apple, orange);

flag0,flag1:boolean; mutex:semaphore;

sp:semaphore; /* 盘子里可以放几个水果 */

sg1，sg2:semaphore; /* 盘子里有桔子，有苹果?*/ sp := 2; /* 盘子里允许放入二个水果*/ sg1:=sg2:= 0; /* 盘子里没有桔子，没有苹果 */ flag0:=flag1:=false;mutex:=1; cobegin process son process father begin begin L3: P(sg1); L1: 削一个苹果; P(mutex); P(sp); if (flag0 & plate[0]= =桔子) then P(mutex); { x := plate[0];flag0:=false;}

if (flag0==false) then

{plate [0]:=苹果; flag0:=true;} else { plate[1]:=苹果; flag1:=true; } V(mutex);

else { x:= plate[1]; flag1:=false;} V(mutex);

V(sg2); goto L1; end;

process mother begin

L2: 剥一个桔子; P(sp); P(mutex);

if (flag0==false) then {plate [0]:=桔子; flag0:=true;}

V(sp); 吃桔子; goto L3; end;

process daughter begin

L4: P(sg2); P(mutex);

if (flag0 & plate[0]= =苹果) then { x := plate[0];flag0:=false;}

else { x:= plate[1]; flag1:=false;} V(mutex);

else { plate[1]:=桔子; flag1:=true; } V(mutex);

V(sg1); goto L2; end;

V(sp); 吃苹果; goto L4; end; coend.

18 有P1、P2、P3三个进程共享一个表格F，P1对F只读不写，P2对F只写不读，P3对F先读

后写。进程可同时读F，但有进程写时，其他进程不能读和写。用(1)信号量和P、V操作，(2)管程编写三进程能正确工作的程序。 答：(1)信号量和P、V操作。

27

《操作系统教程》（第三版）CH1应用题参考答案

这是读--写者问题的变种。其中，P3既是读者又是写者。读者与写者之间需要互斥，写者与写者之间需要互斥，为提高进程运行的并发性，可让读者尽量优先。 var rmutex,wmutex:semaphore;

rmutex:=wmutex:=1; count:integer;count:=0; cobegin {

process P1

begin

repeat

P(rmutex);

count:=count+1;

if count=1 then P(wmutex); V(rmutex); Read F; P(rmutex);

count:=count-1;

if count=0 then V(wmutex); V(rmutex); untile false; end

process P2

begin repeat

P(wmutex);

Write F; V(wmutex); untile false;

process P3

begin

repeat

P(rmutex);

count:=count+1;

if count=1 then P(wmutex); V(rmutex); Read F; P(rmutex);

count:=count-1;

if count=0 then V(wmutex); V(rmutex); P(wmutex); Write F; V(wmutex); untile false;

28

《操作系统教程》（第三版）CH1应用题参考答案

end }

coend

CH4 应用题参考答案

1 在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是： 1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。

分别用FIFO、OPT和LRU算法，对分配给程序3个页框、4个页框、5个页框和6个页框的情况下，分别求出缺页中断次数和缺页中断率。

答： 页框数 FIFO LRU OPT 3 16 15 11 4 14 10 8 5 12 8 7 6 9 7 7

只要把表中缺页中断次数除以20，便得到缺页中断率。

2 在一个请求分页虚拟存储管理系统中，一个作业共有5页，执行时其访问页面次序为：(1) 1、4、3、1、2、5、1、4、2、1、4、5。

(2) 3、2、1、4、4、5、5、3、4、3、2、1、5。

若分配给该作业三个页框，分别采用FIFO和LRU面替换算法，求出各自的缺页中断次数和缺页中断率。

答：(1) 采用FIFO为9次，9/12=75%。采用LRU为8次，8/12=67%。 (2) 采用FIFO和LRU均为9次，9/13=69%。

3 一个页式存储管理系统使用FIFO、OPT和LRU页面替换算法，如果一个作业的页面走向为：

(1) 2、3、2、1、5、2、4、5、3、2、5、2。 (2) 4、3、2、1、4、3、5、4、3、2、1、5。 (3 )1、2、3、4、1、2、5、1、2、3、4、5。 当分配给该作业的物理块数分别为3和4时，试计算访问过程中发生的缺页中断次数和缺页中断率。

答：(1) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为7次，

7/12=58%。使用OPT为6次，6/12=50%。

作业的物理块数为4块，使用FIFO为6次，6/12=50%。使用LRU为6次，6/12=50%。使用OPT为5次，5/12=42%。

(2) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为10次，

29

《操作系统教程》（第三版）CH1应用题参考答案

10/12=83%。使用OPT为7次，7/12=58%。

作业的物理块数为4块，使用FIFO为10次，10/12=83%。使用LRU为8

次，8/12=66%。使用OPT为6次，6/12=50%。

其中，出现了Belady现象，增加分给作业的内存块数，反使缺页中断率上升。

4 在可变分区存储管理下，按地址排列的内存空闲区为：10K、4K、20K、18K、7K、9K、12K和15K。对于下列的连续存储区的请求：(1)12K、10K、9K，(2)12K、10K、15K、18K试问：使用首次适应算法、最佳适应算法、最差适应算法和下次适应算法，哪个空闲区被使用？

答：(1) 空闲分区如图所示。 分区号 分区长

1 10KB

2 4KB

3 20KB

4 18KB

5 7KB

6 9KB

7 12KB

8 15KB

1)首次适应算法

12KB选中分区3，这时分区3还剩8KB。10KB选中分区1，恰好分配故应删去分

区1。9KB选中分区4，这时分区4还剩9KB。 2)最佳适应算法

12KB选中分区7，恰好分配故应删去分区7。10KB选中分区1，恰好分配故应删

去分区1。9KB选中分区6，恰好分配故应删去分区6。 3)最差适应算法

12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。

9KB选中分区8，这时分区3还剩6KB。 4)下次适应算法 12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。9KB选中分区6，恰好分配故应删去分区6。 (2) 原始分区情况同上图。 1)首次适应算法

12KB选中分区3，这时分区3还剩8KB。10KB选中分区1，恰好分配故应删去分

区1。15KB选中分区4，这时分区4还剩3KB。最后无法满否18KB的申请，应该等待。

2)最佳适应算法

12KB选中分区7，恰好分配故应删去分区7。10KB选中分区1，恰好分配故应删

去分区1。15KB选中分区8，恰好分配故应删去分区8。18KB选中分区4，恰好分配故应删去分区4。 3)最差适应算法

12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。

30

《操作系统教程》（第三版）CH1应用题参考答案

15KB选中分区8，恰好分配故应删去分区8。最后无法满否18KB的申请，应该等

待。

4)下次适应算法 12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。15KB选中分区8，恰好分配故应删去分区8。最后无法满否18KB的申请，应该等待。

5 给定内存空闲分区，按地址从小到大为：100K、500K、200K、300K和600K。现有用户进程依次分别为212K、417K、112K和426K，(1)分别用first-fit、best-fit和worst-fit算法将它们装入到内存的哪个分区?(2) 哪个算法能最有效利用内存?

答：按题意地址从小到大进行分区如图所示。

分区号 分区长

1 100KB

2 500KB

3 200KB

4 300KB

5 600KB

(1) 1)first-fit 212KB选中分区2，这时分区2还剩288KB。417KB选中分区5，这

时分区5还剩183KB。112KB选中分区2，这时分区2还剩176KB。426KB无分区能满足，应该等待。

2)best-fit 212KB选中分区4，这时分区4还剩88KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区3，这时分区3还剩88KB。426KB选中分区5，这时分区5还剩174KB。

3)worst-fit 212KB选中分区5，这时分区5还剩388KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区5，这时分区5还剩176KB。426KB无分区能满足，应该等待。

(2) 对于该作业序列，best-fit算法能最有效利用内存

6 一个32位地址的计算机系统使用二级页表，虚地址被分为9位顶级页表，11位二级页表和偏移。试问：页面长度是多少？虚地址空间共有多少个页面？

答：由于32-9-11=12，所以，页面大小为4KB，页面的个数为220 个。

7 一进程以下列次序访问5个页：A、B、C、D、A、B、E、A、B、C、D、E；假定使用FIFO替换算法，在内存有3个和4个空闲页框的情况下，分别给出页面替换次数。

答：内存有3个和4个空闲页框的情况下，页面替换次数为9次和10次。出现了Belady现象，增加分给作业的内存块数，反使缺页中断率上升。

8 某计算机有缓存、内存、辅存来实现虚拟存储器。如果数据在缓存中，访问它需要Ans；如果在内存但不在缓存，需要Bns将其装入缓存，然后才能访问；如果不在内存而在辅存，需要Cns将其读入内存，然后，用Bns再读入缓存，然后才能访问。假

31

《操作系统教程》（第三版）CH1应用题参考答案

设缓存命中率为（n-1）/n，内存命中率为（m-1）/m，则数据平均访问时间是多少？ 答：

数据在缓存中的比率为：(n-1)/n

数据在内存中的比率为：(1-(n-1)/n)×(m-1)/m=(m-1)/nm 数据在辅存中的比率为：(1-(n-1)/n)×(1-(m-1)/m)=1/nm

故数据平均访问时间是=((n-1)/n)×A+((1-(n-1)/n)×(m-1)/m)×(A+B)+( (1-(n-1)/n)×(1-(m-1)/m))×(A+B+C)=A+B/n+C/nm

9 某计算机有cache、内存、辅存来实现虚拟存储器。如果数据在cache中，访问它需要20ns；如果在内存但不在cache，需要60ns将其装入缓存，然后才能访问；如果不在内存而在辅存，需要12ms将其读入内存，然后，用60ns再读入cache，然后才能访问。假设cache命中率为0.9，内存命中率为0.6，则数据平均访问时间是多少(ns)？ 答：506ns。

10 有一个分页系统，其页表存放在主存里，(1)如果对内存的一次存取要1.2微秒，试问实现一次页面访问的存取需花多少时间？(2)若系统配置了联想存储器，命中率为80×%，假定页表表目在联想存储器的查找时间忽略不计，试问实现一次页面访问的存取时间是多少？

答：(1)2.4微秒 (2) 0.8×1.2+0.2×2.4=0.76+0.48=1.24微秒

11给定段表如下：

段 号 段 首 址 段 长 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96 给定地址为段号和位移：1）[0，430]、2）[3，400]、3）[1，1]、4）[2，500]、5）[4，42]，试求出对应的内存物理地址。

答：1)449 2)1727 3)2301 4)越界 5)1994

12 某计算机系统提供24位虚存空间，主存为218B，采用分页式虚拟存储管理，页面

尺寸为1KB。假定用户程序产生了虚拟地址11123456（八进制），而该页面分得块号为100(八进制)，说明该系统如何产生相应的物理地址及写出物理地址。 答：虚拟地址11123456（八进制）转化为二进制为： 001 001 001 010 011 100 101 110

其中前面为页号，而后10位为位移：001 001 001 010 01--------1 100 101 110。由于主存大小为218B，页面尺寸为1KB，所以，主存共有256块。所以，块号为100(八进制)是合法地址，于是，物理地址为100与位移1 100 101 110并接，得到：八进制物理地址100 1 100 101 110。

32

《操作系统教程》（第三版）CH1应用题参考答案

13主存中有两个空间区如图所示，

0K 15K 125K

100K 50K

现有作业序列依次为：Job1要求30K；Job2要求70K；Job3要求50K；使用首次适应、最坏适应和最佳适应算法处理这个作业序列，试问哪种算法可以满足分配？为什么？ 答：首次适应、最坏适应算法处理这个作业序列可以满足分配，最佳适应算法不行。因为后者会分割出无法使用的碎片，浪费内存，从而，不能满足所有作业的内存需求。

14 设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048

字节，内存总共有8个存储块。试问逻辑地址至少应为多少位？内存空间有多大？ 答：逻辑地址211 ×24 ，故为15位。内存大小为23×211=214B=16KB。

15 在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现

有一逻辑地址为2F6AH，且第0、1、2页依次存在物理块10、12、14号中，问相应的物理地址为多少？ 答：因为逻辑地址长度为16位，而页面大小为4096字节，所以，前面的4位表示页号。把2F6AH转换成二进制为：0010 1111 0110 1010，可知页号为2。故放在14号物理块中，写成十六进制为：EF6AH。

16 有矩阵：VAR A：ARRAY[1‥100,1‥100] OF integer；元素按行存储。在

一虚存系统中，采用LRU淘汰算法，一个进程有3页内存空间，每页可以存放200个整数。其中第1页存放程序，且假定程序已在内存。 程序A：

FOR i：＝1 TO 100 DO

FOR j：＝1 TO 100 DO A[i,j]：＝0； 程序B：

FOR j：＝1 TO 100 DO

FOR i：＝1 TO 100 DO A[i,j]：＝0；

分别就程序A和B的执行进程计算缺页次数。

答：题中100×100=10000个数据，每页可以存放200个整数，故一共存放在50个页面中。由于元素按行存储，第1行、第2行放在第1页，?，第99行、第100行放在第50页。故对于程序A，缺页中断为50次。对于程序B，缺页中断为5000次。

33

《操作系统教程》（第三版）CH1应用题参考答案

17 一台机器有48位虚地址和32位物理地址，若页长为8KB，问页表共有多少个

页表项?如果设计一个反置页表，则有多少个页表项? 答：因为页长8KB占用13住，所以，页表项有235个。反置页表项有219个。

18 在虚拟页式存储管理中，为解决抖动问题，可采用工作集模型以决定分给进程

的物理块数，有如下页面访问序列： …… 2 5 1 6 3 3 7 8 9 1 6 2 3 4 3 4 3 4 4 4 3 4 4 3 ……

△ t1 △ t2

窗口尺寸△＝9，试求t1、t2时刻的工作集。 答：t1时刻的工作集为：{1，2，3，6，7，8，9}。t时刻的工作集为：{3，4}。

19 有一个分页虚存系统，测得CPU和磁盘的利用率如下，试指出每种情况下的存

在问题和可采取的措施：(1)CPU利用率为13%，磁盘利用率为97% (2)CPU利用率为87%，磁盘利用率为3% (3)CPU利用率为13%，磁盘利用率为3% 。 答：(1)系统可能出现抖动，可把暂停部分进程运行。(2)系统运行正常，可增加运行进程数以进一步提高资源利用率。(3)处理器和设备和利用率均很低，可增加并发运行的进程数。

20 在一个分页虚存系统中，用户编程空间32个页，页长1KB，主存为16KB。如

果用户程序有10页长，若己知虚页0、1、2、3，已分到页框8、7、4、10 ，试把虚地址0AC5H和1AC5H转换成对应的物理地址。 答：虚地址0AC5H对应的物理地址为：12C5H。而执行虚地址1AC5H会发现页表中尚未有分配的页框而发生缺页中断，由系统另行分配页框。

21 某计算机有4个页框，每页的装入时间、最后访问时间、访问位R、修改位D

如下所示(时间用时钟点数表示)：

page loaded last ref R D 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1

分别用FIFO、LRU、二次机会算法分别淘汰哪一页? 答：(1)FIFO 淘汰page2。 (2)LRU 淘汰page1。

(3) 二次机会 淘汰page0。

22 考虑下面的程序：

for (i=0;i<20；i++)

for(j=0;j<10;j++)

34

《操作系统教程》（第三版）CH1应用题参考答案

a[i]：=a[i]×j

试举例说明该程序的空间局部性和时间局部性。

答：当数组元素a[0]，a[1]，?，a[19]存放在一个页面中时，其空间局部性和时间局部性较好，也就是说，在很短时间内执行都挂行循环乘法程序，而且数组元素分布在紧邻连续的存储单元中。当数组元素存放在不同页面中时，其时间局部性虽相同，但空间局部性较差，因为处理的数组元素分布在不连续的存储单元中。

23 一个有快表的请页式虚存系统，设内存访问周期为1微秒，内外存传送一个页面的平

均时间为5毫秒。如果快表命中率为75%，缺页中断率为10%。忽略快表访问时间，试求内存的有效存取时间。

答：快表命中率为75%，缺页中断率为10%，所以，内存命中率为15%。故内存的有效存

取时间=1×75%+2×15%+(5000+2)×10%=501.25微秒。

24 假设某虚存的用户空间为1024KB，页面大小为4KB，内存空间为512KB。已知用户的

虚页10、11、12、13页分得内存页框号为62、78、25、36，求出虚地址0BEBC(16进制)的实地址(16进制)是多少?

答：虚地址0BEBC(16进制)的二进制形式为：0000 1011 1110 1011 1100。由于页面大小为

4KB，故其中后12位是位移，所以，虚地址的页号为：11。查页表分得内存对应页框号为：78。已知内存空间为512KB，故内存共有128个页框，78是合法物理块。把78化为16进制是4E，虚地址0BEBC(16进制)的实地址(16进制)是：4EEBC。

25 某请求分页存储系统使用一级页表，假设页表全部放在主存内，： 1)若一次访问主存花120ns，那么，访问一个数据的时间是多少?

2)若增加一个快表，在命中或失误时需有20ns开销，如果快表命中率为80%，则

访问一个数据的时间为多少? 答：1) 120ns×2=240ns。

2) (120+20)×80%+(120+120+20)×20%=174ns。

26 设某系统中作业J1，J2，J3占用主存的情况如图。今有一个长度为20k的作业J4要装入

主存，当采用可变分区分配方式时，请回答：

(1) J4装入前的主存已分配表和未分配表的内容。

(2) 写出装入J4时的工作流程，并说明你采用什么分配算法。

0 10k 18k 30k 40k 54k 70k

OS J1 J2 J3

答：(1)主存已分配表共有三项，由作业J1、J2、J3占用，长度依次为：10k、30k和54k。

未分配表共有三项：空闲区1、空闲区2和空闲区3，长度依次为18k、40k和70k。

(2)作业J4装入时，采用直接分配，搜索未分配表，空闲区1不能满足。所以，要继续搜索未分配表，空闲区2可以满足J4的装入要求。

35

《操作系统教程》（第三版）CH1应用题参考答案

27 考虑下列的段表：

段号 始址 段长 0 200 500 1 890 30 2 120 100 3 1250 600 4 1800 88

对下面的逻辑地址，求物理地址，如越界请指明。1) <0,480> 2)<1,25> 3)<1,14> 4)<2,200> 5) <3,500> 6)<4,100>。

答：1)680 2)915 3)904 4)越界 5)1750 6) 越界。

28 请页式存储管理中，进程访问地址序列为：10,11,104,170,73,305,180,240,244,445,467，

366。试问1)如果页面大小为100，给出页面访问序列。2)进程若分得3个页框，采用FIFO和LRU替换算法，求缺页中断率? 答：1) 页面访问序列为1，1，2，2，1，4，2，3，3，5，5，4。 2)FIFO为5次，缺页中断率为5/12=41.6%。LRU为6次，缺页中断率为6/12=50%。 LRU反比FIFO缺页中断率高。

29 假设计算机有2M内存，其中，操作系统占用512K，每个用户程序也使用512K内

存。如果所有程序都有70%的I/O等待时间，那么，再增加1M内存，吞吐率增加多少? 答：由题意可知，内存中可以存放3个用户进程，而CPU的利用率为：1-(70%)3 =1-(0.7)3 =65.7%。再增加1M内存，可增加2个用户进程，这时CPU的利用率为：1-(70%)5 =1-(0.7)5=83.2%。故再增加1M内存，吞吐率增加了：83.2%÷65.7%-100%=27%。

30 一个计算机系统有足够的内存空间存放4道程序，这些程序有一半时间在空闲等待

I/O操作。问多大比例的CPU时间被浪费掉了? 答：(50%)4 =(1/2)4=1/16。

31 如果一条指令平均需1微秒，处理一个缺页中断另需n微秒，给出当缺页中断每k

条指令发生一次时，指令的实际执行时间。 答：(1+n/k)微秒。

32 一台计算机的内存空间为1024个页面，页表放在内存中，从页表中读一个字的开

销是500ns。为了减少开销，使用了有32个字的快表，查找速度为100ns。要把平均开销降到200ns需要的快表命中率是多少? 答：设快表命中率是x，则内存命中率为1-x。于是：500(1-x)+100x=200,解方程得x=75%。

CH5 应用题参考答案

36

《操作系统教程》（第三版）CH1应用题参考答案

1 旋转型设备上信息的优化分布能减少为若干个I/O服务的总时间。设磁鼓上分为20

个区，每区存放一个记录，磁鼓旋转一周需20毫秒，读出每个记录平均需用1毫秒，读出后经2毫秒处理，再继续处理下一个记录。在不知当前磁鼓位置的情况下：

（1）顺序存放记录1、??，记录20时，试计算读出并处理20个记录的总时间；（2）给出优先分布20个记录的一种方案，使得所花的总处理时间减少，且计算出这个方案所花的总时间。

答：定位第1个记录需10ms。读出第1个记录，处理花2ms，这时已到了第4个记录，再转过18个记录(花18ms)才能找到记录2，所以，读出并处理20个记录的总时间：

10+3+(1+2+18)×19=13+21×19=412ms 如果给出优先分布20个记录的方案为：1，8，15，2，9，16，3，10，17，4，11，

18，5，12，19，6，13，20，7，14。当读出第1个记录，花2ms处理后，恰好就可以处理记录2，省去了寻找下一个记录的时间，读出并处理20个记录的总时间： 10+3+3×19=13+247=260ms

2 现有如下请求队列：8，18，27，129，110，186，78，147，41，10，64，12；试

用查找时间最短优先算法计算处理所有请求移动的总柱面数。假设磁头当前位置下在磁道100。

答：处理次序为：100-110-129-147-186-78-64-41-27-18-12-10-8。移动的总柱面数：264。

3 上题中，分别按升序和降序移动，讨论电梯调度算法计算处理所有存取请求移动的

总柱面数。 答：升序移动次序为：100-110-129-147-186-78-64-41-27-18-12-10-8。移动的总柱面数：264。

降序移动次序为：100-78-64-41-27-18-12-10-8-110-129-147-186。移动的总柱面数：270。

4 某文件为连接文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，

均为512字节，并依次存放在50、121、75、80、63号磁盘块上。现要读出文件的1569字节，问访问哪一个磁盘块? 答：80号磁盘块

5 对磁盘存在下面五个请求： 请 求 1 2 3 4 柱 面 号 7 7 7 30 磁 头 号 2 2 1 5 扇 区 号 8 5 2 3 5 3 6 6 假如当前磁头位于1号柱面。试分析对这五个请求如何调度，可使磁盘的旋转圈数为最少？

37

《操作系统教程》（第三版）CH1应用题参考答案

答：使磁盘的旋转圈数为最少的调度次序为：5、3、2、1、和4。

6 有一具有40个磁道的盘面，编号为0~39，当磁头位于第11磁道时，顺序来到如下

磁道请求：磁道号：1、36、16、34、9、12；试用1）先来先服务算法FCFS、2）最短查找时间优先算法SSTF、3）扫描算法SCAN等三种磁盘驱动调度算法，计算

出它们各自要来回穿越多少磁道？

答：1)FCFS为111。 2)SSTF为61。 3)SCAN为60(先扫地址大的请求)，为45(先扫地址小的请求)。

7 假定磁盘有200个柱面，编号0~199，当前存取臂的位置在143号柱面上，并刚刚

完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，

94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。 (1)先来先服务算法FCFS； (2)最短查找时间优先算法SSTF； (3)扫描算法SCAN。 (4)电梯调度。

答：(1)先来先服务算法FCFS为565，依次为143-86-147-91-177-94-150-102-175-130。

(2)最短查找时间优先算法SSTF为162，依次为143-147-150-130-102-94-91-86-175-177。

(3)扫描算法SCAN为169，依次为143-147-150-175-177-199-130-102-94-91-86。 (4)电梯调度为125(先向地址大的方向)，依次为143-147-150-175-177-102-94-91-86。为148(先向地址小的方向) 依次为143-130-102-94-91-86-147-150-175-177。

8

除FCFS外，所有磁盘调度算法都不公平，如造成有些请求饥饿，试分析：(1)为什么不公平？(2)提出一种公平性调度算法。(3)为什么公平性在分时系统中是一个很重要的指标？

答：(1)对位于当前柱面的新请求，只要一到达就可得到服务，但对其他柱面的服务则不

然。如SSTF算法，一个离当前柱面远的请求，可能其后不断有离当前柱面近的请求到达而得不到服务(饥饿)。

(2)可划定一个时间界限，把这段时间内尚未得到服务的请求强制移到队列首部，

并标记任何新请求不能插到这些请求前。对于SSTF算法来说，可以重新排列这些老请求，以优先处理。

(3)可避免分时进程等待时间过长而拉长响应时间。

9

若磁头的当前位置为100柱面，磁头正向磁道号减小方向移动。现有一磁盘读写请求队列，柱面号依次为：190，10，160，80，90，125，30，20，29，140，25。若采用最短寻道时间优先和电梯调度算法，试计算出各种算法的移臂经过的柱面数？

答：采用SSTF处理次序为：100-90-80-125-140-160-190-30-29-25-20-10，总柱面数为：310。采用电梯调度处理次序为：100-90-80-30-29-25-20-10-125-140-160-190，总柱面数为：270。

38

《操作系统教程》（第三版）CH1应用题参考答案

10 若磁头的当前位置为100柱面，磁头正向磁道号增加方向移动。现有一磁盘读写请求队

列，柱面号依次为：23，376，205，132，19，61，190，398，29，4，18，40。若采用先来先服务、最短寻道时间优先和扫描算法，试计算出各种算法的移臂经过的柱面数？

答：采用先来先服务处理次序为：100-23-376-205-132-19-61-190-398-29-4-18-40，总柱

面数为：1596。

采用SSTF处理次序为：100-132-190-205-61-40-29-23-19-18-4-376-398，总柱面数为：700。

采用SCAN处理次序为：100-132-190-205-376-398-61-40-29-23-19-18-4，总柱面数

为：692。

CH6 应用题参考答案

1. 磁带卷上记录了若干文件，假定当前磁头停在第j个文件的文件头标前，现要按名读出文件i，试给出读出文件i的步骤。 答：由于磁带卷上的文件用“带标”隔开，每个文件的文件头标前后都使用了三个带标。

文 文 文 文 件 件 件 件 ? * 头 * 文件体 * 尾 * ? * 头 * 文件体 * 尾 * 标 标 标 标 ?

正常情况磁头应停在文件头标的前面，所以，只要计算带标的个数，就可找到所要文件。

1)当i≧j时，要正走磁带，

步1 组织通道程序正走磁带，走过“带标”个数为3×(i-j)个。 步2 组织通道程序读文件i的文件头标。

步3 根据文件i的文件头标信息，组织读文件信息。

2)当i

步1 组织通道程序反走磁带，走过“带标”个数为3×(j-i)+1个。 步2 组织通道程序读文件i的文件头标。

步3 根据文件i的文件头标信息，组织读文件信息。

2. 假定令B=物理块长、R=逻辑记录长、F=块因子。对定长记录(一个块中有整数个逻

辑记录)，给出计算F的公式。 答：F=[B/R]。

3. 某操作系统的磁盘文件空间共有500块，若用字长为32位的位示图管理盘空间，

试问：(1)位示图需多少个字? (2)第i字第j位对应的块号是多少? (3)并给出申请/归还一块的工作流程。 答： (1) 位示图占用字数为500/32=16(向上取整)个字。

39

《操作系统教程》（第三版）CH1应用题参考答案

(2) 第i字第j位对应的块号N=32×i+j。

(3)申请时自上至下、自左至有扫描位示图跳过为1的位，找到第一个迁到的0位，根据它是第i字第j位算出对应块号，并分配出去。归还时已知块号，块号/32算出第i字第j位并把位示图相应位清0。

4. 若两个用户共享一个文件系统，用户甲使用文件A、B、C、D、E；用户乙要用到

文件A、D、E、F。己知用户甲的文件A与用户乙的文件A实际上不是同一文件；甲、乙两用户的文件D和E正是同一文件。试设计一种文件系统组织方案，使得甲、乙两用户能共享该文件系统又不致造成混乱。 答：可以采用二级目录或树形目录结构来解决难题。例如，

用户名 甲 乙 …?… 用户甲文件目录 文件名 物理地址 B C 主文件目录 A 文件 文件目录始址…… …… D E 用户乙文件目录 文件名 物理地址 文件 D E A F 文件 文件 5. 在UNIX 中，如果一个盘块的大小为1KB，每个盘块号占4个字节，即每块可放

256个地址。请转换下列文件的字节偏移量为物理地址：(1)9999；(2)18000；(3)420000。 答： 步1 将逻辑文件的字节偏移量转换为文件的逻辑块号和块内偏移。方法是：将逻辑文件的字节偏移量/盘块大小，商为文件的逻辑块号，余数是块内偏移。

步2将文件的逻辑块号转换为物理块号。使用多重索引结构，在索引节点中根据逻辑块号通过直接索引或间接索引找到对应物理块号。

(1) 9000 L1=INT(9999，1024)=9 B1=MOD(9999，1024)=783 其逻辑块号为9，故直接索引addr[8]中可找到物理块号。

(2) 18000 L2=INT(18000，1024)=17 B1=MOD(18000，1024)=592 其逻辑块号为17，通过一次间接索引addr[10]中可找到物理块号。

(3) 420000 L1=INT(420000，1024)=410 B1=MOD(9000，1024)=160 其逻辑块号为410，通过二次间接索引addr[11]中可找到物理块号。

40

本文来源：https://www.bwwdw.com/article/uefg.html