死锁条件、预防与避免

死锁（Deadlock）

计算机系统中有很多独占性的资源，在同一时刻每个资源只能由一个进程使用。死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种永久阻塞的现象。若无外力作用，它们都将无法推进下去，此时称系统处于死锁状态。

哲学家就餐问题（Dining Philosophers Problem）

假设有五位哲学家围坐在一张圆形餐桌旁，哲学家只做两件事情：吃饭或思考。餐桌上有一碗食物，每两个哲学家之间有一根筷子，哲学家必须用两根筷子才能吃东西。他们只能使用自己左右手边的那两根筷子。

将5位哲学家分别编号为0至4，第index位哲学家左手边的筷子编号为index。

do {
	wait(chopstick[index]);
	wait(chopstick[(index + 1) % 5]);
	eat;
	signal(chopstick[(index + 1) % 5]);
	signal(chopstick[index]);
} while (true);

但是这个算法存在死锁的问题。如果每个哲学家都拿着左筷子，就会永远等待右筷子（或者相反）。

在实际的计算机问题中，缺乏筷子可以类比为缺乏共享资源。一种常用的计算机技术是资源加锁，用来保证在某个时刻，资源只能被一个程序或一段代码访问。当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。

产生死锁的条件

产生死锁必须要同时满足4个必要条件：

1. 互斥（mutual exclusion）：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅有一个进程所占用。
2. 占有并等待（hold and wait）：当进程因请求资源而阻塞时，对已获得的资源保持不放。
3. 不可剥夺（no preemption）：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
4. 循环等待（circular wait）：一定会有一个环互相等待。

资源分配图（Resource Allocation Graph）

资源分配图是一种有向图，一个图$G$可以由结点集$V$以及边集$E$组成。

在资源分配图中，结点集$V=P\cup R$，边集$E\subseteq(P\times R)\cup(R\times P)$，其中P为系统中所有进程的集合，R为系统中所有资源类的集合。$(P_i,R_j)$表示一条由进程Pi到资源类Rj的有向边，即进程Pi申请资源Rj，$(R_j,P_i)$则表示资源实例的分配。

如果一个图中没有环路（回路），则系统中不存在资源死锁。若有环路，系统可能存在死锁；每类资源只有一个实例时，环路意味着死锁。

死锁预防

可以通过破坏死锁产生的4个必要条件来预防死锁：

1. 破坏“互斥”条件：对于必须独占使用的资源，互斥是不能随意改变的；可安全共享的资源则可以不要求互斥。
2. 破坏“占有并等待”条件：每个进程在开始执行时就申请所需要的全部资源，只要有一个请求的资源不可用，其它可用资源就都不分配给它。采用该方法可能造成资源浪费。
3. 破坏“不可剥夺”条件：一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源，以后需要时再重新申请。该方法仅适用于可以安全释放和恢复的资源，实现复杂且要付出很大的代价，会导致之前的工作失效。
4. 破坏“循环等待”条件：系统将所有资源按类型进行线性排序，并赋予不同的序号，所有进程对资源的请求必须严格按照资源序号递增的次序提出。该方法的缺点是进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费。同时资源的顺序必须保持一致，新增设备也必须遵守该顺序。

鸵鸟算法（Ostrich Algorithm）

传说中鸵鸟看到危险就把头埋在地底下，但这并非真实习性。当你对某一件事情没有一个很好的解决方法时，那就忽略它，装作看不到。这样的算法称为鸵鸟算法。

鸵鸟算法可以称之为不是办法的办法。在计算机科学中，鸵鸟算法是解决潜在问题的一种方法。假设的前提是，这样的问题出现的概率很低。比如，在操作系统中，为应对死锁问题，可以采用这样的一种办法。一些通用操作系统不为所有资源死锁提供统一的避免或检测机制，但这并不意味着UNIX、MINIX和Windows忽略所有子系统的死锁问题。其假设前提是大多数用户宁可在极偶然的情况下发生死锁也不愿接受性能的损失。因为解决死锁的问题，通常代价很大。所以鸵鸟算法，是平衡性能和复杂性而选择的一种方法。当死锁真正发生且影响系统正常运行时，采取手动干预——必要时重新启动。

死锁避免

死锁避免的基本思想就是在进行系统资源分配之前，先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则让进程等待。

若系统能按某种顺序如$\langle P_1,P_2,\dots,P_n\rangle$来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成，则称系统处于安全状态（safe state）。若系统不存在这样一个安全序列，则称系统处于不安全状态（unsafe state）。

在最大需求声明正确、进程得到资源后最终完成并释放的前提下，安全状态不会进入死锁。不安全状态不一定已经或必然死锁。

银行家算法（Banker's Algorithm）

银行家算法可用于银行发放一笔贷款前，预测该笔贷款是否会引起银行资金周转问题。这里，银行的资源就类似于计算机系统的资源，贷款业务类似于计算机的资源分配。该算法可以预测一次资源分配对计算机系统是否是安全的。

银行家算法需要设置以下数据结构：

1. 可利用资源向量Available：一个具有m个元素的数组，其中的每一个元素代表一类可利用资源的数目，其初始值为当前尚未分配的该类资源数目。其值将随着该类资源的分配与回收而动态改变。Available[j]=k表示系统中现有Rj类资源k个可用。
2. 最大需求矩阵Max：一个n×m的矩阵，定义了系统中n个进程中每一个进程对m类资源的最大需求。Max[i,j]=k表示进程i对Rj类资源的最大需求数目为k个。
3. 分配矩阵Allocation：一个n×m的矩阵，定义了当前分配给每个进程的各类资源数量。Allocation[i,j]=k表示进程i当前已分得Rj类资源的数目为k个。
4. 需求矩阵Need：一个n×m的矩阵，表示每一个进程尚需的各类资源的最大数目。Need[i,j]=k表示进程i还可能需要Rj类资源k个方能完成任务。

矩阵间的关系为：

$Need[i,j]=Max[i,j]-Allocation[i,j]$

设$Request_i$是进程$P_i$的请求向量，Request_i[j]=k表示进程Pi需要k个Rj类资源。当进程Pi发出资源请求后，系统按下述步骤进行检查：

1. 如果$Request_i\le Need_i$，则跳转到步骤2；否则，出错。
2. 如果$Request_i\le Available$，则跳转到步骤3；否则，表示尚无足够资源可供分配，进程Pi必须阻塞等待。
3. 系统试探性地将Pi申请的资源分配给它，并修改下列数据：

$\begin{aligned}Available&=Available-Request_i\\Allocation_i&=Allocation_i+Request_i\\Need_i&=Need_i-Request_i\end{aligned}$

4. 系统利用安全性算法，检查此次资源分配以后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi。否则，撤销试探分配的更新，让进程Pi阻塞等待。

例如系统总资源向量为(9,3,6)，资源需求与分配如下：

当前的可用资源为(0,1,1)，如果将这些资源分配给P1、P3、P4，并不能满足它们的需求。因为P2只需要一份R3资源就可以执行，执行结束后P2会释放所有资源，那么可用资源变为(6,2,3)。此时可用资源可以满足剩余任意一个进程，而都不会进入不安全状态。因此，P2、P1、P3、P4就是其中的一个安全序列。

如果无法找到一个安全序列，那么系统就处于不安全状态，便有可能进入死锁状态。