死锁

当且仅当以下所有条件在系统中同时成立时，才会出现资源上的死锁：^[4]

1. 互斥条件：必须以非共享模式持有至少一个资源。否则，在必要时无法阻止进程使用资源。在任何给定的时刻，只有一个进程可以使用该资源。^[5]
2. 请求和保持条件：进程当前持有至少一个资源并请求其他进程占有的额外资源。
3. 不可抢占条件：资源只能由占有它的进程自动释放。
4. 循环等待条件：每个进程必须等待由另一个进程占有的资源，相应地，另一个进程又在等待第一个进程释放资源。一般来说，有一组等待进程的集合 P = {P₁, P₂, …, P_N}，其中P₁等待P₂占有的资源，P₂等待P₃占有的资源，以此类推，直到P_N等待P₁持有的资源。

Edward G. Coffman, Jr在1971年发表的文章中首次将这四种条件称为Coffman 条件。

目前大多数操作系统都不能预防死锁，^[6] 当死锁发生时，不同的操作系统采取不同的应对方法，这些方法没有固定的标准。大多数方法的工作原理是破坏四种Coffman 条件中的任意一种，通常是第四种。^[7] 主要方法如下：

2.1 忽略死锁

在这种方法中，假设死锁永远不会发生。 这也是鸵鸟算法的应用。^[7][8] 这种方法最初由MINIX和UNIX使用。^[9] 当死锁发生的频率不高且每次丢失的数据影响较小时，使用该方法。

2.2 死锁检测

采取死锁检测这一方法时，允许发生死锁。检查系统的状态以检测已发生的死锁，随后解除死锁。采用跟踪资源分配和进程状态的算法，回滚并重新启动一个或多个进程以便解除检测到的死锁。由于操作系统的资源调度程序知道每个进程锁定和/或当前请求的资源，因此很容易检测已经发生的死锁。^[8]

检测到死锁后，可采取下列方法之一解除死锁:

1. 进程终止：死锁中，一个或多个进程可能被终止，可以选择终止死锁中所有的竞争进程，这可以迅速有效的解除死锁，但由于部分计算数据会丢失，代价较大。或者选择逐个终止进程，直至死锁状态解除，这种方法的代价也很大，因为每终止一个进程后，算法都需要来确定系统是否仍处于死锁状态，在选择下一个终止进程时，需要考虑进程的优先级、进程已运行的时间及运行完成还需要的时间这些因素。
2. 资源抢占：分配给各个进程的资源可以被连续抢占并分配给其他进程，直到死锁被解除。^[9]

2.3 死锁预防

通过破坏四种Coffman 条件中的任意一种预防死锁。

• 破坏互斥条件意味着任何进程都不能独占访问资源。对于无法假脱机的资源来说，这是不可能的。 但即使使用假脱机资源，仍然可能发生死锁。 避免互斥的算法称为非阻塞同步算法。
• 在进程运行前（或在开始一组特定操作之前），要求其申请在整个过程中需要的所有资源，从而破坏请求和保持条件。这种方法的优点有限，且从各方面看来，都是对资源的低效利用。另一种方法是要求进程仅在没有资源时才申请资源。因此，进程在从头开始请求所需的所有资源之前，必须释放当前占有的所有资源。这种做法也是不切实际的，因为资源被分配后可能会长期闲置，此外，申请流行资源的进程可能要无止尽的等待，因为这种资源总是被分配给经常发生饥饿现象的进程。^[10] (这些算法，比如序列化令牌，被称为全有或全无算法。)
• 破坏不可抢占条件也很难实现，或者说无法实现，因为过程必须能够在一定时间内拥有资源，否则处理结果可能不一致或者影响进程的稳定性。但是，不强制抢占可能会干扰优先级算法，而抢占“锁定”资源就要利用回滚，这一操作代价太高，应该避免。允许抢占的算法包括无锁和无等待算法以及乐观并发控制。如果进程占有一定资源，并且请求另一些不能立即分配给它的资源，则可以通过释放该进程当前占有的所有资源来解除该条件。
• 最后一个条件是循环等待条件，避免循环等待的方法包括在关键部分禁用中断，以及使用层次结构来确定申请资源的部分顺序。若不存在明显的层次结构，甚至可以使用资源的内存地址来确定顺序，并且按照枚举的升序请求资源。^[11] 也可以使用迪杰斯特拉算法。

活锁类似于死锁。两者间的区别就在于活锁中的进程在虽然不断地改变状态，却未取得实质性进展。

约在20世纪70年代，对这一术语进行正式定义。在Babich早期发表的文献，如1979年这篇关于程序正确性的文章中可以看到这一术语。^[11] 活锁是一种特殊的饥饿，通常用于定义没有实质性进展的进程。^[12]

对于某些检测死锁并从死锁中恢复的算法来说，活锁风险更大。如果多个进程运行，则死锁检测算法可以重复触发。这可以通过确保只有一个进程(任意选择或按优先级选择)运行来避免。^[13]

当使用分布式事务或并发控制时，分布式系统中可能会发生分布式死锁。通过死锁检测器的局部等待图构造全局等待图，或者通过像边缘跟踪等分布式算法，都可以检测到分布式死锁。

虚拟死锁是由于系统内部延迟而在分布式系统中错误检测到的死锁，但实际上并不存在。例如，如果进程释放了资源R1并申请资源R2，而第一条消息丢失或延迟，那么协调器(死锁检测器)可能错误地结束死锁（在占有资源R1时同时请求资源R2会导致死锁）。