进程管理八（死锁）
- 死锁的概念
（1）死锁的定义：
各进程在使用系统资源时，应注意系统产生死锁的问题。死锁，是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又得不到资源，各并发进程不能继续向前推进的状态。
（2）产生死锁的原因：
死锁的起因是并发进程对资源的竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。因为资源的有限性，所以需要采用适当的资源分配算法，以达到消除死锁的目的。
（3）产生死锁的必要条件：
互斥条件：并发进程所要求和占有的资源是不能同时被两个或两个以上进程使用或操作的。
不可剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放。
部分分配：进程每次申请它所需要的一部分资源，在等待新资源的同时，继续占用已分配到的资源。
环路条件：存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。
只要上述4个必要条件中的某一个不满足，死锁就可以排除。
- 死锁的处理策略
解决死锁的方法一般可分为预防、避免、监测与解除3种。
预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。
避免是指系统再分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生。
死锁监测与解除是指设有专门的机构，当死锁发生时，该机构能够监测到死锁发生的位置和原因，并能通过外力破坏死锁发生的条件，从而使得并发进程从死锁中解除出来。
（1）死锁预防：
通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个来防止死锁。产生死锁的4个必要条件中，互斥条件由设备的固有特性决定，不仅不能改变，相反还应加以保证。
打破不可剥夺条件。一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源。以后需要时再重新申请。该方法需要完成对已执行进程的回滚，系统开销大。
打破资源的部分分配条件。系统要求所有进程要一次性地申请在整个运行过程中所需的全部资源。如果某个进程的资源得不到满足，则安排一定的等待次序让其他进程释放资源。但是这种方式也有以下缺点：一是一个用户在进程运行之前可能提不出进程将要使用的全部设备。二是进程必须等待，知道所有资源满足才能运行。实际上某些资源可能要到运行后期才会用到。三是进程运行期间，对某些设备的使用时间很短，甚至不会用到。如当用户进程出错时才需要打印机输出错误信息，但必须把打印机分配给该进程，并长期占用。采用该方法对系统来说是非常浪费的。
打破死锁的环路条件。即把资源分类按顺序排列，是进程在申请、保持资源时不形成环路。如有m种资源，则列出R1<R2<...<Rm。若进程Pi保持了资源Ri，则它只能申请比Ri级别更高的资源Rj（Rj>Ri）。释放资源时必须是Rj优先于Ri被释放，从而避免环路的产生。这种方法的缺点是限制了进程对资源的请求，而且对资源的分类编序也耗去了一定的系统开销。编序必须相对稳定，这就限制了新类型设备的增加。尽管在为资源编号时就已经考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源浪费。此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。
（2）死锁避免：
在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。
避免死锁同样是属于事先预防的策略，但并不是实现采取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。
a.系统安全状态。
避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，让进程等待。
安全状态，是指系统能按某种进程推进顺序（P1，P2...Pn），为某个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都氪顺序地完成。此时称P1，P2...Pn为安全序列。如果系统无法找到一个安全序列，则称系统处于不安全状态。
假设系统有三个进程P1，P2和P3，共有12台磁带机。进程P1总共需要10台磁带机，P2和P3分别需要4台和9台。假设在T0时刻，进程P1，P2和P3分别已经获得5台，2台，2台磁带机，尚有3台还未分配。则系统在T0时刻是安全的，因为存在一个安全序列P2、P1、P3，即只要系统按此进程序列分配资源，则每个进程都能顺利完成。若在T0时刻，系统为P3进程分配1台磁带机，则此时系统便进入不安全状态，因为此时已经无法找到一个安全序列。
总之，并非所有的不安全状态都是死锁状态，但只要系统进入不安全状态，就有可能发生死锁。反之，只要系统处于安全状态，便不可能发生死锁。
b.银行家算法。
银行家算法是著名的死锁避免算法。它提出的思想是：把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家指定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量，则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过，则拒绝分配资源，若没有超过，再测试系统现存的资源能否满足该进程尚需的最大资源量，不能满足则推迟分配，进程等待。若能满足，则需判断按当前的申请量给该进程分配资源后系统的状态是否安全，如果安全则分配，否则拒绝此次资源请求。
银行家算法从避免死锁的角度上来说是非常有效的，但是从某种意义上来说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登陆或退出），况且原本可用的资源也可能突然间变成不可用（如打印机坏掉）。因此，实际中只有很少的系统采用银行家算法来避免死锁。
（3）死锁监测和解除：
实现并不采取任何限制，也不检查系统是否进入不安全区，允许死锁发生，但可通过监测机构及时监测出死锁的发生，并精确确定与死锁有关的进程和资源，然后采取适当措施解除死锁，并以最小的代价回复系统的运行。
a.资源分配图。
系统死锁，可利用资源分配图来描述。用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源，从资源到进程的边称为分配边，表示该类资源已经有一个资源被分配给了该进程。
上图所示的资源分配图中，进程P1已经分得了两个R1资源，并又请求了一个R2资源；进程P2已经分得了一个R2资源和一个R1资源，并又请求R1资源。
b.死锁定理。
可以通过将资源分配图简化的方法来监测系统状态S是否为死锁状态。简化方法如下：
在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于系统中已有空闲资源数量。若所有的连接该进程的边都满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的节点。
上面的资源分配图中，P1是满足这一条件的进程节点。
进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。上面资源分配图中的P2进程就满足这样的条件。根据上面的简化方法简化后，若能消去图中所有的边，则称该图是可完全简化的，如下图所示：
c.死锁的解除。
死锁解除有如下方法：一是资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。二是撤销进程法。强制撤销一个或一部分死锁进程并剥夺这些进程的资源。撤销的原则可按照进程优先级和撤销进程代价的高低进行。三是进程回退法。让一（多）个进程回退到足以避免死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。
无论哪一种解除死锁的方法，都需要很大的开销。但是死锁的监测与解除办法不对系统的资源分配加以任何限制，因此是对付死锁的各种办法中资源利用率最高的一种。