Add to buffer1; signal(mutex1); signal(full1); until false end

CalP:begin repeat

wait(full1); wait(mutex1);

Take a data form buffer1; Add to ch1; signal(mutex1); signal(empty1); calculate ch1; wait (empty2); wait(mutex2);

Take a data form ch1; Add to buffer2; signal (mutex2); signal (full2);

until false end

OutP:begin repeat

wait(full2); wait(mutex2);

Take a data from buffer2; Add to printer controler; signal(mutex2); signal(empty2); start printer;

until false end

（评分标准：信号量设置2分，输入进程、计算进程、打印进程各2分）

11．在一个请求分页系统中，有一个长度为 5 页的进程，假如系统为它分配 3 个物理块 ，并且此进程的页面走向为 2，3，2，1，5，2，4，5，3，2，5，2。试用 FIFO 和 LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。（10分） 解：FIFO：

2 3 2 1 5 2 4 5 3 2 5 2 第1页 2 2 2 5 5 5 3 3 3 第2页 3 3 3 2 2 2 5 5 第3页 1 1 1 4 4 4 2

缺页中断次数 = 6

LUR：

2 3 2 1 5 2 4 5 3 2 5 2 第1页 2 2 2 2 5 5 5 3 第2页 3 3 5 2 3 3 5 第3页 1 1 4 4 2 2

缺页中断次数 = 5

12. 进程 A1，A2，?，An 通过 K 个缓冲区向进程 B1，B2，?，Bm 不断地发送消息。发送和接收工作遵循如下规则：

1． 每个发送进程一次发送一个消息，写入缓冲区，缓冲区大小与消息长度一致； 2． 对每个消息，B1，B2，?，Bm 都需接收一次，读入各自的数据区内； 3． K 个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。 试用 wait 和 signal 原语操作组织正确的发送和接收操作。（10分） 解： BEGIN

Integer Mutex, Avail[n], Full[m]; Integer I;

Mutex:=1;

FOR i:=1 TO m DO BEGIN

Avail[I] := k; Full[I] := 0; END

PROCEDURE Send(K) Integer I; BEGIN

13．一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示（都为十进制数，且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算法，哪一个物理块将被换出？并解释原因．（10分） 页号 块号 加载时间 访问时间 访问位R 修改位M 2 0 60 161 0 1 1 1 130 160 0 0 0 2 26 162 1 0 3 3 20 163 1 1

１． IFO算法

２． LRU算法 ３． CLOCK算法

４． 当页面的访问串为：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法 解：1．换出第3号虚页，因为它加载的时间最早； 2．换出第1号虚页，因为它最近最久没被访问；

3．换出第1号虚页，因为它最近既没被访问，又没被修改； 4．换出第3号虚页，因为它离访问点最远。

14. 用整型信号量描述在哲学家进餐问题中，至多允许4个哲学家同时进餐的算法。（10分） 解：public class diningphilosophers {

semaphore [] fork = new semaphore [5] (1); semaphore room = new semaphore (4); int i;

void philosopher (int i) { while (true) think(); wait (room); wait (fork[i]); wait (fork [(i+1) % 5]); eat();

signal (fork [(i+1) % 5]); signal (fork[i]); signal (room); void main() {

parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4));

}

} }

15．考虑一个有150个存储器单元的系统，如下分配给三个进程： 进程

最大

占有

———————————————————— 1 2 3

使用银行家算法，以确定下面的任何一个请求是否安全：

a．第4个进程到达，最多需要60个存储单元，最初需要25个单元； b．第4个进程到达，最多需要60个存储单元，最初需要35个单元； 如果安全给出安全序列；若不安全给出结果分配简表。（10分） 解：进程 最大 占有 尚需 可用 ———————————————————————— 1 70 45 25 25 2 60 40 20 3 60 15 45 4 60 25 35 安全序列为：1、2、3、4

所以系统是安全的，可以进行分配。 b． 进程 最大 占有 尚需 可用 ———————————————————————— 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25

当前可用的资源不够任何一个进程运行完毕，所以不安全。

16. Jruassic 公园有一个恐龙博物馆和一个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入一个旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客和n辆车的进程。（10分） 解：

visitors=m; Pvi()

cars=n;

mutex=1;

Pci()

70 60 60

45 40 15