封面《絆きらめく恋いろは》

死锁的概念

死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进

死锁产生的原因

  • 系统资源不足
  • 程序执行的顺序有问题
  • 资源分配不当等

死锁产生的必要条件

产生死锁必须满足四个必要条件,任意一个条件不成立,死锁就不会发生。

互斥条件

在某一段时间内,资源仅被一个进程占有。若有其他进程请求该资源,则请求进程只能等待。

不剥夺条件

进程所获得的资源在未使用完之前,不能被其他进程强行夺走,只能由获得该资源的进程自己来释放。

请求并保持条件

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

循环等待条件

存在一种进程资源的循环等待链,链中每个进程已获得的资源同时被链中下一个进程所请求。

处理死锁

死锁预防

破坏死锁的4个必要条件

破坏互斥条件

有些资源必须互斥使用,因此无法破坏互斥条件。

破坏不剥夺条件

当进程请求新资源得不到满足时,必须释放已经持有的资源,重新申请。这个策略实现起来比较复杂,反复的申请和释放会导致系统开销增加,降低系统吞吐量。这种方式适用于容易保存和恢复的资源,例如CPU的寄存器和内存资源,一般不能用于打印机之类的资源。

破坏请求与保持条件

采用预先静态分配方法,进程在运行之前申请完它所需的所有资源,在使用过程中,这些资源一直归它所有。

容易发生两个问题:1.导致部分进程饥饿现象,永远申请不满资源。2.导致资源浪费,有些资源只在运行初期或者结束时候使用。

破坏循环等待条件

为了破坏循环等待条件,可以采用顺序资源分配法。给资源编号,进程按照编号递增的顺序请求资源。

容易造成资源使用的浪费和用户编程的麻烦。

死锁避免

在使用前进行判断,只允许不会产生死锁的进程申请资源
死锁避免是利用额外的检验信息,在分配资源时判断是否会出现死锁,只在不会出现死锁的情况下才分配资源
各种死锁防止方法能够防止发生死锁,但必然会降低系统并发性,导致低效的资源利用率

安全状态

安全状态

图 a 的第二列 Has 表示已拥有的资源数,第三列 Max 表示总共需要的资源数,Free 表示还有可以使用的资源数。从图 a 开始出发,先让 B 拥有所需的所有资源(图 b),运行结束后释放 B,此时 Free 变为 5(图 c);接着以同样的方式运行 C 和 A,使得所有进程都能成功运行,因此可以称图 a 所示的状态时安全的。

定义:如果没有死锁发生,并且即使所有进程突然请求对资源的最大需求,也仍然存在某种调度次序能够使得每一个进程运行完毕,则称该状态是安全的。

银行家算法

银行家算法的主要思想是避免死锁进入不安全状态。每次进行资源分配时,它先检查系统是否有足够的资源满足要求,若有则先进行分配,并对分配后的新状态进行安全性检查。若新状态安全,则正是分配上述资源,否则拒绝分配上述资源。然后回收已分配的资源,进行下一轮分配。这样能保证资源始终处于安全状态,从而避免死锁发生。


上图c为不安全状态,因此算法会拒绝进入图c请求

死锁检测与恢复

死锁检测

资源分配图

资源分配图

  • 圆圈代表进程
  • 方框代表一类资源
  • 进程到资源的有向边代表请求资源边
  • 资源到进程的有向边代表资源分配边
    如图所示,P1进程分得两个R1资源,又请求一个R2资源;P2进程分得一个R1资源和R2资源,又请求了一个R1资源。

简化资源分配图

简化资源分配图步骤

  1. 找一个非孤立、且只有分配边的进程节点,去掉分配边,将其变为孤立节点
  2. 再把相应的资源分配给一个等待该资源的进程,即将该进程的申请边变为分配边
  3. 重复1、2

化简

  • (1)到(2): R2剩余1个资源,分配给P1,释放P1
  • (2)到(3): R1剩余2个资源,分配给P2,释放P2

若能消去所有的边,则该图是可完全简化的,死锁的条件是当且仅当S状态的资源分配图是不可完全简化的

死锁恢复

  • 资源剥夺法。挂起某些死锁进程并抢夺它的资源,直到死锁接触。但要防止被挂起的进程长时间得不到资源而饥饿。
  • 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些资源。
  • 进程回退法。让一个或多个进程回退到足以回避死锁的地步。要求保持进程的历史信息,设置还原点。

参考

什么是死锁(deadlock)

死锁产生的原因及四个必要条件

死锁的四个必要条件、预防和避免办法

​死锁的产生、防止、避免、检测和解除