操作系统应用题2(解答)

1. 设有一台计算机，有两条 I/O 通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓 冲区 B1 中，加工处理后在搬到缓冲区 B2 中，并在打印机上印出，问：

①系统要设几个进程来完成这个任务？各自的工作是什么？

②这些进程间有什么样的相互制约关系？

③用 P、 V 操作写出这些进程的同步算法。

解：

①系统可设三个进程来完成这个任务： R 进程负责从卡片输入机上读入卡片信息， 输入到缓冲区 B1 中； C进程负

责从缓冲区 B1 中取出信息，进行加工处理，之后将结果送到缓冲区 B2 中； P 进程负责从缓冲区 B2 中取出信息， 并在打印机上印出。 ② R 进程受 C 进程影响， B1 放满信息后 R 进程要等待——等 C 进程将其中信息全部取走，才能继续读入信息； C

进程受 R 进程和 P 进程的约束： B1 中信息放满后 C 进程才可从中取出它们，且 B2 被取空后 C 进程才可将加工结

果送入其中； P 进程受 C进程的约束： B2 中信息放满后 P 进程才可从中取出它们 , 进行打印。 ③信号量含义及初值： B1full —— 缓冲区 B1 满，初值为 0；（ B1full ＝1 表示 B1 满）

B1empty——缓冲区 B1 空，初值为 1；（ B1empty＝ 1 表示 B1 空） B2full —— 缓冲区 B2 满，初值为 0；（ B2full ＝1 表示 B21 满） B2empty——缓冲区 B2 空，初值为 1；（ B2empty＝ 1 表示 B2 空）

R 进程 C 进程 P 进程

P(B1empty) P(B1full) P(B2full)

输入信息写入 B1 P(B2empty) 从 B2 中取出信

V(B1full) 取 B1送入 B2 息进行打印

V(B1empty) V(B2empty)

V(B2full)

2、现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下：

段号 主存起始地址（段基址） 段长度

0 120 40

1 760 30

2 480 20

3 370 20

计算逻辑地址（ 2， 15），（ 0， 60），（ 3， 18）的绝对地址是多少？

注：括号中第一个元素为段号，第二个元素为段内地址。

解：

段式存储管理的地址转换过程为： （ 1）根据逻辑地址中的段号查段表的相应栏目； （2）根据段内地址

检查地址是否越界；（ 3）若不越界，则绝对地址 =该段的主存起始地址 +段内地址。

逻辑地址（ 2， 15）查段表得段长度为 20，段内地址 15<20，地址不越界，段号 2 查表得段首地址为 480，于是

绝对地址为 480+15=495 。

逻辑地址（ 0， 60）查段表得段长度为 40，段内地址 60>40，地址越界，系统发出“地址越界”中断。

逻辑地址（ 3， 18）查段表得段长度为 20，段内地址 18<20，地址不越界，段号 3 查表得段首地址为 370，于是 绝对地址 =370+18=388 。

3．若干个等待访问磁盘者依次要访问的柱面为 20， 44，40， 4，80， 12，76，假设每移动一个柱面需要 时间，移动臂当前位于 40 号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。

（ 1）先来先服务算法；

3 毫秒 （ 2）最短寻找时间优先算法。

解（ 1） 3 毫秒× 292=876 毫秒 （ 2） 3 毫秒× 120=360 毫秒

（注：各算法使移动臂的移动次序和移动的柱面数如下：

（1）40 →20 →44 → 40 → 4 →80 →12 →76

（ 20） （ 24）（ 4） （ 36） （ 76）（ 68） （64） 共移动 292 柱面

（2）40 →44 →20 → 12 → 4 →76 →80

（ 4） （ 24）（ 8） （ 8） （ 72）（ 4） 共移动

120 柱面

4．某系统中有 10 台打印机，有三个进程 P1，P2，P3 分别需要

8台， 7台和

4 台。若

P1，P2，P3 已申请到

4 台，

2 台和 2 台。试问：按银行家算法能安全分配吗？请说明分配过程。

解：系统能为进程 P3 分配二台打印机。因为尽管此时 10 台打印机已分配给进程 P1 4 台， P22 台和 P34 台，全

部分配完，但 P3 已分配到所需要的全部 4 台打印机，它不会对打印机再提出申请，所以它能顺利运行下去，能

释放占用的 4 台打印机，使进程 P1， P2 均可能获得乘余的要求 4 台和 5 台，按银行家算法是安全的。

5．用 PV 操作解决读者写者问题的正确程序如下：

begin S, Sr: Semaphore; rc: integer; S:=1; Sr:=1; rc:=0;

cobegin PROCESS Reader i ( i=1,2 )

begin P(Sr)

rc:=rc+1; if rc=1 then P(S);

V(Sr); read file;

P(Sr);

rc:=rc-1

if rc=0 thenV(S);

V(Sr);

end ; PROCESS Writer j (j=1,2 )

begin P(S);

Write file;

V(S)

end;

coend ;

end;

请回答：（ 1）信号量

程同时读怎样修改程序？ Sr

的作用；（

2）程序中什么语句用于读写互斥，写写互斥；（

3）若规定仅允许

5 个进

解（ 1） Sr 用于读者计数 rc 的互斥信号量；

（ 2） if rc=1 then P （ S）中的 P（ S）用于读写互斥，写者进程中的 P（ S）用于写写互斥，读写互斥。

（ 3）程序中增加一个信号量 S5，初值为 5， P（ S5）语句加在读者进程 P（ Sr ）之前， V（S5）语句加在读者进程第 2 个 V（ Sr）之后。

6. 判断下面的同步问题的算法是否正确？若有错，请指出错误原因并予以改正。 设 A、 B 两进程共用一个缓冲区 Q， A 向 Q写入信息， B 则从 Q读出信息，算法框图如图所示。

进程A 进程B

向 Q写入信息

P(S)

V(S) 从 Q读出信息

注：信号量

S 的初值为

0

解：这个算法不对。 因为 A、B两进程共用一个缓冲区 Q，如果 A 先运行，且信息数量足够多，那么缓冲区

生后面的冲掉前面的，造成信息丢失， B 就不能从 Q中读出完整的信息。 进行改正：

A、 B 两进程要同步使用缓冲区 Q。为此，设立两个信号量：

empty 表示缓冲区 Q为空，初值为 1；

full 表示缓冲区 Q为满，初值为 0。

Q中的信息就会发

算法框图如图所示。

A 进程

B

进程

P(empty)

P(full)

向 Q写入信息 从 Q中读出信息 V(full) V(empty)

7. 有三个用户进程 A、 B 和 C，在运行过程中都要使用系统中的一台打印机输出计算结果。

(1) 试说明 A、B、 C 进程之间存在什么样的制约关系？

(2) 为保证这三个进程能正确地打印出各自的结果，请用信号量和 P、V 操作写出各自的有关申请、使用打

印机的代码。要求给出信号量的含义和初值。

解：

(1) A、 B、 C三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。 （ 2） mutex：用于互斥的信号量，初值为1。

各进程的代码如下 ：

进程A 进程B 进程C ...

...

... ...

P(mutex) P(mutex) P(mutex) 申请打印机 使用打印机 申请打印机 使用打印机 申请打印机 使用打印机

V(mutex) V(mutex) V(mutex)

8. 假定在某移动臂磁盘上，刚刚处理了访问

75 号柱面的请求，目前正在

80 号柱面读信息，并且有下述请求序

列等待访问磁盘： 请求序列：

1

2

3

4

5

6

7

8 欲访问柱面号： 160 40 190 188 90 58 32 102

试用： (1) 电梯调度算法

(2) 最短寻找时间优先算法分别列出实际处理上述请求的次序。

解 (1) 电梯调度算法 : 由”刚刚处理了访问

75 号柱面的请求，目前正在

80 号柱面读信息”可知

: 初始磁头前进的

方向是 : ”从小到大”

所以 : 处理次序为：

5 8 1 4 3 6 2 7

90 102 160 188 190 58 40 32

(2) 最短寻找时间优先算法 :

处理次序为：

5 8 6 2 7 1 4 3

90 102 58 40 32 160 188 190

9. 有三个进程 P1，P2 和 P3 并发工作。进程 P1 需用资源 S3 和 S1；进程 P2 需用资源 S1 和 S2；进程 P3 需用资

源 S2 和 S3。回答：

(1) 若对资源分配不加限制，会发生什么情况?为什么 ? (2) 为保证进程正确工作，应采用怎样的资源分配策略?为什么 ?

解：

(1) 可能会发生死锁

例如：进程 P1， P2 和 P3 分别获得资源

( 或进程在等待新源时均不释放已占资源

(2) 可有几种答案：

A. 采用静态分配

S3，S1 和

)

S2 后再继续申请资源时都要等待，这是循环等待。

由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象现象)。 ( 或不会出现循环等待资源

或 B. 采用按序分配或

C.采用银行家算法 不会出现循环等待资源现象。 因为在分配时，保证了系统处于安全状态。

10. 某车站售票厅， 任何时刻最多可容纳

20 名购票者进入， 当售票厅中少于

20 名购票者时， 则厅外的购票者可

立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

(1) 用 PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。 (2) 根据所定义的信号量，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发执行。

COBEGIN PROCESS PI(I=1 ， 2， )

begin ；