解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。
６.７给出在习题６.６中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程的要求变化。
解：为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一个界限。 资源限制现在变成 Ｉ + Ｏ ≤max Ｉ≤max – reso 当0 < reso < max 如果程序 P 正在等候递送输出给磁盘, 程序 O 最后处理所有的早先输出而且产生至少reso页, 然后让 P 继续执行。 因此 P 不会因为 O 而延迟。
如果磁盘充满I/O，Ｉ能被延迟; 但是迟早, 所有的早先的 输入可以被Ｐ处理完，而且对应的输出将会被 O 处理, 因而可以让Ｉ继续执行。
６.８在ＴＨＥ多道程序设计系统中，一个磁鼓（磁盘的先驱，用做辅存）被划分为输入缓冲区，处理和输出缓冲区，它们的边界可以移动，这取决于所涉及的进程速度。磁鼓的当前状态可以用以下参数描述： max表示磁鼓中的最大页数，i示磁鼓中的输入页数，p示磁鼓中的处理页数，o示磁鼓中的输出页数，reso出保留的最小页数，resp理保留的最小页数。 解：
Ｉ + Ｏ + Ｐ≤max – Ｉ + Ｏ≤max – resp Ｉ + Ｐ ≤max – reso Ｉ ≤max – (reso + resp)
６．９在ＴＨＥ多道程序设计系统中，一页可以进行下列状态转换： １.空→输入缓冲区（输入生产）
２.输入缓冲区→处理区域（输入消耗） ３.处理区域→输出缓冲区（输出生产） ４.输出缓冲区→空（输出生产） ５.空→处理区域（输出消耗） ６.处理区域→空（过程调用）
a根据Ｉ，Ｏ和Ｐ的量定义这些转换的结果。
b如果维持习题６.６中关于输入进程，用户进程和输出进程的假设，它们中的任何一个转换是否会导致死锁。
解： 1. i ←i + 1
2. i←i – 1; p ←p + 1 3. p←p – 1; o←o + 1 4. o ←o – 1 5. p←p + 1 6. p ←p – 1
b. 结合在对问题 6.7 的解决办法被列出的资源限制, 我们 能总结下列各项:
6. 过程返回能立刻发生因为他们只释放
36
资源。
5. 程序调用可能用尽磁盘片 (p= max – reso) 导致死锁。 4. 当有输出时输出消耗能立刻发生。
3. 输出生产能暂时被延迟直到所有的早先输出被消耗而且为下一步的输出至少可以产生reso页。 2. 只要有输入，输入消耗能立刻发生。
1. 输入生产被延迟直到所有先前输入和对应的输出已经被消耗。 此时, 当 i= o=0,如果消费进程还没有占用完磁盘空间 ( p < max – reso)，可以产生输入。 结论: 分配给消费进程的不受控制的存储空间是 唯一可能引发死锁的因素。
６.１０考虑一个共有１５０个存储器单元的系统，其单元如下分配三个进程：
进程 最大 占用 1 70 45 2 60 40 3 60 15 使用银行家算法，以确定同意下面的任何一个请求是否安全。如果安全，说明能保证的终止序列；如果不安全，给出结果分配简表。
a．第４个进程到达，最多需要６０个存储单元，最初需要２５个单元。 b第４个进程到达，最多需要６０个存储单元，最初需要３５个单元。
解： a.若同意第4个进程请求，则储存器单元共用去25＋15＋40＋45=125个单元，还有25个存储单元，则可以安全执行全部进程。安全顺序是1－2－3－4
b.若同意第4个进程请求，则还有15个资源可以用，此时处于不安全状态，结果分配见表 进程 最大 占有 需要 空闲 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25
６.１１评价独家算法在实际应用中是否有用。
解：不切实际的: 不能总是预先知道最大要求, 进程数目和资源数目可能随着时间改变 。大多数的操作系统忽视死锁。
６.１２有一个已经实现了的管道算法，使得进程Ｐ０产生的Ｔ类型的数据元素经进程序列Ｐ1Ｐ2?Ｐn-1,并且按该顺序在元素上操作。
a.定义一个一般的消息缓冲区，包含所有部分消耗的数据元素，并按下面的格式为进程Ｐi(0≤i≤n-1)写一个算法。 Repeat 从前驱接收 消耗
给后续发送 Forever
假设Ｐ0收到Ｐn-1发送的空元素。该算法能够使进程直接在缓冲区中保存的消息上操作，而无需复制。 b.说明关于普通的缓冲区进程不会死锁。
解：ar buffer: array 0..max-1 of shared T;
available: shared array 0..n-1 of 0..max;
\var K: 1..n-1;
region available do begin
37
available(0) := max;
for every k do available (k) := 0; end
\
var j: 0..max-1; succ: 0..n-1; begin
j := 0; succ := (i+1) mod n; repeat
region available do
await available (i) > 0;
region buffer(j) do consume element; region available do begin
available (i) := available(i) – 1;
available (succ) := available (succ) + 1; end
j := (j+1) mod max; forever end
b.死锁可以被解决通过 P0 waits for Pn-1 AND P1 waits for P0 AND . . . . .
Pn-1 waits for Pn-2 因为
(available (0) = 0) AND (available (1) = 0) AND . . . . .
(available (n-1) = 0)
但是如果max > 0,这个条件不成立，因为临界域满足 claim(1)+ claim(2)+ ?+claim(n)
< available(1)+available(2)+?+available(n) =max
６.１３ a.３个进程共享４个资源单元，一次只能保留或释放一个单元。每个进程最大需要２个单元。说明不会死锁。
b.Ｎ个进程共享Ｍ个资源单元，一次只能保留或释放一个单元。每个进程最大需要单元数不超过Ｍ，并且所有最大需求的总和小于Ｍ+Ｎ。说明不会发生死锁。
解：a.说明由于每个进程最多需要2个资源，最坏情况下，每个进程需要获得一个，系统还剩1个，这一个资源，无论分给谁都能完成。完成进程释放资源后，使剩余进程也完成，故系统不会死锁。
b.假定每个进程最多申请X个资源，最坏情况下，每个进程都得到X-1个资源都在申请最后一个资源，这时系统剩余资源数量为M-N(X－1)，只要系统还有一个剩余资源，就可以使其中的一个进程获得所需要的全部资源，该进程运行结束以后释放资源，就可以使其他进程得到全部资源的 满足，因此，当M-N(X-1)》1时系统不会发生死锁，解这个不等式X《（M+N-1）,系统不会发生死锁，因此，当所有进程的需求总和小于M+N时，系统是不会发生死锁的。
６.１４考虑一个由四个进程和一个单独资源组成的系统，当前的声明和分配矩阵是
38
3 1 2 1 C = 9 A= 3 7 2
对于安全状态，需要的最小资源数目是多少？
解：最小资源数是３个，总共有１０个资源。Ｐ２获得一个资源，完成后释放两个资源，Ｐ１获得三个资源，完成后释放三个资源，接下来Ｐ４获得五个资源，释放完资源后，Ｐ３获得所需的６个资源后完成。
６.１５考虑下列处理死锁的方法：1银行家算法，2死锁检测并杀死线程，释放所有资源，３事先保留所有资源，４如果线程需要等待，５资源排序，６重新执行检测死锁并退回线程的动作。
评价解释死锁的不同方法使用的一个标准是，哪种方法允许最大的并发。换言之，在没有死锁时，哪种方法允许最多数目的线程无需要等待继续前进？对下面列出的６种处理死锁的方法，给出从１到６的一个排序（１表示最大程序的并发），并解释你的排序。
另一个标准是效率；哪种方法需要最小的处理器开销？假设死锁很少发生，给出各种方法从１到６的一个排序（１表示最有效），并解释这样排序的原因。如果死锁发生很频繁，你的顺序需要改变吗？ 解：a从最多并发事件到最少, 有一个大概的次序如下： 1. 死锁检测并杀死线程，释放所有资源 发现死锁并退回线程的动作，如果线程需要等候那么重新开始线程而且释放所有的资源，在死锁发生之前，这些运算法则都不会限制并发, 因为他们仰赖运行时间检查而并非静态的限制。 他们的效果在死锁被发现比较难以描述：他们仍然允许许多并发(在一些情形，他们增加它), 但是很难有准确的估计。 第三个运算法则是最奇怪的, 因为如此后许多的它的并发将会是无用的重复; 因为线程竞争执行时间, 这一个运算法则也影响运行速度。 因此在两者的极端,它以这顺序被列出两次。 2. 银行家的运算法则 资源排序
这些运算法则因为限制多种的可允许的计算，而相对早先两种法则会引起更多的不必要的等候。 银行家的运算法则避免不安全的配置 和资源排序限制配置序列以便线程在他们是否一定等候的时候有较少的选择。
3. 事先保留所有的资源
这一个运算法则相比前两个要允许更少的并发, 但是比最坏的那一种有更少的缺点。因为要预先保留所有的资源,线程必须等候比较长的而且当他们工作的时候更有可能阻塞其他的线程,因此系统上来说具有更多的线性。
4. 如果线程需要等待，则重新启动线程并且释放所有的资源
如上所述, 这一个运算法则在区别最多和最少并发上有疑问,这具体要看并发的定义。 b从最高效率到最低，有如下大概的一个顺序： 1. 预先保留所有的资源 资源排序
因为他们没有包括运行时间经常开支，所以这些运算法则最有效率。 注意这是在相同的静态限制下的结果。 2. 银行家的运算法则
发现死锁而且杀死线程,释放它的资源
这些运算法则在概略的配置上包括运行时间检查
; 银行家的运算法则运行搜寻查证复杂度在线程和配置的数字和死锁检测中是 O(n m)，死锁检测的复杂度是 O(n)。资源-从属链被线程数目，资源数目和分配数目限制。 3. 发现死锁并退回线程的动作
39
这一个运算法则运行也需要运行上述的相同的时间检查。 在写内存上的复杂度为O(n) 。
4. 如果线程需要等待，则重新启动线程并释放所有的资源
这一个运算法则是非常无效率，有如下两个理由。 首先, 因为线程有重新开始的危险, 他们完成的可能性低。其次，他们与其他重新开始线程竞争有限的执行时间, 因此整个系统运行的速度很慢。
６.１６评价下面给出的就餐问题的解决方案。一位饥饿的哲学家首先拿起他左边的叉子，如果他右边的叉子也是可用的，则拿起右边的叉子开始吃饭，否则他放下左边的叉子，并重复这个循环。 解：如果哲学家们步调完全一致地拿起左边叉子又放下的话，他们会重复这一过程，导致饥饿情况的出现。 ６.１７假设有两种类型的哲学家。一类总是先拿起左边的叉子（左撇子），另一类总是先拿起右边的叉子（右撇子）。左撇子的行为和图６.１２中定义的一致。右撇子的行为如下： begin repeat
think;
wait(fork[(i+1)mod5]); wait(fork[i]); eat;
signal(fork[i]);
signal(fork[(i+1)mod5]);
forever; end;
证明：a如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁。 b如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿。
解：a假设存在死锁情况，设有 D个哲学家，他们每人都有一支叉子而且另一支叉子被邻居占有。不失一般性，设Pj 是一个左撇子。 Pj 抓牢他的左边叉子而且没有他的右边叉子, 他的右边邻居 Pk 没有完成就餐因此也是一个左撇子。 因此依次推理下去所有这Ｄ个哲学家都是左撇子。这与既有左撇子又有右撇子的条件矛盾，假设不成立，不存在死锁。 b
假设左撇子 Pj 饥饿，也就是说，有一部分人在就餐而Pj从不吃。 假如 Pj 没有叉子。 这样 Pj 的左边邻居 Pi 一定持续地占有叉子而始终不吃完。 因此Pi 是 右撇子，
抓住他的右边叉子, 但是从不得到他的左边叉子来完成就餐,也就是说 Pi
也饥饿。 现在 Pi 左边邻居也一定是持续占有右边叉子的右撇子。 向左进行这样的推理，得出所有哲学家都是饥饿的右撇子，这同Pj是个左撇子矛盾。因此 Pj 一直拥有左边子而且在等待他的右边叉子,Pj 的右边邻居 Pk 一直举着他的左边叉子而且从不完成一餐,也就是, Pk 是也饥饿的左撇子。 如果 Pk 不是一直拿着他的左边叉子， Pj 就可以就餐;因此 Pk 拿着他的左边叉子。向右推理可得所有哲学家都是饥饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。
６.１８图１.１７显示了另外一个使用管程解决哲学家就餐问题的方法。和图６.１４比较并阐述你的结论。
解：图６.１４是等待可用的叉子，图６.１７是等待邻居吃完，在本质上逻辑是一样的，后者显得更加紧凑。
40