13．一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示（都为十进制数，且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算法，哪一个物理块将被换出？并解释原因．（10分） 页号 2 1 0 3
0 1 2 3
块号 60 130 26 20 IFO算法 LRU算法 CLOCK算法
当页面的访问串为：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法
加载时间
161 0 160 0 162 1 163 1
访问时间
1 0 0 1
访问位R 修改位M
１． ２． ３． ４．
解：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 70 45 2 60 40 3 60 15
使用银行家算法，以确定下面的任何一个请求是否安全：
a．第4个进程到达，最多需要60个存储单元，最初需要25个单元；
b．第4个进程到达，最多需要60个存储单元，最初需要35个单元； 如果安全给出安全序列；若不安全给出结果分配简表。（10分） 解：进程 最大 占有 尚需 ———————————————————————— 1 70 45 25 2 60 40 20 3 60 15 45 4 60 25 35 安全序列为：1、2、3、4
所以系统是安全的，可以进行分配。 b．
进程 最大 占有 尚需 ———————————————————————— 1 70 45 25 2 60 40 20 3 60 15 45 4 60 35 25
可用 15
可用
25
当前可用的资源不够任何一个进程运行完毕，所以不安全。
16. Jruassic 公园有一个恐龙博物馆和一个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入一个旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客和n辆车的进程。（10分） 解：
visitors=m; Pvi() { repeat wait(cars); wait(mutex); get on; travell; get off; signal(cars); wait(mutex); until false; }
cars=n;
mutex=1; Pci() { repeat wait(visitors); wait(mutex); start; run; stop; signal(visitors); wait(mutex); until false; }
18、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。
（1）先来先服务算法； （2）最短寻道时间优先算法。
（3）扫描算法（当前磁头移动的方向为磁道递增）（10分） 解：
（1）磁道访问顺序为：20，44，40，4，80，12，76
寻道时间=（20+24+4+36+76+68+64）*3=292*3=876 （2）磁道访问顺序为：40，44，20，12，4，76，80 寻道时间=（0+4+24+8+8+72+4）*3=120*3=360 （3）磁道访问顺序为：40，44，76，80，20，12，4 寻道时间=（0+4+32+4+60+8+8）*3=116*3=348
19、生产者和消费者问题 （10分）
有一组生产者P1，P2，……，PM和一组消费者C1，C2，……，CK，他们通过由n个环形缓冲区构成的缓冲池进行通信，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用wait和signal原语实现他们的同步操作。
解：生产者和消费者问题 begin
Var mutex,empty,full:semaphore:=1,n,0; buffer:array[0,…,n-1] of item; in,out:integer := 0,0; parbegin
producer: begin repeat produce next product ; wait (empty); wait (mutex); buffer(in):=nextp ; in := (in+1) mod n ; signal (full); signal (mutex); until false ; end consumer: begin repeat wait (full); wait (mutex); nextc := buffer(out); out := (out+1) mod n; signal (empty); signal (mutex); consume the item in nextc; until false ; end parend end
21．今有三个并发进程R，M，P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”；进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。请用PV操作为同步机制写出它们能正确并发执行的程序。 （10分） 解：（10分） begin
Var mutex,input,calculate,output:semaphore:=1,n,0,0; buffer:array[0,…,n-1] of item; in,mid,out:integer := 0,0,0; proR() { do { wait (input); wait (mutex); buffer(in):=input data; in := (in+1) mod n ; signal (calculate); signal (mutex); while true ; } proM() { do { wait (calculate); wait (mutex); buffer(middle):=calculate data ; mid := (mid+1) mod n ; signal (output); signal (mutex); } while true ; } proP() { do { wait (output); wait (mutex); buffer(out):=calculate data ; out := (out+1) mod n ; signal (input); signal (mutex); } while true ; }
25、设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是：1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。试用FIFO、LRU页面置换算法，列出各自的页面淘汰顺序和页面置换次数。假设开始时没有任何页在内存中。 (10分) 解：FIFO：
1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1 1 1 1 1 4 4 4 4 5 5 2 2 2 2 7 7 7 7 6
3 3 3 2 2 2 2 2
6 6 6 6 1 1 1 页面置换次数为：10次 LRU：
1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1 1 1 1 1 4 4 4 1 1 1 1 6 6 6 2 2 2 2 7 7 7 4 4 4 4 2 2
3 3 3 3 3 3 3 7 7 7 7 7 1
6 6 6 2 2 2 2 5 5 5 5 页面置换次数为：14次
26、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：
(1)用wait和signal操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。