《厦门大学操作系统56章习题讲解汇编》由会员分享，可在线阅读，更多相关《厦门大学操作系统56章习题讲解汇编（33页珍藏版）》请在金锄头文库上搜索。
1、5-6章作业,P177复习题5.8,在信号量上可执行的操作： 初始化=0（一般情况） semWait原语，值减1 如果值变为负数，则执行semWait的进程被阻塞 semSignal原语，值加1 如果值小于或等于0，则唤醒一个该信号量的阻塞进程,P177复习题5.11,什么是管程？ 管程（Monitor）是一个程序设计语言结构，它提供与信号量同样的功能，但更易于操作 管程是一个软件模块 一个或多个过程 一个初始化序列 局部数据,P177复习题5.13,与读者-写者问题相关联的条件： 任意多的读进程可以同时读一个文件 一次只有一个写进程可以往文件中写 如果一个写进程正在往文件中写时，则禁止任何读
2、进程读文件,P179习题5.2,一个并发程序，它的两个进程p与q，A、B、C、D、E是任意的原子语句。设主程序执行两个进程的parbegin。 void p()A;B;C; void q()D;E; 给出这两个进程所有可能的交替执行（根据原子语句给出执行轨迹） ABCDE; ABDCE; ABDEC; ADBCE; ADBEC; ADEBC;DEABC; DAEBC; DABEC; DABCE,P179习题5.3,考虑右边的程序： a、确定由这个并发程序输出的共享变量最后值的上限与下线。设进程可以以任意相对速度执行，并当一个值由独立的机器指令载入一个寄存器中后，它只能增1. b、在a的假设下，
3、允许任意多的进程并发执行，tally值的范围？,const int n=50; int tally; void total() int count; for(count=1;count=n;count+) tally+; void main() tally=0; parbegin(total(),total(); write(tally); ,P179习题5.3,a. 乍一看,tally的范围好像是落在50,100 这个区间里,因为当没有互斥时可以从0直接增加到50.这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得tally值还低的一个最终tally值.但是考虑
4、下面由这两进程按交替顺序执行载入,增加,存储的情况下同时变更这个共享变量的取值:,1.进程A载入tally值,并将tally的值加到1,在此时失去处理器(它已经增加寄存器的值到1,但是还没有存储这个值). 2.进程B载入tally值(仍然是0),然后运行完成49次增加操作,在它已经将49这个值存储给共享变量tally后,失去处理器控制权. 3.进程A重新获得处理器控制权去完成它的第一次存储操作(用1去代替先前的49这个tally值),此时被迫立即放弃处理器. 4.进程B重新开始,将1(当前的tally值)载入到它自己的寄存器中,但此时被迫放弃处理器(注意这是B的最后一次载入). 5.进程A被重
5、新安排开始,但这次没有被中断,直到运行完成它剩余的49次载入,增加和存储操作,结果是此时tally值已经是50. 6.进程B在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至2,同时存储这个值做为这个共享变量的最终结果. 一些人认为会出现低于2这个值的结果,这种情况是不会出现.所以 tally值的正确范围是2,100.,P182习题5.3,P182习题5.3,b、在a的假设下，允许任意多的进程并发执行，tally值的范围？ 对一般有N个进程的情况,tally值的最终范围是2,N*50,因为对其他所有进程来说,从最初开始运行到在第五步完成.但最后都被进程B破坏掉它们的最终结果.,P18
6、2习题5.13,考虑图5.10中定义的无限缓冲区生产者/消费者问题的解决方案，设生产者与消费者都以大致相同的速度运行，运行情况如下： 生产者：append;semSignal;produce;.;append;semSignal;produce;.; 消费者：consume;.;take;semWait;consume;.;take;semWait;.;,生产者通常管理给缓冲区添加一个新元素，并在消费者消费了前面的元素后发出信号。生产者通常添加到一个空缓冲区中，而消费者通常取走缓冲区中的惟一元素。消费者从不在信号量上阻塞，但必须进行大量的信号量调用，产生相当多的开销。 构造新程序，使之更有效。
7、 提示：允许n的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生产者产生新的数据。这个方案不要图5.10中的局部变量m 。,P182习题5.13,P182习题5.13,program producerconsumer; var n: integer; s: (*binary*) semaphore (:= 1); delay: (*binary*) semaphore (:= 0); procedure producer; begin repeat produce; semWaitB(s); append; n := n + 1; if n=0 then semSi
8、gnalB(delay); semSignalB(s) forever end;,P182习题5.13,procedure consumer; begin repeat semWaitB(s); take; n := n - 1; if n = -1 then begin semSignalB(s); semWaitB(delay); semWaitB(s) end; consume; semSignalB(s) forever end; begin (*main program*) n := 0; parbegin producer; consumer parend,P182习题5.14,考
9、虑图5.13，若发生下面的交换，程序的意义是否会改变？ a. semWait(e);semWait(s) b. semSignal(s);semSignal(n) c. semWait(n);semWait(s) d. semSignal(s);semSignal(e),P182习题5.14,P182习题5.14,信号量s控制对临界区的访问，在临界区只包含append 或take 操作。 AC会导致死锁。 BD不变，但效率变低（临界区变长）。,p211复习题 6.2,可能发生死锁所必需的三个条件： 互斥 一次只有一个进程可以使用一个资源 占有且等待 一个进程在等待其它资源分配时，继续占有已分配
10、的资源 非抢占 不能强行抢占已分配给其它进程的资源 除非进程主动释放,p211复习题6.3,产生死锁的第四个条件： 循环等待 资源分配图中存在一条封闭的进程链,p212习题6.3,证明图6.3所反映的情况不会发生死锁（图见P186）,资源可重用的，P、Q同时申请B，Q获得B，P、Q同时申请A，P获得A，Q释放B，P得到A，P释放A，Q得到A，不构成死锁的第四个条件。,p212习题6.5,把6.4节中的死锁检测算法应用于下面的数据，给出结果。 Available=(2 1 0 0) Request Allocation 2 0 0 1 0 0 1 0 1 0 1 0 2 0 0 1 2 1 0
11、0 0 1 2 0,p212习题6.5,1. W = (2 1 0 0) 2. Mark P3; W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0) 3. Mark P2; W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1) 4. Mark P1; no deadlock detected,算法步骤见P195,p212习题6.6,一个假脱机系统（如图示）含一个输入进程I、用户进程P和一个输出进程0，他们之间用两个缓冲区连接。进程以相等大小块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘上，并取决于进程的速度，所用的通信原
12、语满足下面的资源约束：i+o=max max表磁盘中的最大块数，i表示输入块数，o表输出块数,输入缓冲区,输出缓冲区,I,P,0,p212习题6.6,说明可能死锁 当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。,p213习题6.7,给出在习题.中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程的要求变化。 为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一个界限。 资源限制现在变成 + max max
13、reso 其中 0 reso max 如果程序 P 正在等候递送输出给磁盘, 程序 O 最后处理所有的早先输出而且产生至少reso页, 然后让 P 继续执行。 因此 P 不会因为 O 而延迟。 如果磁盘充满I/O，能被延迟; 但是迟早, 所有的早先的 输入可以被处理完，而且对应的输出将会被 O 处理, 因而可以让继续执行。,p213习题6.10,考虑一个共有150个存储单元的系统，其单元分给三个进程 进程 最大 占有 1 70 45 2 60 40 3 60 15 使用银行家算法，确定下面的请求是否安。如果安全，说明能保证的终止序列；如果不安全，给出结果分配简表,p213习题6.10,a 第4
14、个进程到达，最多要60个存储单元，最初要25个单元。 不会死锁，剩下存储单元数： 150-（45+40+15+25）=25 满足进程1，2，可任选一个，执行完后可满足其它 安全顺序是1234 b 第4个进程到达，最多要60个存储单元，最初要35个单元。 会死锁，剩下存储单元数： 150-（45+40+15+35）=15,银行家算法： 测试进程对资源的最大需求，若系统当前的剩余资源满足它的最大需求，则满足进程的当前的申请，否则，推迟分配。这样能保证至少有一个进程获得资源的最大需求而运行，结束后释放资源供其它进程用。 a b,p214习题6.13,a 3个进程共享4个资源单元，一次只能保留或释放一
15、个单元，每个进程最大需要2个单元。说明不会发生死锁。 由于每个进程最多需要2个资源，最坏情况下，每个进程需要获得一个，系统还剩1个，这一个资源，无论分给谁都能完成。完成进程释放资源后，使剩余进程也完成，故系统不会死锁。,p214习题6.13,b N个进程共享M个资源单元，一次只能保留或释放一个单元，每个进程最大需求单元数不超过M，并且所有最大需求的总和小于M+N。说明不会发生死锁。 方法一： 假定每个进程最多申请X个资源，最坏情况下，每个进程都得到X-1个资源都在申请最后一个资源，这时系统剩余资源数量为M-N(X1)，只要系统还有一个剩余资源，就可以使其中的一个进程获得所需要的全部资源，该进程
16、运行结束以后释放资源，就可以使其他进程得到全部资源的 满足，因此，当M-N(X-1)1时系统不会发生死锁，解这个不等式X（M+N-1）,系统不会发生死锁，因此，当所有进程的需求总和小于M+N时，系统是不会发生死锁的。,p214习题6.13,方法二： 每个进程有Ni个资源未分配，有Ai个资源已分配 则Ci= Ai+ Ni M+N 假设死锁： Ai=M，则NiN,至少有一个Nk为0，矛盾,p214习题6.14,考虑一个由四个进程和一个单独资源组成的系统，当前的声明和分配矩阵是 3 1 2 1 C = 9 A= 3 7 2 对于安全状态，需要的最小资源数目是多少？ 最小资源数是个，总共有个资源。获得一个资源，完成后释放两个资源，获得三个资源，完成后释放三个资源，接下来获得五个资源，释放完资源
