1         死锁

操作系统中有若干进程并发执行，它们不断申请、使用、释放系统资源，虽然系统的进程协调、通信机构会对它们进行控制，但也可能出现若干进程都相互等待对方释放资源才能继续运行，否则就阻塞的情况。此时，若不借助外界因素，谁也不能释放资源，谁也不能解除阻塞状态。根据这样的情况，操作系统中的死锁被定义为系统中两个或者多个进程无限期地等待永远不会发生的条件，系统处于停滞状态，这就是死锁。

2         产生死锁的原因

（1）系统资源不足。

（2）进程运行推进的顺序不合适。

（3）资源分配不当等。

如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。

3         产生死锁的四个必要条件

（1）互斥条件：一个资源每次只能被一个进程使用。

（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

（3）不可剥夺条件：进程已获得的资源，在末使用完之前，不能强行剥夺。

（4）循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

4         死锁处理方法（PAID）

（1）      死锁预防（Prevent）

（2）      死锁避免（Aviod）

（3）      忽视这个问题（Ignore）

（4）      死锁检测与恢复（Detect）

4.1      死锁预防

产生死锁有四个必要条件，只要确保至少一个必要条件不成立，就能预防死锁发生。通过限制如何申请资源来预防死锁发生。

（1）      互斥条件：通常不能通过否定互斥条件来预防死锁：有的资源本身是非共享的。

（2）      请求与保持条件：为了确保请求与保持条件不会成立，必须保证：一个进程请求一个资源时，它没有占有其他资源。

有两种可用的协议：一是每个进程在执行前申请并获得所需的所有资源，二是一个进程可以在没有资源时才申请资源，但是在申请更多资源之前，必须释放已经占有的所有资源。

这两种协议有两个主要缺点：第一，资源利用率可能比较低，因为许多资源可能已分配但长时间没有使用，第二，进程可能发生饥饿，一个进程如需要多个常用资源可能会永久等待，因为其所需要的资源中至少有一个已分配给其他进程。

（3）      不可剥夺条件：为了确保这一条件不成立，可使用协议：如果一个进程占有资源并申请另一个不能立即分配的资源，那么其占有的资源都被剥夺。这个协议通常由于状态可以被保存和恢复的资源。

（4）      循环等待条件：确保此条件不成立的一个方法是，对所有资源类型进行完全排序，并要求每个进程按递增顺序来申请资源。

4.2      死锁避免

为提高系统资源的利用率，避免死锁并不严格限制死锁必要条件的存在，而是在资源的动态分配过程中，使用某种方法去防止系统进入不安全状态，从而避免死锁的最终出现。进程的每次资源申请要求系统考虑现有可用资源、现已分配给每个进程的资源和每个进程将来申请与释放的资源，已决定当前申请是否满足或必须等到从而避免将来死锁发生的可能性。

常用的算法有：

（1）      如果每种资源只有一个实例，可以使用资源分配图算法

（2）      如果每种资源不只一个实例，可以使用银行家算法

http://curely.blog.51cto.com/1627940/803342

4.3      死锁忽视

认为死锁不可能在系统内发生，又称为鸵鸟算法。这种方法为绝大多数操作系统如Unix使用。

4.4      死锁检测和恢复

死锁检测和恢复是指，系统并不试图阻止死锁的产生，而是允许死锁发生，当检测到死锁发生后，采取措施进行恢复。

4.4.1         死锁检测算法

（1）      每种资源只有一个实例的情况

检测资源分配图中是否存在环，若存在，则死锁发生。

（2）      每种资源不只一个实例的情况

使用基于矩阵的检测算法，类似于银行家算法。

假设系统有m种资源，n个进程。

E[m]是现有资源向量，代表每种资源存在的实例数目，

A[m]是可用资源向量，代表当前每种资源可供使用的实例数目，

C[n][m]是当前分配矩阵，C的第i行Ci代表进程Pi当前所占有的每种资源的实例数目，

R[n][m]是请求矩阵，R的第i行Ri代表进程Pi当前要申请的每种资源的实例数目。

每个进程在开始时都没有标记。算法会对进程做标记，进程被标记后就表明它能够执行完毕，不会发生死锁。算法结束时，任何没有标记的进程都是死锁进程。

死锁检测算法如下：

1）  查找一个没有标记的进程Pi，对于进程Pi，向量Ri小于等于向量A。

2）  如果找到一个这样的进程，将向量Ci加到向量A上，标记该进程，表示该进程会执行完毕，释放其占有的资源。然后回到1）。

3）  如果没有这样的进程，算法终止。

算法结束时，任何没有标记的进程都是死锁进程。

4.4.2         死锁恢复

（1）      利用抢占恢复：临时将某个资源从其持有者转移到另一个进程。

（2）      利用回滚恢复：将一个进程回滚到以前的某个状态，使其释放从那时到现在所占有的资源。

（3）      通过杀死进程恢复。