2．进程A1，A2，．．．，Anl通过m个缓冲区向进程B1，B2，．．．，Bn2不断地发送消息，发送和接收工作遵循如下规则：
（1）每个发送进程一次发送一个信息，写入一个缓冲区，缓冲区大小与消息长度一样； （2）对每一个消息，B1，B2，．．．，Bn2都需各接收一次，读入各自的数据区内； （3）m个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。 试用P、V操作组织正确的发送和接收操作。
解答：
这是一个变形的生产和消费问题。每个缓冲区只需写一次，但需读n2次。可以把一组缓冲区看做n2组缓冲区，这样，每个生产者需要同时写n2个缓冲区组中相应的n2个缓冲区，而每一个消费者只需读它自己对应的那组缓冲区中的单元。生产者须在n2个缓冲区都为空闲是方可写入，这时，就可以用n2组信息量（avail,free ）来实现这一流程，具体流程如下：
BEGIN
integer mutex,avail[n2],full[n2]; integer I; mutex : =1;
for I :=1 to n2 do begin
avail [I] := m; full [I] := 0; end;
procedure send[M] integer I ; begin
for I :=1 to n2 do begin
P( avail [I]); end ; P (metux);
将消息放入缓冲区;
for I :=1 to n2 do begin
V(full [I]); end ;
V (metux)
end ;
procedure receive(M,I)
1 / 22
begin
P (full[I]); P (metux);
从缓冲区中取消息; V (avail [I]); V (mutex);
end ; Cobegin Ai:begin …….. send [M] ……… end Bi;begin …….
Receive(M,i); ………
end; Coend; end;
3．设系统中仅有一类数量为M的独占型资源，系统中有N个进程竞争该类资源，其中各进程对该类资源的最大需求数为W，当M，N，W分别取下列值时，试判断哪些情况会发生死锁，为什么？
（1） M=2，N=2，W=1 （2） M=3，N=2 W=2 （3） M=3，N=2，W=3 （4） M=5 N=3 W=2 （5） M=6 N=3 W=3
解答：
（1） 不会发生死锁。因为系统中只有两个进程，每个进程的最大需求量为1， 且系统中资源总数为2，系统能够满足两个进程的最大资源需求量，故不会发生死锁。
（2） 不会发生死锁。因为系统中有两个进程，每个进程的最大资源需求量为2， 且系统中资源总数为3，无论如何分配，两个进程中必有一个进程可以获得两个资源，该进程将顺利完成，从而可以将分配给它的资源归还给系统，使另一个进程也能顺利执行完成，故不会发生死锁。
（3） 可能发生死锁。因为系统中有两个进程，每个进程的最大资源需求量为3， 且系统中资源总量为3，若系统先将全部资源分配给其中一个过程，则该进程将顺利完成，从而可将分配给它的资源归还给系统，使另一进程也能顺利完成，以这种方式分配资源时不会发生死锁；若系统将两个资源分配给一个过程，而剩余的一个资源分配给另一个进程，则系统中没有空闲资源，而每个进程都需要等待资源，此时发生死锁。
（4） 不会发生死锁。因为系统中有3个过程，每个进程的最大资源需求量为2，
2 / 22
且系统中资源总量为5，无论如何分配，3个进程中必有一个进程可以获得2个资源，该进程将顺利完成，从而可以将分配给它的资源归还给系统，使其他进程也能顺利执行完成，故不会发生死锁
（5） 可能会发生死锁。因为系统中有3个进程，每个进程的最大资源需求量为 3，且系统中资源总数为6 ，若系统先将3个资源分配给其中一个过程，则该进程将顺利完成，从而可将分配给它的资源归还给系统，使其他进程也能顺利完成，以这种方式分配资源时不会发生死锁；若系统给每个进程分配两个资源，则系统中没有空间资源，而每个进程都需要等待一个资源，此时发生死锁。
4． 设某作业占有7个页面，如果在主存中只允许装入4个工作页面（即工作集为4），作业运行时，实际访问页面的顺序是1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1。试用FIFO与LRU页面调度算法，列出各自的页面淘汰顺序和缺页中断次数，以及最后留驻主存4页的顺序（假设开始的4个页面已装入主存）。 解答：
对ＦＩＦO算法 ：
页面淘汰顺序为１，２，３，６，４，７； 缺页中断６次；
最后留驻主存４页的顺序为：２，１，５，6。 对ＬＲＵ 的算法；
页面淘汰顺序为１，２，６，４，７，３，２，１，４，７ 缺页中断１０次；
最后留驻主存４页的概率：６，５，２，１ 注：假定前面四页１，２，３，６ 已在主存
5．在某请求分页管理系统中，一个作业共５页，作业执行时依次访问如下页面：
１，４，３，１，２，５，１，４，２，１，４，５ 若分配给该作业的主存块数为３，分别采用ＦＩＦＯ，ＬＲＵ页面置换算法，试求出缺页中断的次数及缺页率。 解答：
（1）采用ＦＩＦＯ页面置换算法，
缺页中断的次数为９，缺页率9/１２＝７５％ （２）采用ＬＲＵ页面置换短法
缺页中断的次数为８，缺页率８／１２＝６７％
3 / 22
6．设内存中有三道 程序A，B，C，它们按A/B/C的优先次序执行，它们的计算和I/O操作的时间如表所1-1示（单位；MS）
表1-1 3道程序的操作时间 操 作 计算 I/O 计算 20 30 10 40 20 10 10 30 20 程 序 A B C
假设3道程序使用相同设备进行I/O操作，即程序以串行方式使用设备，试画出单道运行和多道运行的时间关系图（调度程序执行时间忽略不计）在两种情况下，完成这三道程序各要花多少时间？
解答 ：若采用单道方式运行三道程序，则运行次序为A，B，C，即程序A先执行20MS的计算，再完成30MS的I/O操作。最后在进行10MS的计算。接下来程序B先执行40MS的计算，再完成20MS的I/O操作。最后在进行10MS的计算。然后程序C先执行10MS的计算，再完成30MS的I/O操作。最后在进行20MS的计算。至此，三到程序全部运行完毕，其程序运行的时间关系如图1-1所示 总的运行时间为 20+30+ 10+ 40+ 20+ 10+ 10+ 30+ 20=190ms
A B C
I/O
A C B C A B 计算
时间ms
0 20 50 60 100 120 130 140 170 190
若采用都道方式运行三道程序，因系统按照A，B，C的优先次序执行， 则在运行 过程中，无论使用CPU还是I/O设备，A的优先级最高，B的优先级次之，C的优先级最低，即程序A先执行20MS的计算，再完成30MS的I/O操作（与此同时，程序B进行30MS的计算），最后在进行10MS的计算（此时程序B等待，因还继续10MS计算）：接下来程 序B先执行10MS的计算，再完成20MS的I/O操作（与此同时，程序C进行10MS的计算，然后等待I/O的设备），最后在进行10MS的计算（此时程序C执行I/O操作10MS）。然后程序C先执行20MS的I/O操作，最后在进行20MS的计算。至此，三到程序全部运行完毕， 其程序运行的时间关系如图1-2所示 总的运行时间为 20+30+ 10+ 10+ 20+ 10+ 10+ 20+ 30=140ms
4 / 22
A B C I/O
A C C B B A B 计算
时间ms
0 20 50 60 70 80 90 100 120 140
7． 在南京大学和天津大学的之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车在以从两端进入小路情况下错车使用，如下图所示，试设计一个算法，使来往的自行车辆均靠顺利通过。
天津大学
T
M L K S 南开大学
解答：对于这一类问题，关键在于正确分析所需控制的对象、工作流程以及控制关系。在这一问题中，根据从S到T路段的特点，可以把它分为3个小段：从S到K，驶进安全岛M，从L到T。路段S到K及L到T，只允许一辆自行车通过（即一个进程使用），而安全岛M允许两辆自行车通过（即两个进程使用）。对它们分别用3个信号量来管理。再注意到同时最多只能由一个方向的一辆自行车通过，因此每个方向的自行车还要用一个信号量来控制。
用bikeT_to_N和bikeN _to_T分别表示从天津大学到南开大学和从南开大学到天津大学
5 / 22
操作系统大题全集
