死锁

死锁

在进程同步的时候，我们已经发现了死锁存在。有两个信号量S和Q。进程P0和进程P1都需要S和Q，但是两者申请的顺序不同，这就存在P0和P1分别拿到S和Q两个信号量之后，一直陷入无法拿到下一个信号量的死循环之中，这就是死锁。

死锁：当一个进程申请资源，如果资源不可用，那么它将进入等待状态，如果申请的资源被其他等待进程所占据，并且该等待进程有可能无法改变它等待的状态，那么这种情况就会发生死锁。

死锁发生的必要条件有下面四个：

• 互斥：至少有一个资源处于互斥状态，它只能一次被一个进程使用。
• 占有并等待：一个进程占有某一个资源并等待另一个资源，而这个资源被其他进程占据。
• 非抢占：资源不能被抢占。
• 循环等待：进程1等待的资源被进程2占据，进程2等待的资源被进程3占据，......，进程n等待的资源被进程1占据。这就是循环等待。在哲学家进餐问题中就有可能发生这种情况。

这四个条件并不是完全独立的，当他们一旦被同时满足，那么死锁必将出现。

死锁的描述

死锁问题可以用称为系统资源分配图的有向图来精确描述。这个有向图的节点分为两种类型，进程P的集合P={P1，P2，...，Pn}；以及资源R的集合R={R1，R2，...，Rn}；这个图的边也分为两种，若由资源指向进程，那么表示该资源已经被该进程占据；若由进程指向资源，那么表示该进程申请该资源，并正在等待。

在资源分配图中如果没有环，那么系统就一定不是死锁状态；如果有环，那么系统可能处于死锁状态，也可能不是死锁。

死锁处理的方法

从原理上来讲，死锁有三种方法可以来处理它。分别是死锁避免，死锁检测和恢复，死锁忽略。

死锁忽略

OS不能保证死锁不会发生，并且也不提供死锁避免和死锁检测。那么就是说，当死锁发生的时候，操作系统是不知道的。这样就会导致系统性能下降，资源一直被占用。这种策略看起来没有解决死锁问题。但是它却被现代的大多数操作系统所使用。对于许多系统而言，死锁发生的频率是非常低下的。OS去不断的检测死锁是一个很昂贵的开销，这对很务实的操作系统而言是不必要的。当然了，死锁的发生绝大多数是应用程序的问题，那么OS的态度就是，你发生了死锁，关我什么事。就相当于十字路口堵车了，你去打酱油，关你屁事。操作系统就是这种态度，关我屁事。这事应该交给应用程序开发者去解决。

当然了，OS并不是一直打酱油，它其实提供了一些策略，例如：时间片轮转，让所有的进程都能运行一会儿，大家雨露均沾。OS还提供了虚拟合并技术，例如：当我们打开多个窗口的时候，OS给我们提供了虚拟，使得每个进程认为自己都有一个屏幕，都去写显存，但是OS提供了虚拟合并，来使得窗口合理的显示在屏幕上。

死锁预防

出现死锁有四种必要条件，只要确保至少有一个条件不成立，就能避免死锁发生。但是这个要求很难实现。有些资源它一定是非共享的。一个进程几乎不可能在执行之前就能申请并获取它所需要的所有资源。还有一些设备是串行的，你只能等待。最后一种办法就是合理的分配，调度资源。当然，这也是及其困难的。可以看到，预防死锁几乎是不可能的。

死锁避免

死锁避免算法动态的检测资源分配状态以确保循环等待条件不可能成立。

如果系统能按照某个顺序给每个进程分配资源，并能避免死锁，那么系统状态就是安全的。我们称这个序列为“安全序列”。如果存在一个安全序列，那么系统将处于安全状态。安全状态是不会发生死锁的。非安全状态不一定死锁。采用这种方案的 时候，系统一开始处于安全状态，当进程申请一个可用资源的时候，系统必须确定这一资源申请是可以立即分配还是需要等待。只有分配以后系统仍旧处于安全状态，才允许申请资源。采用这种方案，如果进程申请的资源是可用的，但是使用以后会使系统进入不安全状态，那么系统就不会该可用资源给该进程。这种方法的资源使用率是较低的。

前面提及的资源分配图，它可以在每种资源都只有一个实例的时候，很好地实现避免死锁的算法。因为，我们只需要检测有向图是否有环。但是对于每种资源有多个实例的情形下，资源分配图算法就不适用了，银行家算法一种解决方案。

银行家算法：新进程进入系统时，它必须说明其可能需要的每种资源类型的最大数量。当进程申请某一资源的时候，系统必须确定这些资源的分配是否会使得系统处于不安全状态。如果会，那么就不分配资源。否则，就分配资源。

上面这些算法仍旧是非常复杂的，会降低系统的效率。当系统既不采用死锁预防，也不采用死锁避免。因此就有了死锁检测。用来检查系统是否出现了死锁。一个用来从死锁状态恢复。

死锁检测当然也会带来系统额外开销，何时使用死锁检测算法，这取决于死锁可能发送的概率以及死锁发生的时候会影响到几个进程？

在实际中，以上的各种各样的方法可能都不会被采用，而是采用类似“看门狗的做法”。看门狗能捕捉到其它进程（喂狗进程）发出的信号，来判断进程是否陷入了无限等待状态。

死锁恢复

当死锁检测算法检测到了死锁已经存在，那么可以采用的恢复办法是较多的。一是简单地终止一个进程或者多个进程以打破循环等待。另一个方法是从一个或多个死锁进程哪里抢夺资源。

最简单，最暴力，最无脑的做法就是杀死所有陷入死锁的进程。但是这样的代价是巨大的。

另一种方法是一次只杀死一个进程，直到死锁被解开。这个方法的开销比较大，每次终止一个进程之后，都需要调用一次死锁检查算法。终止进程的时候，需要去选择终止哪一个，这并不是一个简单地问题。许多因素影响着应该选择哪个进程去终止它。需要考虑的要素包括但不限于：优先级，已执行时间，需要什么资源，需要多少资源，还需要执行多久，进程是前台的还是后端的等。

资源抢夺虽然没有杀死进程那么极端，但是仍旧存在选择哪一个进程来牺牲。这依然还是一个难题。我们有一个叫做回滚的策略来终止死锁，那就是将进程回滚到某个安全状态，但是这仍旧存在着足够倒霉的情形，那就是它执行一段时间后，又死锁了。更倒霉的是，如何保证资源不会总是从同一个进程哪里抢夺而来的。也就是说，要符合科学发展观，可持续发展可是王道。不然，有些进程可能就会被饿死。