死锁（deadlock）

是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

虽然进程在运行过程中，可能发生死锁，但死锁的发生也必须具备一定的条件，死锁的发生必须具备以下四个必要条件。

1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
2）请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

4）环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源，在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。因此，对资源的分配要给予合理的规划。

避免死锁算法1：

有序资源分配法
这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3等等），申请时必须以上升的次序。系统要求申请进程：
1、对它所必须使用的而且属于同一类的所有资源，必须一次申请完；
2、在申请不同类资源时，必须按各类设备的编号依次申请。

例如：

进程PA，使用资源的顺序是R1，R2；

进程PB，使用资源的顺序是R2，R1；

若采用动态分配有可能形成环路条件，造成死锁。
采用有序资源分配法：R1的编号为1，R2的编号为2；
PA：申请次序应是：R1，R2
PB：申请次序应是：R1，R2
这样就破坏了环路条件，避免了死锁的发生。

避免死锁算法2：
银行算法
避免死锁算法中最有代表性的算法是DijkstraE.W于1968年提出的银行家算法：
该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。
这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。

活锁（livelock）

指事物1可以使用资源，但它让其他事物先使用资源；

事物2可以使用资源，但它也让其他事物先使用资源，于是两者一直谦让，都无法使用资源。

避免活锁的简单方法是采用先来先服务的策略。当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批准申请队列中第一个事务获得锁。

饥饿（hungry）

所谓饥饿，是指如果事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。T3也请求封锁R，当T1释放了R上的封锁后，系统首先批准了T3的请求，T2仍然等待。然后T4又请求封锁R，当T3释放了R上的封锁之后，系统又批准了T4的请求......T2可能永远等待，这就是饥饿。

优先级反转（Priority inversion）

优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源。高优先任务由于因资源缺乏而处于受阻状态，一直等到低优先级任务释放资源为止。而低优先级获得的CPU时间少，如果此时有优先级处于两者之间的任务，并且不需要那个共享资源，则该中优先级的任务反而超过这两个任务而获得CPU时间。如果高优先级等待资源时不是阻塞等待，而是忙循环，则可能永远无法获得资源，因为此时低优先级进程无法与高优先级进程争夺CPU时间，从而无法执行，进而无法释放资源，造成的后果就是高优先级任务无法获得资源而继续推进。

解决方案：
（1）设置优先级上限，给临界区一个高优先级，进入临界区的进程都将获得这个高优先级，如果其他试图进入临界区的进程的优先级都低于这个高优先级，那么优先级反转就不会发生。

（2）优先级继承，当一个高优先级进程等待一个低优先级进程持有的资源时，低优先级进程将暂时获得高优先级进程的优先级别，在释放共享资源后，低优先级进程回到原来的优先级别。嵌入式系统VxWorks就是采用这种策略。

这里还有一个八卦，1997年的美国的火星探测器（使用的就是vxworks)就遇到一个优先级反转问题引起的故障。简单说下，火星探测器有一个信息总线，有一个高优先级的总线任务负责总线数据的存取，访问总线都需要通过一个互斥锁（共享资源出现了）；还有一个低优先级的，运行不是很频繁的气象搜集任务，它需要对总线写数据，也就同样需要访问互斥锁；最后还有一个中优先级的通信任务，它的运行时间比较长。平常这个系统运行毫无问题，但是有一天，在气象任务获得互斥锁往总线写数据的时候，一个中断发生导致通信任务被调度就绪，通信任务抢占了低优先级的气象任务，而无巧不成书的是，此时高优先级的总线任务正在等待气象任务写完数据归还互斥锁，但是由于通信任务抢占了CPU并且运行时间比较长，导致气象任务得不到CPU时间也无法释放互斥锁，本来是高优先级的总线任务也无法执行，总线任务无法及时执行的后果被探路者认为是一个严重错误，最后就是整个系统被重启。Vxworks允许优先级继承，然而遗憾的工程师们将这个选项关闭了。

（3）第三种方法就是使用中断禁止，通过禁止中断来保护临界区，采用此种策略的系统只有两种优先级：可抢占优先级和中断禁止优先级。前者为一般进程运行时的优先级，后者为运行于临界区的优先级。火星探路者正是由于在临界区中运行的气象任务被中断发生的通信任务所抢占才导致故障，如果有临界区的禁止中断保护，此一问题也不会发生。

护航现象（Lock Convoys）

Lock Convoys是在多线程并发环境下由于锁的使用而引起的性能退化问题。

当多个相同优先级的线程频繁地争抢同一个锁时可能会引起lockconvoys问题，一般而言，lockconvoys并不会像deadlock或livelock那样造成应用逻辑停止不前，相反地，遭受lock convoys的系统或应用程序仍然往前运行，但是，由于线程们频繁地争抢锁而导致过多的线程环境切换，从而使得系统的运行效率大为降低，而且，若存在同等优先级下不参与锁争抢的线程，则它们可以获得相对较多的处理器资源，从而造成系统调度的不公平性。

本文将解释lockconvoys问题的缘由。

假设一组线程在频繁地获取锁（所谓频繁，指在一个时间片的执行周期内多次获取锁），比如在Windows应用程序中常常用临界区（criticalsection）来保护一个共享变量或者防止一段代码被重入，这是极有可能发生的。

假设线程A获取到了锁，这时发生了线程调度中断，它的时间片用完了，于是，系统调度器交给下一个线程执行，不妨设线程B获得了执行权。由于此锁被线程A获取，所以，当线程B执行到获取锁的操作时，虽然时间片未用完，但不得不放弃执行权。如此继续，所有同等优先级且要竞争此锁的线程都被阻塞。调度器再次回到线程A，很快地线程A释放了锁。在操作系统中，释放一个锁，意味着内核中如果有线程正在等待该锁，则它的状态就可以变成运行态。比如，线程B的获取操作成功。但此时，内核只是将线程B标记为锁的所有者，而线程A继续执行。很快地，线程A又要获取锁了，由于该锁已经被标记给线程B了，所以线程A不得不放弃时间片，将控制权交给调度器。调度器终于可以捡起线程B，将处理器的执行权交给它。等到线程B释放了锁，下一个线程获得锁的所有权，并且等到线程B放弃执行权或者结束时间片之后就有机会被执行。此过程一直持续，经过一轮之后又会回到线程A，从而继续下一轮的争抢。在此期间，这些线程总是未执行满时间片就不得不放弃执行权。下面的图说明了三个线程在争抢一个锁时候的执行情况。

假设一个线程在一个满时间片的执行过程中要多次获取/释放锁，它一旦释放了锁，则意味着，只要存在锁竞争，它在分配给它的当前时间片内已经无法再重新获得锁了。所以，它只能执行到它的下一次获取操作为止。譬如，参与竞争的线程平均执行1/3时间片就要获取锁，那么，线程的实际执行时间变成了1/3时间片。系统的调度粒度变成原来的1/3时间间隔。这引起了3倍数量的线程切换。从上图的右半部分可以看出，每个线程在一轮的循环中，只有1/3时间片的机会。这导致了3倍的线程切换。

除了引起调度粒度变小以外，lockconvoys的另一个问题是造成调度器的时间分配不公平。假设另有一个线程X也是在同等的优先级上运行，但没有参与锁竞争。于是，在每一轮的锁竞争过程中，线程X都有机会被分配一次完整的时间片，于是，这些竞争的线程在一轮中获得1/3时间片，而非竞争的线程可以获得完整的时间片。当然，你可以说这种不公平是由于它们抢锁而引起的，但从时间分配比例而言，参与竞争与不参与竞争的线程是不公平的。下图说明了线程X和A、B、C之间的执行时间差异。

由以上描述可以看出，Lockconvoys的存在条件是，参与竞争的线程频繁地获取锁，锁被一个线程释放以后其所有权便落到了另一个线程的手里。在操作系统中，相同优先级的线程按照FIFO的顺序被调度和执行，竞争同一个锁的线程也按照FIFO的顺序被依次成功地获取到锁。这些条件在现代操作系统中都能被满足，包括Windows。

Lock convoys虽然不是致命的问题，但也可能在实际系统中发生。Sue Loh在她的博客文章中展示了在Windows CE中发生的lock convoy问题。她也讨论了一种合理的缓解lockconvoy的方案，要求在每个线程获取锁的时候先尝试（try），如果尝试多次仍不成功，再阻塞。

References:

[1] Sue Loh, Lock Convoys and How toRecognize Them,http://blogs.msdn.com/b/sloh/archive/2005/05/27/lock-convoys-and-how-to-recognize-them.aspx,2005.

[2] Lock Convoys, http://en.wikipedia.org/wiki/Lock_convoy

Linux同步机制 - 基本概念(死锁,活锁,饿死,优先级反转,护航现象)