在之前的复习里面我们讲过一点点死锁，这个概念太重要了以至于要专门重点讲这部分。当两个或以上的线程/进程在互相等待同一资源，死锁(Deadlock)就出现了。维基百科^1给了一个很好的生活中的例子: 当两个人在狭窄的巷道里面对面碰上对方，两个人互不相让，都在等对方让开。

死锁的观察

资源分配图

资源分配图(Resource allocation graph) 展示了目前资源在进程之间的分配。

rag

如上图：我们用圆来代表进程；用方框里面带小圆来代表资源及其数量。从资源到进程的一个箭头表示一个单位的资源正在被该进程使用；从进程到资源的箭头表示该进程请求的资源。因为资源有限，如果进程申请不到资源就会进入阻塞态。比如说图中$R_{1}$只有一个单位的资源，并且该资源正在被$P_{1}$使用。$P_{2}$ 想要申请到资源$R_{1}$的话就会进入阻塞态，待 $P_{1}$ 释放资源后才能使用。

注：当我们讨论死锁的时候，我们假设进程的代码都是“正确”的。所谓正确，是指不会出现逻辑错误。比如说一个进程P正在使用某个有限资源，在这个基础上又请求该资源导致了自己锁死了自己。

死锁与可复用资源

可复用资源(reusable resource)是指在资源中，每个单位都能被不同进程请求。

状态图

资源分配图可以表示某一时刻资源的分配，另一种可以表示资源分配变换的模型叫状态转移(state transitions)。我们知道，进程和资源之间的操作无非就是三种

请求资源
使用资源
释放资源

死锁状态及安全状态

如果在状态S中，一个进程处于阻塞态，之后的状态无论如何改变也无法改变该状态，那么，我们就称这个在阻塞状态的进程被锁死(deadlock)了。

一个状态，包含两个及以上的进程被阻塞，我们称它为锁死状态(Deadlock state)；反之，我们称之为安全状态(safe state)。

如下图，因为$P_{2}$和$P_{3}$请求的资源都被占用了，所以它们都被锁死了。这整个图是进程和资源之间关系变化中的一种，我们称它为一个状态(State)。而因为该状态包含了两个阻塞进程，我们称这个状态为锁死状态。

deadlock_state_process

如下图， $S_{0}$ 是一个死锁状态，因为它包含两个阻塞的进程。我们通过执行一个释放资源的操作使 $S_{0}$ 可以转到$S_{1}$；在 $S_{1}$ ，再进行一个使用资源的操作使得 $P_{2}$ 可以使用资源 R 3 。可以看出，我们从 $S_{0}$ 变成 $S_{2}$ 的时候解除了死锁进程，回顾上面的话：一个进程在后面的状态中无论如何改变也在阻塞状态才是被锁死了，所以 $S_{0}$ 中的 $P_{1}$ 没有被锁死。
state_trans

通过穷举所有的状态，我们可以观察进程竞争有没有可能进入死锁状态。当然啦，我没有将他们全都画出来。上面的状态图不必将所有细节画出来，我们只要知道$S_{0}$长什么样就能知道后面的状态。所以也可以这么画:

state_trans

学过自动机理论的同学看出来这个是一个确定有限状态自动机(deterministic finite automaton， DFA)，但这是题外话了。

死锁的检测

我们可以用一个简化算法来查看资源分配图是否存在死锁：

1
2
3

while(没有非阻塞进程在图中):
  选择一个非阻塞进程P
  将P移除，包括所有对P请求和分配资源的箭头

移除那些P后，剩下的这个图就能给出死锁的信息。记住两个定理

一个状态S是死锁状态，当且仅当这个资源图无法完全最简。
拥有相同数量进程及资源的图，完全简化后的资源配置图长得都一样。

我们来简化之前例子中的资源进程图：

reduce

首先是 $P_{1}$ ，因为 $P_{1}$ 是非阻塞状态，我们可以移除$P_{1}$及其箭头; 在$P_{1}$被移除之后，$P_{2}$变成了非阻塞状态，所以也可以被移除。
如果最简资源图里有进程处于死锁状态，这个图将无法最简(所有进程都被挪走)。

连续死锁检测

如果我们用连续的方式去做，测试死锁还可以更高效。我们先定义几个逻辑陈述

I(x):状态x是一个死锁状态。
P(p, x):请求资源x的进程p当前在死锁状态。
K(p, x): 执行请求的进程P在状态s中是阻塞态。
C(x): 转向状态x的操作是一个请求操作。

然后给出这样一个成立的定理：

$$(¬I(CurrentState)→I(NextState))→(P(Process,NextState)∧C(NextState))$$

翻译一下就是：

如果当前的状态S不在死锁状态，那么它的下一个状态S‘是一个死锁当

转向S’的是一个请求操作
发出请求操作的进程P在S’中被锁死。

连续死锁状态的检测的步骤如下：

如果当前的操作是一个请求操作，并且发出这个请求操作的进程在下个状态中被阻塞。那么就进行状态图简化算法直到：

该进程被从状态图中移除，或者
图中再无阻塞进程。

如果P被移出了状态图，那么S’就不是一个死锁状态，并且算法完成。我们举一个例子：

现在有这样的一个状态转移， $S_{0}$通过请求操作进入 $S_{1}$ ,此时只有一个进程处被阻塞，所以该状态不是死锁状态； $S_{1}$ 通过一个请求操作进入 $S_{2}$ , 因为有两个进程被阻塞。

c_deadlock

根据算法，当发现有$S_{2}$这样的状态出现的时候，我们就测试连续死锁:
移除$P_{2}$及其箭头，发现$P_{1}$和$P_{3}$跳出了死锁状态，因此$S_{2}$并非死锁状态。

单一资源的死锁检测

等待图(wait-for graph)是一种只有进程的资源分配图。每个在图中的进程可以有多个占用资源，但只有一个请求资源。

wait-for graph

如上, 左边是资源分配图，右边是对应的等待图。所谓等待，是指某个进程请求的资源被另一个进程占用，并因此进入了阻塞状态。而且我们有一个定理

一个循环出现时(图中$P_{1}$和$P_{2}$这样，相互等待)是死锁的充分必要条件。

动态地避免死锁

除了像上面一样发现死锁之后再解决，我们可以在死锁发生之前就将其解决。

资源需求图

最大资源需求(maximum claim)是指一个进程所需要的所有资源，一个进程将要请求的资源可以用一个带虚线的箭头来表示。

资源请求图(resource claim graph)在资源配置图的基础上加入了一些新的元素，包括

目前资源在进程之间的分配。
目前的资源请求以及潜在的资源请求。

下图展示了一个资源请求图，$P_{1}$有可能在下一个状态中请求$R_{1}$和$R_{1}$
rcg

银行家算法

银行家算法(The Banker’s Algorithm)是一个模拟银行提供贷款的算法。想一下，银行的贷款和系统的资源分配有着类似的操作

银行	操作系统
贷款	资源分配
客户的信用	最大资源需求

银行家算法：

在状态S中，有一个资源请求，先假设该资源请求成功
用简化算法将新的状态S’简化
如果该图可以完全简化，那么就接受这个新的状态，否则拒绝资源分配并回归到S

定理:

如果分配资源后的状态无法最简，那便拒绝该分配，如此资源需求图将永远是在安全状态。

banker

我们来看看上面那个例子, 我们的银行家算法先假设 $P_{1}$ 的请求会成功,进入S‘。由于两个进程阻塞，我们要用简化算法将$P_{1}$ 移除，剩下的 $P_{2}$ , $P_{3}$可以相继被移除，因此 $P_{1}$的请求可以接受。依此法类推，我们可以找出所有的安全状态。

防止死锁

相比每步都要检测死锁来说，从根源上解决死锁的存在还可以再上一层楼。我们想想看死锁是怎么产生的

抢占+等待：某进程一边拿资源A一边等待资源B
循环等待：某进程甲一边拿资源A一边等待资源B，而进程乙则一边拿资源B一边等资源A。

如果我们能让所有的进程都只能要么等待资源，要么使用资源，这个问题是否就能解决了呢？

解决抢占和等待

三种方法可以解决 抢占+等待的问题。

第一种是只允许进程拥有一种类型的操作，要么在请求所有资源，要么在使用所有资源，这么做资源可能会分配不周，但总是可以避免死锁。
如果进程A正在使用资源1，现在需要资源2，它必须先放弃资源1再请求资源二。这么做一定程度上解决了方法1中的分配问题。
如果进程A在使用资源1，现在需要资源2，它会先检查资源2的使用情况。如果没有其他进程占用，它就可以使用资源2，如果有，它就会放弃所有正在使用的资源重新申请资源2.

解决循环等待：

我们将所有的资源排序，R0…Rn一个正在占用Ri的进程不可以申请Rk，其中k<i。如此，便解决了循环等待。