1、死锁的条件

        死锁有三个必要条件：
  1. 互斥。一次只有一个进程可以使用资源。其他线程不能访问已分配给其他进程的资源。
  2. 占有且等待。当一个进程等待其他进程时，继续占有已经分配的资源。
  3. 不可抢占。不能强行抢占进程已占有的资源。
        在很多情况下，这些条件都是合乎要求的。例如，为确保结果的一致性和数据库的完整性，互斥是非常必要的。同理，不能随意的进行资源抢占。比如，当涉及数据库资源时，必须提供回滚恢复机制以支持资源抢占，这样才能把进程和它的资源恢复到以前适当的状态，使得进程最终可以重复它的动作。
        以上三个条件都只是死锁存在的必要条件，但不是充分条件。对死锁的产生，还需要第四个条件：

    4.循环等待。存在一个封闭的进程链，使得每个进程至少占有此链中下一个进程所需要的一个资源。

        第四个条件实际上是前三个条件的潜在结果，即假设前三个条件存在，可能发生的一系列事件会导致不可解的资源等待。这个不可解的循环等待实际上就是死锁的定义。条件4列出的循环等待之所以不可解，是因为有前面三个条件的存在。因此，这四个条件连在一起就构成了死锁的充分必要条件。
        有三种方法可以处理死锁。第一种方法是采用某种策略来消除4个条件中某一个条件的出现来预防死锁。第二种方法时基于资源分配的当前状态做动态选择来避免死锁。第三种方法是试图检测死锁的存在并且试图从死锁中恢复。

2、死锁预防

        一般来说，死锁预防策略是试图设计一种系统来排除发生死锁的可能性。可以把死锁预防方法分成两类。一类是间接的死锁预防，即防止前面列出的三个必要条件中任何一个的发生；一种是直接的死锁预防方法，即防止循环等待的发生。


  • 互斥。一般来说，第一个条件不可能禁止。如果需要对资源进行互斥访问，那么操作系统必须支持互斥。
  • 占有且等待。为预防占有且等待的条件。可以要求进程一次性请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。这种方法在两个方面是低效的。首先，一个进程可能被阻塞很长时间，以等待满足其所有的资源请求。而实际上，只要有一部分资源，他就可以继续执行。第二，分配给一个进程的资源可能有相当长的一段时间不会被使用，且在此期间，它们不能被其他进程使用。另一个问题是一个进程可能实现并不会知道他所需要的所有资源   。
  • 不可抢占。有几种方法可以预防这个条件。首先，如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占有的资源，如果有必要，可再次请求这些资源和另外的资源。另一种方法是，如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求他释放资源。只有在任意两个进程的优先级都不相同的条件下，后一种方案才能预防死锁。只有在资源状态可以很容易地保存和恢复地情况下（就像处理器一样），这种方法才是实用的。
  • 循环等待。循环等待条件可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了R类型的资源，那么他接下来请求的资源只能是排在R资源之后的资源类型。

3、死锁避免

        死锁预防和死锁避免的差别很微妙（术语“避免”有一点含糊。实际上可以把本节讨论的策略看作死锁预防的一个例子，因为它们确实防止了死锁的发生）。
        死锁预防中，通过约束资源请求，防止4个死锁条件中的至少一个的发生。这可以通过防止发生三个必要条件策略中的一个间接完成，也可以通过防止循环等待直接完成，但是这都会导致低效的资源利用和低效的进程执行。
        死锁避免则相反，它允许三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此死锁避免可以比死锁预防允许更多的并发。
        死锁避免有两种方法：
        1、如果一个进程的请求会导致死锁，则不启动该进程；
        2、如果一个进程增加的资源请求会导致死锁，则不允许此分配。

4、死锁检测

        死锁预防策略是非常保守的，它们通过限制访问资源和在进程上强加约束来解决死锁问题。死锁检测则完全相反，它不限制资源访问或约束进程行为。对于死锁检测来说，只要有可能，被请求的资源就被授权给进程。操作系统周期性的执行一个算法来避免条件4，即循环等待条件。
        一旦检测到死锁，就需要某种策略以恢复死锁。下面按复杂度递增的顺序列出可能的方法：
  1. 取消所有死锁进程。不管怎样，这是操作系统中最常用的方法；
  2. 把每个死锁进程回滚到前面定义的某些检查点，并且重新启动所有进程。这要求操作系统实现回滚和重启机制。该方法的风险是原来的死锁可能再次发生。但是，并发进程的不确定性通常能够保证不会发生这种情况；
  3. 连续取消死锁进程直到不再存在死锁。选择取消进程的顺序基于某种最小代价原则。在每次取消后，必须重新调用检测算法，以测试是否仍存在死锁；
  4. 连续抢占资源直到不存在死锁。和3一样，需要使用一种基于代价的选择方法，并且需要在每次抢占后重新调用检测算法。一个被强占的进程必须回滚到获得资源之前的状态。

        对于上面的3和4中的选择算法可以采用下面中的一种：
  1. 目前为止消耗的处理器时间最少
  2. 目前为止产生的输出最少
  3. 目前为止分配的资源总量最少
  4. 优先级最低

5、一种综合的死锁策略

 上面所有的解决死锁的策略都各有其优缺点，与其将操作系统机制设计为只采用其中一种策略，还不如在不同情况下使用不同的策略更有效。 
1. 把资源分成几组不同的资源类。
2. 为预防在资源类之间由于循环等待产生死锁，可使用前面定义的线性排序策略。 
3. 在一个资源类中，使用该类最适合的算法。 
4. 作为该技术的一个例子，考虑下列资源类：

  1. 可交换空间：在进程交换中所使用的外存中的存储块。可采用以下策略： 通过要求一次性分配所有请求的资源来预防死锁，就像占有且等待预防策略一样。 如果知道最大存储需求，则这个策略是合理的。死锁避免也是可能的。 
  2. 进程资源：可分配的设备，如磁带设备和文件。
  3. 可采用的策略： 对这类资源，死锁避免策略常常是很有效的，这是因为进程可以事先声明它们将需要的这类资源。采用资源排序的预防策略也是可能的。
  4. 内存：可以按页或按段分配给进程。 
    对于内存，基于抢占的预防是最适合的策略。当一个进程被抢占后，它仅仅被换到外存，释放空间以解决死锁。
  5. 内部资源： 
    诸如I/O通道. 
    可以使用基于资源排序的预防策略。