定义

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

产生的条件

1. 互斥条件：进程应互斥使用资源，任一时刻一个资源仅为一个进程独占，若另一个进程请求一个已被占用的资源时，它被置成等待状态，直到占用者释放资源。

2. 占有和等待条件：一个进程请求资源得不到满足而等待时，不释放已占有的资源。

3. 不可抢占条件：任一进程不能从另一进程那里抢夺资源，即已被占用的资源，只能由占用进程自己来释放。

4. 环路等待条件：死锁了生时，系统中一定有两个或两个以上的进程组成一个循环，循环中的每个进程都在等待下一个进程释放的资源。

   发生死锁时，以上条件必须同时满足。任意一个条件不成立，死锁就不会发生。

驼峰算法

把头埋在沙子里，假装问题根本没有发生。

死锁检测和恢复

这种解决方式不会尝试去阻止死锁的出现。相反，这种解决方案会希望死锁尽可能的出现，在监测到死锁出现后，对其进行恢复

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

如果这张图包含了一个或一个以上的环，那么死锁就存在，处于这个环中任意一个进程都是死锁的进程。

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

如果有多种相同的资源存在，就需要采用另一种方法来检测死锁。可以能过构造一个矩阵来检测从P1-Pn这n个进程中的死锁。

考量标准：

• 每当有资源请求时就去检测，这种方式会占用昂贵的CPU时间。
• 每隔n分钟检测一次，或者当CPU使用率低到某个标准下去检测。考虑到CPU效率的原因，如果死锁进程达到一定数量，就没有多少进程可能运行了，所以CPU会经常空闲。

从死锁中恢复

通过抢占进行恢复

在某些情况下，可能会临时将某个资源从它的持有者转移到另一个进程。比如在不通道原进程的情况下，将某个资源从进程中强制取走给其他进程使用，使用完后又送回。这种恢复方式一般比较困难而且有些简单粗暴，并不可取。

通过回滚进程恢复

如果系统设计者和机会操作员知道可能发生死锁，那么就可以定期检查流程。进程的检测点意味着进程的状态可能被写入到文件以后便后面进行恢复。检测点不仅包含存储镜像，还包含资源状态。一种更有效的解决方式是不需要覆盖原有的检测点，而是每出现一个检测点都要把它写入到文件中，这样当进程执行时，就会有一系列的检查点文件被累积起来。

为了进行恢复，要从上一个较早的检查点开始，这样所需要的资源的进程会回滚到一个时间点，在这个时间点上，死锁进程还没有获取所需要的资源，可能在此时对其进行资源分配。

杀死进程恢复

最简单有效的解决方案是直接杀死一个死锁进程。但是杀死一个进程可能照样行不通，这时候就需要杀死中坚力量的资源进行恢复。

另外一种方式是选择一个环外的进程作为牺牲品来释放进程资源。

死锁的避免

单个资源的银行家算法

多个资源的银行家算法

死锁的预防

破坏互斥条件

破坏占有并等待条件

破坏不可抢占条件

破坏环路等待条件

参考文献

1. 现在操作系统 第四版