操作系统复习宝典 (老师就是从里边出题的)

（一）进程同步进程同步4多个进程对信号量S进行了5次wait操作，2次signal操作后，现在信号量的值是-3，与信号量S相关的处于阻塞状态的进程有几个？信号量的初值是多少？解(1)因为S的当前值是-3，因此因为S处于阻塞状态的进程有3个；(2)因为每进行一次wait(S)操作，S的值都减1，每执行1次signal操作S的值加1，故信号量的初值为-3+5-2=0;进程同步5使用多个进程计算Y=F1(X)+F2(X).在这个问题中，F1(X)和F2(X)的计算是可以并行处理的，因此F1(X)和F2(X)可以分别出现在两个进程中。在F1(X)+F2(X)中，必须在F1(X)和F2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。解(1)确定并发和顺序操作在这个问题中，F1(X)和F2(X)的计算是可以并行处理的，因此F1(X)和F2(X)可以分别出现在两个进程中。(2)确定互斥或同步的规则在F1(X)+F2(X)中，必须在F1(X)和F2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。(3)同步的操作流程〈进程main〉创立进程p1来计算F1(X)；创立进程p2来计算F2(X)；F1(X)计算是否完成？没有，等待；①F2(X)计算是否完成？没有，等待；②进行加法运算。〈进程p1〉y1=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(S1)；上面④处是一个V操作，V(S2)。解法1Main()Publicy,y1,y2,.P1,P2SemaphoreS1,S2{S1=0;S2=0;P1=Creat(N-F1,F1,x,……);P2=Creat(N-F2,F2,x,……);P(S1);P(S2);y=y1+y2;}ProcedureF1(x){y1=计算1;V(S1)；}ProcedureF2(x){y2=计算2;V(S2)}解法2Main()Publicy,y1,y2,.P1,xSemaphoreS1{input(x);S1=0;P1=Creat(N-F1,F1,x,……);Y2=F2(x);P(S1);y=y1+y2;}ProcedureF1(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的容量是n,PUT、MOVE、GET每次操作一个数据，在操作的过程中要保证数据不丢失。试用Ｐ、Ｖ原语协调PUT、MOVE的操作，并说明每个信号量的含义和初值。图4.2进程操作图解(1)确定并发的操作本问题是把2个消费者和生产者问题综合在一起。多个PUT操作与一个MOVE操作并发进行，多个GET操作与一个MOVE操作并发进行。因此本题涉及三类进程：PUT类进程，有多个；GET类进程，有多个；MOVE类进程，有1个。(2)操作规则1)只有buff1有空间才能进行PUT操作；2)只有buff1有数据，buff2有空间才能进行MOVE操作；3)只有buff2有数据才能进行GET操作；4)不允许多个进程同时操作buff1；5)不允许多个进程同时操作buff2。(3)操作流程PUT类进程{repeat判断buff1是否有空间，没有则等待；是否可操作buff1；PUT；设置buff1可操作标志；设置buff1有数据的标志；untilfalse}MOVE类进程{repeatGETPUTBuff1Buff2MOVE判断buff1是否有数据，没有则等待；判断buff2是否有空间，没有则等待；是否可操作buff1；是否可操作buff2；MOVE；设置buff1可操作标志；设置buff2可操作标志；设置buff1有空间标志；设置buff2有数据标志；untilfalse}GET类进程{repeat判断buff2是否有数据，没有则等待；是否可操作buff2；GET；设置buff1可操作标志；设置buff1有空间标志；untilfalse}(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操作实现PUT类进程{repeatP(empty1)；/*判断buff1是否有空间，没有则等待*/P(B-M1)；/*是否可操作buff1*/PUT；V(B-M1)；/*设置buff1可操作标志*/V(full1)；/*设置buff1有数据的标志*/untilfalse}MOVE类进程{repeatP(full1)；/*判断buff1是否有数据，没有则等待*/P(empty2)；/*判断buff2是否有空间，没有则等待*/P(B-M1)；/*是否可操作buff1*/P(B-M2)；/*是否可操作buff2*/MOVE；V(B-M1)；/*设置buff1可操作标志*/V(B-M2)；/*设置buff2可操作标志*/V(empty1)；/*设置buff1有空间标志*/V(full2)；/*设置buff2有数据标志*/untilfalse}GET类进程{repeatP(empty2)；/*判断buff2是否有空间，没有则等待*/P(B-M2)；/*是否可操作buff2*/GET；V(B-M2)；/*设置buff2可操作标志*/V(full2)；/*设置buff2有数据的标志*/untilfalse}进程同步7一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用P、V操作编程，并写出信号量的初值。解〈购票者进程〉{┋P(S)；进入售票厅；购票；退出售票厅；V(S)；}信号量的初值S=300进程同步8针对如下所示的优先图解答下列问题：S1S4S2S3S5S6图4.4进程优先图（1）仅使用并发语句能否将其转换成正确的程序？如果能则写出相应程序，如果不能则说明为什么？（2）若可以使用信号量机构，该优先图将如何转换成正确的程序？解(1)如果仅用并发语句不能将其转换成程序。因为S5有２个前趋，S4有２个前趋，S6有２个前趋。(2)使用信号量机构，就可以将其转换成程序。Vara,b,c,d,e,f,g,h:Semaphores;{初值均为0}ParbeginBeginS1;V(a);V(b);V(c);EndBeginP(a);S2;V(d);V(e);EndBeginP(b);S3;V(f);EndBeginP(c);S4;V(h);EndBeginP(d);P(f);S5;V(g);EndBeginP(g);P(h);S6;EndParend进程调度与死锁5有三个进程P1、P2和P3并发工作。进程P1需要资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3，回答：（1）若对资源分配不加限制，会发生什么情况？为什么？（2）为保证进程正确地工作，应采用怎样的资源分配策略？为什么？解(1)若对进程间的资源分配不加限制，可能会发生死锁，因为这样的分配可能导致进程间的“循环等待”，并且这种状态将永远持续下去。进程P1、P2和P3分别获得资源S3、S1和S2，后再继续申请资源时都要等待。进程和资源会形成如下环路：图4.3进程资源分配图(2)为保证系统处于安全状态，应采用下面列举3种资源分配策略：1)采用静态分配:由于执行前已获得所需的全部资源，故不会出现占有资源又S2S5S2S4S3S5S12S4等待的资源的现象（或不会出现循环等待资源现象）。2)采用资源按序分配，避免出现循环等待资源的现象。3)采用银行家算法进行分配资源前的检测。进程调度与死锁6有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。(1)先来先服务（按A，B，C，D，E）算法。(2)优先级调度算法。(3)时间片轮转算法。解(1)采用先来先服务（FCFS）调度算法时，5个任务在系统中的执行顺序、完成时间及周转时间如下表所示：执行次序运行时间优先数等待时间周转时间A103010B651016C221618D411822E842230根据表中的计算结果，5个进程的平均周转时间T为：T=（10+16+18+22+30）/5=19.2min(2)采用最高优先级调度（HPF）算法时，5个任务在系统中的执行顺序、完成时间及周转时间如下表所示：执行次序运行时间优先数等待时间周转时间B6506E84614A1031424C222426D112627它们的平均周转时间为：T=（6+14+24+26+27）/5=19.4min(3)如果系统采用时间片轮转（RR）算法，令时间片为2分钟，5个任务轮流执行的情况为：第1轮：（A，B，C，D，E）第2轮：（A，B，D，E）第3轮：（A，B，E）第4轮：（A，E）第5轮：（A）显然，5个进程的周转时间为：T1=30min、T2=22min、T3=6min、T4=16min、T5=28min。它们的平均周转时间T为：T=（30+22+6+16+28）/5=20.4min进程调度与死锁7设某系统进程的状态除了最基本的三种状态外，还增加了创建状态、延迟状态和完成状态。试画出系统的进程状态变迁图，并说明状态变迁可能的原因。解一般的多道程序运行环境中，进程最基本的状态有3个：就绪、运行、阻塞。本题又增加了创建、延迟、完成3种状态，使进程状态增至6个。图4.3进程状态转换配图(1)就绪→运行：进程具备运行条件，当进程调度程序选择了进程后，便将其转入运行状态。(2)运行→阻塞：进程需要等待某种事件的发生，如执行了输入输出指令，或者请求资源得不到满足时，进程转阻塞状态。(3)阻塞→就绪：进程等待的I/O已完成，或者请求的资源得到满足，进程转为就绪状态。(4)创建→就绪：进程尚不具备运行条件，所需的资源尚未得到满足。当进程创建完成后，进程可转入就绪状态。(5)运行→延迟：进程运行过程中，因某种原因需要延迟运算，则设定好延迟时间后被转入延迟状态。(6)运行→完成：进程运行时遇到结束指令后，被转入完成状态。进程调度与死锁8一个计算机系统中拥有6台打印机，现有N个进程竞争使用，每个进程要求两台，试问，N的值如何选取时系统中绝对不会出现死锁？解本题的考核要点是资源竞争与死锁问题。已知系统中的每个进程需要两台打印机，那么在最坏的情况下，各进程都占用了其中的一台，而且都在请求自己所需的另一台。如果此时系统尚有多余的一台，那么就可以满足其中一个进程运行完毕。因此说，如果让6-1台打印机分给N个进程，满足它们每人一台的话，进程数量N必然小于等于5。当该进程运行完毕释放出它所占有的打印机后，又可以进一步满足其他进程。系统就不会出现死锁。内存管理5有一计算机系