定义

多个进程争夺资源造成的僵局情况，若不外力作业，则无法想前推进。

死锁的四个条件

1）互斥：争夺资源的时候，某个资源在同一时间只能有一个进程得到。
2）不抢占：资源是不可抢占的，如果可以抢占则不会进入互相等待的情况。
3）拥有且再请求：一个进程无法一次性获取全部的资源，则会在持有已有资源的情况下，再去请求另外的资源
4）互相等待：A请求B，B请求C，C请求A，形成了一个环状的等待关系。

死锁的处理

死锁的预防

破坏4个条件中的一个条件。
缺点：比较保守，无法高效的处理任务

破坏互斥条件
如果允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。
破坏不剥夺条件
当一个已保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺了，或从而破坏了不可剥夺条件。
该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。
破坏请求和保持条件
釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。
这种方式实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，当由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。
破坏循环等待条件
为了破坏循环等待条件，可釆用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于Ri的资源。

死锁的避免

银行家算法：如果能找到一个顺序，使进程能被分配资源，则系统不会出现死锁。
①如果Requesti[j] <= Need[i, j]，便转向步骤②；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

②如果Requesti[j] <= Available[j]，便转向步骤③;否则，表示尚无足够资源，Pi须等待。

③系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j] = Available[j] - Requesti[j];
Allocation[i, j] = Allocation[i, j] + Requesti[ j];
Need[i, j] = Need[i, j] - Requesti[j];

④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

缺点：需要预先知道其他进程要求的资源

操作系统——死锁
某时刻的资源占有图。
现有资源是 3 3 2，顺序比较p1是最先分配到资源的，分配后回收之前分配的资源
就是 3 3 2 + 2 0 0 = 5 3 2
按这样的算法，则可以得出资源被分配的顺序 1 3 4 2 0

死锁的检查

缺点：通过剥夺接触死锁，会造成损失

资源分配图

操作系统——死锁
所示的资源分配图中，进程P1已经分得了两个R1资源，并又请求一个R2 资源；进程P2分得了一个R1和一个R2资源，并又请求一个R1资源。

在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。
进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在图2-17中，进程P2就满足这样的条件。根据第1) 条中的方法进行一系列简化后,若能消去图中所有的边，则称该图是可完全简化的。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的,该条件为死锁定理。

死锁的解除

一旦检测出死锁，就应立即釆取相应的措施，以解除死锁。死锁解除的主要方法有：

资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

操作系统——死锁

死锁

定义