1. 死锁概述
- 如果要对死锁进行一个定义的话，下面的定义比较贴切。如果一组进程中的每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程触发，这种情况会导致死锁
- 简单一点来表述一下，就是每个进程都在等待其他进程释放资源，而其他资源也在等待每个进程释放资源，这样没有进程抢先释放自己的资源，这种情况会产生死锁，所有进程都会无限的等待下去
- 换句话说，死锁进程结合中的每个进程都在等待另一个死锁进程已经占有的资源。但是由于所有进程都不能运行，它们之中任何一个资源都无法释放资源，所以没有一个进程可以被唤醒。这种死锁也被称为资源死锁(resource deadlock)。资源死锁是最常见的类型，但不是所有的类型，我们后面会介绍其他类型，我们先来介绍资源死锁
2. 资源死锁的条件
针对我们上面的描述，资源死锁可能出现的情况主要有
- 互斥条件：每个资源都被分配给了一个进程或者资源是可用的
- 保持和等待条件：已经获取资源的进程被认为能够获取新的资源
- 不可抢占条件：分配给一个进程的资源不能强制的从其他进程抢占资源，它只能由占有它的进程显示释放
- 循环等待：死锁发生时，系统中一定有两个或者两个以上的进程组成一个循环，循环中的每个进程都在等待下一个进程释放的资源
发生死锁时，上面的情况必须同时会发生。如果其中任意一个条件不会成立，死锁就不会发生。可以通过破坏其中任意一个条件来破坏死锁，下面这些破坏条件就是我们探讨的重点
3. 死锁模型
Holt 在 1972 年提出对死锁进行建模，建模的标准如下
- 圆形表示进程
- 方形表示资源
从资源节点到进程节点表示资源已经被进程占用，如下图所示
- 在上图中表示当前资源 R 正在被 A 进程所占用
由进程节点到资源节点的有向图表示当前进程正在请求资源，并且该进程已经被阻塞，处于等待这个资源的状态
在上图中，表示的含义是进程 B 正在请求资源 S 。Holt 认为，死锁的描述应该如下
这是一个死锁的过程，进程 C 等待资源 T 的释放，资源 T 却已经被进程 D 占用，进程 D 等待请求占用资源 U ，资源 U 却已经被线程 C 占用，从而形成环。总结一点：吃着碗里的看着锅里的容易死锁，那么如何避免死锁呢？我们还是通过死锁模型来聊一聊
假设有三个进程 (A、B、C) 和三个资源(R、S、T) 。三个进程对资源的请求和释放序列如下图所示
操作系统可以任意选择一个非阻塞的程序运行，所以它可以决定运行 A 直到 A 完成工作；它可以运行 B 直到 B 完成工作；最后运行 C。这样的顺序不会导致死锁（因为不存在对资源的竞争），但是这种情况也完全没有并行性。进程除了在请求和释放资源外，还要做计算和输入/输出的工作。当进程按照顺序运行时，在等待一个 I/O 时，另一个进程不能使用 CPU
所以，严格按照串行的顺序执行并不是最优越的。另一方面，如果没有进程在执行任何 I/O 操作，那么最短路径优先作业会优于轮转调度，所以在这种情况下串行可能是最优越的
现在我们假设进程会执行计算和 I/O 操作，所以轮询调度是一种合理的调度算法。资源请求可能会按照下面这个顺序进行
下图是针对上面这六个步骤的资源分配图
这里需要注意一个问题，为什么从资源出来的有向图指向了进程却表示进程请求资源呢？笔者刚开始看也有这个疑问，但是想了一下这个意思解释为进程占用资源比较合适，而进程的有向图指向资源表示进程被阻塞的意思
在上面的第四个步骤，进程 A 正在等待资源 S；第五个步骤中，进程 B 在等待资源 T；第六个步骤中，进程 C 在等待资源 R，因此产生了环路并导致了死锁
然而，操作系统并没有规定一定按照某种特定的顺序来执行这些进程。遇到一个可能会引起死锁的线程后，操作系统可以干脆不批准请求，并把进程挂起一直到安全状态为止。比如上图中，如果操作系统认为有死锁的可能，它可以选择不把资源 S 分配给 B ，这样 B 被挂起。这样的话操作系统会只运行 A 和 C，那么资源的请求和释放就会是下面的步骤
下图是针对上面这六个步骤的资源分配图
在第六步执行完成后，可以发现并没有产生死锁，此时就可以把资源 S 分配给 B，因为 A 进程已经执行完毕，C 进程已经拿到了它想要的资源。进程 B 可以直接获得资源 S，也可以等待进程 C 释放资源 T。有四种处理死锁的策略：
- 忽略死锁带来的影响（惊呆了）
- 检测死锁并回复死锁，死锁发生时对其进行检测，一旦发生死锁后，采取行动解决问题
- 通过仔细分配资源来避免死锁
- 通过破坏死锁产生的四个条件之一来避免死锁