第五章 习题及解答
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-10 p个进程共享m个同类资源，每一个资源在任一时刻只能供一个进程使用，每一进程对任一资源都只能使用一有限时间，使用完便立即释放，并且每个进程对该类资源的最大需求量小于该类资源的数目，设所有进程对资源的最大需求数目之和小于p+m，试证在该系统中不会发生死锁。
解：采用“反证法”，假定max(i)为第i个进程最大资源需求量，need(i)为第i个
1
进程还需要的资源量，alloc(i)为第i个进程已分配的资源量，则
max(i)<=m
max(i)=need(i)+alloc(i)
max(1)+?+ max(p)=(need(1)+ ?…+need(p))+(alloc(1)+ ?…+alloc(p)) ① 全部分配，alloc(1)+…+alloc(p)=m；② 所有进程无限等待 由①②可得， need(1)+…+need(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 桥之间的公路都 2 被汽车占据，而汽车又要求通过A 桥。这样驳船和汽车都无法前进，形成死锁的局面。 (2) 答：方案之一。可规定资源按序申请和分配，从而破坏了死锁的循环等待条件，防止死锁的发生。规定如B 桥的序号小于A 桥的序号，驳船和汽车都必须先申请序号小的资源B 桥，申请得到满足后，再申请序号大的资源A 桥。 (3) 答：将每台车的行驶看作是进程，则有Auto1，Auto2，?Autoi i个汽车进程。将每条驳船的航行看作是进程，则有Ship1，Ship2，?Shipj个驳船进程。桥A和桥B对车和船为互斥资源。 方案1： main{ } Autoi(){ 车在公路上行驶； P（SB）； 过B桥； V（SB）； 过弯道； P（SA）； 过A桥； V（SA）； 3 int SA=1；//A桥的互斥信号量// int SB=1；//B桥的互斥信号量// cobegin Auto1;Auto2;?Autoi; Ship1; Ship2; ?Shipj; coend 车在公路上行驶； } Shipj(){ 运河航行； P（SB）； P（SA）； 吊起过A桥； 运河航行； 吊起过B桥； V（SA）； V（SB）； 运河航行； } 方案2：方案1的缺点是船在过A桥前需要先占用B桥，使桥的通过率降低，增加交通阻塞的可能。因此方案2将弯道作为有界缓中区，基本思想是只要弯道有空，车就可以通过B桥，进入弯道。而船则不用先占用B桥，使桥的通过率降低。 main{ } 4 int SA=1；//A桥的互斥信号量 int SB=1；//B桥的互斥信号量 int Sn=n；//弯道可容纳汽车数n cobegin Auto1;Auto2;?Autoi; Ship1; Ship2; ?Shipj; coend Autoi(){ 车在公路上行驶； 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个 5
第5章习题及答案
