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

p214习题6.17 a 如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁 假设存在死锁情况，设有 D个哲学家，他们每人都有一支叉子而且另一支叉子被邻居占有。不失一般性，设Pj 是一个左撇子。 Pj 抓牢他的左边叉子而且没有他的右边叉子, 他的右边邻居 Pk 没有完成就餐因此也是一个左撇子。 因此依次推理下去所有这Ｄ个哲学家都是左撇子。这与既有左撇子又有右撇子的条件矛盾，假设不成立，不存在死锁。 p214习题6.17 b 如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿 假设左撇子 Pj 饥饿，也就是说，有一部分人在就餐而Pj从不吃。 假如 Pj 没有叉子。 这样 Pj 的左边邻居 Pi 一定持续地占有叉子而始终不吃完。 因此Pi 是 右撇子，抓住他的右边叉子, 但是从不得到他的左边叉子来完成就餐,也就是说 Pi也饥饿。 现在 Pi 左边邻居也一定是持续占有右边叉子的右撇子。 向左进行这样的推理，得出所有哲学家都是饥饿的右撇子，这同Pj是个左撇子矛盾。因此 Pj 一直拥有左边子而且在等待他的右边叉子,Pj 的右边邻居 Pk 一直举着他的左边叉子而且从不完成一餐,也就是, Pk 是也饥饿的左撇子。 如果 Pk 不是一直拿着他的左边叉子， Pj 就可以就餐;因此 Pk 拿着他的左边叉子。向右推理可得所有哲学家都是饥饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。 5-6章作业 P177复习题5.8 在信号量上可执行的操作： 初始化=0（一般情况） semWait原语，值减1 如果值变为负数，则执行semWait的进程被阻塞 semSignal原语，值加1 如果值小于或等于0，则唤醒一个该信号量的阻塞进程 P177复习题5.11 什么是管程？ 管程（Monitor）是一个程序设计语言结构，它提供与信号量同样的功能，但更易于操作 管程是一个软件模块 一个或多个过程 一个初始化序列 局部数据 P177复习题5.13 与读者-写者问题相关联的条件： 任意多的读进程可以同时读一个文件 一次只有一个写进程可以往文件中写 如果一个写进程正在往文件中写时，则禁止任何读进程读文件 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的假设下，允许任意多的进程并发执行，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值.但是考虑下面由这两进程按交替顺序执行载入,增加,存储的情况下同时变更这个共享变量的取值: 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被重新安排开始,但这次没有被中断,直到运行完成它剩余的49次载入,增加和存储操作,结果是此时tally值已经是50. 6.进程B在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至2,同时存储这个值做为这个共享变量的最终结果. 一些人