操作系统大题全集

1、word2 .进程A1 , A2，Anl通过m个缓冲区向进程 B1 , B2，.，Bn2不断地发送消息， 发送和接收工作遵循如下规如此：1每个发送进程一次发送一个信息，写入一个缓冲区，缓冲区大小与消息长度一样；2对每一个消息，B1，B2，.，Bn2都需各接收一次，读入各自的数据区内；3m个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。试用P、V操作组织正确的发送和接收操作。解答：这是一个变形的生产和消费问题。每个缓冲区只需写一次，但需读n2次。可以把一组缓冲区看做n2组缓冲区，这样，每个生产者需要同时写n2个缓冲区组中相应的 n2个缓冲区，而每一个消费者只需读它自己对应的那组缓冲

2、区中的单元。生产者须在n2个缓冲区都为空闲是方可写入，这时，就可以用n2组信息量avail,free丨来实现这一流程，具体流程如下：BEGINin teger mutex,avail n2,full n2;in teger I;mutex : =1;for I :=1 to n2 dobeginavail I := m;full I := 0;en d;procedure sen dMin tegerI ;beginfor I :=1 to n2 do beginP( avail I);end ;P (metux);将消息放入缓冲区；for I :=1 to n2 do begin V(ful

3、l I);end ;V (metux) end ;procedure receive(M,I) beginP (fulll);P (metux);从缓冲区中取消息V (avail I);V (mutex); end ;Cobegi nAi:begi nsend M endBi;begi nReceive(M,i);en d;Coe nd;en d;3设系统中仅有一类数量为M的独占型资源，系统中有N个进程竞争该类资源，其中各进程对该类资源的最大需求数为W，当M, N , W分别取如下值时，试判断哪些情况会发生死锁，为什么？（1）M=2，N=2，W=1（2）M=3，N=2W=2（3）M=3，N=2

4、，W=3（4）M=5N=3W=2（5）M=6N=3W=3解答：（1） 不会发生死锁。因为系统中只有两个进程，每个进程的最大需求量为1， 且系统中资源总数为 2，系统能够满足两个进程的最大资源需求量，故不会发生死锁。（2）不会发生死锁。因为系统中有两个进程， 每个进程的最大资源需求量为 2, 且系统中资源总数为 3，无论如何分配，两个进程中必有一个进程可以获得两个资源，该进程将顺利完成，从而可以将分配给它的资源归还给系统，使另一个进程也 能顺利执行完成，故不会发生死锁。（3）可能发生死锁。因为系统中有两个进程， 每个进程的最大资源需求量为 3, 且系统中资源总量为 3，假设系统先将全部资源分配给

5、其中一个过程，如此该进程将顺利完成，从而可将分配给它的资源归还给系统，使另一进程也能顺利完成，以 这种方式分配资源时不会发生死锁；假设系统将两个资源分配给一个过程，而剩余 的一个资源分配给另一个进程，如此系统中没有空闲资源，而每个进程都需要等待 资源，此时发生死锁。（4） 不会发生死锁。因为系统中有3个过程，每个进程的最大资源需求量为 2, 且系统中资源总量为 5,无论如何分配，3个进程中必有一个进程可以获得 2个资 源，该进程将顺利完成，从而可以将分配给它的资源归还给系统，使其他进程也能 顺利执行完成，故不会发生死锁（5）可能会发生死锁。因为系统中有3个进程，每个进程的最大资源需求量为 3,

6、且系统中资源总数为 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个页面已装入主存。

7、解答：对FIF O算法 ：页面淘汰顺序为1 ,2,3,6,4,7;缺页中断6次；最后留驻主存4页的顺序为：2,1,5,6。对LRU 的算法；页面淘汰顺序为1 ,2,6,4,7,3,2,1,4,7缺页中断10次；最后留驻主存4页的概率：6,5,2,1注：假定前面四页1,2,3,6已在主存5在某请求分页管理系统中，一个作业共5页，作业执行时依次访问如下页面： 1,4,3,1,2,5,1,4,2,1,4,5假设分配给该作业的主存块数为3,分别采用FI FO,LRU页面置换算法，试求出缺页中断的次数与缺页率。解答：1采用FIFO页面置换算法，缺页中断的次数为9,缺页率 9/12 = 75%2采用LRU

8、页面置换短法缺页中断的次数为8,缺页率8/12 = 67%6设内存中有三道 程序A , B , C,它们按A/B/C的优先次序执行，它们的计算和 I/O操 作的时间如表所1-1示单位；MS表1-13道程序的操作时间程操 0"序 作ABC计算204010I/O302030计算101020假设3道程序使用一样设备进展I/O操作，即程序以串行方式使用设备，试画出单道运行和多道运行的时间关系图调度程序执行时间忽略不计在两种情况下，完成这三道程序各要花多少时间？解答：假设采用单道方式运行三道程序，如此运行次序为 A , B, C,即程序A先执行20MS的计算，再完成 30MS的I/O操作。最后

9、在进展10MS的计算。接下来程序 B先执行40MS 的计算，再完成20MS的I/O操作。最后在进展10MS的计算。然后程序 C先执行10MS的 计算，再完成30MS的I/O操作。最后在进展20MS的计算。至此，三到程序全部运行完毕， 其程序运行的时间关系如图1-1 所示总的运行时间为20+30+ 10+ 40+ 20+ 10+ 10+ 30+ 20=190msI/O计算0 205060100120130 140170190假设采用都道方式运行三道程序，因系统按照A，B，C的优先次序执行，如此在运行过程中，无论使用 CPU还是I/O设备，A的优先级最高，B的优先级次之，C的优先级最 低,即程序A

10、先执行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=140msABABC-*BCij;1时间ftI/O

11、计算CABms0 2050607080 901001201407.在某某大学和某某大学的之间有一条弯曲的小路，其中从 S到T 一段路每次只允许一 辆自行车通过，但中间有一个小的安全岛 M同时允许两辆自行车停留，可供两辆自行车 在以从两端进入小路情况下错车使用， 如如下图所示，试设计一个算法， 使来往的自行车辆 均靠顺利通过。解答：对于这一类问题，关键在于正确分析所需控制的对象、工作流程以与控制关系。在这一问题中，根据从 S到T路段的特点，可以把它分为 3个小段：从S到K，驶进安全岛M, 从L到T。路段S到K与L到T,只允许一辆自行车通过即一个进程使用，而安全岛M允许两辆自行车通过即两个进程使用

12、。对它们分别用 3个信号量来管理。再注意到同时最多只能由一个方向的一辆自行车通过，因此每个方向的自行车还要用一个信号量来控制。用bikeT_to_N和bikeN _to_T分别表示从某某大学到南开大学和从南开大学到某某大学 两个方向的自行车。控制流程如下：BeginIn teger: 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

13、 to S;V(M);V(K);V(T_to_N);En d;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);En d;End;&例：在银行家算法中，假设出现表2-4所示的资源分配情况，试问：1. 该状态是否安全？2. 如果进程P2提出请求Request2(1,2,2,2)后，系统能否将资源分配给它。表2-4资源分配表进资<源 情况程Allocati onNeedAvailableA

14、BCDABCDA B CDP000320012P110001750P2135423561 6 2 2P303320652P400140656解答:1利用银行家算法对此时刻的资源分配情况进展分析，可得表2-5所示的安全性分析情况。表2-5安全性检查表资、源情赶 '、况 程WorkNeedAllocati onWork+AllocationFi nishA B C DA B C DABC DA B C DP016 2 20 0 12003 21654true true true true trueP316540652033 21986P4198 61750001419910P1199100

15、65610 0 029910P22991023 56135 43121414从以上情况分析可以看出，此时存在一个安全序列p0,p3,p4,p1,p2,故该状态是安全的。2P2提出请求Request2(1,2,2,2)。按银行家算法进展检查：Request2(1,2,2,2)<=need(2,3,5,6)Request2(1,2,2,2)<=available(1,6,2,2)试分配并修改相应数据结构，资源分配情况如表2-6所示。表2-6 P2申请资源后的资源分配表进资源 情 、况 程Allocati onNeedAvailableABCDABCDA B CDP000320012P1

16、10001750P2135411340400P303320652P400140656再利用安全性检查算法检查系统是否安全，可用资源available(0,4,0,0)已不能满足任何进程的需要，此时系统不能将资源分配给P2。9有桥如图2-7所示。北南车流如箭头所示，桥上不允许两车交会，但允许同方向多辆车依次通行即桥上可以有多个同方向的车。用P、V操作实现交通管理以防止桥上阻塞。解答：由于桥上不允许两车相会，故桥应该互斥访问，而同一方向上允许多辆车一次通过，即临界区允许多个实例访问。 用同一信号量来互斥访问临界区。由于不能允许某一方向的车完全“控制桥，应保证最多某一方向上连续通过一定数量的车后，必

17、须让另一方向的车通过，可以通过3个信号量来控制。具体程序如下：BeginIn teger:mutex,avail n, abails;Mutes:=O;avial n:=m;avails:=m;Cobegi nSouth: beg inP(avails); P(mutex);过桥；V(mutex);V(avails);End;North: begi nP(avail n);P(mutex);过桥；V(mutex);V(avail n);End;Coe nd;En d;10.设系统中有三类资源A、B和C,又设系统中有 5个进程P1, P2, P3, P4和P5在T0时刻系统状态如下:8 / 22

18、word最大需求量已分配资源量剩余资源量ABCABCABCP1 8641212 1 1P2 433311P3 1013413P4 333322P5 546113(1)系统是否处于安全状态？如是，如此给出进程安全序列(2)如果进程P5申请1个资源类A、个资源类B和1个资源类C,能否实施分配？为什么?答案：1最大需求量已分配资源量剩余资源量尚需要量ABCABCAB CAB CP1 864121 21 1743P2 433311122P3 1013413600P4 333322011P5 546113433W厶大H.右|、千安全序列为：P4, P2, P1,P3, P5安全状态，2P5申请1,1,

19、1最大需求量已分配资源量剩余资源量尚需要量ABCABCAB CAB CP1 864121 10 0743P2 433311122P3 1013413600P4 333322011P5 546224322不能实施分配，因为分配后找不到安全序列，系统将处于不安全状态31.有三个进程PA, PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区 2,每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等 于一个记录大小。请用 P, V操作来保证文件的正确打印。解答：在此题中，进程 PA, P

20、B和PC之间的关系为：PA与PB共用一个单缓冲区，而 PB又 与PC共用一个单缓冲区，其合作方式可用图2-10表示，当缓冲区1为空时，进程PA可将一个记录读入其中；假设缓冲区1中有一个数据且缓冲区 2为空，如此进程 PB可将记录从缓冲区1复制到缓冲区2中；假设缓冲区2中有数据，如此进程PC可以打印记录， 在其他条件下，相应进程必须等待。事实上，这是一个生产者一消费者的问题PA 图2-10 进程间的合作方式 为遵循这一同步规如此。缓应设置四个信口 曰.号量 PC 一empty缓冲区pt2 , full1 , full2，信号量empty1从磁盘读入打印复制9 / 22word与empty2分别表

21、示缓冲区1与缓冲区2是否为空，其初值为1;信号量fulll , full2分别表示缓冲区1与缓冲区2是否有记录可供处理，其初值为0。其同步描述如下：int empty1=1 ；int empty2=1 ；int full1=0;int full2=0;mai n ()cobegi nPA()；PB();PC();coendPA()while( 1 ) 从磁盘读一个记录；P (empty1;将记录存入缓冲区1 ；V(full1);PB()while(1)P(full1；从缓冲区1中取出记录；V(empty1);P (empty2);将记录存入缓冲区2 ；V(full2);PC()while(1)

22、P(full2);从缓冲区2中取出记录；V(empty2);打印记录；20 / 22此题也是一个 典型生产者一消费者的问题，其中的难点在于 一个消费者。PB既是一个生产者又是11 有一个虚拟存储系统，每个进程在内存占有 3页数据区、1页程序区刚开始时数据区为空有以下访页序列1、5、4、1、2、3、2、1、5、4、2、4、6、5、1试给出如下情形下的缺页次数：(1) 系统采用先进先出(FIFO)淘汰算法(2) 系统采用最近最少使用(LRU)淘汰算法12.有个一虚拟存储系统，每个进程在内存占有 3页数据区， 以下访页序列：2、3、4、5、3、4、1、2、3、5、1、4、2、4、5、 试给出如下情形

23、下的缺页次数：(1) 系统采用先进先出(FIFO)淘汰算法(2) 系统采用最近最少使用(LRU)淘汰算法刚开始时数据区为空有1、 3、 2、 1、 3用PV操作解决读者写者问题的正确程序如下：begin S, Sr: Semaphore; rc: integer;S:=1; Sr:=1; rc:=0;cobegin PROCESS Reader i ( i=1,2)begin P(Sr)rc:=rc+1;if rc=1 then P(S);V(Sr);read file;P(Sr);rc:=rc-1if rc=0 the nV(S);V(Sr);end ;PROCESS Writer j (j

24、=1,2)begin P(S);Write file;V(S)en d;coend ;en d;3请回答：1信号量Sr的作用；2程序中什么语句用于读写互斥，写写互斥； 假设规定仅允许 5个进程同时读怎样修改程序?答：1Sr用于读者计数rc的互斥信号量;2if rc=1 then P S中的PS用于读写互斥，写者进程中的P S用于写写互斥,读写互斥。3程序中增加一个信号量 S5,初值为5, P S5语句加在读者进程 PSr之前，V S5语句加在读者进程第 2个V Sr之后。2.考虑一个由8个页面、每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：(1) 逻辑地址需要多少

25、二进制位表示？(2) 物理地址需要多少二进制位表示？因为页面数为8 = 23,故需要3位二进制数表示。每页有 1024个字节，1024= 210, 于是页内地址需要 10位二进制数表示。32个物理块，需要5位二进制数表示(32 = 25)(1) 页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。(2) 页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。1.某虚拟存储器的用户编程空间共32个 页面，每页为1KB，内存为16KB。假定某 时刻一用户页表中已调入内存的页面的页 号和物理块号的对照表如下：页号物理块 号0511024 J37计算逻辑地址0A

26、5C(H)所对应的物理 地址要求写出分析过程。1解：页式存储管理的逻辑地址分为两局部：页号和页内地址。 由条件用户编程空间共32个页面"，可知页号局部占5位；由每 页为1KB : 1K=210,可知内页地址占10位。由 内存为16KB : 可知有16块，块号为4位。逻辑地址0A5C H丨所对应的二进制表示形式是:000 1010 0101 1100,根据上面的分析，下划线局部为页内地址，编码“00010为页号，表示该逻辑地 址对应的页号为2。查页表，得到物理块号是 4十 进制，即物理块地址为：01 00,拼接块内地址100101 1100,得 01 0010 0101 1100,即

27、125C H。2.假设一个磁盘有 200个磁道，编号从0199。当前磁头正在143道上服务，并且刚刚完成了 125道的请求。如果寻道请求队列的顺序是:86, 147, 91, 177, 94, 150, 102, 175, 130问：为完成上述请求，使用最短寻道时间优先磁盘调度算法SSTF时，磁头移动的总量是多少？要求写出分析过程采用最短寻道时间优先磁盘调度算法SSTF，进展调度的情况为：从143道开始下一磁道移动磁道数147415031302010228948913865175891772磁头移动总量为162。设某文件的物理存储方式米用方式，该文件由5个逻辑记录组成，每个逻辑记录的大小与磁盘

28、块大小相等，均为 512字节，并依次存放在50、121、75、80、63号磁盘块上。10分文件的第1569逻辑字节的信息存放在哪一个磁盘块上？要访问第1569逻辑字节的信息，需要访问多少个磁盘块？假设该文件的FCB在内存因为：1569=512X 3+33所以要访问字节的逻辑记录号为 3,对应的物理磁盘块号为80。 故应访问第80号磁盘块。由于采用方式，所以要访问第 3个逻辑记录的信息，必须访问逻 辑记录第0、1、2后，才能访问第3个逻辑记录，所以要访问第1569 逻辑字节的信息，需要访问4个磁盘块。37.当磁头处于100号磁道时，有9个进程先后提出读写请求涉与 的柱面号为 63、57、34、8

29、8、91、103、76、18 和 128。要求：（1）写出按最短寻找时间优先算法 SSTF时的调度次序；（2）计算按SSTF调度算法时的平均寻道数。答：（1）调度次序：100 103 9188 76 63 57 3418 1282总移过的道数为：3+12+3+12+13+6+23+16+110=198平均寻道数为：198/9=22（道）34.哲学家就餐问题是一个经典的进程同步问题，该问题中描述有5个哲学家，他们的生活方式是交替地进展思考和进餐。哲学家们共用 一X圆桌，分别坐在周围的椅子上。在圆桌上有5只碗和5支筷子，平时哲学家们进展思考，饥饿时便试图取用其左、右两边的筷子，只 有在他拿到两支筷

30、子时才能进餐。进餐完毕，放下筷子继续思考。为了解决哲学家就餐问题，可以用一个信号量表示一支筷子，由 这5个信号量构成信号量数组：semaphore stick5;所有信号量初值为 1,第1个哲学家的活动算法可以推述如下：semaphore stick5=1,1,1,1,1;mai n() cobeg inPhilosopehr(O);Philosopehr(1);Philosopehr(2);Philosopehr(3);Philosopehr(4);Coend;Philosopehr(i nt I)While(true)思考；P(stickI);P(stick(l+1)%5);进餐；v(st

31、ickI;v(stick(I+1)%5);试问上述算法是否会发生死锁？为什么？假设会发生死锁，请给 出一个不会发生死锁的哲学家就餐算法。34.答案上述算法可能发生死锁。例如，5个哲学家几乎同时饥饿而各自 拿起左边的筷子时，使得5支筷子信号量均为0,当他们试图去拿右 边筷子时，都将因无筷子拿而无限期地等待下去。对于上述算法的死锁问题有多种解决方法， 这里给出两种解决方 案。方案一：用额外的信号量 mutex（初值为1）来控制对临界资源的 使用。算法如下：Semaphore mutex=1;Philosopehr(i nt I)While(true)思考；P(mutex);P(stickl);P(

32、stick(l+1)%5);进餐；v(stickI;v(stick(I+1)%5);改良的算法实质上是对资源申请过程进展限制， 即要求一次申请 完所有的资源，也就是在申请两个资源的过程中不被其他进程打断。 且在系统满足该进程要求之前别的进程无法申请资源，因而也就可以防止死锁。方案二：对申请资源筷子的进程哲学家进展限制，要求 至多允许4个哲学家同时进餐，以保证至少有一个哲学家能够拿到两 支筷子进餐，最后总会进餐完毕并释放他占有的两支筷子， 以使其他 哲学家可以进餐。算法如下：Semaphore s=4; /用于控制同时进餐的人数Philosopehr(i nt I)While(true)思考；P

33、(s);P(stickl);P(stick(l+1)%5);进餐；v(stickI;v(stick(I+1)%5);v(s);16. 在一个系统中采用分页存储管理，页的大小为 4KB，允许用户 进程的存储映像最大为16页，物理内存共有512内存块，试问：虚 拟地址存放器和内存地址存放器的长度各是多少位？答：1页的大小为4KB=212B,页面数为16=24，所以虚拟地址 存放器需要12+4=16位。2页的大小为4KB=212B,物理块数为512=29，所以内存地址存放器需要12+9=21位。17. 考虑一个由8个页面、每页1024字节组成的存储空间，把它映 射到容量为32个物理块的存储器中，试问

34、逻辑地址和物理地址分别 是多少位？为什么？答：因为每页大小为1024字节，故页内地址需要10个二进制 位描述；作业的逻辑地址有8页，页号需要3个二进制位。由此可知, 物理地址共需要15位。word因为每个物理块与页大小一样，即大小为 1024字节，故块内地 址需要10个二进制位描述；内存空间容量为32块，块号需要个二进 制位。由此可知，物理地址共需要 15位。18. 假定某页式存储器管理系统中，主存为 128KB，分为32块，块 号为0、1、2、3、.、31;某作业有5块，其页号为0、1、2、3、 4,被分别装入主存的3、& 4、6、9块中。有一逻辑地址为3,70。 试求出相应的物理地址其中方括号中的第一个元素为页号， 第二个 元素为页内地址，按十进制计算，并画图说明地址变换过程。答：由可得，块大小为 128KB/32=4KB,因为块与页面大小一样， 因此每页大小为4KB。再由题目可知，第3页被装入到主存第6块中，故逻辑地址3,70 对应的物理地址为：4KB*6+70=24646。其地址变换过程如如下图：页号3页内地址70页号块号0119. 在某段式存储管理系统中，有一作业共 4段，段号分别