死锁 - 简书

资源

需要排他性使用的对象称为资源。

资源分为两类：可抢占的和不可抢占的。可抢占资源可以从拥有它的进程中抢占而不会产生任何副作用。不可抢占资源是指在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来。

某个资源是否可抢占取决于上下文环境。标准pc中，内存中的页面总是可以置换到磁盘中并置换出来，故内存是可抢占的。死锁与不可抢占资源有关。有关可抢占资源的潜在死锁通常可能通过在进程之间重新分配资源而化解。

使用一个资源需要的事件顺序可以用抽象的形式表示如下：

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

死锁

死锁的规范定义：如果一个进程集合中的每个进程都在等待只能由该进程集合中其他进程才能引发的事件，那么，该进程集合就是死锁的。

资源死锁的条件

Coffman等人（1971）总结了发生（资源）死锁的四个必要条件：

互斥条件。
占有和等待条件。
不可抢占条件。
环路等待条件。

死锁发生时，必是4个条件同时满足。如果其中有任何一个条件不满足，死锁就不会发生。

死锁处理的四种方法

忽略该问题：鸵鸟算法
检测死锁并恢复。
仔细对资源进行分配，动态的避免死锁
通过破坏引起死锁的四个必要条件之一，防止死锁的产生

鸵鸟算法

鸵鸟算法的思路就是把头埋在沙子里面,不管问题的发生.
当死锁发生的频率足够低的时候,这种方法就是可以接受的.考虑一个个人PC机,如果一个月出现一次死锁,那么就可以直接重启就好了.

死锁检测和恢复

系统并不阻止死锁的产生，而是允许死锁发生，当检测到死锁发生后，采取措施进行恢复。

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

构建一张资源分配图，然后用图论算法深度优先搜索检测有向图中是否存在环路，如果是，就存在死锁。

数据结构L，L代表一些节点的集合。通过对已经检查过的边进行标记，以免重复检查：

对图中的每一个节点N，将N作为起始点执行下面5个步骤
将L初始化为空表，并清除所有的有向边标记
将当前节点添加到L的尾部，并检测该节点是否在L中已经出现过两次，如果是，那么该图包含了一个环，算法结束
从给定的节点开始，检测是否存在没有标记的从该节点触发的有向边，如果存在的话，做第五步，如果不存在，跳到第六步
随机选取一条没有标记的从该节点出发的有向边，标记它。然后顺着这条弧线找到新的当前节点，返回到第三步
如果这一节点是起始节点，那么表明该图不存在任何环，算法结束。否则意味着我们走进了死胡同，所以需要移走该节点，返回到前一个节点，即当前节点前面的一个节点，并将它作为新的当前节点，同时转到第三步。

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

先构建现有资源向量E、可用资源向量A、当前分配矩阵C、请求矩阵R（E、A、C之间存在某种关系），再开始会对进行做标记，进程被标记后就表明它们能够被执行，不会进入死锁，当算法结束时，任何没有标记的进程都是死锁进程。

死锁检测算法：

①：寻找一个没有标记的进程Pi，对于它而言R矩阵的第i行向量小于或等于A。

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

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

算法结束时，所有没有标记过的进程(如果存在的话)都是死锁进程

关于检测时机有几种方法，每当有资源请求时去检测，每隔固定时间检测一次，当CPU的使用率到某一域值时去检测。

c.从死锁中恢复

利用抢占恢复：在不通知原进程的情况下，将某一资源从一个进程强行取走给另一个进程使用，接着又送回。
利用回滚恢复：周期性的对检查点检查，进程检查点检查就是讲进程的状态写入一个文件以备以后重启，该检查点不仅包括存储映象，还包括资源状态，即哪些资源分配给了该进程。一旦检测到死锁，就很容易发现需要哪些资源。为了进行恢复，要从一个较早的检查点上开始，这样拥有所需要资源的进程会回滚到一个时间点，在此时间点之前该进程获得了一些其他的资源。在该检查点后所做的所有工作都丢失。
通过杀死进程恢复：杀死环中的一个进程，如果走运的话，其他进程将可以继续。如果这样行不通的话，就需要继续杀死别的进程直到打破死循环。

死锁避免

没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。换句话说，通过仔细的调度就能够避免死锁的状态就是安全状态。

a.资源轨迹图

避免死锁的主要算法是基于一个安全状态的概念。

image

b.安全状态和不安全状态

如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

不安全状态并不是死锁。

安装状态和不安全状态的区别是：从安全状态出发，系统能够保证所有进程都能完成；从不安全状态出发，就没有这样的保证。

c.银行家算法

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

检查一个状态是否安全的步骤如下：

(1)查找右边矩阵中是否有一行，其未被满足的设备数均小于或等于向量A。如果找不到，则系统将死锁，因为任何进程都无法运行结束。

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

(3)重复以上两步，直到所有的进程都标记为结束。若达到所有进程结束。则状态是安
全的,否则将发生死锁。

死锁预防

a.破坏互斥条件

如果资源不被一个进程所独占，那么死锁肯定不会产生。当然，允许两个进程同时使用打印机会造成混乱，通过采用假脱机打印机技术允许若干个进程同时产生输出。

b.破坏占有和等待条件

规定所有进程在开始执行前请求所需的全部资源，如果所需的资源全部可用，那么就将他们分配给这个进程，于是该进程肯定能运行结束。如果一个或多个资源正被使用，那么久不进行分配，进程等待。

c.破坏不可抢占条件

即允许进程强行从占有者那里夺取某些资源。就是说，当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。

d.破坏环路等待条件

一种是保证每个进程在任何时刻只能占用一个资源，如果要请求另外一个资源，它必须先释放第一个资源。第二种是将所有资源统一编号，所有请求必须按资源编号提出。

其他问题

两阶段加锁

在第一阶段,进程试图对所有所需的记录进行加锁,一次锁一个记录.如果第一阶段成功,就开始第二阶段,完成更新然后释放锁.在第一阶段并没有做实际的工作.

如果在第一阶段某个进程需要的记录已经被加锁,那么该进程释放它所有的加锁记录,然后重新开始第一阶段.从某种意义上说,这种方法类似于提前或者至少是未实施一些不可逆操作之前请求所有的资源.在两阶段加锁的一些版本中,如果在第一阶段碰到了已经加锁的记录,并不会释放锁然后重新开始,这就可能导致死锁.
但是在一般情况中,这种策略并不通用,因为,让一个进程重新开始是那么现实的.

通信死锁

发生在通信系统中的死锁，即两个或两个以上进程利用发送信息来通信时。标准定义，每个进程因为等待另外一个进程引发的事件而产生阻塞，这就是一种死锁。这叫做通信死锁。通信死锁是协步同步的异常情况，处于这种死锁中的进程如果是各自独立执行的，则无法完成服务。

解决方法：超时。超时策略作为一种启发式方法可探测死锁并使进程恢复正常。

活锁

在某种情形下,轮询可用于进入临界区或者获取资源.
在下面这段代码中,

void process_A(void){
    enter_region(resource1);
    enter_region(resource2);
    use_both_resources();
    leave_region();
    leave_region(resource2);
    leave_region(resource1);
}
void process_B(void){
    enter_region(resource2);
    enter_region(resource1);
    use_both_resources();
    leave_region();
    leave_region(resource1);
    leave_region(resource2);
}

如果A进程得到资源1,然后B得到2,然后它们就会一直轮询下去,虽然没有死锁现象(进程没有阻塞),但是死锁确实发生了.这就是活锁;

饥饿

和死锁非常相近的一个问题是饥饿（starvation）。在动态运行的系统中，在任何时刻都会产生申请资源。这就需要规定一些策略来决定在什么时候，谁获得什么资源。虽然这个策略表面上很有道理，但依然有叫能使一些进程永远得不到服务，虽然它们并没有被死锁。

在一个繁忙的系统中，有一个进程有一个很大的文件要打印，每当打印机空闲，系统纵观所有进程，并把打印机分配给打印最小文件的进程。如果存在一个固定的进程流，其中的进程都是只打印小文件，那么，要打印大文件的进程永远也得不到打印机。很简单，它会如饥饿而死一般（无限制地推后，尽管它没有被阻塞）。

饥饿可以通过先来先服务资源分配策略来避免。