Deadlock
定义
|
如果一组进程中的每个进程都在等待该组进程中只有其它进程会引起的事件，则该组进程将死锁。 —Andrew Tanenbaum |
更简单地说，当两个或多个进程相互阻塞时，就会出现死锁，因为没有人愿意“让步”让其他进程继续进行 - 导致所有进程都将无限期地保持僵局。
一个典型的例子是在资源管理中，例如当两个进程试图获得对一对文件的独占访问权时。 如果进程1独占访问文件A，并试图获得文件B的独占访问权，而进程2独占访问文件B，并希望独占访问文件A，则两者都将阻止等待另一个完成并释放其锁。
要发生死锁，必须满足某些条件：（译者注：以下其实主要说明了回避死锁条件，对解除死锁的方法进行总结）
- 进程必须是能够获得对给定资源的独占访问权限，以使其成为唯一允许访问的进程-否则，一个进程不会阻碍另一个进程。
- 进程还必须在获得对一个资源的访问权后，保持一段时间(在此期间，其他进程可能会采取行动并获取到它们自己的其它锁)， 然后去获得对另一个资源的访问，且不丢失之前的独占锁——“保持并等待”。 如果不是这种占用并保持，那么一个进程要么会拿到独占访问并阻止其他进程，要么被阻止并处于等待访问状态，而不会进退两难。
- 进程的独占锁必须先到先得，无法被抢占，这样才会导致死锁。 如果外部代理能够删除进程对资源的独占访问权限，则另一个进程就有可能获取该资源，死锁就会结束。
- 一旦开始尝试获取锁，进程就会不停尝试获取锁。 如果可以把锁抢占过来，它可以继续执行其他操作，因此不会构成死锁（因为它不再需要陷入等待）
- 如上所述，还存在一种循环传递的情况，进程需要访问由该组中的下一个进程锁定的资源。 显然，如果只有一个进程存在不可能发生死锁，或者不同线程可访问受到其他控制访问的资源，则也不会发生死锁。 例如，进程1可以锁定资源A和B，进程2可以锁定B和C，进程3可以锁定C和D —— 本来是会死锁的。 但是如果允许后来抢占，也不可能形成阻塞进程循环，也不会发生死锁。
预防
通过上述至少一种预防措施，可以防止死锁。 第一个情境很简单-如果无法独占资源，则无法锁定死锁，尽管这种 “解决方案” 通常不可行。 例如，必须专门分配内存空间，以防止进程相互损坏数据。 然而，在某些情况下可以使用更智能的锁定系统-文件可能具有独占写入锁，并且仍然是可读的，从而防止了许多潜在的死锁。 无等待同步（Wait-Free synchronization）研究了这种方法。
第二个情境可以通过要求一个进程在访问更多资源之前放弃所有锁定的资源来解决，允许其他进程有机会获取这些资源并继续。 这可以实现为将资源同时持有的锁数量限制为1个(因此它必须在获取另一个锁之前释放它持有的最后一个锁)，或者要求进程原子声明它的所有锁-也就是说，进程必须在单个调用中锁定A和B，而不是锁定A、等待，然后锁定B(或者锁定A、等待、释放A，然后锁定A和B)。 因此，如果另一个进程持有任一资源，则请求进程没有得到锁，并且必须等待直到所有资源变为空闲，并且它可以在没有阻碍的情况下继续进行。 然而，这需要提前了解所有所需资源（这并不总是可能的），而且有时候进程会不断请求和释放资源。
防止第三种情境的可行性取决于所涉及的资源，以及是否可以后来抢占进程对资源的访问，然后将其恢复到抢占之前的状态。 例如，如果两个进程各自占用了可用内存空间的一半，并且都请求更多内存，则可能会发生死锁。 但是，一个进程可以通过将其内存分页移动到虚拟内存中来释放抢占，好允许另一个进程继续，然后再将被抢占的进程分页放回内存中 - 在这种情况下，抢占是透明的，进程永远不会知道它失去了原有的独占访问。 或者，后来抢占可以简单地通知进程它已经失去访问权限，并要求进程自行处理后果。 然而，在某些情况下，抢占有主的资源是不可能或不安全的 ——例如：在打印作业中途抢占恐怕只是浪费墨水。 此外，后来抢占行为需要被触发器触发-因此，必须有一种检测死锁的方法，最简单的办法可以只是被阻塞进程持有的锁会超时。
第四个情境与第三个情境相似，因为可以通知进程潜在的死锁。 但是，不会释放锁，这会使相关进程更容易处理这种情况。
最后一个情境是需要仔细规划每个进程可以锁定的资源。 如果每个资源仅可由单个进程访问，而该进程会协调其他线程（如后台打印程序）的访问，则可以防止死锁。 然而，这需要更多的固定预先计划，而且这些固化安排通常比死锁的风险更麻烦。 - 例如考虑存在10个进程，并且每个进程可能仅使用10分之1的内存空间，或者可能仅在处理器时间的10分之1上运行，则资源效率将受到严重损害，只为了防止几乎肯定不会发生的死锁。 资源排序也是防止死锁的有力手段。 比如可以对锁进行编号，并且程序将只按递增顺序获取它们，则不会有任何死锁，因为程序将无法开始等待只具有较低编号的锁的任何程序，因此不会存在持有等待阶段。