【王道考研】死锁

【王道考研】死锁

2.4 死锁

知识来源： B站王道考研

死锁的概念

什么是死锁

知识回顾：哲学家进餐问题就是一个死锁。

死锁： 各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
饥饿： 由于长时间得不到想要的资源，某进程无法向前推进的现象。比如：短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生进程“饥饿”。

死锁产生的必要条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。
不剥夺条件： 进程所获得的资源在未使用完只看，不能由其他进程强行夺走，只能主动释放。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被下一个进程所请求。

注意：发生死锁一定有循环等待，但是发生循环等待不一定死锁。

什么时候会发生死锁

1. 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的。
2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。A申请R1资源，再申请R2资源；B申请R2资源，再申请R1资源。就有可能造成死锁。
3. 信号量的使用不当也会照成死锁。如生产者-消费者问题中的，如果实现互斥的P操作再实现同步的P操作之前，就可能导致死锁（自己用笔画画，分析一下）

预防死锁

破坏互斥条件

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

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如SPOOLing技术，操作系统可以采用SPOOLing技术把独占设备的罗吉吉上改造为共享设备。

该策略的缺点：并不是所有的资源都可以改造程可共享使用的资源，并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

破坏不剥夺条件

不剥夺条件： 进程所获得的资源在未使用完只看，不能由其他进程强行夺走，只能主动释放。


破坏不剥夺条件：
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时，再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。


方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）


该策略的缺点：

1. 实现起来比较复杂。
2. 四方已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保持和恢复状态的资源，如CPU。
3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这种情况，就会导致进程饥饿。

破坏循环等待条件

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

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

原理分析：一个进程只有已占有小编号的资源时，才有资源申请更大编号的资源。按此规则，已有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会循环等待的现象。

该策略的缺点：

1. 不方便增加新的设备，因为可能需要重新分配所有的编号。
2. 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源消费。
3. 必须按规定次序申请资源，用户编程麻烦。

避免死锁

什么时安全序列

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


如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，系统未必发生死锁。但发生死锁移动是在不安全状态。
因此可以在资源分配之前预先判断这次分配是否导致系统进入不安全状态，以此决定是否答应资源分配请求，“银行家算法”的核心思想。

银行家算法

用于避免死锁。


核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

系统中有5个进程P0 - P4，3种资源R0 - R2，初始数量为(10,5,7),则某一时刻的情况可表示如下：

此时总共已分配(7,2,5)，还剩余(3,3,2)可把最大需求、已分配的数据看作矩阵，两矩阵相减，就可算出各进程最多还需要多少资源了。

资源总数(10,5,7)，剩余可用资源(7,4,3)

进程	最大需求	已分配	最多还需要
P0	(7,5,3)	(0,1,0)	(7,4,3)
P1	(3,2,2)	(2,0,0)	(1,2,2)
P2	(9,0,2)	(3,0,2)	(6,0,0)
P3	(2,2,2)	(2,1,1)	(0,1,1)
P4	(4,3,3)	(0,0,2)	(4,3,1)

P0最多还需要 > (3,3,2)
P1最多还需要 <= (3,3,2).可分配，执行结束，获取已分配资源(2,0,0) + (3,3,2) = (5,3,2)

P0最多还需要 > (5,3,2)
P2最大还需要 > (5,3,2)
P3最大还需要 (2,1,1)<= (5,3,2) 可分配，执行结束，获取已分配资源 (2,1,1) + (5,3,2) = (7,4,3)

之后所有都为安全序列

思路：尝试找到一个安全序列… {P1,P3,P0,P2,P4}

以上可转为代码实现思路：
**剩余资源 = Available **

进程	最大需求(Max)	已分配(Allocation)	最多还需要(Need)
P0	(7,5,3)	(0,1,0)	(7,4,3)
P1	(3,2,2)	(2,0,0)	(1,2,2)
P2	(9,0,2)	(3,0,2)	(6,0,0)
P3	(2,2,2)	(2,1,1)	(0,1,1)
P4	(4,3,3)	(0,0,2)	(4,3,1)

每个进程发出请求为Request矩阵

可用银行家算法预判本次分配是否会导致系统进入不安全状态：
①. 如果Request[j] <= Need[i,j] (0 <= j <= m)便转向②；否则认为出错。
②.如果Request[j] <= Available[j] (0 <= j <= m)便转向③；否则表示尚无足够资源，Pi必须等待。
③.系统试探着把资源分配给进程Pi，并修改相应的数据（并非真的分配，修改数值只是为了做预判）.
④.操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配；否则，恢复相同数据，让进程阻塞等待。

检测和解除

死锁的检测

用于检测系统状态，以确定系统中是否发生了死锁。
①用某种数据结构来保存资源的请求和分配信息；
②提供一种算法，利用上述信息来检测系统是否已进入死锁状态。


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


如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）


如果最终不能消除所有边，那么此时就是发生了死锁
死锁定量：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁的解除

当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

1. 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2. 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，可能导致已经运行很长时间的进程，直接结束。
3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。