夺命剪刀脚（死锁）

产生死锁的原因和必要条件

死锁的定义

有多个进程竞争共享资源而引起进程不能向前推进的僵死状态称为死锁。

产生死锁的原因

竞争共享资源且分配资源的顺序不当。

产生死锁的必要条件

互斥条件

指一个进程在访问资源过程中，其他进程不能访问该资源。

请求和保持条件

进程已经保持至少一个资源，又提出来新的资源要求，而新的请求的资源已经被其他进程占有，此时进程阻塞，但又对已经获取的资源保持不放，是其他进程无法使用被保持的资源。

不剥夺条件

进程已获取的资源不能被剥夺，只能由进程自己释放。

环路等待条件

在发生死锁时，必然存在一个进程申请资源的换形链。

处理死锁的基本方法

预防死锁

死锁的预防是根据前面讨论的死锁的必要条件，通过保证至少其中一个条件不成立来达到预防死锁的目的。在操作系统中无法预知进程是否一定不访问临界资源，所以通常不能采用摒弃互斥访问的条件来预防死锁的发生。

摒弃请求和保持条件

方法是系统要求所有进程执行前要一次性地申请运行过程中所需要的全部资源，只要有一个资源申请不成功，其他所有资源也不能分配给该进程，并阻塞该进程。对某些进程在申请其他资源前要求该进程必须释放已经分配它的所有其他资源。

摒弃不剥夺条件

一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足的时候，必须释放它已经保持的所有资源。

摒弃环路等待条件

进程必须按照规定数学申请资源，对所有不同类型的资源排序，要求每一进程按照规定的顺序申请资源。

避免死锁

把系统资源分配状态分为安全状态和不安全状态，只要资源分配使系统资源分配状态处于安全状态，死锁就不会发生。

系统的安全状态

当系统能找到一个执行序列，使系统只要按照此序列为每一个进程分配资源，就可以保证进程的资源分配和执行顺利完成，不会发生死锁时，称系统处于安全状态。若系统不存在这样的序列，则称系统处于不安全状态。

举例说明（后期将于银行家算法合并整理）

安全状态假定系统有 3 个进程 P1，P2，P3 ，共有 12 个资源 R，进程 P1 总共需要 10 个 R 资源，P2 和 P3 分别是 4 和 9 个 R 资源。

银行家算法（后期专门整理）

1965 年 Dijkstra 提出了一种能够避免死锁的资源分配算法。基本思想是一个进程提出申请资源后，系统要进行资源的试分配。然后检测本次的试分配是否使系统处于安全状态，若安全则按照试分配方案分配资源，否则不分配资源。

死锁的检测和解除

操作系统可以不采用事先预防和避免的方式来解决死锁的问题，而是检测是否有死锁发生。如果检测到系统中有死锁的进程，则解除死锁。

何时调用检测算法

取决于两个因素一是死锁可能发生的濒临。二是当死锁发生时受到影响进程的数量。

资源分配图

系统死锁可以利用资源分配图来描述，该图有一组结点和一组边组成。

P1 和 P2 代表进程，R1，R2 方块中的小圆代表一类资源。请求边有进程指向资源。分配边则始于一类资源。如上图，P1 获取到 R1 的 2 个资源和正在请求 R2 的 1 个资源。P2 获取到 R2 的 1 个资源，R1 的一个资源和正在请求 R1 的一个资源。

死锁定理

死锁定理用于检测系统所处的资源分配状态 S 是否为死锁状态。

死锁定理：S 为死锁状态的充分条件是当仅当 S 状态的资源分配图是不可简化的。

利用资源分配中的例子展现一下简化过程。

找出一个即不阻塞又非独立点的进程节点 P1，在顺利的情况下，P1 获取所有需要的资源而继续执行，直到运行完成，并释放其所占有的全部资源。（这相当于消除 P1 的全部请求边和全部分配边）

经过一系列的简化后，若能消除图中的边，使 P1 和 P2 称为孤立的点，则说明该图可以完全简化。若不能通过任何简化过程使该图简化，则称该图不可完全简化。

死锁的解除

检测到系统出现死锁后，可以有系统管理员人工处理死锁，也可以让系统自动解除死锁。

途径

进程终止

终止死锁进程后，系统回收进程所占用的资源。

终止所有死锁进程。

一次只终止一个处于死锁的进程。直到死锁解除。

需要考虑问题

1.进程的优先级？

2.进程已经执行了多久？进程在完成指定任务之前还需要多长时间？

3.进程使用了多少资源？分别是什么类型的资源？这些资源是否容易被抢占？

4.进程需要多少资源才能完成？

5.需要终止多少进程才能解除死锁？

6.进程是交换还是批处理？

资源抢占

逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止。

需要考虑的问题

抢占那些进程和那些资源？必须确定抢占的顺序以使代价最小。

影响因素有：死锁进程所拥有的资源数量。死锁进程到目前为止消耗的执行时间等。

回滚：如果从一个进程那里抢占一个资源，那么该进程因缺少资源不能从抢占点正常执行，必须将进程回滚到某个安全状态，以便于从该状态重启进程。最简单的方式是完全回滚，就是终止进程并重启进程。

饥饿：饥饿是进程因长时间不能获取所需要的资源而无限等待的状态。

欢迎大家的留言讨论。按惯例最后分享一首诗给大家。

啊！

啊！啊！

！