剩余资源数
解：（共9分，每小题3分）
3 3 0 1． T0时刻是安全的，安全序列为：P1，P4，P5，P2，P3 2． P4请求资源（1，2，0），根据银行家算法，预分配后系统是安全的，安全
序列为：P1，P4，P5，P2，P3 3． P3请求资源（1，1，0），根据银行家算法，预分配后系统不安全，所以不
能实施资源分配。
9．一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如图所示：（共8分） 块号 存在位P 访问位R 修改位M 0x1C 1 1 0 0x3F 1 1 1 - 0 0 0 0x5D 1 0 0 - 0 0 0
1． 有那些页面不在内存？（2分）
2． 请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址
（用十六进制表示），并说明理由。 （6分）
解：（共8分）
不在内存的是第2和4页（按页号），或第3和5页（按序号）。 （2分） 0x3B7的物理地址=0x 73 B7 （2分）
0x12 A5的物理地址=0x 176 A5，缺页，换出第三页。 （2分） 0x1432地址越界，出错。 （2分）
10．系统运行有三个进程：输入进程、计算进程和打印进程，它们协同完成工作。输入进程和计算进程之间共用缓冲区buffer1,计算进程和打印进程之间共用缓冲区buffer2。输入进程接收外部数据放入buffer1中；计算进程从buffer1中取出数据进行计算，然后将结果放入buffer2；打印进程从buffer2取出数据打印输出。
用算法描述这三个进程的工作情况，并用wait和signal原语实现其同步操作。（共8分） 解：（共8分）
解答：输入进程、计算进程和打印进程之间的同步问题描述如下：
var：mutex1，mutex2，empty1，empty2，full1，full2：=1，1，1，1，0，0； InP:begin repeat
wait(empty1); wait(mutex1);
input a data from keyboard;
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() { repeat wait(cars);
70 60 60
45 40 15
cars=n;
mutex=1; Pci() { repeat wait(visitors);