第2章 进程与线程习题.doc

《操作系统》 第2章 进程与线程习题
第2章 进程与线程习题
1. 多个作业能够并行运行，比它们顺序执行完成的要快。假设有两作业同时开始执行，每个需要10分钟的CPU时间。如果顺序执行，那么最后一个作业需要多长时间可以完成？如果并并行执行又需要多长时间？假设I/O等待占50%。（来源：A.S.Tanenbaum《现代操作系统(原书第3版)》P95）
解：因为I/O等待占50%，所以当一个作业时，CPU利用率近似为50%，设I/O等待时间为x，满足
x/(x+10)=50%
解得每个作业的等待时间x=10分钟，完成一个作业需要20分钟
所以，当两作业顺序执行时,最后一个作业完成需要20+20=40分钟；
当两个作业并行执行时，最后一个作业完成需要20+20-10=30分钟
2. 一个快餐店有四类雇员：（1）领班，接收顾客点的菜单；（2）厨师，准备饭菜；（3）打包工，将饭菜装在袋子里；（4）收银员，将食品袋交给顾客并收钱。它们采用的进程间通信方式是什么？（来源：A.S.Tanenbaum《现代操作系统(原书第3版)》P96）
解：由管道的定义：在一个shell管道中，第一个进程的输出必须传送给第二个进程
然后沿着管道传递下去。我觉得题目所描述的进程通信方式为管道。因为在餐厅里，
当领班接受到顾客点的菜单时，传递给厨师，厨师接收到领班的菜单时，就准备饭
菜，待准备好饭菜之后，由打包工将准备好的饭菜装进袋子里，收银员再将装好的
饭菜交给顾客并收钱。就像管道一样，一个进程的输出必须传送给第二个进程，然
后沿着管道继续传递下去。
3. 今有3个并发进程R、S、T，它们共享一个缓冲区B。进程R负责从输入设备读入信息，每读出一个记录后就把它存入缓冲区B中；进程S利用缓冲区B加工进程R存入的记录；进程T把加工完毕的记录打印输出。缓冲区B一次只能存放一个记录。只有在进程T把缓冲区里的记录输出后，才能再往里放新的记录。试用信号量及期P、V操作控制这3个进程间的正确工作关系。（来源：宗大华《操作系统(第二版)》P162）
解：P、V操作如下：
P(s1)，执行P操作
从输入设备读入信息
V(s2)，执行V操作
P(s2)，执行P操作
加工进程R存入的记录
R
S
P(s3)，执行P操作
V(s3)，执行V操作
V(s1)，执行V操作
打印输出加工完毕的记录
T

由P、V操作图以及题意可设置初始信号量s1、s2、s3分别为1、0、0。
4. 有一个阅览室共100个座位。用一张表来管理它，每个表目记录号以及读者姓名。读者进入时要先在表上登记，退出时要注销登记。度用信号量及期P、V操作来描述各个读者“进入”和“注销”工作之间的同步关系。（来源：宗大华《操作系统(第二版)》P162）
解：P、V操作如下：
进入阅览室，登记
V(s1)，执行V操作
P(s2)，执行P操作
P(s1)，执行P操作
退出阅览室，注销
V(s2)，执行V操作
学生
学生

由上述P、V操作图以及题意可设置初始信号量s1、s2分别为0、0。
5. 有5个待运行作业，估计它们的运行时间分别是9,6,3,5和X。采用哪种次序运行这些作业将得到最短的平均响应时间？（答案将依赖于X。）（来源：A.S.Tanenbaum《现代操作系统(原书第3版)》P97）
解：x的取值有几种可能性：x>=9、6=<x<9、5<=x<6、3=<x<5、x<3，当采用非抢占的最短作业优先时，根据：
平均周转时间=(5a+4b+3c+2d+e)/5
可知，当x取值最小时，即x<3，平均周转时间最短=(5x+4*3+3*5+2*6+1*9)/5=x+9.6
6. 有5个批处理作业A到E。它们几乎同时到达一个计算中心。估计它们的运行时间分别为10，6，2，4和8分钟。其优先级（由外部设定）分别为3，5，2，1和4，其中5为最高优先级。对于下列每种调度算法，计算其平均进程周转时间，可以忽略进程切换的开销。
a) 轮转法（时间片分别为1和2）
b) 优先级调度
c) 先来先服务（按照10，6，2，4，8次序运行）。
d) 最短作业优先。
e) 最短剩余时间（时间片为1）
f) 最高响应比优先（顺序同c）
对a)，假设系统具有多道程序处理能力，每个作业均公平共享CPU时间，对b)到f)，假设任一时刻只有一个作业运行，直到结束。所有的作业都完全是CPU密集型作业。
解：
a) 轮转法
(1)时间片为1时

进程
到达时间
运行时间
开始时间
结束时间
周转时间
A
0
10
0
30
30
B
0
6
1
23
23
C
0
2
2
8
8
D
0
4
3
17
17
E
0
8
4
28
28

平均周转时间=(30+23+8+17+28)/5
(2)时间片为2时
进程
到达时间
运行时间
开始时间
结束时间
周转时间
A
0
10
0
30
30
B
0
6
2
22
22
C
0
2
4
6
6
D
0
4
6
16
16
E
0
8
8
28
28

平均周转时间=(30+22+6+16+28)/5
b) 优先级调度
进程
优先级
到达时间
运行时间
开始时间
结束时间
周转时间
A
3
0
10
14
24
24
B
5
0
6
0
6
6
C
2
0
2
24
26
26
D
1
0
4
26
30
30
E
4
0
8
6
14
14
平均周转时间=(24+6+26+30+14)/5
c) 先来先服务（按照10，6，2，4，8次序运行）
进程
到达时间
运行时间
开始时间
结束时间
周转时间
A
0
10
0
10
10
B
0
6
10
16
16
C
0
2
16
18
18
D
0
4
18
22
22
E
0
8
22
30
30
平均周转时间=(10+16+18+22+30)/5
d) 最短作业优先
进程
到达时间
运行时间
开始时间
结束时间
周转时间
A
0
10
20
30
30
B
0
6
6
12
12
C
0
2
0
2
2
D
0
4
2
6
6
E
0
8
12
20
20
平均周转时间=(30+12+2+6+20)/5
e) 最短剩余时间（时间片为1）

进程
到达时间
运行时间
开始时间
结束时间
周转时间
A
0
10
20
30
30
B
0
6
6
12
12
C
0
2
0
2
2
D
0
4
2
6
6
E
0
8
12
20
20
平均周转时间=(30+12+2+6+20)/5
f) 最高响应比优先（顺序同c）
进程
到达时间
运行时间
开始时间
结束时间
周转时间
A
0
10
0
10
10
B
0
6
16
22
22
C
0
2
10
12
12
D
0
4
12
16
16
E
0
8
22
30
30
平均周转时间=(10+22+12+16+30)/5

4/4 北理珠“操作系统”课题组2011-9-30