12操作系统复习题答案基本全部答案.docx

1、12操作系统复习题答案基本全部答案（一）进程同步进程同步1进程P1和进程P2并发执行时满足一定的时序关系，P1的代码段S1执行完后，才能执行P2的代码段S2.为描述这种同步关系，：试设计相应的信号量，：给出信号量的初始值，：给出进程P1和P2的结构解答: 信号量变量申明为Typedef struct int value; /信号量中的值，表示资源的数量 struct PCB *L; /等待该信号量的队列 semaphore;设信号量semaphore synch;初始值为：synch.value=0进程P1和P2的结构为P1: P2: S1 wait(synch); signal(synch)

2、; S2 进程同步2 问题描述：(理发店问题)一个理发店有一间配有n个椅子的等待室和一个有理发椅的理发室。如果没有顾客，理发师就睡觉；如果顾客来了二所有的椅子都有人，顾客就离去；如果理发师在忙而有空的椅子，顾客就会坐在其中一个椅子；如果理发师在睡觉，顾客会摇醒他。1给出同步关系2设计描述同步关系的信号量；3给出满足同步关系的进程结构(请完成满足同步关系的进程结构)。解答：顾客customer应满足的同步关系为： a:顾客来时要等空的椅子，否则不进理发室b:座椅上的顾客要等理发椅空才有可能与别的顾客竞争理发椅，如果顾客坐上理发椅，就要腾空其座椅给新来顾客，同时叫理发师给其理发。c：一旦顾客理发完

3、，就要让别的等待顾客有机会理发。理发师应满足的同步关系为： 一旦顾客唤醒，就给顾客理发，之后进入睡觉。 信号量定义如下：Typedef struct int value; /信号量中的值，表示资源的数量 struct PCB *L; /等待该信号量的队列 semaphore; 互斥信号量定义如下： Typedef struct bool flag; struct PCB *L;binary_semaphore;理发店问题的解决需要信号量和互斥信号量为：semaphore chair; binary_semaphore barber_chair, hair_cut;它们的初始值为：chair.v

4、alue=n; barber_chair.flag=1; hair_cut.flag=0; 顾客和理发师进程分别为： customer barber wait(chair); do waiting in the chair； wait(hair_cut); wait(barber_chair); cutting hair； signal(hair_cut); signal(barber_chair); sitting in barber chair for haircut; while(1) signal(chair); 进程同步2 设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆

5、，正常行车，到站停车；售票员的活动为关车门，售票，开车门。给出在汽车不断地到站、停车、行驶过程中，司机和售票员的活动的同步关系。用信号量和wait, signal操作实现他们间的协调操作。解答：根据一般的常识，有 售票员应满足的同步关系为：当司机停车后，才将车门打开让顾客上下车。 司机的同步关系为：当售票员关门后，才能开车. 设互斥信号量 binary_semaphore bus_closed,bus_stopped; 初始值为bus_closed.flag=0; bus_stopped.flag=0; /表达初始情况第一次用到信号量时情形为车门没有关，车是开着的 进程为: driver bu

6、sserver do do wait(bus_closed); closing the door; bus starting up； signal(bus_closed); bus is driving； ticket selling; bus is parking； wait(bus_stopped); signal(bus_stopped); opening the door; while(1) getting onoff the bus; while(1) 进程同步3： 某高校计算机系开设网络课并安排上机实习，假设机房共有2m台机器，有2n名学生选该课，规定：(1)每两个学生组成一组，各

7、占一台机器，协同完成上机实习；(2)只有凑够两个学生，并且此时机房有空闲机器，门卫才允许该组学生进入机房；(3)上机实习由一名教师检查，检查完毕，一组学生才可以离开机房。 试用信号量机制（P/V操作）实现它们的同步关系。解 (1)确定并发和顺序操作在这个问题中，学生(student)、检查教师(teacher)和门卫(gategard)是并行操作的，因此, 有多个学生(student)进程、一个检查教师(teacher)进程和一个门卫(gategard)进程。 (2)确定互斥和同步的规则 gateguard：只有凑够两个学生，并且此时机房有空闲机器时，门卫才分配计算机给学生，允许该组学生进入机

8、房； student：只有门卫分配完计算机后，学生才能进入机房上机操作。只有老师检查完毕才能离开。 Teacher：只有老师检查完学生的实习，才准许学生离开。(3)每个进程的操作流程 设立有学生到达标志，通知gateguard进程；学生是否可进入？上机实习；设立实习完成标志，通知教师；教师是否可检查，等待教师检查完毕；学生释放一台计算机资源； repeat 是否有学生实习完成？是否有学生实习完成？（是否有一组学生实习完成） 检查学生实习结果； 检查完成，允许学生1离开； 检查完成，允许学生2离开； until false repeat 等待学生1到达; 等待学生2到达; 是否有可用的计算机1;

9、 是否有可用的计算机2; 分配计算机； 设置学生1可进入标志; 设置学生2可进入标志; until false(4)确定信号量的个数和含义student：是否有学生;computer：是否有可用的计算机；enter：学生是否可以进入机房；finish：是否有学生完成实习；test： 老师是否检查完一组学生。(5)确定信号量的初值在初始状态，各信号量的初值如下：student=0 学生没有到达;compute=2m 有2m个可用的计算机；enter=0 不允许学生进入机房，因为需要得到门卫允许；finish=0 没有学生实习完成；test=0 老师没有检查学生。(6)确定P、V操作的位置设立有学

10、生到达标志，通知gateguard进程 =V(student)学生是否可进入？= P(enter)上机实习；设立实习完成标志，通知教师 = V(finish)教师是否可检查，等待教师检查完毕 = P(test(i) 学生释放一台计算机资源 = V(computer) repeat 是否有学生实习完成？=P(student)是否有学生实习完成？=P(student)（是否有一组学生实习完成） 检查学生实习结果； 检查完成，允许学生1离开 = V(test(i) 检查完成，允许学生2离开 = V(test(i) until false repeat 等待学生1到达 =P(student) 等待学生

11、2到达 =P(student) 是否有可用的计算机1 = P(computer) 是否有可用的计算机2 = P(computer) 分配计算机； 设置学生1可进入标志 = V(enter) 设置学生2可进入标志 = V(enter) until false(7)P、V操作实现 程序如下：student:=0;computer:=2m;enter:=0;finish:=0;test(i):=0;parbeginStudent i: Begin V(student); /*表示有学生到达，通知gateguard进程 */ P(enter); /*学生是否可进入*/ 上机实习； V(finish);

12、 /*实习结束，通知教师,有需要检查的学生*/ P(test(i); /*等待教师检查完毕*/ V(computer); /*释放计算机资源 End; . Teacher:Begin repeat P(finish); /*是否有需要检查的学生，等待实习完成*/ P(finish); /*是否有需要检查的学生，等待实习完成*/ 选出可检查的第i组学生；检查第i组学生实习结果； V(test(i); /*检查完成*/ V(test(i); /*检查完成*/ until false End; Gategard:Begin repeat. P(student); /*等待学生到达*/ P(stude

13、nt); /*等待另一学生到达*/ P(computer); /*是否有可用的计算机*/ P(computer); /*是否有可用的计算机*/ 分配计算机； V(enter); /*设置学生1可进入标志*/ V(enter); /*设置学生2可进入标志*/ untile false End;Parend;在student进程中，如果在一个学生到达后，立即向gateguard进程发信号，在gateguard进程为其分配计算机后，该学生才被允许进入机房，因此避免了让该学生争夺计算机的使用权和死锁的发生。进程同步4：多个进程对信号量S进行了5次 P操作，2次V操作后，现在信号量的值是 -3，与信号量

14、S相关的处于阻塞状态的进程有几个？信号量的初值是多少？ 解 (1)因为S的当前值是-3，因此因为S处于阻塞状态的进程有3个；(2)因为每进行一次P(S)操作，S的值都减1，每执行1次V操作S的值加1，故信号量的初值为-3+5-2=0;进程同步5：使用多个进程计算Y=F1(X)+F2 (X).解 (1)确定并发和顺序操作在这个问题中，F1(X)和F2 (X)的计算是可以并行处理的，因此F1(X)和F2 (X)可以分别出现在两个进程中。(2)确定互斥或同步的规则在F1(X)+F2 (X)中，必须在F1(X)和F2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。(3)同步的操作流程进程mai

15、n 创立进程p1来计算F1(X)； 创立进程p2来计算F2(X)； F1(X)计算是否完成？没有，等待； F2(X)计算是否完成？没有，等待； 进行加法运算。进程p1y1= F1(X)； 设置F1(X)计算完成标志； 进程p2 y1= F2(X)； 设置F2(X)计算完成标志。 (4)确定信号量的个数和含义根据同步规则以及操作流程确定信号量的个数是2个，S1和S2：S1含义是F1(X)计算是否完成； S2含义是F2(X)计算是否完成。 (5)确定信号量的初值S1=0；S2=0。 (6) 确定P、V操作的位置上面处是一个P操作，P(S1)；上面处是一个P操作，P(S2)；上面处是一个V操作，V(

16、S1)；上面处是一个V操作，V(S2)。解法1Main ( )Public y, y1, y2,. P1, P2Semaphore S1,S2 S1=0;S2=0;P1=Creat(N-F1, F1,x,);P2=Creat(N-F2, F2, x,);P(S1);P(S2);y=y1+y2;Procedure F1(x)y1= 计算1;V(S1)；Procedure F2(x)y2=计算2;V(S2)解法2Main ( )Public y, y1, y2,. P1,xSemaphore S1 input(x);S1=0;P1=Creat(N-F1, F1,x,);Y2=F2(x);P(S1)

17、;y=y1+y2;Procedure F1(x)y1= 计算1;V(S1)采用2个进程和1个信号量来实现Y=F1(X)+F2 (X)的时候，采用的方法是父进程创立子进程，F1(X)在子进程中计算，F2 (X)在父进程中计算，因此F1(X)和F2(X)计算仍然是并发进行的。S1信号量的含义为F1(X)是否完成。改进的方法比原来的方法节约一个进程和一个信号量，但并发操作的程度并没有降低。进程同步6：例 如下图所示，有多个PUT操作同时向BUFF1放数据，有一个MOVE操作不断地将BUFF1的数据移到Buff2，有多个GET操作不断地从Buff2中将数据取走。BUFF1的容量为m，BUFF2的容量是

18、n, PUT、 MOVE、 GET每次操作一个数据，在操作的过程中要保证数据不丢失。试用、原语协调PUT、 MOVE的操作，并说明每个信号量的含义和初值。GETPUTBuff1Buff2MOVE 图 4.2 进程操作图解(1)确定并发的操作 本问题是把2个消费者和生产者问题综合在一起。多个PUT操作与一个MOVE操作并发进行，多个GET操作与一个MOVE操作并发进行。因此本题涉及三类进程：PUT类进程，有多个；GET类进程，有多个；MOVE类进程，有1个。(2)操作规则1)只有buff1有空间才能进行PUT操作；2)只有buff1有数据，buff2有空间才能进行MOVE操作；3)只有buff2

19、有数据才能进行GET操作；4)不允许多个进程同时操作buff1；5)不允许多个进程同时操作buff2。(3)操作流程 repeat判断buff1是否有空间，没有则等待； 是否可操作buff1；PUT； 设置buff1可操作标志； 设置buff1有数据的标志； until false repeat判断buff1是否有数据，没有则等待；判断buff2是否有空间，没有则等待； 是否可操作buff1；是否可操作buff2；MOVE； 设置buff1可操作标志； 设置buff2可操作标志； 设置buff1有空间标志； 设置buff2有数据标志； until false repeat判断buff2是否有数

20、据，没有则等待； 是否可操作buff2；GET；设置buff1可操作标志； 设置buff1有空间标志；until false (4)信号量 设置6个信号量full1、empty1、B-M1、full2、empty2、B-M2，它们的含义和初值如下：1)full1表示buff1是否有数据，初值为0；2)empty1表示buff1有空间，初值为m；3)B-M1表示buff1是否可操作，初值为1；4)Full2表示buff2是否有数据，初值为0；5)Empty2表示buff2有空间，初值为n；6)B-M2表示buff2是否可操作，初值为1；(5)P、V操作实现 repeatP(empty1)； /*

21、判断buff1是否有空间，没有则等待 */ P(B-M1)； /*是否可操作buff1*/PUT； V(B-M1)； /*设置buff1可操作标志 */ V(full1)； /*设置buff1有数据的标志 */ until false repeatP(full1)； /*判断buff1是否有数据，没有则等待*/P(empty2)； /*判断buff2是否有空间，没有则等待*/ P(B-M1)； /*是否可操作buff1 */P(B-M2)； /*是否可操作buff2 */MOVE； V(B-M1)； /*设置buff1可操作标志*/ V(B-M2)； /*设置buff2可操作标志*/ V(em

22、pty1)； /*设置buff1有空间标志*/ V(full2)； /*设置buff2有数据标志*/ until false repeatP(empty2)； /*判断buff2是否有空间，没有则等待 */ P(B-M2)； /*是否可操作buff2*/GET； V(B-M2)； /*设置buff2可操作标志 */ V(full2)； /*设置buff2有数据的标志 */ until false 进程同步7：一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用P、V操作编程，并写出信号量的初值。解 购票者进程 P(S)； 进入售票厅； 购票

23、； 退出售票厅； V(S)； 信号量的初值 S=300进程同步8：针对如下所示的优先图解答下列问题：S1S4S2S3S5S6 图 4.4 进程优先图（1）仅使用并发语句能否将其转换成正确的程序？如果能则写出相应程序，如果不能则说明为什么？（2）若可以使用信号量机构，该优先图将如何转换成正确的程序？解 (1)如果仅用并发语句不能将其转换成程序。S2S5S2S4S3S5S12S4 因为S5有个前趋，S4有个前趋，S6有个前趋。(2)使用信号量机构，就可以将其转换成程序。Var a, b, c, d, e, f, g, h: Semaphores;初值均为0Parbegin Begin S1; V(

24、a); V(b); V(c); End Begin P(a); S2; V(d); V(e); EndBegin P(b); S3; V(f); End Begin P(c); S4; V(h); End Begin P(d); P(f); S5; V(g); End Begin P(g); P(h); S6; EndParend（二）死锁死锁1 ：5个进程，3种资源，某个时刻，资源分配情况如下： Allocation Max Available A B C A B C A B CP0 0 1 0 7 5 3 ,3 3 2P1 2 0 0 3 2 2 P2 3 0 2 9 0 2P3 2 1

25、1 2 2 2P4 0 0 2 4 3 3问：系统是否处于安全状态？如果P1再提出请求1个A类，2个C类资源，是否该批准？ 解答：由Allocation 和Max矩阵得到，系统未来需求矩阵为：Need=,在当前的资源分配状态可以有安全的分配序列p1,p3,p4,p2,p0,具体分析如下：Available(3, 3, 2)可以满足P1的未来请求(1, 2, 2),P1得到执行，释放资源； Available(5, 3, 2)可以满足P3的未来请求(0, 1, 1),P3得到执行, 释放资源； Available(7, 4, 3)可以满足P4的未来请求(4, 3, 1),P4得到执行，释放资源；

26、 Available(7, 4, 5)可以满足P2的未来请求(6,0,0),P2得到执行，释放资源； Available(9, 4, 5)可以满足P0的未来请求(6, 4, 3),P0得到执行，释放资源。 所以，系统当前的状态是安全的。 对P1提出的分配请求(1, 0, 2)，假设分配予以满足后，系统状态为： Allocation= ，Need=，Available=(2, 3, 0),由于可用资源无法满足任何一个进程未来的请求，这样系统就处于不安全状态，所以，对进程P1的请求，不能予以满足。解答：死锁2： 假设一个系统有某类资源m个，被n个进程共享，进程每次只请求和释放一个资源， 证明只要系

27、统满足下面两个条件，就不会发生死锁：(1)每个进程需求资源的最大值在1到m之间；(2)所有进程需要资源的最大值的和小于m+n。解答：由题目有条件 ： i= 1 Maxi m + n， m Maxi 1, ： Needi=Maxi-Allocationi 。如果存在死锁，还有条件： i=1 Allocationi= m 由和得： i= 1Needi+ i= 1Allocationi= i= 1 Maxi m + n 由得： i= 1Needi+ m m + n, i= 1Needi n，所以，至少一个进程满足Needi=0,该进程可以执行完，释放占有的资源，所以，目前状态不是死锁状态。 死锁3：

28、和死锁1相同，系统的资源数量为：（10，5，7）。经过一段时间的分配后，资源分配与占用情况见下表所示。 进程MAX A B CAllocation A B CNeed A B CAvailable A B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1分析进程P0的请求(0, 1, 0)能否满足？死锁4：假设系统有4个相容类型的资源被3个进程共享，每个进程最多需要2个资源，证明这个系统不会死锁。 证明：每个进程请求共享资源的最大量相等，且为x，（0x2，x是整数），那么在最坏的情况下每个进程都占有（x-1）个共享资源，并各自最多再申请一个资源就可以运行完毕，进而释放它们所占有的全部资源。此刻，系统剩余的可用资源数为：4 - 3*(x-1)。此时不论x为1还是2，4 3*(x-1)1时，系统不会出现死锁的。进程调度与死锁5： 有三个进程P1，P2和P3并发工作，进程P1需用资源S3和S1，进程P2需用资源S1和S2，进程P3需用资源S2和S3。回答。(1)若对资源分配不加限制，会发生什么情况?为什么?(