操作系统部分习题参考答案(孙钟秀版).doc

操作系统部分习题参考答案
第一章
2. 一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A先开始做，程序B后开始运行。程序A的运行轨迹为：计算50ms、打印100ms、再计算50ms、打印100ms，结束。程序B的运行轨迹为：计算50ms、输入80ms、再计算100ms，结束。试说明(1)两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？为什么会等待？(2)程序A、B有无等待CPU的情况？若有，指出发生等待的时刻。
答：画出两道程序并发执行图如下：

(1) 两道程序运行期间，CPU存在空闲等待，时间为100至150ms之间(见图中有色部分)。
(2) 程序A无等待现象，但程序B有等待。程序B有等待时间段为180ms至200ms间(见图中有色部分)。

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设备利用率。
答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：

(1) Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms。
(2) CPU空闲时间段为：60ms至70ms，80ms至90ms。所以CPU利用率为(90-20)/80=77.78%。
(3) 设备I1空闲时间段为：20ms至40ms，故I1的利用率为(90-20)/90=77.78%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(90-20)/90=77.78%。

第二章
7．假定执行作业Job1——Job5，作业号即为其到达顺序，依次在时刻0按照序号1、2、3、4、5进入单处理器系统。
作业号 执行时间/ms 优先权
Job1 10 3
Job2 1 1
Job3 2 3
Job4 1 4
Job5 5 2
（1）分别采用先来先服务调度算法、时间片轮转算法（时间片为1ms）、短作业优先算法及非抢占式优先权调度算法，计算出各作业的执行次序（注意：优先权越高，其数值越小）
（2）计算每种情况下作业的平均周转时间和平均带权周转时间。
答：（1）采用先来先服务调度算法
执行次序
执行时间
等待时间
开始时间
完成时间
周转时间
带权周转时间
Job1
Job2
Job3
Job4
Job5
10
1
2
1
5
0
10
11
13
14
0
10
11
13
14
10
11
13
14
19
10
11
13
14
19
1
11
6.5
14
3.8
作业平均周转时间
作业平均带权周转时间
13.4
7.26
（2）采用时间片轮转算法，令时间片=1，各作业执行情况为：1234513515151511111
执行次序
执行时间

完成时间
周转时间
带权周转时间
Job1
Job2
Job3
Job4
Job5
10
1
2
1
5

19
2
7
4
14
19
2
7
4
14
1.9
2
3.5
4
2.8
作业平均周转时间
作业平均带权周转时间
9.2
2.84
（3）短作业优先算法
执行次序
执行时间
等待时间
开始时间
完成时间
周转时间
带权周转时间
Job2
Job4
Job3
Job5
Job1
1
1
2
5
10
0
1
2
4
9
0
1
2
4
9
1
2
4
9
19
1
2
4
9
19
1
2
2
1.8
1.9
作业平均周转时间
作业平均带权周转时间
7
1.74

（4）非抢占式优先权调度算法
执行次序
优先数
执行时间
等待时间

周转时间
带权周转时间
Job2
Job5
Job1
Job3
Job4
1
2
3
3
4
1
5
10
2
1
0
1
6
16
18

1
6
16
18
19
1
1.2
1.6
9
19
作业平均周转时间
作业平均带权周转时间
12
6.36

11. 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) 时间片轮转法

 按次序A B C D E B C D EC D E D E E轮转执行。
 (2) 优先级调度算法

  (3)SJF调度算法 

 (4)FCFS调度算法 

15．在单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪种算法性能较好？请完成下表。
作业
提交时间
运行时间
开始时间
完成时间
周转时间
带权周转时间
1
2
3
10: 00
10：10
10: 25
2:00
1:00
0:25

作业平均周转时间=
作业平均带权周转时间=
 答：（1）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
170/60
180/25
作业平均周转时间=2.61
作业平均带权周转时间=3.68
（2）HRRF算法
作业
提交时间
运行时间
开始时间
完成时间
周转时间
带权周转时间
1
2
3
10: 00
10：10
10: 25
2:00
1:00
0:25
10:00
12:25
12:00
12:00
13:25
12:25
2
3:15
2
120/120
195/60
120/25
作业平均周转时间=2.41
作业平均带权周转时间=3.02
可见HRRF比FIFO要好。

27. 某多道程序设计系统供用户使用的主存为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分钟。 

分析：本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。
8:00 作业1到达，占有资源并调入主存运行。
8:20 作业2和3同时到达，但作业2因分不到打印机，只能在后备队列等待。作业3资源满足，可进主存运行，并与作业1平分CPU时间。
8:30 作业1在8:30结束，释放磁带与打印机。但作业2仍不能执行，因不能移动而没有30KB的空闲区，继续等待。作业4在8:30到达，并进入主存执行，与作业3分享CPU。
8:35 作业5到达，因分不到磁带机/打印机，只能在后备队列等待。
9:00 作业3运行结束，释放磁带机。此时作业2的主存及打印机均可满足，投入运行。作业5到达时间晚，只能等待。
9:10 作业4运行结束，作业5因分不到打印机，只能在后备队列继续等待。
9:15 作业2运行结束，作业5投入运行。
9:30 作业全部执行结束。
第三章
（思考题）42．某系统有m个同类资源供n个进程共享，若每个进程最多申请x个资源（1≤x≤m）,推导出系统不发生死锁（n、m和x）的关系式。
答：最坏：每个（x-1）个资源，申请最后一个，剩m-n(x-1)
若还有一个资源可用，则可使所有进程执行结束。
m-n(x-1)≥1，即n(x-1)+1≤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;      ⑦
        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。
此外，还有第三种情况，语句③被推迟，直至语句⑧后再执行，于是依次执行以下三个语句：
z:=z+x；
z:=y+1;
          y:=z+y;
这时z的值只可能是y+1=5，故y=z+y=5+4=9，而x=10。
第三种情况为：x=10，y=9，z=5。

（注：第28和30题请参考书上的例题，使用表格给出求解安全序列的过程。正式考试中，如果没有求解过程，一律扣分！）
28、（1）2 2 2
1 0 2
1 0 3
4 2 0
（2）存在安全序列2,1,3,4，所以安全
（3）存在安全序列2,1,3,4，所以安全
（4）不可以分配，资源不足
（5）不可以分配，处于不安全状态

30、（1）存在安全序列4,1,5,2,3，所以系统安全
（2）可以分配，存在安全序列4,1,5,2,3
（3）不可以分配，因为系统进入不安全状态

第四章
1．在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是：
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
分别使用FIFO、OPT和LRU算法，对于分配给程序四个页框的情况，求出缺页中断次数和缺页中断率。
答：FIFO
1
2
3
4
2
1
5
6
2
1
2
3
7
6
3
2
1
2
3
6

F(1)
F(2)
F(3)
F(4)

F(5)
F(6)
F(2)

F(1)
F(3)

F(7)

1
1
1
1
1
1
2
3
4
5
5
6
2
1
1
3
7
7
6
6

2
2
2
2
2
3
4
5
6
6
2
1
3
3
7
6
6
2
2

3
3
3
3
4
5
6
2
2
1
3
7
7
6
2
2
1
1

4
4
4
5
6
2
1
1
3
7
6
6
2
1
1
3
3
缺页中断次数：14，缺页中断率：14/20
OPT
1
2
3
4
2
1
5
6
2
1
2
3
7
6
3
2
1
2
3
6

F(4)
F(5)

F(1)

F(7)

1
1
1
1
1
1
1
1
1
1
1
1
7
7
7
7
1
1
1
1

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

4
4
4
5
6
6
6
6
6
6
6
6
6
6
6
6
6
缺页中断次数：8，缺页中断率：8/20
LRU
1
2
3
4
2
1
5
6
2
1
2
3
7
6
3
2
1
2
3
6

F(3)
F(4)

F(5)
F(6)
F(1)

F(7)

1
1
1
1
1
3
4
2
1
5
5
6
1
2
2
7
6
6
6
1

2
2
2
3
4
2
1
5
6
6
1
2
3
7
6
3
3
1
2

3
3
4
2
1
5
6
2
1
2
3
7
6
3
2
1
2
3

4
2
1
5
6
2
1
2
3
7
6
3
2
1
2
3
6
缺页中断次数：10，缺页中断率：10/20

4.在可变分区存储管理下，按地址排列的主存空闲区为：10KB、4KB、20KB、18KB、7KB、9KB、12KB和15KB。对于下列连续存储区的请求：（1）12KB、10KB、9KB；（2）12KB、10KB、15KB、18KB；试问：使用首次适应算法、最佳适应算法、最差适应算法和下次适应算法，哪个空闲区将被使用？
答：（1）空闲分区如图所示
分区号
分区长
1
2
3
4
5
6
7
8
10KB
4KB
20KB
18KB
7KB
9KB
12KB
15KB
首次适应算法：12KB选中分区3，此时分区3还剩8KB。10KB选中分区1，恰好分配完，所以删去分区1。9KB选中分区4，这时分区4还剩9KB。
最佳适应算法：12KB选中分区7，恰好分配完，所以删去分区7。10KB选中分区1，恰好分配完，所以删去分区1。9KB选中分区6，恰好分配完，所以删去分区6。
最差适应算法：12KB选中分区3，此时分区3还剩8KB。10KB选中分区4，此时分区4还剩8KB。9KB选中分区8，此时分区8还剩6KB。
下次适应算法：12KB选中分区3，此时分区3还剩8KB。10KB选中分区4，此时分区4还剩8KB。9KB选中分区6，恰好分配完，所以删去分区6。
（2）略

第五章
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-130-102-94-91-86。

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

补充习题：
从100号磁道开始，向磁道号增加的方向访问，则有9个进程分别按下述四种方法调度，顺序及平均寻道长度分别为：
请求的下一磁道号
FCFS的移动距离（磁道数）
SSTF的移动距离（磁道数）
电梯算法
循环扫描算法
55
55
45
90
10
150
50
150
50
58
58
3
58
32
160
10
160
10
39
39
19
55
3
184
24
184
24
18
18
21
39
16
90
94
18
166
90
90
72
38
1
58
32
38
20
160
160
70
18
20
55
3
39
1
150
150
10
150
132
39
16
55
16
38
38
112
160
10
38
1
58
3
184
184
146
184
24
18
20
90
32
平均寻道长
55.3
27.5
27.8
35.8
第六章
3． 某操作系统的磁盘文件空间共有500块，若用字长为32位的位示图管理盘空间，试问：(1)位示图需多少个字? (2)第i字第j位对应的块号是多少? (3)并给出申请/归还一块的工作流程。
答： (1) 位示图占用字数为500/32=16(向上取整)个字。
  (2) 第i字第j位对应的块号N=32×i+j。
(3)申请时自上至下、自左至有扫描位示图跳过为1的位，找到第一个迁到的0位，根据它是第i字第j位算出对应块号，并分配出去。归还时已知块号，块号/32算出第i字第j位并把位示图相应位清0。

15．磁盘共有100个柱面，每个柱面有8个磁头，每个盘面分4个扇区。若逻辑记录
与扇区等长，柱面、磁道、扇区均从0起编号。现用16位的200个字(0-199)来组成位示图来管理盘空间。现问：(1)位示图第15个字的第7位为0而准备分配给某一记录，该块的柱面号、磁道号、扇区号是多少?(2)现回收第56柱面第6磁道第3扇区，这时位示图的第几个字的第几位应清0?
答：(1)位示图第15个字的第7位对应的块号=15×16(字长)+7=247，而块号247对应的：
柱面号=247/(8×4)=7(从0编号，向下取整)
磁头号=(247 MOD 32)/4=5
扇区号=247 MOD 32 MOD 4=3
(2)块号=柱面号×柱面扇区数+磁道号×盘扇区+盘扇区=56×(8×4)+6×4+3=1819
字号=1819/16=113
位号=1819 MOD 16 =11
所以，回收第56柱面第6磁道第3扇区时，位示图的第113字的第11位应清0。

14