概述

如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该进程集合就是死锁的。简单的说就是进程之间互相占有对方需要的资源。由于所有的进程都在等待，所以没有一个进程能引发可以唤醒该进程集合中的其他进程的事件。这样，所有的进程只好无限期等待下去。

死锁的产生有四个必要条件：

互斥条件。每个资源要么已经分配给了一个进程，要么就是可用的。
占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。
不可抢占条件。已经分配给一个进程的资源不能强制性的被抢占，它只能被占有它的进程显示地释放。
环路等待条件。死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

必须上述4个条件同时满足才会发生死锁，所以一般避免死锁的方法就是打破其中一条。

死锁的建模可以用有向图的两类结点来表示：圆形表示进程，方形表示资源，从资源到进程的有向边代表资源已被占用。从进程到资源的有向边代表进程正在请求该资源，并且进程处于阻塞状态

死锁的检测

每种类型一个资源的死锁检测

看书上的一个例子：

A进程有R资源，且需要S资源。
B没有任何资源，但是需要T资源。
C没有任何资源，但是需要S资源。
D有U资源，且需要S和T资源。
E有T资源，且需要V资源。
F有W资源，且需要S资源。
G有V资源，且需要U资源。
问：系统是否存在死锁？如果存在的话，死锁设计了哪些进程。

对于如此复杂的过程，典型的方法是构造一张资源分配图：

可以很容易的看出存在一个环：DTEVGU。所以答案一目了然，存在死锁，涉及进程EDG。不过为了实用，应有一个正规算法来检测。
检测算法

用一个数据结构L存储点的集合。对已经检测过的有向边进行标记，以免重复检查。

对图中每一个结点N，将N作为起始点执行下面5个步骤。

将L初始化为空表，清除所有有向边标记。

将当期结点添加到L的尾部，并检测该结点是否在L中出现过两次。如果是，那么该图包含了一个环，算法结束。

从给定的节点开始，检测是否存在没有标记的从该节点出发的有向边。如果存在做第5步，不存在做第6步。

随机选择一条没有标记的从该结点出发的有向边，标记它，然后顺着这条边找到新的结点，返回第3步。

如果这一结点是起始结点，那么表明该图不存在任何环，算法结束。否则意味着走进了死胡同，应移走该结点，返回到前一个结点，并将它作为新的当前节点，同时转到第3步。

每种类型多个资源的死锁检测

上面说的有向图的方法以及检测算法适用于每种资源只有一个的情形，如果一种资源有多个，就应该用另一种方法来检测。
这是一种基于矩阵的算法：假设资源的类型数为m，
E（existing）代表现有资源向量，即总共的资源数。Ei代表资源类型i。
A（available）代表可用资源向量，即没有被分配的资源。
C（current）代表当前分配矩阵，Cij代表进程i所持有的资源j的数量。
R（request）代表请求矩阵，Rij代表进程i所需要的资源j的数量。
这死者之间存在一个恒等式：
∑Cij+Aj = Ej。C的i从1到n求和
即所有已分配的资源j的数量加起来再和所有可供使用的资源数相加，结果就是该类的总资源数。
检测算法

每个进程起初都是恶没有标记过的。算法开始会对进程做标记，进程被标记后表明它们能够被执行，不会进入死锁。算法结束时，所有没有标记的进程都是死锁进程。

寻址一个没有标记的进程Pi，对于它而言R矩阵的第i行小于或等于Ai。

如果找到了这样一个进程，那么将C矩阵的第i行向量加到Ai中，标记该进程并转到第一步。

如果没有这样的进程，那么算法终止。

死锁的恢复

利用抢占恢复

在不通知原进程的情况下，将某一资源从一个进程强行取走给另一个进程使用，接着又送回，这种做法是否可行主要取决于该资源本身的特性。用这种方法恢复通常比较困难或者说不太可能。若选择挂起某个进程，则在很大程度上取决于哪一个进程拥有比较容易收回的资源。

利用回滚恢复

在预估到可能有死锁发生的情况下，可以周期性的对进程进行检查点检查。进程检查点检查就是将进程的状态写入一个文件以备以后重启。该检查点中包括存储映像、资源状态等。新的检查点不应该覆盖原有文件，而应写到新文件中。也就是说，当进程执行时，将会有一系列的检查点文件被积累起来。一旦检测到死锁，就能发现需要哪些资源。为了进行恢复，可以从一个较早的检查点上开始，这样拥有所需要的资源的进程将回滚到一个时间点，在此时间点之前，进程获得了一些其他资源，此时间点之后所做的工作全部丢失。然后重新分配资源。

通过杀死进程恢复

最直接也是最简单的方法就是杀死一个或若干个进程。一种方法是杀死环中的一个进程，如果走运的话，其他进程可以继续；如果行不通的话。就要继续杀死进程直到打破死循环。另一种方法是选择一个环外的进程作为牺牲品以释放该进程的资源，它应该正好持有环中进程所需要的资源。有可能的话，最好杀死可以从头开始重新运行而不会带来副作用的进程。

死锁的避免

使用资源轨迹图

看书上的一个例子：

初始状态为P，最后状态为U，I5到I7为进程B请求绘图仪，I6到I8为进程B请求打印机，两个阴影部分表示两个进程同时请求相同的资源，也就是死锁状态，需要保证进程的运行不可以进入这两个阴影区域，假设目前已到达t状态，如果将绘图仪分配给B进程，则会进入I1,I2,I5,I6的矩形区域，以后不管怎么走，都会进入阴影区域，产生死锁。所以结论就是：绕开阴影区域，就可以避免死锁。

单个资源的银行家算法

银行家算法就是对每一个请求进行检查，检查如果满足这一请求是否会达到安全状态。若是，那么就满足该请求；否则就推迟对这一请求的满足。为了检查状态是否安全，银行家需要考虑他是否有足够的资源来满足某一个客户。如果可以，那么这笔单款就是能够收回的，并且接着检查最接近最大限额的一个客户，以此类推。如果所有投资最终都能被收回，那么该状态就是安全的，最初的请求可以批准。

多个资源的银行家算法

将单个资源的银行家算法的矩阵横向扩展，每一列表示一种资源。用两个矩阵来表示，一个表示已分配，另一个表示仍然需要的资源。
最右边的E表示现有资源，即总资源数。P表示已经分配的资源数。A表示可分配的资源数，即剩余资源数。易得：E=P+A。

检查一个状态是否安全的算法如下：

检查需求矩阵是否有一行，其没有被满足的资源数小于或等于A。如果不存在这样的行，那么系统将会死锁，因为任何进程都无法运行结束。

假若找到这样一行，那么可以假设它获得所需的资源并运行结束，将该进程标记为终止，并将其资源加到向量A上。

重复以上两步，或者直到所有的进程都标记为终止，其初始状态是安全的；或者所有进程的资源需求都得不到满足，此时就是发生了死锁。

参考资料：
《现代操作系统 4th》