操作系统大题全集2,进程Al, A2,., AnI通过m个缓冲区 向进程Bl,Bn2不断地发送消息，发送和接收工作遵循如下规则：(1) 每个发送进程一次发送一个信息，写 入一个缓冲区，缓冲区大小与消息长度一样；(2) 对每一个消息，Bl,Bn2都需各接收一次，读入各自的数据区内；(3) m个缓冲区都满时，发送进程等待， 没有可读的消息时，接收进程等待。试用P、V操作组织正确的发送和接收操 作。解答：这是一个变形的生产和消费问题。每个缓 冲区只需写一次，但需读n2次。可以把一组缓 冲区看做n2组缓冲区，这样，每个生产者需要 同时写n2个缓冲区组中相应的n2个缓冲区，而 每一个消费者只需读它自己对应的那组缓冲区 中的单元。生产者须在n2个缓冲区都为空闲是 方可写入，这时，就可以用n2组信息量 (avail,free )来实现这一流程，具体流程如下:BEGINinteger mutex,availn2,fulln2; integer I;mutex : =1;for I :=1 to n2 do beginavail I := m;full I := 0;end;procedure sendM integer I ;beginfor I :=1 to n2 dobeginP( avail I); end ;P (metux);将消息放入缓冲区；for I :=1 to n2 do begin V(full I)； end ;V (metux) end ;procedure receive(M,I) beginP (fulI);P (metux);从缓冲区中取消息；V (avail I);V (mutex);end ;CobeginAi:beginsend Mend Bi;beginReceive(M,i);end;Coend;end;3.设系统中仅有一类数量为M的独占型i=j资源，系统中有N个进程竞争该类资源，其中 各进程对该类资源的最大需求数为W,当M，N， W分别取下列值时，试判断哪些情况会发生死 锁，为什么？（1）M=2, N=2, W=1（2）M=3, N=2W=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,系统能够满足两个进程的最大资源需求量，故不会发生死锁。=JI=Jw（2）不会发生死锁。因为系统中有两个 进程，每个进程的最大资源需求量 为2，且系统中资源总数为3,无论如何分配，两 个进程中必有一个进程可以获得两个资源， 该进程将顺利完成，从而可以将分配给它的 资源归还给系统，使另一个进程也能顺利执 行完成，故不会发生死锁。l=Jw（3）可能发生死锁。因为系统中有两个 进程，每个进程的最大资源需求量 为3，1=1w且系统中资源总量为3,若系统先将全部资 源分配给其中一个过程，则该进程将顺利完 成，从而可将分配给它的资源归还给系统， 使另一进程也能顺利完成，以这种方式分配 资源时不会发生死锁；若系统将两个资源分 配给一个过程，而剩余的一个资源分配给另 一个进程，则系统中没有空闲资源，而每个 进程都需要等待资源，此时发生死锁。=J（4）不会发生死锁。因为系统中有3个 过程，每个进程的最大资源需求量为2,i=jw且系统中资源总量为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个页面已装入主存）。解答：对FIFO算法:6,4,7；2,1,5,4,7,3,3,2,6,6。页面淘汰顺序为1,2,缺页中断6次；:后留驻主存4页的顺序为: 对LRU的算法； 页面淘汰顺序为1,2,缺页中断10次;最后留驻主存4页的概率:6,5,2,1注：假定前面四页1 ,2,3,6 已在主存5. 在某请求分页管理系统中，一个作业共5页, 作业执行时依次访问如下页面： 14,3,1,2,5,1,4,2,1,4,5若分配给该作业的主存块数为3,分别采用 断的次数及缺页率。FIFO, LRU页面置换算法，试求出缺页中=i解答：(1)采用FIFO页面置换算法，缺页中断的次数为9,缺页率9/12 = 75%(2)采用LRU页面置换短法缺页中断的次数为8,缺页率8/12 = 67%6. 设内存中有三道 程序A, B, C,它们按AB/C 的优先次序执行，它们的计算和I/O操作的时间 如表所1-1示(单位；MS)表1-13道程序的操作时间操灌序ABC计算204010I/O302030计算101020假设3道程序使用相同设备进行I/O操作， 即程序以串行方式使用设备，试画出单道运行和 多道运行的时间关系图（调度程序执行时间忽略 不计）在两种情况下，完成这三道程序各要花多 少时间？解答：若采用单道方式运行三道程序，则运行次序为A，B，C，即程序A先执行20MS的计算，再完成30MS的I/O操作。最后在进行10MS的计算。接下来程序B先执行40MS的计算，再完成20MS的I/O操作。最后在进行10MS的计算。然后程序C先执行10MS的计算，再完成30MS的UO操作。最后在进行20MS的计算。至此，三到程序全部运行完毕，其程序运行的时 间关系如图1-1所示总的运行时间为20+30+ 10+ 40+ 20+ 10+ 10+ 30+20=190ms0205060若采用都道方式运行三道程序，因系统按照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执行UO操作10MS）。然后程序C先执行 20MS的IO操作，最后在进行20MS的计算。 至此，三到程序全部运行完毕，其程序运行的时间关系如图1-2所示总的运行 时间为20+30+ 10+ 10+ 20+ 10+ 10+ 20+ 30=140msABA BCBCABCI/O计20506070liiJliiJ7. 在南京大学和天津大学的之间有一条弯曲的 小路，其中从S到T 一段路每次只允许一辆自 行车通过，但中间有一个小的安全岛M （同时 允许两辆自行车停留），可供两辆自行车在以从 两端进入小路情况下错车使用，如下图所示，试 设计一个算法，使来往的自行车辆均靠顺利通 过。_S南开liiJliiJ解答：对于这一类问题，关键在于正确分析所需 控制的对象、工作流程以及控制关系。在这一问 题中，根据从S到T路段的特点，可以把它分 为3个小段：从S到K，驶进安全岛M，从L 到丁。路段S到K及L到T，只允许一辆自行 车通过（即一个进程使用），而安全岛M允许两 辆自行车通过（即两个进程使用）。对它们分别 用3个信号量来管理。再注意到同时最多只能由 一个方向的一辆自行车通过，因此每个方向的自 行车还要用一个信号量来控制。用bikeT_to_N和bikeN _to_T分别表示从天 津大学到南开大学和从南开大学到天津大学两 个方向的自行车。控制流程如下：BeginInteger: N _to_T, T_to_N,L,M,K;N _to_T:=1; T_to_N:=1;L:=1;M:=2;K:=1;Procedure bikeT_to_N()BeginP(T_to_N);P(L);Go through T to L;P(M)；Go into M；V(L);P(K);Go through K to S;V(M);V(K);V(T_to_N);End;Procedure bikeN_to_T()BeginP(N_to_T);P(K);Go through S to K;P(M)；Go into M；V(K);P(L)；Go through L to T;V(M);V(L);V(N_to_T);End;End;8. 例：在银行家算法中，若出现表2-4所示的 资源分配情况，试问：1. 该状态是否安全？2. 如果进程P2提出请求Request2(1222)后， 系统能否将资源分配给它。资源 程情况AllocationNeedAvailableABC DABC DABC DP0003200121 62 2P110001750P213542356P303320652P400140656表2-4资源分配表资源程情况WorkNeedAlloca tionWork+AllocatiFini sh解答(1)利用银行家算法对此时刻的资源分配情况 进行分析，可得表2-5所示的安全性分析情况。表2-5安全性检查表onA BC DA BC DA BC DA BC DP01 62 2001 2003 216 54truetruetruetruetrueP3165 4065 2033 219 8 6P4198 6175 0001 419 910P1199 10065 6100 02 9 910P2