第5章习题及答案

1第五章习题及解答5-5假设一个可移动磁头的磁盘具有200个磁道，其编号为0~199,当它刚刚结束了125道的存取后，现正在处理143道的服务请求，假设系统当前的请求序列以请求的先后次序排列如下:86、147、91、177、150、102、175、130。试问对以下几种磁盘IO请求调度算法而言，满足以上请求序列，磁头将分别如何移动?（1）先来先服务算法（FCFS）（2）最短寻道时间优先调度（SSTF）（3）扫描算法（SCAN）（4）循环扫描算法（CSCAN）答：（1）FCFS：143→86→147→91→177→150→102→175→130；（2）SSTF：143→147→150→130→102→94→91→86→175→177；（3）SCAN：143→147→150→175→177→130→102→94→91→86；（4）C-SCAN：143→147→150→175→177→86→91→94→102→130。5-9三个进程共享四个同类资源，这些资源的分配与释放只能一次一个，已知每一进程最多需要两个资源，试问该系统会发生死锁吗？为什么？答：该系统不会发生死锁。因为最坏情况是每个进程都占有一个资源，申请第二个资源，而此时系统中还剩一个资源，不管这个资源分给哪个进程，都能满足它的资源要求，因此它能在有限时间内运行结束而释放它所占有的两个资源，这两个资源又可以分配给另外两个进程，使它们能够运行结束，所以系统不会发生死锁。5-10p个进程共享m个同类资源，每一个资源在任一时刻只能供一个进程使用，每一进程对任一资源都只能使用一有限时间，使用完便立即释放，并且每个进程对该类资源的最大需求量小于该类资源的数目，设所有进程对资源的最大需求数目之和小于p+m，试证在该系统中不会发生死锁。解：采用“反证法”，假定max(i)为第i个进程最大资源需求量，need(i)为第i个2进程还需要的资源量，alloc(i)为第i个进程已分配的资源量，则max(i)=mmax(i)=need(i)+alloc(i)max(1)++max(p)=(need(1)+…+need(p))+(alloc(1)+…+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桥之间的公路都3被汽车占据，而汽车又要求通过A桥。这样驳船和汽车都无法前进，形成死锁的局面。(2)答：方案之一。可规定资源按序申请和分配，从而破坏了死锁的循环等待条件，防止死锁的发生。规定如B桥的序号小于A桥的序号，驳船和汽车都必须先申请序号小的资源B桥，申请得到满足后，再申请序号大的资源A桥。(3)答：将每台车的行驶看作是进程，则有Auto1，Auto2，Autoii个汽车进程。将每条驳船的航行看作是进程，则有Ship1，Ship2，Shipj个驳船进程。桥A和桥B对车和船为互斥资源。方案1：main{intSA=1；//A桥的互斥信号量//intSB=1；//B桥的互斥信号量//cobeginAuto1;Auto2;Autoi;Ship1;Ship2;Shipj;coend}Autoi(){车在公路上行驶；P（SB）；过B桥；V（SB）；过弯道；P（SA）；过A桥；V（SA）；4车在公路上行驶；}Shipj(){运河航行；P（SB）；P（SA）；吊起过A桥；运河航行；吊起过B桥；V（SA）；V（SB）；运河航行；}方案2：方案1的缺点是船在过A桥前需要先占用B桥，使桥的通过率降低，增加交通阻塞的可能。因此方案2将弯道作为有界缓中区，基本思想是只要弯道有空，车就可以通过B桥，进入弯道。而船则不用先占用B桥，使桥的通过率降低。main{intSA=1；//A桥的互斥信号量intSB=1；//B桥的互斥信号量intSn=n；//弯道可容纳汽车数ncobeginAuto1;Auto2;Autoi;Ship1;Ship2;Shipj;coend}5Autoi(){车在公路上行驶；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个6进程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）系统处于安全状态，如P4→P2→P3→P5→P1。（2）不能满足。由于P4与P1提出请求后，A、B、C剩余（0，1，2），此时A类无，只能等待拥有足够A类资源的进程结束释放A类资源，别的进程才能执行，而此时P4需（0，2，0），P3需（0，0，6），而剩余（0，1，2），不能满足要求，产生死锁。