操作系统大题全集.doc

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,availn2,fulln2; integer I; mutex : =1; for I :=1 to n2 do begin avail I := m; full I := 0; end; procedure sendM 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) begin P (fullI); 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，且系统中资源总量为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/（）采用页面置换短法缺页中断的次数为，缺页率6设内存中有三道 程序A，B，C，它们按A/B/C的优先次序执行，它们的计算和I/O操作的时间如表所1-1示（单位；MS） 表1-1 3道程序的操作时间程序操作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的I/O操作。最后在进行20MS的计算。至此，三到程序全部运行完毕，其程序运行的时间关系如图1-1所示 总的运行时间为 20+30+ 10+ 40+ 20+ 10+ 10+ 30+ 20=190msI/O计算时间ms 0 20 50 60 100 120 130 140 170 190 AAABBBCCC 若采用都道方式运行三道程序，因系统按照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 CCBBBAAAI/O计算CB时间ms 0 20 50 60 70 80 90 100 120 140 7 在南京大学和天津大学的之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车在以从两端进入小路情况下错车使用，如下图所示，试设计一个算法，使来往的自行车辆均靠顺利通过。M南开大学天津大学SKLT解答：对于这一类问题，关键在于正确分析所需控制的对象、工作流程以及控制关系。在这一问题中，根据从S到T路段的特点，可以把它分为3个小段：从S到K，驶进安全岛M，从L到T。路段S到K及L到T，只允许一辆自行车通过（即一个进程使用），而安全岛M允许两辆自行车通过（即两个进程使用）。对它们分别用3个信号量来管理。再注意到同时最多只能由一个方向的一辆自行车通过，因此每个方向的自行车还要用一个信号量来控制。用bikeT_to_N和bikeN _to_T分别表示从天津大学到南开大学和从南开大学到天津大学两个方向的自行车。控制流程如下：Begin Integer: 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()Begin P(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()Begin P(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(1,2,2,2)后，系统能否将资源分配给它。表2-4 资源分配表资源情况进程AllocationNeedAvailableA B C DA B C DA B C DP00 0 3 20 0 1 21 6 2 2P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6解答：（1）利用银行家算法对此时刻的资源分配情况进行分析，可得表2-5所示的安全性分析情况。表2-5 安全性检查表资源情况进程WorkNeedAllocationWork+AllocationFinishA B C DA B C DA B C DA B C DP01 6 2 20 0 1 20 0 3 21 6 5 4truetruetruetruetrueP31 6 5 40 6 5 20 3 3 21 9 8 6P41 9 8 61 7 5 00 0 1 41 9 9 10P11 9 9 100 6 5 61 0 0 02 9 9 10P22 9 9 102 3 5 61 3 5 43 12 14 14从以上情况分析可以看出，此时存在一个安全序列p0,p3,p4,p1,p2,故该状态是安全的。（2）P2提出请求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申请资源后的资源分配表资源情况进程AllocationNeedAvailableA B C DA B C DA B C DP00 0 3 20 0 1 20 4 0 0P11 0 0 01 7 5 0P21 3 5 41 1 3 4P30 3 3 20 6 5 2P40 0 1 40 6 5 6再利用安全性检查算法检查系统是否安全，可用资源available(0,4,0,0)已不能满足任何进程的需要，此时系统不能将资源分配给P2。9有桥如图2-7所示。北南桥车流如箭头所示，桥上不允许两车交会，但允许同方向多辆车依次通行（即桥上可以有多个同方向的车）。用P、V操作实现交通管理以防止桥上阻塞。解答：由于桥上不允许两车相会，故桥应该互斥访问，而同一方向上允许多辆车一次通过，即临界区允许多个实例访问。用同一信号量来互斥访问临界区。由于不能允许某一方向的车完全“控制桥”，应保证最多某一方向上连续通过一定数量的车后，必须让另一方向的车通过，可以通过3个信号量来控制。具体程序如下： Begin Integer:mutex,availn,abails; Mutes:=0;avialn:=m;avails:=m; Cobegin South: begin P(avails); P(mutex); 过桥； V(mutex); V(avails); End; North: begin P(availn); P(mutex); 过桥； V(mutex); V(availn); End;Coend;End;10 设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：最大需求量已分配资源量剩余资源量A B CA B CA B C P1 8 6 41 2 12 1 1 P2 4 3 33 1 1 P3 10 1 34 1 3 P4 3 3 33 2 2 P5 5 4 61 1 3(1) 系统是否处于安全状态？如是，则给出进程安全序列.(2) 如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？答案：（1） 最大需求量已分配资源量剩余资源量 尚需要量A B CA B CA B C A B C P1 8 6 41 2 12 1 1 7 4 3 P2 4 3 33 1 1 1 2 2 P3 10 1 34 1 3 6 0 0 P4 3 3 33 2 2 0 1 1 P5 5 4 61 1 3 4 3 3 系统是处于安全状态，安全序列为：P4，P2，P1，P3，P5 （2）P5申请（1，1，1） 最大需求量已分配资源量剩余资源量 尚需要量 A B CA B CA B C A B C P1 8 6 41 2 11 0 0 7 4 3 P2 4 3 33 1 1 1 2 2 P3 10 1 34 1 3 6 0 0 P4 3 3 33 2 2 0 1 1 P5 5 4 62 2 4 3 2 2 不能实施分配，因为分配后找不到安全序列，系统将处于不安全状态.31 有三个进程PA，PB和PC 合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录 ；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P，V操作来保证文件的正确打印。 解答：在本题中，进程PA，PB和PC之间的 关系为：PA 与PB共用一个单缓冲区，而PB又 与PC共用一个单缓冲区，其合作方式可用图2-10表示，当缓冲区1为空时，进程PA可将一个记录读入其中；若缓冲区1中有一个数据且缓冲区2为空，则进程PB可将记录从缓冲区1复制到缓冲区2中；若缓冲区2中有数据，则进程PC 可以打印记录，在其他条件下，相应进程必须等待。事实上，这是一个生产者消费者的问题打印缓冲区1缓冲区2PA从磁盘读入PBPC复制 图2-10 进程间的合作方式为遵循这一同步规则。应设置四个信号量 empty1，empty2，full1，full2，信号量 empty1及empty2分别表示缓冲区1及缓冲区2是否为空，其初值为1；信号量full1，full2分别表示缓冲区1及缓冲区2是否有记录可供处理，其初值为0。其同步描述如下： int empty1=1； int empty2=1； int full1=0; int full2=0;main ( ) cobegin PA( ); PB( ); PC( ); coend PA( ) while( 1 ) 从磁盘读一个记录; P (empty1）; 将记录存入缓冲区1； V(full1); PB( ) while(1) P(full1）; 从缓冲区1中取出记录; V(empty1); P (empty2); 将记录存入缓冲区2； V(full2); PC( ) while(1) P(full2); 从缓冲区2中取出记录; V(empty2); 打印记录; 本题也是一个 典型生产者消费者的问题，其中的难点在于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、1、3、2、1、3 试给出下列情形下的缺页次数: (1) 系统采用先进先出(FIFO)淘汰算法.(2) 系统采用最近最少使用(LRU)淘汰算法.用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-1       if rc=0 thenV(S);       V(Sr);       end ;     PROCESS Writer j (j=1,2)     begin P(S);           Write file;           V(S)     end;   coend ; end; 请回答：（1）信号量 Sr的作用；（2）程序中什么语句用于读写互斥，写写互斥；（3）若规定仅允许5个进程同时读怎样修改程序？答：（1）Sr用于读者计数rc的互斥信号量； （2）if rc=1 then P（S）中的P（S）用于读写互斥，写者进程中的P（S）用于写写互斥，读写互斥。（3）程序中增加一个信号量S5，初值为5，P（S5）语句加在读者进程P（Sr）之前，V（S5）语句加在读者进程第2个V（Sr）之后。  2考虑一个由8个页面、每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：(1)逻辑地址需要多少二进制位表示?(2)物理地址需要多少二进制位表示?  因为页面数为823，故需要3位二进制数表示。每页有1024个字节，1024210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示(3225)    (1)页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。    (2)页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。    1. 某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号051102437    计算逻辑地址0A5C(H)所对应的物理地址（要求写出分析过程）。1解：页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100，根据上面的分析，下划线部分为页内地址，编码“000 10”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00，拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。2.       假设一个磁盘有200个磁道，编号从0199。当前磁头正在143道上服务，并且刚刚完成了125道的请求。如果寻道请求队列的顺序是：86, 147, 91, 177, 94, 150, 102, 175, 130问：为完成上述请求，使用最短寻道时间优先磁盘调度算法SSTF时，磁头移动的总量是多少？（要求写出分析过程）采用最短寻道时间优先磁盘调度算法SSTF，进行调度的情况为：从143道开始下一磁道移动磁道数147150130102949186175177432028835892磁头移动总量为162。一、 设某文件的物理存储方式采用链接方式，该文件由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字节，并依次存放在50、121、75、80、63号磁盘块上。（10分）l 文件的第1569逻辑字节的信息存放在哪一个磁盘块上？l 要访问第1569逻辑字节的信息，需要访问多少个磁盘块？（假如该文件的FCB在内存）答：因为：1569=512×3+33所以要访问字节的逻辑记录号为3，对应的物理磁盘块号为80。故应访问第80号磁盘块。 由于采用链接方式，所以要访问第3个逻辑记录的信息，必须访问逻辑记录第0、1、2后，才能访问第3个逻辑记录，所以要访问第1569逻辑字节的信息，需要访问4个磁盘块。37.当磁头处于100号磁道时，有9个进程先后提出读写请求涉及的柱面号为63、57、34、88、91、103、76、18和128。要求：(1)写出按最短寻找时间优先算法SSTF时的调度次序;(2)计算按SSTF调度算法时的平均寻道数。答： (1)调度次序：100à103à91à88à76à63à57à34à18à128（2）总移过的道数为：3+12+3+12+13+6+23+16+110=198平均寻道数为：198/9=22(道)34. 哲学家就餐问题是一个经典的进程同步问题，该问题中描述有5个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的椅子上。在圆桌上有5只碗和5支筷子，平时哲学家们进行思考，饥饿时便试图取用其左、右两边的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子继续思考。为了解决哲学家就餐问题，可以用一个信号量表示一支筷子，由这5个信号量构成信号量数组:semaphore stick5；所有信号量初值为1，第1个哲学家的活动算法可以推述如下：semaphore stick5=1,1,1,1,1;main() cobegin Philosopehr(0); Philosopehr(1);Philosopehr(2);Philosopehr(3);Philosopehr(4); Coend; Philosopehr(int I) While(true) 思考； P(stickI); P(stick(I+1)%5); 进餐； v(stickI; v(stick(I+1)%5); 试问上述算法是否会发生死锁？为什么？若会发生死锁，请给出一个不会发生死锁的哲学家就餐算法。34答案上述算法可能发生死锁。例如，5个哲学家几乎同时饥饿而各自拿起左边的筷子时，使得5支筷子信号量均为0，当他们试图去拿右边筷子时，都将因无筷子拿而无限期地等待下去。对于上述算法的死锁问题有多种解决办法，这里给出两种解决方案。方案一：用额外的信号量mutex(初值为1)来控制对临界资源的使用。算法如下：Semaphore mutex=1;Philosopehr(int I) While(true) 思考； P(mutex); P(stickI); P(stick(I+1)%5); 进餐； v(stickI; v(stick(I+1)%5);改进的算法实质上是对资源申请过程进行限制，即要求一次申请完所有的资源，也就是在申请两个资源的过程中不被其他进程打断。且在系统满足该进程要求之前别的进程无法申请资源，因而也就可以避免死锁。方案二：对申请资源（筷子）的进程（哲学家）进行限制，要求至多允许4个哲学家同时进餐，以保证至少有一个哲学家能够拿到两支筷子进餐，最后总会进餐完毕并释放他占有的两支筷子，以使其他哲学家可以进餐。算法如下： Semaphore s=4; /用于控制同时进餐的人数Philosopehr(int I) While(true) 思考； P(s); P(stickI); P(stick(I+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个物理块的存储器中，试问逻辑地址和物理地址分别是多少位？为什么？ 答：因为每页大小为1024字节，故页内地址需要10个二进制位描述；作业的逻辑地址有8页，页号需要3个二进制位。由此可知，物理地址共需要15位。因为每个物理块与页大小相同，即大小为1024字节，故块内地址需要10个二进制位描述；内存空间容量为32块，块号需要个二进制位。由此可知，物理地址共需要15位。18. 假定某页式存储器管理系统中，主存为128KB，分为32块，块号为0、1、2、3、.、31；某作业有5块，其页号为0、1、2、3、4，被分别装入主存的3、8、4、6、9块中。有一逻辑地址为3,70。试求出相应的物理地址（其中方括号中的第一个元素为页号，第二个元素为页内地址，按十进制计算），并画图说明地址变换过程。答：由已知可得，块大小为128KB/32=4KB,因为块与页面大小相同，因此每页大小为4KB。再由题目可知，第3页被装入到主存第6块中，故逻辑地址3,70对应的物理地址为：4KB*6+70=24646。其地址变换过程如下图：页号（3） 页内地址（70）3 8