目录
说明使用互斥锁时死锁是如何发生的。
系统模型：
死锁的特性：
处理死锁的方法：
死锁的预防：
死锁避免：
说明使用互斥锁时死锁是如何发生的。
我们先来看一个例子：
当两列火车在十字路口逼近时，它们要完全停下来，且在一列火车开走之前，另一辆火车不能启动。
系统模型：
资源类型的例子：CPU周期，内存空间，I/O设备。
每种资源类型Ri有Wi个实例。
每个进程按如下方式利用资源：
1，申请。
2，使用。
3，释放。
死锁的定义：当一组进程中的每一个进程都在等待一个事件，而这个事件只能由这组进程中的另一个进程引起，那么这组进程就处于死锁状态。
死锁是指多个进程因竞争系统资源或相互通信而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。
例子：假设一条河上有一座独木桥，若桥两端人相向而行。死锁就会发生。
死锁的特性：
死锁产生的原因与资源的使用相关，下面介绍资源的分类。
资源包括可剥夺资源和不可剥夺资源，有点类似于抢占式和 非抢占式。
可剥夺资源：是指某进程获得这类资源后，该资源可以被其他进程或系统剥夺，如CPU，存储器。
不可剥夺资源:又称为非剥夺资源，是指系统将这类资源分配出去之后，再不能强行收回，只能等进程结束后主动释放，如打印机，读卡机。
注意：竞争可剥夺资源不会发生死锁。
永久性资源：可顺序重复使用的资源，如打印机。
消耗性资源：有一个进程产生，被另一个进程使用的短暂时间后便无法使用的资源，又称为临时性资源，如消息。
竞争永久性资源和临时性资源都有可能发生死锁。
死锁产生的原因：
竞争资源：多个进程竞争资源，而资源又不能同时满足其需求。
进程推进顺序不当：进程申请资源和释放资源的顺序不当。
下面给出竞争非剥夺资源引起的死锁：
如消息通信按下述顺序进行，则不会发生死锁：
P1：...Release(S1)；Request(S2)；...
P2：...Release(S2)；Request(S1)；...
若按下述顺序，则可能发生死锁：
P1：... Request(S2)；Release(S1)；...
P2：... Request(S1)；Release(S2)；...
显然，若两者都是先释放再请求，就不会发生死锁，但是要是先请求，显然是得不到对方已经持有的资源。
显然，造成死锁的原因就是资源有限，而进程顺序相矛盾。
互斥：一次只有一个进程能使用一个资源。
占有并等待：一个至少持有一个资源的进程等待获得另外的资源，而该资源由其他进程所持有。
非抢占：资源不能被抢占，即资源只能在进程完成任务后自动释放。
循环等待：等待资源的进程之间存在环。
死锁产生的必要条件：
互斥条件：在一段时间内某个资源仅被一个进程所占有。
请求和保持条件：又称为部分分配条件，当进程因请求资源被阻塞时，已分配的资源保持不放。
不剥夺条件：进程所获得的资源在未被使用完毕之前，不能被其他进程强行夺走。
循环等待条件：死锁发生时，存在一个进程资源的循环。
死锁是因为资源竞争造成的僵局。
通常死锁至少涉及两个进程。
死锁与部分进程及资源相关。
资源分配图有一个节点集合V和一个边集合E组成，V被分为两部分：系统中的进程集合P，系统中的资源集合R。请求边是:Pi->Ri，分配边：Ri->Pi。
图中圆形表示进程Pi，方框表示资源类型Ri，在方框中用原点表示实例。
可以证明：如果资源分配图中没有环，那么系统就没有进程死锁，如果分配图中存在环，那么就有可能死锁。
显然，这个就有可能存在死锁，R2的资源全都被持有，而P3还要请求R2的资源，要等P2或P1执行完释放，而P1释放首先要请求R1，而R1被P2所持有，所以要先等P2释放，P2释放首先要请求R3，而R3被P3所持有，所以首先要等到P3释放，但是在请求到R2的资源之前，P3不能完成进程，不能完成进程就不能释放资源，总结起来就是P3请求R2资源的必要条件是P3已经拥有R2的资源，显然自相矛盾，故会被死锁。
但是有环也不一定是死锁，如下图：
由于P4持有资源R2，而P4又不请求什么资源，所以P4执行完自动释放持有的一个R2资源，P2同理，这时R1，R2资源充足，对所有请求都能及时回应。
处理死锁的方法：
有三种方法可以处理死锁：
通过协议预防或避免死锁。
允许系统进入死锁状态，然后检测它并恢复系统。
忽略这个问题。
第三种方法被大多数操作系统所使用，包括UNIX和Windows。
用于处理死锁的方法主要有：
忽略死锁：这种处理方式又称为鸵鸟算法，指像鸵鸟一样对死锁视而不见。
预防死锁：设置某些限制条件，通过破坏死锁产生的四个必要条件之一来预防死锁。
避免死锁：在资源的动态分配过程中，用某种方法来防止系统进入不安全状态。
死锁的预防：
只要确保至少有一个必要条件不成立，就能预防死锁发生。
预防死锁的特点是：较易实现，广泛使用，但是限制较严，资源利用率低。
互斥：
通常不能通过否定互斥条件来预防死锁，有的资源本身就是非共享的。
互斥是设备本身固有的属性，此条件不能被破坏。
占有并等待：
必须保证进程申请资源的时候没有占有其他资源。
要求进程在执行前一次申请全部的资源，或只有没有占有资源时才可以分配资源。
资源利用率低，可能出现饥饿。
破坏请求和保持条件：
要求进程一次申请他所需的全部资源，若有足够的资源则分配给进程，否则不分配资源，进程等待，这种方法被称之为分配法。
特点是：简单，安全且易于实现，但是资源利用率低，进程延迟运行。
非抢占：
如果一个进程占有资源并申请另外一个不能立即分配的资源，那么其现在已经分配的资源都可以被抢占。
该协议通常应用于状态可以保存和恢复的资源，例如CPU寄存器，内存。
破坏不剥夺条件：
一个应景获得某种资源的进程，如果新的资源请求得不到满足，则它必须释放已获得的所有资源。
特点是：实现较复杂，释放已获得的资源可能造成前一段时间工作失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。
循环等待：
对所有资源类型进行完全排序，且要求进程按照递增顺序来申请资源。
破坏循环等待条件：
将所有资源按照类型排队，并赋予不同序号，要求进程均严格按照序号递增的书序请求资源，同类资源一次申请完，这种方法称之为资源的有序分配法。
特点是：比前两种方法资源利用率高，吞吐量大，但要求资源序号相对稳定，从而限制了新设备的增加，使用资源的顺序与系统规定的顺序不同，造成资源的浪费，使用资源的次序限制用户编程。
为什么有序分配资源不存在环：
采用有序资源分配，系统必须按照资源编号升序进行申请资源。
因此在任意时刻，系统中总存在一个进程，它占有已申请资源中编号最高的资源，且它继续申请的资源必定是空闲的，因而它可以一直向前推进直到完成。
当该进程完成后，即释放它所占有的全部资源，这样剩余的进程集合中又会存在一个进程，它占有已申请资源中编号最高的资源，且它继续请求的资源必定是空闲的，因而它也可以一直推进直到完成任务。
以此类推，最终所有进程均可以运行完成，故不会发生死锁。
死锁避免：
死锁避免算法动态检查资源分配以确保不会出现循环等待的情况。
资源分配状态由可用资源，已分配资源和进程所需的最大资源数量定义。
死锁的避免是在动态分配的过程中，用于某种方法防止系统进入不安全状态，从而避免死锁的发生。
特点是：以较弱的限制获得较高的利用率，但实现由一定的难度。
我们看一下什么是安全状态：
如果每个进程Pi所申请的资源数可以由当前可用资源数加上其他所有进程Pj(j<i)所持有的该资源数的和来满足，则进程序列<P1, P2, …, Pn>是安全的。
在避免死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。
安全状态是指系统能按某种顺序如< P1、P2… 、Pn>来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利完成，则称此时的系统状态为安全状态，称序列< P1、P2、…、Pn >为安全序列。
若不存在一个安全序列，则称系统状态为不安全状态。
安全状态不是死锁状态，死锁状态是不安全状态。
关系图大致如下：
我们看一个安全状态的例子:
这是安全状态：
P1需要2个资源，现在空闲的资源有3个，P1可以申请得到，然后执行完P1之后释放资源，空闲资源现在有5个，P0申请可以获得资源，然后P0执行，执行完之后释放资源，则目前资源数量是10，p2申请可以获得所需的资源，然后P2执行。
明显<P1,P0,P2>满足安全条件。
最具代表性的死锁避免算法是DIjkstra的银行家算法。
每一个进程必须事先声明资源的最大使用量。
当用户申请一组资源时，系统必须确定这些资源的分配是否会使系统处于安全状态，如果是就可以分配资源，否则等待。
下一节讲银行家算法，今天先到此为止，陪天佑去吃烧烤。
