《操作系统》课程笔记（Ch07-死锁） Ch07 - 死锁

有时，一个进程申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态，这种情况称为死锁。

死锁特征

必要条件

• 互斥

  至少有一个资源必须处于非共享模式

• 占有并等待

  一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程占有

• 非抢占

  资源不能被抢占，只能在任务完成后自愿释放

• 循环等待

  资源的等待关系成循环。即有一组等待进程，P0等待资源为P1占有，P1等待的为P2占有，…，Pn等待的为P0占有

资源分配图

P集合：所有活动进程的集合；R集合：所有资源类型的集合；申请边：Pi→Rj；分配边：Rj→Pi

如果分配图没有环，那么系统一定没有进程死锁；如果有环则可能存在进程死锁

死锁处理

整体上有三种思路：

• 预防或避免死锁，确保系统不会进入死锁状态
• 允许进入死锁状态，然后检测并恢复
• 忽视，认为死锁不可能发生

死锁预防（Prevent）

破坏死锁的4个必要条件中的一个。

互斥

很难破坏互斥条件。因为许多资源固有地就是非共享的。

占有并等待

保证进程申请一个资源时，没有占有其他资源。

• 两种方法
  • 每个进程在执行前申请所有资源
  • 进程仅在没有资源时才可申请资源，即在申请更多资源之前释放已分配的所有资源
• 两个问题
  • 资源利用率可能较低
  • 可能发生饥饿

无抢占

如果一个进程在申请一个不能立即分配的资源，那么它已分配到的资源都可被抢占（隐式释放）。只有当它分配到该资源并且恢复被抢占的资源后，才能重新执行。

适合于状态可保存和恢复资源（如寄存器、内存），不适合其他资源（如信号量、互斥锁）。

循环等待

对所有资源类型进行完全排序，要求每个进程按递增顺序来申请资源，申请多个同类资源时应一起申请。

死锁避免（Avoid）

每次分配前检测安全状态，安全则分配，不安全则暂缓分配。

安全状态

只有存在一个安全序列，系统才处于安全状态。

安全序列是指一个进程序列<P1, P2, …, Pn> ，Pi仍然可以申请的资源数小于当前可用资源加上所有j<i的进程锁占有的资源，即当所有Pj完成时，Pi可得到所需的资源来完成自己。

安全状态一定不是死锁状态，死锁状态是非安全状态，但非安全状态不一定产生死锁。

资源分配图算法

适合于每种资源类型只有一个实例的情况。

除了申请边和分配边外，引入需求边Pi→Rj，用虚线，表示Pi可能在将来某个时刻申请Rj。当申请完成时，申请边反向，变为分配边。

如果在尝试满足一个申请，即将申请边转为分配边后，边成环，就是进入了非安全状态，不应进行此分配。

银行家算法

适合于每种资源类型有多个实例的情况。

进程进入系统时，声明可能需要的每种资源的实例的最大数量（不能超过系统资源总和）；用户申请资源时，系统应确定分配会不会让系统进入非安全状态。

n：进程数；m：资源种类数

Available：长度为m的向量，表示每种资源可用实例数量

Max：n×m矩阵，表示每个进程的最大需求

Allocation：n×m矩阵，表示每个进程目前获得的分配

Need：n×m矩阵，表示每个进程还需要的分配

性质：Need = Max - Allocation

• 安全算法：确定系统是否处于安全状态

  Work：长度为m的向量，工作向量，初始化Work=Available

  Finish：长度为n的向量，表示任务是否完成，初始化全false

  • 找一个未完成的i，满足Need[i]≤Work（即当前工作向量能满足完成的需求）
  • Finish[i]=true，即将它完成；Work += Allocation[i]，即交还分配，转第一步
  • 如果第一步没有找到i，则检查Finish是否均为true，是的话即处于安全状态

• 资源请求算法：如何进行安全的资源请求

  • 确认Request[i] ≤ Need[i]，否则该进程进行了过量需求
  • 确认Request[i] ≤ Available，否则该进程要等待
  • 修改状态：
    • Available -= Request[i]，即进行分配
    • Allocation += Request[i]，记录当前分配
    • Need[i] -= Request[i]，削减需求
  • 检查当前是否在安全状态，如果不，则恢复

死锁检测

每种资源只有单个实例

使用wait-for图。在资源分配图中删去所有资源，适当合并边，即得到wait-for图。当且仅当在wait-for图中有一个环，系统发生死锁。

每种资源有多个实例

Work：长度为m的向量，工作向量，初始化Work=Available

Finish：长度为n的向量，表示任务是否完成，如果Allocation[i]不为0则false，否则true（当前没分到，等效于已经完成）

• 找一个未完成的i，满足Request[i]≤Work（即当前工作向量能满足完成的需求）
• Finish[i]=true，即将它完成；Work += Allocation[i]，即交还分配，转第一步
• 如果第一步没有找到i，则检查Finish，如果Finish[i]为false则系统死锁、进程i死锁

什么时候进行检测

• 隔一段时间检测一次
• CPU使用率过低时

如果任意时间地检测，那么资源图可能有多个环，难以确定哪个进程造成了死锁。

死锁恢复

进程终止（Abort）

• 中止所有死锁进程：代价大
• 一次中止一个死锁进程，直到消除死锁循环
  • 如何确定中止哪一个？优先级、计算已用时间、计算剩余时间、是否是交互的进程…

资源抢占

不断地抢占一些进程的资源给其他进程使用，直到死锁循环被打破。

• 选择哪一个进程牺牲？
• 回滚到哪一个安全状态？
• 怎么避免饥饿？