操作系统概念学习笔记 14

死锁（二）

死锁避免（deadlock-avoidance）

在上篇博客中讨论的死锁预防问题中，通过限制资源申请的方法预防死锁。这种限制保证４个必要条件之一不会发生，保证不会发生死锁，然而通过这种方式预防死锁的副作用是低设备使用率和系统吞吐率。

避免死锁的另外一种方法是获得以后如何申请资源的附加信息。

不同的算法所要求的信息量和信息的类型上有所不同，最为简单和最为常用的模型要求每个进程说明可能需要的每种资源类型实例的最大需求。根据每个进程可能申请的每种资源类型实例的最大需求的事先信息，可以构造一个算法以确保系统绝不会进入死锁状态。这种算法定义了死锁避免（deadlock-avoidance）方法。

死锁避免算法动态的检测资源分配状态以确保循环等待条件不可能成立。资源分配状态是由可用资源和已分配资源，以及进程最大需求所决定的。

安全状态：

如果系统能按某个顺序为每个进程分配资源（不超过其最大值）并能避免死锁，那么系统状态就是安全的。即如果存在一个安全序列，那么系统处于安全状态。如果没有这样的顺序存在，那么系统处于不安全状态。

进程顺序{P1, P2, …, Pn}，如果对于每个Pi，Pi仍然可以申请的资源数小于当前可用资源加上所有进程Pj（其中j小于i）所占用资源，那么这一顺序称为安全序列。

在这种情况下，进程Pi所需要的资源即使不能立即使用，那么Pi等待直到所有Pj释放其资源，当它们完成时，Pi可得到其所需要的所有资源，完成其给定任务。

安全状态不是死锁状态，相反，死锁状态是不安全状态。然而，不是所有不安全状态都能够导致死锁状态。

只要状态为安全，操作系统就能避免不安全（和死锁）状态。在不安全情况下，操作系统不能阻止进程以会导致死锁的方式申请资源。进程行为控制了不安全状态。

例如考虑一个系统，有12台磁带驱动器和三个进程P0,P1,P2,目前状况如下表：

顺序｛P1，P0，P2｝满足安全条件，因为：

• 对于P0,5小于等于2+3
• 对于P1,2小于3
• 对于P2,7小于2+5+3

系统可以从安全状态转变为不安全状态，加入某时刻，进程P2申请并又得到了一台磁带驱动器，系统就不再安全了。

此时P0还需要5台，但是系统只剩４台了，必须等待，同时P2还需要６台，也必须等待，由此导致了死锁。

造成这个错误的原因即允许P2再获取了一台磁带驱动器。

有了安全状态的概念，可定义避免算法确保系统不会死锁，即确保系统处于安全状态，开始，系统处于安全状态，当进程申请一个可用资源时，系统必须确定这一资源申请是可以立即分配还是要等待，即便现在资源可用，也只有分配后系统仍处于安全状态，才允许申请。

也因此采用这种方法和没有采用死锁避免算法相比资源使用率可能更低。

资源分配图算法：

利用资源分配图，引入需求边Pi->Rj表示进程Pi可能在将来某个时候申请资源Rj。只有申请边变为分配边而不会导致资源分配图形成环时，才允许申请。

如果没有环存在，那么会使得系统处于安全状态，如果有环存在则分配会导致系统处于不安全状态。

例如：

假如进程p2申请资源R2。虽然R2现在可用，但是不能分配给P2，因为这会创建一个环，环表示系统处于不安全状态，如果P1再申请R2就会造成死锁。

银行家算法：

银行家算法：对于每种资源类型有多个实例的资源分配系统，资源分配图就不再适用。使用银行家算法，但是效率比资源分配图方案低。

当新进程进入系统时，它必须说明其可能需要的各种类型资源实例的最大数量，这一数量不能超过当前系统资源的总和。当用户申请一组资源时，系统必须确定这些资源的分配是否仍会使系统出于安全状态，如果是，就分配资源；否则，进程必须等待直到某个其他进程释放足够资源为止。

实现银行家算法，必须有几个数据结构：Available，Max，Allocation，Need。

这些数据结构对资源分配系统的状态进行了记录。设ｎ为系统的进程的个数，ｍ为资源类型的种类：

• Available：长度为m的向量，表示每种资源类型的现有实例的数量。如果Available[j] = k，则说明资源类型Rj有现有ｋ个实例。

• Max：ｎＸｍ矩阵，定义每个进程的最大需求，如果Max[ｉ][ｊ] = k，那么进程Pi最多申请ｋ个资源类型Rj的实例。

• Allocation：ｎＸｍ矩阵，定义每个进程现在所分配的各种资源类型的实例数量，例如Allocation[ｉ][ｊ]　= k，那么进程Pi现在已经分配了ｋ个资源类型Rj的实例。

• Need：ｎＸｍ矩阵，表示每个进程还需要的剩余的资源。如果Need[ｉ][ｊ] = k，那么进程Pi还需要申请ｋ个资源类型Rj的实例。并且Need[ｉ][ｊ] = 　Max[ｉ][ｊ]　 - Allocation[ｉ][ｊ]

这些数据结构的大小和值会随着时间而改变。

为了简化银行家算法的描述：

设Ｘ，Ｙ为长度为n的向量，那么X <= Y 当且仅当对所有的i = 1,2,3…,n ，X[i] <= Y[i]，如果X <= Y 并且Ｘ!=Ｙ,那么Y小于X。

可以将矩阵Allocation 和Need的每行作为向量，并分别用Allocationi 和Needi来表示。

向量Allocationi表示分配给进程Pi的资源，Needi表示进程Pi为完成其任务可能仍然需要申请的额外资源。

安全性算法

确定计算机是否处于安全状态需要以下几步：

• 1 创建Work 和 Finish 向量，长度分别为m,n，并且Work = Avallable，将Finish的每一项置为false

• 2 查找是否存在这样的i使得满足：

  Finish[i] = false

  Needi <= Work

如果不存在则跳到第四步。

• 3

  Work = Work + Allocationi

  Finish[i] = true

跳回第二步

• 4 如果对所有的ｉ，Finish[i] = true,那么系统处于安全状态。

资源请求算法

设Requesti为进程Pi的请求向量。即如果Requesti[j]　== k ，那么Pi所需要资源类型Rj的实例数量为k。

当进程Pi做出资源申请时，采取如下动作：

• 1 如果Requesti　< Needi，那么进行下一步，否则产生出错条件，因为已经超过了其最大请求。

• 2 如果Requesti　< Available，那么进行下一步，否则Pi必须等待，因为没有可用的资源。

• 3 假定系统可以分配给进程Pi所需的资源，并按如下方式修改状态：

Available = Available - Requesti

Allocationi = Allocationi + Requesti

Needi = Needi - Requesti

如果所产生的资源分配状态是安全的，那么交易完成且进程Pi可分配到其所需要的资源。

然而，如果新状态不安全，那么进程Pi必须等待Requesti并回复到原资源分配状态。

举例

假定系统中有4个进程P1、P2、P3、P4和3种类型的资源R1、R2、R3，数量分别为9、3、6，在t0时刻的资源分配情况如表所示。

t0时刻的资源分配表：

试问：

（1）t0时刻是否安全？

（2）P2发出请求向量Request2（1，0，1），系统能否将资源分配给它？

（3）在P2申请资源后，若P1发出请求向量Request1（1，0，1），系统能否将资源分配给它？

（4）在P1申请资源后，若P3发出请求向量Request3（0，0，1），系统能否将资源分配给它？

解答：

（1）安全序列：P2、P1、P3、P4

（2）可以分配，因为分配资源后可找到一安全序列：P2、P1、P3、P4

（3）不能分配，因为request1(1,0,1)＞available(0,1,1)

（4）不能分配，因为分配资源后找不到一安全序列。

死锁检测

检测和恢复都会有额外的开销：这不仅包括维护所需信息和执行检测算法的运行开销，而且也包括死锁恢复所引起的损失。

情况一：每种资源类型只有单个实例：

该算法使用了资源分配图的变种，等待（wait-for）图。从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。等待图中由Pi到Pj的边意味着进程Pi等待进程Pj释放一个Pi所需的资源。

当且仅当等待图中有环，系统中存在死锁。为了检测死锁，系统需要维护等待图，并周期性调用在图中进行搜索的算法。从图中检测环的算法需要n2级别操作，其中n为图中的节点数。

情况二：每种资源类型可有多个实例：

采用与银行家算法相类似的算法。

• Available：长度为m的向量，表示各种资源的可用实例。

• Allocation：ｎＸｍ矩阵，表示当前各进程的资源分配情况。

• Request：ｎＸｍ矩阵，表示当前各进程的资源请求情况。如果Request[ｉ][ｊ] = k，那么Pi现在正在请求k个资源Rj。

• 1 创建Work 和 Finish 向量，长度分别为m,n，并且Work = Avallable，将Finish的每一项置为false

• 2 查找是否存在这样的i使得满足：

  Finish[i] = false

  Requesti <= Work

如果不存在则跳到第四步。

• 3

  Work = Work + Allocationi

  Finish[i] = true

跳回第二步

• 4 如果对所有的ｉ，Finish[i] == false,那么系统处于死锁状态。而且进程Pi死锁

应用检测算法

极端情况下，在每次请求分配不能立即允许时，就调用死锁检测算法。但会引起相当大的计算开销。或以一个不太高的频率调用检测算法，但这通常不能确定死锁进程中哪些“造成”了死锁。

死锁恢复

一种措施是通知操作员死锁已发生，以便操作人员人工处理死锁。

另一种措施是让系统从死锁状态中自动恢复过来。打破死锁有两种方法：一个方法是简单地终止或多个进程以打破循环等待。

另一个方法是从一个或多个死锁进程那里抢占一个或多个资源。

进程终止：

一是，终止所有死锁进程，这种方式虽然终止了死锁循环，代价太大。

二是，一次只终止一个进程直到取消死锁循环为止，这种方法的开销会很大，因为每次终止一个进程，就需要调用死锁检测算法以确定进程是否仍处于死锁。

资源抢占：

这里有三个问题需要处理：

①选择一个牺牲品：抢占哪些资源和哪个进程？必须确定抢占顺序以使代价最小化。

②回滚：如果从一个进程那里抢占一个资源，那么应对该进程做些什么安排？必须将这个进程回滚到某个安全状态，以便以后重启进程。

最简单的方法是完全回滚：终止进程并重新执行。更为有效的方法是将进程回滚到足够打破死锁。另一方面，这种方法要求系统维护有关运行进程状态的更多信息。

③饥饿：如何确保不会发生饥饿？最为常用的方法是在代价因素中加上回滚次数。