进程死锁与银行家算法

介绍

上篇中,看到在单个进程中,多个线程中可能会形成死锁,并用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,则表示系统安全;否则,不安全!

参考