前言
计算机系统中有很多独占性的资源，在同一时刻只能每个资源只能由一个进程使用，我们之前经常提到过打印机，这就是一个独占性的资源，同一时刻不能有两个打印机同时输出结果，否则会引起文件系统的瘫痪。所以，操作系统具有授权一个进程单独访问资源的能力。
两个进程独占性的访问某个资源，从而等待另外一个资源的执行结果，会导致两个进程都被阻塞，并且两个进程都不会释放各自的资源，这种情况就是 死锁(deadlock)。
死锁可以发生在任何层面，在不同的机器之间可能会发生死锁，在数据库系统中也会导致死锁，比如进程 A 对记录 R1 加锁，进程 B 对记录 R2 加锁，然后进程 A 和 B 都试图把对象的记录加锁，这种情况下就会产生死锁。
下面我们就来讨论一下什么是死锁、死锁的条件是什么、死锁如何预防、活锁是什么等。
首先你需要先了解一个概念，那就是资源是什么
资源
大部分的死锁都和资源有关，在进程对设备、文件具有独占性（排他性）时会产生死锁。我们把这类需要排他性使用的对象称为资源(resource)。资源主要分为 可抢占资源和不可抢占资源
可抢占资源和不可抢占资源
资源主要有可抢占资源和不可抢占资源。可抢占资源(preemptable resource) 可以从拥有它的进程中抢占而不会造成其他影响，内存就是一种可抢占性资源，任何进程都能够抢先获得内存的使用权。
不可抢占资源(nonpreemtable resource) 指的是除非引起错误或者异常，否则进程无法抢占指定资源，这种不可抢占的资源比如有光盘，在进程执行调度的过程中，其他进程是不能得到该资源的。
死锁与不可抢占资源有关，虽然抢占式资源也会造成死锁，不过这种情况的解决办法通常是在进程之间重新分配资源来化解。所以，我们的重点自然就会放在了不可抢占资源上。
下面给出了使用资源所需事件的抽象顺序
如果在请求时资源不存在，请求进程就会强制等待。在某些操作系统中，当请求资源失败时进程会自动阻塞，当自资源可以获取时进程会自动唤醒。在另外一些操作系统中，请求资源失败并显示错误代码，然后等待进程等待一会儿再继续重试。
请求资源失败的进程会陷入一种请求资源、休眠、再请求资源的循环中。此类进程虽然没有阻塞，但是处于从目的和结果考虑，这类进程和阻塞差不多，因为这类进程并没有做任何有用的工作。
请求资源的这个过程是很依赖操作系统的。在一些系统中，一个 request 系统调用用来允许进程访问资源。在一些系统中，操作系统对资源的认知是它是一种特殊文件，在任何同一时刻只能被一个进程打开和占用。资源通过 open 命令进行打开。如果文件已经正在使用，那么这个调用者会阻塞直到当前的占用文件的进程关闭文件为止。
资源获取
对于一些数据库系统中的记录这类资源来说，应该由用户进程来对其进行管理。有一种管理方式是使用信号量(semaphore) 。这些信号量会初始化为 1 。互斥锁也能够起到相同的作用。
这里说一下什么是
互斥锁(Mutexes):在计算机程序中，
互斥对象(mutex)是一个程序对象，它允许多个程序共享同一资源，例如文件访问权限，但并不是同时访问。需要锁定资源的线程都必须在使用资源时将互斥锁与其他线程绑定（进行加锁）。当不再需要数据或线程结束时，互斥锁设置为解锁。
下面是一个伪代码，这部分代码说明了信号量的资源获取、资源释放等操作，如下所示
typedef int semaphore; semaphore aResource; void processA(void){ down(&aResource); useResource(); up(&aResource); }
上面显示了一个进程资源获取和释放的过程，但是一般情况下会存在多个资源同时获取锁的情景，这样该如何处理？如下所示
typedef int semaphore; semaphore aResource; semaphore bResource; void processA(void){ down(&aResource); down(&bResource); useAResource(); useBResource(); up(&aResource); up(&bResource); }
对于单个进程来说，并不需要加锁，因为不存在和这个进程的竞争条件。所以单进条件下程序能够完好运行。
现在让我们考虑两个进程的情况，A 和 B ，还存在两个资源。如下所示
typedef int semaphore; semaphore aResource; semaphore bResource; void processA(void){ down(&aResource); down(&bResource); useBothResource(); up(&bResource); up(&aResource); } void processB(void){ down(&aResource); down(&bResource); useBothResource(); up(&bResource); up(&aResource); }
在上述代码中，两个进程以相同的顺序访问资源。在这段代码中，一个进程在另一个进程之前获取资源，如果另外一个进程想在第一个进程释放之前获取资源，那么它会由于资源的加锁而阻塞，直到该资源可用为止。
在下面这段代码中，有一些变化
typedef int semaphore; semaphore aResource; semaphore bResource; void processA(void){ down(&aResource); down(&bResource); useBothResource(); up(&bResource); up(&aResource); } void processB(void){ down(&bResource); // 变化的代码 down(&aResource); // 变化的代码 useBothResource(); up(&aResource); // 变化的代码 up(&bResource); // 变化的代码 }
这种情况就不同了，可能会发生同时获取两个资源并有效地阻塞另一个过程，直到完成为止。也就是说，可能会发生进程 A 获取资源 A 的同时进程 B 获取资源 B 的情况。然后每个进程在尝试获取另一个资源时被阻塞。
在这里我们会发现一个简单的获取资源顺序的问题就会造成死锁，所以死锁是很容易发生的，所以下面我们就对死锁做一个详细的认识和介绍。
死锁
如果要对死锁进行一个定义的话，下面的定义比较贴切
如果一组进程中的每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程触发，这种情况会导致死锁。
简单一点来表述一下，就是每个进程都在等待其他进程释放资源，而其他资源也在等待每个进程释放资源，这样没有进程抢先释放自己的资源，这种情况会产生死锁，所有进程都会无限的等待下去。
换句话说，死锁进程结合中的每个进程都在等待另一个死锁进程已经占有的资源。但是由于所有进程都不能运行，它们之中任何一个资源都无法释放资源，所以没有一个进程可以被唤醒。这种死锁也被称为资源死锁(resource deadlock)。资源死锁是最常见的类型，但不是所有的类型，我们后面会介绍其他类型，我们先来介绍资源死锁
资源死锁的条件
针对我们上面的描述，资源死锁可能出现的情况主要有
- 互斥条件：每个资源都被分配给了一个进程或者资源是可用的
- 保持和等待条件：已经获取资源的进程被认为能够获取新的资源
- 不可抢占条件：分配给一个进程的资源不能强制的从其他进程抢占资源，它只能由占有它的进程显示释放
- 循环等待：死锁发生时，系统中一定有两个或者两个以上的进程组成一个循环，循环中的每个进程都在等待下一个进程释放的资源。
发生死锁时，上面的情况必须同时会发生。如果其中任意一个条件不会成立，死锁就不会发生。可以通过破坏其中任意一个条件来破坏死锁，下面这些破坏条件就是我们探讨的重点
死锁模型
Holt 在 1972 年提出对死锁进行建模，建模的标准如下：
- 圆形表示进程
- 方形表示资源
从资源节点到进程节点表示资源已经被进程占用，如下图所示
在上图中表示当前资源 R 正在被 A 进程所占用
由进程节点到资源节点的有向图表示当前进程正在请求资源，并且该进程已经被阻塞，处于等待这个资源的状态
这是一个死锁的过程，进程 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，那么资源的请求和释放就会是下面的步骤
