进程死锁与银行家算法

介绍

上篇中,看到在单个进程中，多个线程中可能会形成死锁，并用jstack检测出来了。那是怎么进行检测的呢？
产生死锁也就意味着先生之间的等待关系出现了闭合环路，发生死锁。我们可以将等待关系想象成一个单项链表。那么也就将问题转化为判断这个链表中是否出现环路。

当然这里中间个线程中的等待关系。

在操作系统中，也存在类的情况。只是抽象层次更高。并发进程，等待锁，变为等待资源。

死锁的概念

在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而，多个进程的并发执行也带来了新的问题——死锁。所谓死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。

死锁预防

预防死锁只需要破坏四个必要条件之一即可。

• 破坏互斥资源。破坏互斥条件不现实，有的时候甚至需要保护资源的互斥性。
• 破坏不剥夺条件。实现复杂；被剥夺的进程可能丢失工作；反复申请导致系统开销变大。通常用于状态容易保护和恢复的资源，如CPU的寄存器和内存，一般不用于打印机等资源。
• 破坏请求和保持条件。运行前一次性申请所有需要的资源，不够则不运行。实现简单，但是非常容易浪费资源，还会导致饥饿。
• 破坏循环等待条件。采用顺序资源分配法。

死锁的解除

• 资源剥夺法
• 撤销进程法
• 进程回退法

银行家算法

数据结构描述

• 可利用资源矢量Available
• 最大需求矩阵Max
• 分配矩阵Allocation
• 需求矩阵Need：

银行家算法模块

1. 如果Request<=Need,则转向2;否则,出错
   2．如果Request<=Available,则转向3,否则等待
   3．系统试探分配请求的资源给进程
   4．系统执行安全性算法

安全性算法模块

1. 设置两个向量,工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目) ,Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False
2. 若Finish[i]=False&&Need<=Work,则执行3;否则执行4(i为资源类别)
3. 进程P获得第i类资源,则顺利执行直至完成，并释放资源: Work=Work+Allocation; Finish[i]=true;转2
   4.若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!

参考

• 经典同步问题、死锁、银行家算法
• 死锁
• 银行家算法，死锁检测算法实践
• 银行家算法
• 【操作系统】处理死锁的方法