死锁--deadlock

定义：当一组进程中的每个进程都在等待只能由该组中的另一个进程释放的资源时，该组进程（例如）处于死锁状态。

资源--Resource

  • 资源是任何可以在一段时间内获得、使用和发布的东西。是需要排他性使用的对象。
  • 分类：
    • 可抢占资源--preemptable resource
      • 可以从拥有它的进程中抢占而不会产生任何副作用
        • 例如：存储器
    • 不可抢占资源--nonpreemptable resource
      • 是指在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来
  • 涉及可抢占资源的潜在死锁通常可以通过将资源从一个进程重新分配到另一个进程来解决
  • 一个资源所需要的事件顺序：
    • 请求资源--request
    • 使用资源--use
    • 释放资源--release
  • 如果请求被拒绝必须等待
    • 请求的进程可能被阻塞
    • 可能因为错误代码失败

死锁的条件

死锁建模

  • 用圆形表示进程，用方形表示资源
  • 从资源节点到进程节点的有向边代表该资源已被请求、授权并被进程占用
  • 由进程节点到资源节点的有向边表明当前进程正在请求该资源

  • 基本的判断
    • 图中没有环，没有死锁
    • 如果有一个循环
      • 如果一个资源里只有一个实例，那么是死锁
      • 如果一个资源里有多个实例，那么可能没被占用完，可能不是死锁

最简单的解决办法：鸵鸟算法

  • 忽略死锁
  • 死锁发生的很少
  • 维护的花费很高

死锁检测和死锁恢复

  • 使用这种技术时，系统并不视图阻止死锁的产生，而是允许死锁发生，当死锁发生后，采取措施进行恢复
每种类型一个资源的死锁检测

  • 一个简单的算法

    • 对有向图进行检测，并在发现图中有环路存在或确定无环路时结束

每种类型多个资源的死锁检测
  • 提供一种基于矩阵的算法来检测从\(P_1到P_n\)这n个进程中的死锁
  • m为资源的类型数，\(E_i\)代表资源类型i
  • E是现有资源向量，代表每种已存在的资源总数；A是可用资源向量
  • C代表当前分配矩阵，R代表请求矩阵

从死锁中恢复
  • 利用抢占恢复 preemption
    • 从其他一些进程中获取资源
    • 取决于资源的性质
  • 利用回滚恢复 rollback
    • 周期性地对进程进行检查点检查
      • 进程点检查就是将进程的状态写入一个文件以备重启
    • 检查点恢复进程，定期使用此保存状态
    • 如果发现进程陷入僵局，则重新启动进程
  • 通过杀死进程恢复
    • 杀死一个或若干个进程
      • 一种方法：杀掉环中的一个进程
      • 另一种方法：选一个环外的进程作为牺牲品来释放该进程的资源

问题

Check points

  1. What is deadlock?
    • A set of processes is in a deadlock state when every process in the set is waiting for a resource that can only be released by another process in the set
  2. What is resource in computer?
  • A resource is anything that can be acquired, used, and released over the course of time.
  1. What are the four conditions for a deadlock to occur?
    • mutual
    • hold and wait
    • no preemption
    • circular wait
  2. How to detect deadlock?
    • One resource of each type：cycle
    • Multi resource of each type:
  3. How to recovery from deadlock
    • kill one process
    • preemption
    • rollback