厦门大学操作系统5-6章习题讲解

1、5-6章作业P177复习题复习题5.8 在信号量上可执行的操作： 初始化初始化=0（一般情况）（一般情况） semWait原语，值减原语，值减1 如果值变为负数，则执行如果值变为负数，则执行semWait的进程被阻塞的进程被阻塞 semSignal原语，值加原语，值加1 如果值小于或等于如果值小于或等于0，则唤醒一个该信号量的阻塞进，则唤醒一个该信号量的阻塞进程程P177复习题复习题5.11 什么是管程？ 管程（管程（Monitor）是一个程序设计语言结构，）是一个程序设计语言结构，它提供与信号量同样的功能，但更易于操它提供与信号量同样的功能，但更易于操作作 管程是一个软件模块管程是一个软件模

2、块 一个或多个过程一个或多个过程 一个初始化序列一个初始化序列 局部数据局部数据P177复习题复习题5.13 与读者-写者问题相关联的条件： 任意多的读进程可以同时读一个文件任意多的读进程可以同时读一个文件 一次只有一个写进程可以往文件中写一次只有一个写进程可以往文件中写 如果一个写进程正在往文件中写时，则禁止任如果一个写进程正在往文件中写时，则禁止任何读进程读文件何读进程读文件P179习题习题5.2 一个并发程序，它的两个进程p与q，A、B、C、D、E是任意的原子语句。设主程序执行两个进程的parbegin。 void p()A;B;C; void q()D;E; 给出这两个进程所有可能的交

3、替执行（根据原子语句给出执行轨迹） ABCDE; ABDCE; ABDEC; ADBCE; ADBEC; ADEBC;DEABC; DAEBC; DABEC; DABCE P179习题习题5.3考虑右边的程序： a、确定由这个并发程序输出的共享变量最后值的上限与下线。设进程可以以任意相对速度执行，并当一个值由独立的机器指令载入一个寄存器中后，它只能增1.b、在a的假设下，允许任意多的进程并发执行，tally值的范围？const int n=50;int tally;void total()int count;for(count=1;count=n;count+)tally+;void main

4、()tally=0;parbegin(total(),total();write(tally);P179习题习题5.3 a. 乍一看,tally的范围好像是落在50,100 这个区间里,因为当没有互斥时可以从0直接增加到50.这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得tally值还低的一个最终tally值.但是考虑下面由这两进程按交替顺序执行载入,增加,存储的情况下同时变更这个共享变量的取值:1.进程A载入tally值,并将tally的值加到1,在此时失去处理器(它已经增加寄存器的值到1,但是还没有存储这个值).2.进程B载入tally值(仍然是0),然后

5、运行完成49次增加操作,在它已经将49这个值存储给共享变量tally后,失去处理器控制权.3.进程A重新获得处理器控制权去完成它的第一次存储操作(用1去代替先前的49这个tally值),此时被迫立即放弃处理器.4.进程B重新开始,将1(当前的tally值)载入到它自己的寄存器中,但此时被迫放弃处理器(注意这是B的最后一次载入).5.进程A被重新安排开始,但这次没有被中断,直到运行完成它剩余的49次载入,增加和存储操作,结果是此时tally值已经是50.6.进程B在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至2,同时存储这个值做为这个共享变量的最终结果. 一些人认为会出现低于2这个

6、值的结果,这种情况是不会出现.所以 tally值的正确范围是2,100.P182习题习题5.3P182习题习题5.3b、在a的假设下，允许任意多的进程并发执行，tally值的范围？对一般有N个进程的情况,tally值的最终范围是2,N*50,因为对其他所有进程来说,从最初开始运行到在第五步完成.但最后都被进程B破坏掉它们的最终结果.P182习题习题5.13考虑图5.10中定义的无限缓冲区生产者/消费者问题的解决方案，设生产者与消费者都以大致相同的速度运行，运行情况如下：生产者：append;semSignal;produce;.;append;semSignal;produce;.;消费者：c

7、onsume;.;take;semWait;consume;.;take;semWait;.;生产者通常管理给缓冲区添加一个新元素，并在消费者消费了前面的元素后发出信号。生产者通常添加到一个空缓冲区中，而消费者通常取走缓冲区中的惟一元素。消费者从不在信号量上阻塞，但必须进行大量的信号量调用，产生相当多的开销。构造新程序，使之更有效。提示：允许n的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生产者产生新的数据。这个方案不要图5.10中的局部变量m 。P182习题习题5.13P182习题习题5.13programproducerconsumer;varn: integ

8、er;s: (*binary*) semaphore (:= 1);delay: (*binary*) semaphore (:= 0);procedure producer;beginrepeatproduce;semWaitB(s);append;n := n + 1;if n=0 then semSignalB(delay);semSignalB(s)foreverend;P182习题习题5.13procedure consumer;beginrepeatsemWaitB(s);take;n := n - 1;if n = -1 thenbeginsemSignalB(s);semWai

9、tB(delay);semWaitB(s)end;consume;semSignalB(s)foreverend;begin (*main program*)n := 0;parbeginproducer; consumerparendP182习题习题5.14 考虑图5.13，若发生下面的交换，程序的意义是否会改变？ a. semWait(e);semWait(s) b. semSignal(s);semSignal(n) c. semWait(n);semWait(s) d. semSignal(s);semSignal(e)P182习题习题5.14P182习题习题5.14 信号量s控制对临

10、界区的访问，在临界区只包含append 或take 操作。 AC会导致死锁。 BD不变，但效率变低（临界区变长）。p211复习题 6.2可能发生死锁所必需的三个条件：互斥一次只有一个进程可以使用一个资源占有且等待一个进程在等待其它资源分配时，继续占有已分配的资源非抢占不能强行抢占已分配给其它进程的资源 除非进程主动释放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，不构成死锁的第

11、四个条件。p212习题6.5 把6.4节中的死锁检测算法应用于下面的数据，给出结果。 Available=(2 1 0 0) Request Allocation2 0 0 1 0 0 1 01 0 1 0 2 0 0 12 1 0 0 0 1 2 0p212习题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 算法步骤见P195p212习

12、题6.6 一个假脱机系统（如图示）含一个输入进程I、用户进程P和一个输出进程0，他们之间用两个缓冲区连接。进程以相等大小块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘上，并取决于进程的速度，所用的通信原语满足下面的资源约束：i+o=max max表磁盘中的最大块数，i表示输入块数，o表输出块数输入缓冲区输出缓冲区IP0p212习题6.6 说明可能死锁 当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。p213习题6.7 给出在习题.中预防死锁的附

13、加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程的要求变化。为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一个界限。 资源限制现在变成 + max max reso其中 0 reso max如果程序 P 正在等候递送输出给磁盘, 程序 O 最后处理所有的早先输出而且产生至少reso页, 然后让 P 继续执行。 因此 P 不会因为 O 而延迟。如果磁盘充满I/O，能被延迟; 但是迟早, 所有的早先的输入可以被处理完，而且对应的输出将会被 O 处理,因而可以让继续执行。p213习题6.10 考虑一个共有150个存储单元的系统，其单元分给三个

14、进程 进程最大占有 17045 26040 36015使用银行家算法，确定下面的请求是否安。如果安全，说明能保证的终止序列；如果不安全，给出结果分配简表p213习题6.10a 第4个进程到达，最多要60个存储单元，最初要25个单元。 不会死锁，剩下存储单元数： 150-（45+40+15+25）=25 满足进程1，2，可任选一个，执行完后可满足其它 安全顺序是1234b 第4个进程到达，最多要60个存储单元，最初要35个单元。 会死锁，剩下存储单元数： 150-（45+40+15+35）=15银行家算法：测试进程对资源的最大需求，若系统当前的剩余资源满足它的最大需求，则满足进程的当前的申请，否

15、则，推迟分配。这样能保证至少有一个进程获得资源的最大需求而运行，结束后释放资源供其它进程用。abp214习题6.13a 3个进程共享4个资源单元，一次只能保留或释放一个单元，每个进程最大需要2个单元。说明不会发生死锁。由于每个进程最多需要2个资源，最坏情况下，每个进程需要获得一个，系统还剩1个，这一个资源，无论分给谁都能完成。完成进程释放资源后，使剩余进程也完成，故系统不会死锁。p214习题6.13b N个进程共享M个资源单元，一次只能保留或释放一个单元，每个进程最大需求单元数不超过M，并且所有最大需求的总和小于M+N。说明不会发生死锁。方法一：假定每个进程最多申请X个资源，最坏情况下，每个进

16、程都得到X-1个资源都在申请最后一个资源，这时系统剩余资源数量为M-N(X1)，只要系统还有一个剩余资源，就可以使其中的一个进程获得所需要的全部资源，该进程运行结束以后释放资源，就可以使其他进程得到全部资源的 满足，因此，当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 考虑一个由四个进程和一个单独资源组成的

17、系统，当前的声明和分配矩阵是 3 1 2 1 C = 9 A= 3 7 2 对于安全状态，需要的最小资源数目是多少？ 最小资源数是个，总共有个资源。获得一个资源，完成后释放两个资源，获得三个资源，完成后释放三个资源，接下来获得五个资源，释放完资源后，获得所需的个资源后完成。p214习题6.17假设有两种类型的哲学家。一类总是先拿起左边的叉子（左撇子），另一类总是先拿起右边的叉子（右撇子）。左撇子的行为和图.中定义的一致。右撇子的行为如下：begin repeat think; wait(fork(i+1)mod5); wait(forki);eat;signal(forki);signal(f

18、ork(i+1)mod5);forever;end;证明：a如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁。b如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿。p214习题6.17a 如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁假设存在死锁情况，设有 D个哲学家，他们每人都有一支叉子而且另一支叉子被邻居占有。不失一般性，设Pj 是一个左撇子。 Pj 抓牢他的左边叉子而且没有他的右边叉子, 他的右边邻居 Pk 没有完成就餐因此也是一个左撇子。 因此依次推理下去所有这个哲学家都是左撇子。这与既有左撇子又有右撇子的条件矛盾，假设不成立，不存在死锁。p214习题6.17b 如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿假设左撇子 Pj 饥饿，也就是说，有一部分人在就餐而Pj从不吃。 假如 Pj 没有叉子。 这样 Pj 的左边邻居 Pi 一定持续