20-死锁

死锁的基本概念

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里资源，导致各个进程都阻塞，无法向前推进的现象，称为“死锁”。发生死锁后若无外力的干涉，这些进程都将无法向前推进

要注意的是，死锁，饥饿和死循环是三个比较容易混淆的概念

• 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。例如：在短进程优先算法（SPF）中，若有源源不断的短进程到来，则长进程一直得不到处理机，从而发生长进程“饥饿”
• 死循环：某进程执行过程中一直跳不出某个循环的现象，有时是因为程序逻辑bug导致，有时也可能是程序故意设计

综上，可以总结三者的异同点：

死锁的必要条件

产生死锁必须同时满足以下的四个条件，任意条件不成立，死锁都不会发生

• 互斥条件：只有对必须互斥使用的资源进行争抢才会导致死锁。例如哲学家就餐问题，打印机设备等。像内存，扬声器这种可以同时被多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）
• 不剥夺条件：进程获得的资源，在未使用完之前，不能被其他进程强行夺走，只能主动释放
• 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
• 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

发生死锁一定又循环等待，但发生循环等待不一定有死锁

发生死锁的时机

• 对系统资源的竞争：各个进程对不可剥夺资源的竞争（例如打印机）可能引起死锁，对可剥夺资源（CPU）的竞争不会引起死锁
• 进程推进顺序非法：请求和释放资源的顺序不当，同样会导致死锁。例如：并发执行的进程P1，P2分别申请并占有了资源R1，R2，之后进程P1又紧接着申请资源R2，P2申请资源R1，就会导致死锁
• 信号量的使用不当：例如在生产者与消费者问题中，如果实现互斥操作的P操作在实现同步操作的P操作之前，就可能导致死锁（这里可以把互斥信号量和同步信号量也堪称一种抽象的系统资源）

总之，对不可剥夺资源的不合理分配，可能导致死锁

死锁的处理策略–不允许死锁发生

1. 预防死锁：破坏死锁产生必要条件中的一个或几个
2. 避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）

死锁的处理策略–允许死锁发生

1. 死锁的检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁

静态策略：预防死锁

破坏死锁产生必要条件中的一个或几个

破坏互斥条件

• 互斥条件：只有对必须互斥使用的资源进行争抢才会导致死锁。

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。例如SPOOLing技术，操作系统可以使用SPOOLing技术把独占设备在逻辑上改造成共享设备，比如用SPOOLing技术将打印机改造为共享设备

该策略的缺点：并不是所有资源都可以改造成可共享使用的资源。并且处于系统安全角度考虑，很多地方必须保护这种互斥性，所以破坏互斥条件的应用范围不广

破坏不可剥夺条件

• 不剥夺条件：进程获得的资源，在未使用完之前，不能被其他进程强行夺走，只能主动释放

1. 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时重新申请，也就是说，即使资源尚未使用完，也需要主动释放，从而破坏不可剥夺条件
2. 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑进程之间的优先级（优先级高的进程可以剥夺低优先级进程的资源）

该策略的缺点：

• 实现起来比较复杂
• 释放已获得的资源可能造成前一阶段工作的失效。因此这种方式一般只适用于易保存和恢复状态的资源，例如CPU
• 反复申请和释放资源会增加系统开销，降低系统吞吐量
• 若采用方案一，意味着只要暂时得不到资源，之前的资源需要全部放弃，后面重新申请，如果该现象一直发生，会导致饥饿

破坏请求和保持条件

• 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放

可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行，一旦投入运行，这些资源就一直归他所有，该进程不会请求别的任何资源

该策略缺点：有些资源可能只需要使用很短的时间，因此如果进程的整个运行期间都保持所有资源，就会造成部分资源的严重浪费，资源利用率低。另外策略也可能导致某些进程饥饿

例如上图中A类进程与B类进程分别需要使用资源1和资源2就可以运行，而C类进程需要同时等待两种资源全部空闲才可执行，此时若A类B类进程交替不断到来，则C类进程会由于没有全部资源陷入饥饿

破坏循环等待条件

• 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

可采用顺序资源分配法。首先给系统中的资源编号，并且规定每个进程必须按照编号递增的顺序请求资源，同类资源（编号相同的资源）一次申请完

原理分析：一个进程已占有小编号资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程无法逆向申请小编号的资源，从而打破循环等待

该策略的缺点

1. 不方便新增设备，因为可能需要重新分配所有的编号
2. 进程时机使用资源的顺序和编号递增顺序不一致，会导致资源浪费。例如某进程需要申请5号打印机资源和7号扫描仪资源，使用顺序是先使用扫描仪后使用打印机，但由于5号打印机编号较小，所以必须提前申请该资源并一直占用，知道申请并使用完7号扫描仪后，才能使用并释放，导致5号打印机被浪费
3. 必须按规定次序申请资源，用户编程麻烦

动态策略：避免死锁

基本概念-安全序列

银行家算法:在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

不合理请求

合理请求

根据上面的两个示例我们可以看到，在给B借30亿的情况下，如果B，A，T同时提出20亿借贷的请求，则我们所有企业都无法满足，此时系统陷入死锁状态，而与之相对的，在给A借20亿的情况下，我们有T->B->A这样的能够保证系统安全的系列存在

上面给出的T->B->A序列，就是一个安全序列，所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

银行家算法核心思想

在进程提出资源申请时，预先判断此次分配是否会导致系统进入不安全状态(不存在安全序列)，如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待

但是上面的例子中，只涉及一种资源的分配（钱），而在计算机这种可能涉及多种资源分配的环境下，就需要通过高维向量来解决上述问题：例如系统中有五个进程P0-P4，三种资源R0-R2，初始数量为(10,5,7)则某一时刻的情况可以表示如下

此时系统剩余可用资源(3,3,2)要判断系统是否处于安全状态，思路就是尝试找到一条安全序列，而方法就是自上而下依次检查剩余可用资源(3,3,2)是否能满足各进程需求

检查过程：

1. 首先P0最多需要资源(7,4,3)>剩余资源(3,3,2)，所以P0暂时无法进入安全序列
2. 接下来P1(1,2,2)<(3,3,2)所以P1可以进入安全序列
3. P1进入安全序列分配资源并等待P1归还所有已分配资源
4. P1归还所有已分配资源，所以系统剩余资源(2,0,0) (3,3,2)=(5,3,2)
5. 继续向下执行P2(6,0,0)>(5,3,2)，所以P2暂时不能进入安全序列
6. P3(0,1,1)<(5,3,2)所以P3进入安全序列，分配资源，并等待P3归还所有已分配资源
7. P3归还资源，系统剩余资源(2,1,1) (5,3,2)=(7,4,3)
8. 继续向下执行P4(4,3,1)<(7,4,3)，P4进入安全序列，分配资源，并归还
9. P4归还资源，系统剩余资源(0,0,2) (7,4,3)=(7,4,5)
10. 不断执行，此时所有进程都可进入安全序列
11. 最终得到安全序列P1->P3->P4->P0->P2(安全序列不唯一)

成功找到一条安全序列表明系统处于安全状态，不可能发生死锁

银行家算法实现思路

死锁的检测和解除

死锁的检测

为了能对系统是否已经发生了死锁进行检测，我们需要：

1. 用某种数据结构来保存资源的请求和分配信息
2. 提供一种算法，利用上述信息来检测系统是否已经进入死锁状态

能够用来保存资源的请求与分配信息的结构就是资源分配图，资源分配图具有如下特点：

• 具有两种节点
  • 进程节点：对应一个进程
  • 资源节点：对应一类资源，一类资源可能有多个
• 具有两种边
  • 请求边：从进程节点指向资源节点，表示进程想申请几个资源（一条边表示想要申请一个）
  • 分配边：从资源节点指向进程节点，表示已经为该进程分配了几个资源（一条边表示已分配一个资源）

介绍了一种保存资源和请求分配信息的数据结构后，我们就应该考虑如何利用算法，检测整个过程中系统是否发生死锁。

以上面这张资源分配图为例，P1进程请求一个R2资源，此时R2资源一共两个，其中一个被分配给P2进程，所以剩余资源足够分配给P1进程，此时P1进程不需要额外资源，可以正常执行。待执行结束后归还一个R2资源和两个R1资源，此时P2请求一个额外的R1资源，R1资源一共三个，其中一个已经分配给P2进程，剩余两个空闲，所以能够分配一个额外的R1资源给P2，P2进程也可顺利执行，则该情况下未发生死锁

相对的，如果资源分配图变成这种情况，则P1进程请求两个R2资源，但空闲R2资源为0，P1被阻塞，P2进程请求一个R1资源，空闲R1资源为0，P2被阻塞，P3进程不请求额外资源，只有P3进程可以正常执行，执行后归还一个R2资源，但此时P1进程仍无法执行，P2进程也无法请求到额外资源，系统进入死锁状态

所以说，如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源,这样可能又会激活另外一些阻塞的进程…

如果按照上述的过程分析最终能够消除所有边，则称该图是“可完全简化的”，此时一定没有死锁，如果最终不能消除所有边，则此时就发生了死锁，最终还连这边的进程就是处于死锁状态的进程

综上，检测死锁的算法就可以描述为：

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

死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁。

注意:并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程

解除死锁的主要方法有:

1. 资源剥夺法。挂起（暂时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2. 撤销进程法（或称终止进程法)。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，己经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息,设置还原点。

如何绝对挂起或剥夺哪些进程

1. 考虑进程的优先级，对优先级低的进程进行剥夺
2. 考虑已执行的时间，避免剥夺已经长时间运行的进程，造成损失
3. 考虑进程完成时间，优先为可快速完成的进程分配资源
4. 考虑进程已经使用了多少资源
5. 考虑进程是交互式的还是批处理式的，避免交互式进程被剥夺影响用户体验