第5章习题及答案.doc
精品文档，仅供学习与交流，如有侵权请联系网站删除第五章 习题及解答5-5 假设一个可移动磁头的磁盘具有 200个磁道，其编号为0199,当它刚刚结束了 125道的存取后，现正在处理143道的服务请求，假设系统当前的请求序列以请求的先后次序排列如下: 86、147、91、177、150、102、175、130。试问对以下几种磁盘IO请求调度算法而言，满足以上请求序列，磁头将分别如何移动?（1） 先来先服务算法（FCFS）（2） 最短寻道时间优先调度（SSTF）（3） 扫描算法（SCAN）（4） 循环扫描算法（CSCAN）答：（1） FCFS：1438614791177150102175130；（2） SSTF：143147150130102949186175177；（3） SCAN：143147150175177130102949186；（4） C-SCAN：143147150175177869194102130。5-9 三个进程共享四个同类资源，这些资源的分配与释放只能一次一个，已知每一进程最多需要两个资源，试问该系统会发生死锁吗？为什么？答：该系统不会发生死锁。因为最坏情况是每个进程都占有一个资源，申请第二个资源，而此时系统中还剩一个资源，不管这个资源分给哪个进程，都能满足它的资源要求，因此它能在有限时间内运行结束而释放它所占有的两个资源，这两个资源又可以分配给另外两个进程，使它们能够运行结束，所以系统不会发生死锁。5-10 p个进程共享m个同类资源，每一个资源在任一时刻只能供一个进程使用，每一进程对任一资源都只能使用一有限时间，使用完便立即释放，并且每个进程对该类资源的最大需求量小于该类资源的数目，设所有进程对资源的最大需求数目之和小于p+m，试证在该系统中不会发生死锁。解：采用“反证法”，假定max(i)为第i个进程最大资源需求量，need(i)为第i个进程还需要的资源量，alloc(i)为第i个进程已分配的资源量，则max(i)<=mmax(i)=need(i)+alloc(i)max(1)+L+ max(p)=(need(1)+ L+need(p)+(alloc(1)+ L+alloc(p)<p+m若发生死锁，则需要满足下面两个条件， 全部分配，alloc(1)+alloc(p)=m； 所有进程无限等待由可得， need(1)+need(p)<p则死锁后，p个进程需要的资源小于p，则一定存在进程i，need (i) = 0，进程已获得全部资源，进程i 可以执行完，同假设发生矛盾，所以不会发生死锁。5-11图5.9 表示一带闸门的运河，其上有两架吊桥，吊桥坐落在一条公路上，为使该公路避开一块沼泽地而其横跨运河两次。运河和公路的交通都是单方向的，运河的基本运输由驳船担负。在一艘驳船接近吊桥A 时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾部通过该桥为止，对吊桥B按同样次序处理(1) 一艘典型驳船的长度为200 米，当它在河道航行时是否会产生死锁？若会，其理由是什么？(2) 如何能克服一个可能的死锁？请想出一个防止死锁的办法。(3) 如何利用信号灯的P、V 操作实现车辆和驳船的同步？图5.9(1) 答：驳船长200 米，当驳船通过了A 桥，其船头到达B 桥，请求B 桥吊起，而此时它的尾部占据A 桥，若这个时候B 桥及B桥到A 桥之间的公路都被汽车占据，而汽车又要求通过A 桥。这样驳船和汽车都无法前进，形成死锁的局面。(2) 答：方案之一。可规定资源按序申请和分配，从而破坏了死锁的循环等待条件，防止死锁的发生。规定如B 桥的序号小于A 桥的序号，驳船和汽车都必须先申请序号小的资源B 桥，申请得到满足后，再申请序号大的资源A 桥。(3) 答：将每台车的行驶看作是进程，则有Auto1，Auto2，LAutoi i个汽车进程。将每条驳船的航行看作是进程，则有Ship1，Ship2，LShipj个驳船进程。桥A和桥B对车和船为互斥资源。方案1：mainint SA=1；/A桥的互斥信号量/int SB=1；/B桥的互斥信号量/cobeginAuto1;Auto2;LAutoi;Ship1; Ship2; LShipj;coendAutoi()车在公路上行驶；P（SB）；过B桥；V（SB）；过弯道；P（SA）；过A桥；V（SA）；车在公路上行驶； Shipj()运河航行；P（SB）； P（SA）； 吊起过A桥； 运河航行； 吊起过B桥； V（SA）； V（SB）；运河航行；方案2：方案1的缺点是船在过A桥前需要先占用B桥，使桥的通过率降低，增加交通阻塞的可能。因此方案2将弯道作为有界缓中区，基本思想是只要弯道有空，车就可以通过B桥，进入弯道。而船则不用先占用B桥，使桥的通过率降低。mainint SA=1；/A桥的互斥信号量int SB=1；/B桥的互斥信号量int Sn=n；/弯道可容纳汽车数ncobeginAuto1;Auto2;LAutoi;Ship1; Ship2; LShipj;coendAutoi()车在公路上行驶；P（Sn）；P（SB）；过B桥；V（SB)；过弯道；P（SA）；上A桥；V（Sn）；过A桥；V（SA）；车在公路上行驶；Shipj()运河航行； P（SA）； 船头行驶至B桥； P（SB）； 运河航行； 船尾过A桥； V（SA）； 船尾过B桥； V（SB）； 运河航行；5-14在采用银行家算法管理资源分配的系统中，有A、B、C三类资源可供5个进程P1、P2、P3、P4、P5共享。3类资源的总量为(17, 5, 20)，即A类17个，B类5个，C类20个。假设T0时刻各进程对资源的需求和分配情况如下表所示。（1） 现在系统是否处于安全状态？如是，给出一个安全序列。（2） T0时刻，如果进程P4和P1依次提出A、B、C资源请求（2,0,1）和（0,2,0），系统能否满足它们的请求?请说明原因。答：（1）系统处于安全状态，如P4P2P3P5P1。（2）不能满足。由于P4与P1提出请求后，A、B、C剩余（0，1，2），此时A类无，只能等待拥有足够A类资源的进程结束释放A类资源，别的进程才能执行，而此时P4需（0，2，0），P3需（0，0，6），而剩余（0，1，2），不能满足要求，产生死锁。【精品文档】第 5 页
