操作系统笔记7

死锁

死锁的定义：当两个及两个以上的进程因为竞争资源而互为等待导致系统无法推进，所处的状态称为死锁。

死锁产生的原因

  1. 资源不足
  2. 进程推进的顺序不合理

死锁产生的必要条件

以下条件缺一个必不会死锁

  1. 对资源的使用是互斥的而非共享的
  2. 占有并等待
  3. 不可抢占
  4. 环路等待（无环一定没有死锁，有环不一定有死锁，死锁必定有环）

处理死锁的方法

  1. 构建无死锁系统
  2. 允许进入死锁，但加以恢复
  3. 假设系统不存在死锁

资源分配图

死锁的处理——构建无死锁系统

破坏死锁的必要条件之一

  1. 破坏占有并等待
    • 采用一次性资源分配
    • 缺点：资源浪费严重，道数降低进而导致吞吐量降低
  2. 破坏环路等待
    • 采用有序资源使用法：对资源按类型编号，所有进程都要按递增顺序申请资源
    • 缺点：浪费
  3. 互斥和非抢占：不宜破坏

死锁的处理——死锁避免

资源分配时进行银行家算法，确保不会构成环。

银行家算法：当银行进行一次分配后，无法满足所有客户的需求时，即不存在安全序列时，银行不会进行此次分配。

死锁的处理——死锁检测

允许系统进入死锁，利用死锁检测算法检测是否进入死锁，并加以恢复

死锁恢复

  1. 终止进程：
    • 终止所有死锁的进程：代价太大
    • 终止一个进程，直到无死锁为止：开销太大
  2. 资源抢占：
    • 选择一个代价最小的进程，将其回退
    • 需要处理三个问题：1.牺牲品？2.回滚到什么地步才是安全状态？3.饥饿问题？