死锁

阅读数: 次 2021-07-10

死锁的引入

死锁处理是多进程图像产生的问题 -> 多个进程在内存中同时出发交替执行的时候，如果控制不好就会出现互相死锁的情况。这种死锁就需要操作系统作出一定的处理，否则就会引发一些问题！

再看一下生产者-消费者的信号量解法…

生产者和消费者因为信号量的问题就会造成死锁，下面我们分析一下死锁产生的原因

如下图所示，生产者上来以后本应该是先申请 empty -> 空闲缓冲区信号量，再申请 mutex -> 互斥信号量。现在我们让生产者申请信号量的顺序反过来-> 即先申请 mutex 再申请 empty，消费者也跟着改变；(为什么会反过来 -> 生产者和消费者的代码是用户写的，用户很完全可能给反过来，用户以为这样没什么，反正我就想申请两个信号量，两个都满足了我就进去了呗，但是这样会有本质的区别) 这样就造成了一些问题…

首先生产者进来，先申请mutex 将 mutex 从1变为0，表示已经有进程进入不再允许其他进程互斥进入，然后申请 empty, 假设此时的空闲缓冲区为 0-> 资源已经满了，不需要生产，那么此时将 empty 从 0 变为 -1，生产者阻塞，此时CPU调度到消费者执行，消费者一上来申请 mutex 发现 mutex 为 0-> 已经有进程进入，那么就将 mutex 从 0 变为 -1并开始阻塞。此时生产者、消费者都开始阻塞，生产者想要生产就依赖于消费者的 v(empty) ，而消费能执行到 v(empty) 的前提是它能下来执行，此时它还在上面等着呢，同时决定它能不能下来的条件是生产者的 v(mutex) -> 释放mutex ，而生产者能执行到 v(mutex) 的前提是它能够下来执行，可它刚上来就阻塞在上面了…. 所以信号量这样写完之后就引起了进程间互相等待的环路等待状态。

我们将这种多个进程由于互相等待对方持有的资源而造成的谁都无法执行的情况叫死锁

死锁造成的结果

一旦出现了死锁，当有新的的进程申请”闭环资源”时同样要被阻塞，而它所持有的资源同样会陷入到这种死锁的局面中，这样就造成了资源锁的越来越多，进程锁的越来越多。我们知道操作系统的核心是多进程图像，只有进程执行了，计算机才能向前工作，那很进程都不执行了，计算机就不工作了呗，用户的最直观感受就是计算机特别慢。本质并不是CPU变慢了，而是CPU没干正经活，进程都在哪阻塞呢，CPU是没有程序可执行。

死锁的成因

要想处理死锁，我们应该先分析下死锁的成因

死锁的4个必要条件

互斥使用 (Mutual exclusion) : 资源的固有特性，一次只能被一个进程使用，如：道路、打印机
不可抢占 (No preemption) : 资源只能自愿放弃
请求和保持 (Hold and wait) : 进程必须占有资源，再去申请
循环等待 (Circular wait) : 在资源分配图中存在一个环路，即出现环路等待

死锁的处理

死锁预防：破坏死锁出现的条件 –> “no smoking” ,预防火灾
死锁避免 ：检测每个资源请求，如果造成死锁就拒绝 –> 检测到煤气超标时，自动切断电源
死锁检测 + 恢复 ：检测到死锁出现，让一些进程回滚，让出资源 –> 发现火灾时，立刻拿起灭火器
死锁忽略 ：什么都不就好像没有出现死锁一样 -> 重启，重新来过

死锁预防

方法一：在进程执行前，一次性申请所有需要的资源，不会占有资源再去申请其他资源

缺点1：需要预知未来，编程困难
缺点2：许多资源分配后很长时间后才使用，资源利用率低

方法二：对资源类型进行排序，资源申请必须按序进行，不会出现环路等待

缺点1：仍然造成资源的浪费

死锁避免

如果系统中的所有进程存在一个可以完成的执行序列 P1,P2,…..Pn,则称系统处于安全状态

那么安全序列如何找呢？

如上图所示，表示当前系统中进程与资源的关系，拿进程P0为例，此时进程持有(Allocation)A B C 三种资源分别为 0 1 0 个，进程P0 想要执行还需要 (Need) 资源 A B C 各 7 4 3 个，而此时系统中还剩余(Available) A B C 三种资源各 2 3 0 个。现在我们分析一下是否有一条执行序列能够让这些进程都执行完。

首先系统剩余资源 2 3 0 ，可以将资源分配给进程 P1,P3 我们假设先分配给进程 P1, 那么此时P1获得资源开始执行，P1执行完毕后释放所持有的资源，那么此时系统中的剩余资源变为 5 3 2 (2+3, 3+0, 0+2) ，接着将资源分配给 P3 ，P3执行完毕释放资源，此时系统中剩余 7 4 3 ,这样往复判断分配执行，再释放收回，最后所有进程都会有序执行完毕，并且安全序列有< P1,P3,P2,P4,P0 >等

银行家算法

int Available[1...m] ;//每种资源剩余数量
int Allocation [ 1...n, 1...m] ;//己分配资源数量
int Need [ 1..n, 1..ml;//进程还需的各种资源数量
int Work [ 1..m] ;//工作向量
bool Finish  [ 1..n] ;//进程是否结束

Work=Available;Finish[1..n]=false;
while(true){
    for (i=1;i<=n; i++)
	{
		if(Finish[i]==false && Need [i] <= Work[i] )
		{
			Work=Work+Allocation[i];
			Finish[i]=true;  break; 
		}
		else
		{
			goto end;
		}
    }
}
End:
	for (i=1;i<=n; i++)
	  	if(Finish[i]==false)return "deadlock";

银行家算法是由Dijkstra 提出, 主要是寻找上面所提出的安全序列。T(n) = O(mn2) -> m 表示资源数量，n表示进程个数。

死锁避免之银行家算法实例：

银行家算法只是判断系统是否可以有安全序列，那么它是如何避免死锁的呢？

请求出现时，首先假装分配，然后调用银行家算法

如上图所示：假设进程 P0 申请资源 (0,2,0)，那我们就假装给其分配一下，那么此时系统中的进程与资源的关系就要更新，然后根据分配后的进程资源关系调用银行家算法，判断看看是否有一条安全序列。如果此时没有安全序列-> 表示如果给 P0分配资源，那么系统就会产生死锁，一个也别想执行了，所以就不该给 P0 分配资源，拒绝其申请。

方法固然很好，但是每次申请资源都要进行调用判断，时间复杂度太高，系统开销太大；

死锁检测 + 恢复

既然银行家算法时间复杂度太高，每次申请资源都要调用，系统开销太大，那我们能不能不每次申请时都调用啊！反正死锁出现的概率很低，那就当每次出现问题，感觉系统慢了，再进行检测呗！

定时检测或者发现资源利用率低时检测

Finish[1...n] = false;
if (Allocation[i] == 0) Finish[i] = true;
//和Banker 算法完全一致
for (i = 1; i <= n; i++) 
	if (Finish[i] == false)
	 	deadlock = deadlock + {i};

恢复

通过抢占进行恢复
在某些情况下，可能会临时将某个资源从它的持有者转移到另一个进程。比如在不通知原进程的情况下，将某个资源从进程中强制取走给其他进程使用，使用完后又送回。这种恢复方式一般比较困难而且有些简单粗暴，并不可取。

通过回滚进行恢复
如果系统设计者和机器操作员知道有可能发生死锁，那么就可以定期检查流程。进程的检测点意味着进程的状态可以被写入到文件以便后面进行恢复。检测点不仅包含存储映像(memory image)，还包含资源状态(resource state)。一种更有效的解决方式是不要覆盖原有的检测点，而是每出现一个检测点都要把它写入到文件中，这样当进程执行时，就会有一系列的检查点文件被累积起来。为了进行恢复，要从上一个较早的检查点上开始，这样所需要资源的进程会回滚到上一个时间点，在这个时间点上，死锁进程还没有获取所需要的资源，可以在此时对其进行资源分配。

杀死进程恢复
最简单有效的解决方案是直接杀死一个死锁进程。但是杀死一个进程可能照样行不通，这时候就需要杀死别的资源进行恢复。另外一种方式是选择一个环外的进程作为牺牲品来释放进程资源。

死锁忽略

许多通用操作系统，如PC 机上安装的 Windows 和 Linux,都采用死锁忽略的方法。

死锁忽略的处理代价最小
这种机器上出现死锁的概率比其他机器低
死锁可以用重启来解决，PC重启造成的影响小
死锁预防让编程变得困难

参考资料