死锁避免

动机

  • 在大多数系统中，一次请求一个资源。 希望系统可以决定授予资源是否安全
  • 有没有一种算法可以做出正确的决定？
    • 我们可以避免死锁，但前提是可以提前获得某些信息

Resource Trajectories 资源轨迹图

  • 进入I1、I2、I5、I6包围的矩形时，系统一定会向着造成死锁的矩形区域移动，从而造成死锁

Safe and Unsafe States 安全状态和不安全状态

安全状态

定义

  • 如果存在某种调度顺序，即使所有进程突然请求最大数量的资源，每个进程都可以运行完成，（没有死锁发生），则状态是安全的

a可以通过资源分配逐步完成所有进程，说明他是安全的

b是不安全的，他不可以完成A和C

安全状态和不安全状态的区别

  • 从安全状态，系统可以保证所有进程都将完成；
  • 但是从不安全的状态，就不能给出这样的保证。

单个资源的银行家问题

  • 银行家：操作系统

  • 客户：进程

  • 贷款项目：资源

银行家向一群客户分别承诺了一定的贷款项目

判断对请求的满足是否会导致进入不安全状态

  • 如果是，就拒绝
  • 如果不是，则分配

a、b是安全的，b可以将空闲资源分配给C，从而获取其他进程所需要的资源

c是不安全的，此时没办法满足任何一个进程

多个资源的银行家系统

总结

银行家算法就是对每一个请求进行检查，检查满足后是否会进入不安全状态。

Starvation

定义：一个进程永远被剥夺必要的资源来处理它的工作

即永远执行不了

Starvation vs Deadlock

  • Starvation：线程无限期等待
    • 可能结束，但没有外部干预，僵局无法结束
  • Deadlock：循环等待资源。
    • 是Starvation，反之不成立
    • 死锁并不总是确定性的

Deadlock Detection, Deadlock Avoidance, and Deadlock Prevention的比较

  • Deadlock Detection: 确定是否有死锁

  • Deadlock Avoidance: 确定系统是否会进入不安全状态

  • Deadlock Prevention:确保至少一个死锁的必要条件永远不能成立

Deadlock Prevention 死锁预防

确保至少一个死锁的必要条件永远不能成立

破坏互斥条件 Attacking the Mutual Exclusion Condition

如果资源不被一个进程所独占，那么死锁肯定不会产生。

破坏占有并等待条件 Attacking the Hold and Wait Condition
  • 要求进程在启动前请求所需要的所有资源
    • 问题：很难在运行开始知道需要多少资源
破坏不可抢占条件 Attacking the No Preemption Condition
  • 如果一个进程持有一些资源并请求另一个无法分配给它的资源，那么所有资源都会被释放。
    • 问题：该方法可以应用于状态可以在以后保存和恢复的资源，例如内存。 不能应用于打印机等资源
破坏环路等待条件 Attacking the Circular Wait Condition

方法一：一个进程在任何时候都只能使用一个资源。

方法二：强加所有资源类型的总排序，并要求每个进程以枚举递增的顺序请求资源。

其他问题

两阶段加锁 two-phase locking

第一阶段：

  • 进程试图对所有所需的记录进行加锁，一次锁一个记录
    • 如果发现需要的记录被锁了，重新启动
  • 加锁成功则开始第二阶段

第二阶段：

  • 完成更新
  • 释放锁
非资源死锁 Non-resource Deadlocks

  • Communication Deadlock

  • 可能在信号量中发生

问题

（1）D asks for one more unit：safe state

（2）C asks for one more unit：unsafe state

  • 安全状态一定不会发生死锁
  • 不安全状态可能是资源数不够满足所有进程造成的，不一定是死锁这种状态
  • 死锁一定是不安全状态

  • 死锁检测是看当前拥有的资源和请求的资源
  • 死锁避免是看当前拥有的资源和进程所需要的最多资源

a = 1， b = 2

p*(m - 1) < r

​