兰斯小窝

Appearance

ch7 死锁 ​

7.1 基本概念 ​

  1. 死锁与饥饿
    1. 死锁：一组处于等待（阻塞）状态的进程，每一个进程持有其他进程所需要的资源而又等待其他进程所拥有的资源，致使这组进程互相等待，均无法向前推进
    2. 饥饿：就绪进程长时间得不到调度处于等待状态，而不是死锁中的相互等待。若信号量的等待队列按照LIFO或优先级管理，则可能导致饥饿
  2. 进程使用资源的顺序
    1. 申请
    2. 使用
    3. 释放
    • 资源的申请与释放为系统调用：设备request()/release()；文件open()/close()；内存allocate()/free()；其他资源的申请与释放可以由信号量的申请与释放wait()/signal()操作来完成
  3. 死锁特征（必要条件）
    • 四个条件同时满足就会引起死锁
    1. mutual exclusion：互斥：至少一个资源要求互斥的共享
    2. hold and wait：持有并等待：一个进程至少占有一个资源并等待另一资源，该资源为其他进程所持有
    3. no preemption：非抢占：资源不能被占，只能进程完成任务后自动释放
    4. circular wait：循环等待：相互等待形成了一个环
  4. 资源分配图 alt text
    • 资源分配图中没有环就一定没有死锁，如果有环且环中每种资源只有一个实例也一定是死锁，否则就得根据四个条件展开的讨论 alt text
    • 左图也环了，但是可以看到p2p4都没有在等待组内的资源，任意一个进程结束释放资源后环就会消失，所以不是死锁
    • 对于右图的p1、p2、p3每个进程占有资源并且等待着其他进程释放资源，且循环等待，所以形成了死锁
  5. 死锁处理方法
    1. 使用协议预防死锁
      死锁预防（prevention）是一组方法，需要确定至少一个必要条件不成立
      死锁避免（avoidance）要求操作系统事先得到有关进程申请使用资源的额外信息，当进程申请资源时，若发现满足该资源的请求可能导致死锁地发生，则拒绝该申请
    2. 允许进入死锁状态，检测并加以恢复
    3. 忽视死锁问题：大多数系统采用，因为发生的并不频繁，预防、避免、恢复消耗太大

7.2 死锁预防 ​

预防死锁的特点是一定不会死锁，但是会降低资源利用率和系统吞吐量

  1. 互斥
    • 非共享资源必须互斥使用，共享资源不要求互斥所以不会死锁。无法从互斥条件下手避免死锁。
  2. 持有并等待
    1. 拥有不等待：资源静态分配策略，要求一个进程在执行的前获得所有的资源
    2. 等待不占有：进程在申请其他资源的时候必须释放已分配的资源
    • 缺点：资源利用率低，分配以后可能很久不被使用；产生饥饿，对于第一种协议，如果有进程需要多个常用资源，就可能会永久等待
  3. 非抢占
    • 如果一个进程占有一些资源并在申请一些无法立刻分配到的资源，那么它占有的这些资源就都可以被抢占；该进程将会在它重新获得原有资源以及原本要申请的资源的时候重启
    • 用于状态可保存和可恢复的资源，如CPU、内存等，不适合打印机等设备
  4. 循环等待
    • 对所有资源类型完全排序，要求每个进程按照递增顺序申请资源 alt text

7.3 死锁避免 ​

死锁避免算法动态监测资源分配状态以确保循环等待条件不可能成立。
资源分配状态 resource-allocation state 是由可用资源、已分配资源和进程最大需求所决定的；所以这种算法要求每个进程说明可能需要的每种资源类型实例的最大需求。
死锁避免算法会因为跟踪当前资源分配成本增加巡行成倍，但是相对于静态死锁预防方法它允许更多的并发使用资源，所有系统吞吐量大于死锁预防

  1. 安全状态（safe state）
    • 如果系统能按照某个顺序为每个进程分配资源并能避免死锁，系统状态就是安全的
    • 存在一个安全序列safe sequence<P0,P1,P2,...,Pn>使得前面的进程能够得到足够的资源，同时它释放的资源又能满足后面的进程的话，就是安全的
    • 不安全状态不一定导致死锁，但是死锁一定是不安全状态，使得系统处于安全状态，就一定不会死锁
  2. 单实例——资源分配图（RAG）（single-instance resource allocation graph）
    • 使用具有claim边的RAG，适用于每种资源类型有单个实例的资源分配系统 alt text
    • 虚边：将要请求或可能使用claim adge
    • 实边：请求边和分配边request，assignment
    • 规定：图中如果没有环，就是安全状态；如果有环，即使环中有虚边，也是不安全状态，在避免算法里面是不允许出现的，如果出现了实环边，就是死锁
    • 算法步骤：
      1. 请求资源看资源是否可用，不可用则等待，可用转下一步
      2. 假分配看是否出现死锁，如果不会就进行分配，如果有死锁那么请求资源的进程进入等待状态 alt text
  3. 多实例——银行家算法 multiple-instance banker's algorithm
    • 效率低于资源分配法
    • 当新进程进入系统时，必须说明其可能需要的每种类型资源实例的最大数量。用户申请一组资源时，系统必须确保资源分配后系统仍处于安全状态。假定有n个进程和m种资源类型
    1. 安全性算法：确定计算机系统是否处于安全状态 alt text
    2. 资源请求算法：判断是否可安全允许请求
      1. 确定request<=need否则出错；reques<=available否则等待
      2. 按照请求假分配，修改系统当前的available和need，然后判断假分配以后系统状态是否安全；如果安全，该分配得到允许

7.4 死锁检测 ​

  • 检测并恢复方案有额外开销，包括维护所需信息和执行算法的巡行开销和死锁恢复所引起的损失
  1. 每种资源类型只有单个实例：等待图（wait-for graph）
    • 点表示进程，Pi→Pj表示Pi在等待Pj。如果等待图中出现了环，就存在死锁
      （（a）资源分配图 （b）等待图） alt text
  2. 每种资源类型可有多个实例
    • 与银行家算法相似，只不过现在我们不需要知道每个进程的最大需求资源量，而是假定在一个进程的请求被接受以后执行完这一段程序就会释放占用的资源，其实本质上和银行家算法是一样的，不过是把 need 变成了 request。银行家算法是重点内容，为了防止读者混乱，在这里再列一个多实例死锁检测的例子，就会发现它和银行家算法并没有什么不同 alt textalt text

7.5 死锁恢复 ​

  1. 进程终止
    • 无论采用哪种方法，系统都会回收分配给终止进程的所有资源
    1. 终止所有进程：代价高昂，被终止的进程都要重新计算
    2. 一次只终止一个直到死锁消失：开销大，因为需要不停的调用死锁检测
  2. 资源抢占
    • 从进程中抢占资源给其他进程用，需要处理以下三个问题
    1. 选择一个牺牲品：代价最小化
    2. 回滚：被抢占的进程需要回滚到安全状态
    3. 饥饿：必须保证不会发生饥饿，因为有可能被抢占的总是同一个进程