操作系统设计/并发/死锁
在计算机科学中，死锁指的是两个或多个进程都等待另一个进程释放资源的特定状态，或者两个以上进程在循环链中等待资源（参见必要条件）。死锁是多处理中常见的问题，在多处理中，许多进程共享一种特定类型的互斥资源，称为软件或软锁。 用于分时和/或实时市场的计算机通常配备硬件锁（或硬锁），它保证独占访问进程，强制序列化。 死锁特别麻烦，因为没有通用的解决方案可以避免（软）死锁。
这个情况可以用两个人画图来理解，他们之间只有一支铅笔和一把尺子。 如果一个人拿了铅笔，另一个人拿了尺子，当拿铅笔的人需要尺子，而拿尺子的人需要铅笔才能放弃尺子时，就会发生死锁。 两个请求都无法满足，因此发生了死锁。
电信对死锁的描述更强一些：当所有进程都没有满足条件可以转移到另一个状态（如进程的有限状态机中所述）并且所有通信通道都为空时，就会发生死锁。 第二个条件通常在其他系统中被忽略，但在电信环境及其系统中很重要。
发生死锁有四个必要条件，被称为Coffman 条件，源自 E. G. Coffman 在 1971 年的一篇文章中对它们的首次描述。
- 互斥条件：一个资源一次只能被一个进程使用
- 持有并等待条件：已经持有资源的进程可以请求新的资源
- 不可抢占条件：只有持有资源的进程才能释放它
- 循环等待条件：两个或多个进程形成一个循环链，其中每个进程都等待链中下一个进程持有的资源
只有在所有 4 个条件都满足的情况下才会发生死锁。
循环等待预防包括允许进程等待资源，但要确保等待不会形成循环。 一种方法可能是为每个资源分配优先级，并强制进程按优先级递增的顺序请求资源。 也就是说，如果一个进程持有某些资源，而这些资源中优先级最高的为m，那么这个进程就不能请求优先级小于m的任何资源。 这将强制资源分配遵循特定且非循环的排序，因此不会发生循环等待。 另一种方法是允许每个进程只持有单个资源； 如果进程请求另一个资源，它必须先释放它当前持有的资源（或持有并等待）。
在数据库产品中可能发生死锁的一个例子如下。 使用数据库的客户端应用程序可能需要对表进行独占访问，为了获得独占访问，它们会请求锁。 如果一个客户端应用程序持有对一个表的锁，并尝试获取另一个已经被第二个客户端应用程序持有的表的锁，这可能会导致死锁，如果第二个应用程序随后尝试获取第一个应用程序持有的锁。（但是这种特定类型的死锁很容易防止，例如，使用全部或无资源分配算法。）
另一个例子可能是文本格式化程序，它接收发送给它的文本进行处理，然后返回结果，但只有在收到“足够”的文本可以处理后才会返回结果（例如 1KB）。 一个文本编辑器程序被编写为向格式化程序发送一些文本，然后等待结果。 在这种情况下，在最后一个文本块上可能会发生死锁。 由于格式化程序可能没有足够的文本可供处理，它会挂起自己，同时等待额外的文本，而这些文本永远不会到达，因为文本编辑器已经发送了它所有的文本。 同时，文本编辑器本身也挂起，等待来自格式化程序的最后一个输出。 这种类型的死锁有时被称为死锁（只在两个应用程序参与时使用）或饥饿。 然而，这种情况也容易防止，方法是让文本编辑器用它最后一个（部分）文本块发送一个强制消息（例如 EOF），这将强制格式化程序在格式化后返回最后一个（部分）块，而不是等待额外的文本。
尽管如此，由于没有通用的死锁预防解决方案，因此必须预测每种类型的死锁并专门防止。 但是，可以在操作系统中实现通用算法，这样如果一个或多个应用程序被阻塞，它通常会在（并且在此期间，不允许其他资源，可能需要放弃它已经拥有的资源，回滚到获取之前状态）之后终止。
如果在分配资源之前提前获得有关进程的某些信息，则可以避免死锁。 对于每个资源请求，系统都会查看授予该请求是否意味着系统将进入不安全状态，这意味着可能导致死锁的状态。 然后，系统只授予导致安全状态的请求。 为了让系统能够弄清楚下一个状态是安全还是不安全，它必须提前知道任何时候所有存在的、可用的和请求的资源的数量和类型。 一个用于死锁避免的已知算法是银行家算法，它需要提前知道资源使用限制。 然而，对于许多系统来说，在提前知道每个进程会请求什么是不可能的。 这意味着死锁避免通常是不可能的。
还有两种其他算法，Wait/Die 和 Wound/Wait，它们都使用对称性破坏技术。 在这两种算法中，都存在一个较旧的进程 (O) 和一个较年轻的进程 (Y)。 进程年龄可以通过进程创建时间时的 timestamps 来确定。 timestamps 越小，进程越旧，而 timestamps 越大，进程越年轻。
| Wait/Die | Wound/Wait | |
|---|---|---|
| O 需要 Y 持有的资源 | O 等待 | Y 死亡 |
| Y 需要 O 持有的资源 | Y 死亡 | Y 等待 |
需要注意的是，进程可能处于不安全状态，但不会导致死锁。 安全/不安全状态的概念只指系统是否可能进入死锁状态。 例如，如果一个进程请求 A，这将导致不安全状态，但释放 B 将防止循环等待，那么该状态是不安全的，但系统没有处于死锁状态。
可以通过确保以下四个条件中的至少一个发生来防止死锁
- 消除互斥条件意味着任何进程都不能独占访问资源。 对于无法卷绕的资源，这证明是不可能的，即使对于卷绕的资源，死锁仍然可能发生。 避免互斥的算法称为非阻塞同步算法。
- 可以通过要求进程在启动之前（或在执行特定操作集之前）请求它们将需要的全部资源来消除“持有并等待”条件； 这种预先的知识通常难以满足，而且无论如何都是对资源的低效使用。 另一种方法是要求进程在请求所需全部资源之前释放所有资源。 这也经常不切实际。（此类算法，例如序列化令牌，被称为全有或全无算法。）
- “不可抢占”（锁定）条件也可能难以或无法避免，因为进程必须能够在一定时间内拥有资源，否则处理结果可能不一致或发生抖动。 然而，无法强制抢占可能会干扰优先级算法。（注意：对“锁定”资源的抢占通常意味着回滚，应该避免，因为它在开销方面非常昂贵。）允许抢占的算法包括无锁和无等待算法以及乐观并发控制。
- 循环等待条件：避免循环等待的算法包括“在临界区禁用中断”，以及“使用层次结构来确定资源的部分排序”（在没有明显层次结构的情况下，甚至资源的内存地址也被用来确定排序）以及 Dijkstra 的解决方案。
通常既不能使用死锁避免也不能使用死锁预防。 相反，通过使用跟踪资源分配和进程状态并回滚和重启一个或多个进程以消除死锁的算法，使用死锁检测和进程重启。 检测已经发生的死锁很容易，因为每个进程锁定的和/或当前请求的资源都是资源调度器或操作系统已知的。
在死锁发生之前检测死锁的可能性要困难得多，实际上，通常是不可判定的，因为停机问题可以重新表述为死锁场景。但是，在特定的环境中，使用特定的资源锁定方式，死锁检测可能是可判定的。在一般情况下，无法区分仅仅在等待极不可能发生的事件集发生的算法和由于死锁而永远无法完成的算法。
当分布式事务或并发控制被使用时，分布式死锁可能发生在分布式系统中。分布式死锁可以通过构建全局等待图（从死锁检测器的本地等待图）或通过像边追逐这样的分布式算法来检测。
幽灵死锁是指在分布式系统中检测到的死锁。