什么是死锁？

什么是死锁？
在两个或多个并发进程中，如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该进程集合就产生了死锁。

延伸问题：死锁产生有哪些条件？
死锁产生的根本原因是多个进程竞争资源时，进程的推进顺序出现不正确。

互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
占有和等待：已经得到了某个资源的进程可以再请求新的资源。
不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
延伸问题：怎么解决死锁？
对于死锁，主要有4种解决策略。
鸵鸟策略

就是直接忽略死锁。就像鸵鸟遇到危险的时候，把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁预防

死锁预防是指通过破坏死锁产生的四个必要条件中的一个或多个，以避免发生死锁。

破坏互斥：不让资源被一个进程独占，可通过假脱机技术允许多个进程同时访问资源；
破坏占有和等待：有两种方案，
已拥有资源的进程不能再去请求其他资源。一种实现方法是要求进程在开始执行前请求需要的所有资源。
要求进程请求资源时，先暂时释放其当前拥有的所有资源，再尝试一次获取所需的全部资源。
破坏不可抢占：有些资源可以通过虚拟化方式实现可抢占；
破坏循环等待：有两种方案：
一种方法是保证每个进程在任何时刻只能占用一个资源，如果要请求另一个资源，必须先释放第一个资源；
另一种方法是将所有资源进行统一编号，进程可以在任何时刻请求资源，但要求进程必须按照顺序请求资源。
死锁避免

为了避免因为预防死锁而导致所有线程变慢，死锁避免采用了与死锁预防相反的措施。它允许三个必要条件，但通过算法判断资源请求是否可能导致循环等待的形成并相应决策，来避免死锁点的产生。因此，其前提是知道当前资源使用的整体情况，以及申请资源线程本身所占有的资源细节。

判断和决策中，主要使用两种避免方法。

线程启动拒绝：如果一个线程的请求会引发死锁，则不允许其启动。
资源分配拒绝：如果一个线程增加的资源请求会导致死锁，则不允许此申请。
整体来看，死锁避免是从资源和线程相互间关系着手，避免形成循环等待是其主要任务。

死锁检测和恢复

可以允许系统进入死锁状态，但会维护一个系统的资源分配图，定期调用死锁检测算法来检测途中是否存在死锁，检测到死锁发生后，采取死锁恢复算法进行恢复。

死锁检测方法如下：

在资源分配图中，找到不会阻塞又不独立的进程结点，使该进程获得其所需资源并运行，运行完毕后，再释放其所占有的全部资源。也就是消去该进程结点的请求边和分配边。
使用上面的算法进行一系列简化，若能消去所有边，则表示不会出现死锁，否则会出现死锁。
检测到死锁后，就需要解决死锁。目前操作系统中主要采用如下几种方法：

取消所有死锁相关线程，简单粗暴，但也确实是最常用的
把每个死锁线程回滚到某些检查点，然后重启
连续取消死锁线程直到死锁解除，顺序基于特定最小代价原则
连续抢占资源直到死锁解除