操作系统期末复习——第6章：死锁

6.1 资源

1. 可抢占资源

   可以从拥有它的进程中抢占而不会产生任何副作用，如存储器

2. 不可抢占资源

   在不引起相关的计算失败的话，无法把它从占有它的进程处抢占过来，如蓝光光盘

6.2 死锁简介

6.2.1 ⭐死锁的定义

如果一组进程集合中的每个进程都在等待只能由该进程集合的其他进程才能引发的事件，那么该组进程集合就是死锁的

6.2.2 ⭐死锁的条件（缺一不可）

1. 互斥条件

2. 占有和等待条件

3. 不可抢占条件

4. 环路等待条件

   • 无环不死锁

   • 有环

     • 一个资源仅一个实例会死锁

     • 一个资源有多个实例可能不死锁

6.2.3 资源分配图

1. 圆形是进程，方形是资源

2. 资源指向进程：占有资源
   进程指向资源：请求资源

6.2.3 解决死锁

1. 忽略问题，假装没发生死锁

   鸵鸟算法

2. 允许进入死锁，检测然后恢复

3. 确保不进入死锁

   • 避免（仔细分配资源）

   • 预防（破坏四个条件之一）

6.3 鸵鸟算法

1. 使用鸵鸟算法原因

   • 死锁不经常发生

   • 预防成本高

2. UNIX和Windows使用该方法

3. 是便利性和正确性的折中

6.4 死锁检测和死锁恢复

6.4.1 死锁检测

1. 简介

   • 允许进入死锁，执行死锁检测算法。检测到死锁后执行恢复算法

   • 运行检测算法代价大，成本高

2. 流程

   DFS算法

6.4.2 ⭐死锁恢复

1. ⭐利用抢占恢复

2. ⭐利用回滚恢复（回到上一状态）

3. ⭐通过杀死进程恢复

6.5 ⭐死锁避免

1. 资源轨迹图

2. ⭐安全状态和不安全状态

   从安全状态出发，系统能保证所有进程完成。而不安全状态存在死锁的风险（但仍可能所有进程都完成）。（注意：不安全状态≠死锁）

3. ⭐银行家算法

   实用性不高

   • 很少有进程在运行前就知道其所需资源的最大值

   • 进程数量不固定

   • 可用资源可能会消失（机器会坏）

6.6 ⭐死锁预防

6.6.1 破坏互斥条件

1. 假脱机技术

   • 假脱机打印机允许若干个进程同时产生输出

   • 由守护进程按顺序处理请求

   • 若假脱机内存空间满也会出现死锁

2. 原理

   • 非绝对必要时避免分配资源

   • 实际占用资源的进程尽可能少

3. 问题

   不是所有设备都可以假脱机

6.6.2 破坏占有并等待条件

1. 进程执行前请求所有的资源

2. 问题

   • 开始执行时可能不知道所需资源

   • 占用其他进程的资源，资源利用率差（请求所有的资源，就会占用别的进程的资源）

3. 变体

   请求资源前先释放当前持有的资源，然后再请求所有所需资源

6.6.3 破坏不可抢占条件

1. 强行抢占

   实践中难以实现

2. 资源虚拟化

   • 假脱机打印机向磁盘输出，并仅允许守护进程访问真实打印机（可以抢占进程顺序？）

   • 问题

     • 并非所有资源都可以虚拟化

6.6.4 破坏环路等待条件

1. 法1：一次请求一个资源。请求下一个资源时释放当前资源

2. 法2：资源进行编号，按升序请求

3. 法3：法2的变体，取消升序，按大于等于

4. 问题

   • 很难/不可能找到合适的编号满足所有进程需求

   • 增加程序员了解编号的负担

6.7 其他问题

6.7.1 两阶段加锁Two-Phase Locking

1. 第一阶段：对所有所需记录加锁

   若某个记录已加锁，就释放所有加锁记录，重新开始第一阶段

2. 第二阶段：完成更新然后释放锁

6.7.2 通信死锁Communication Deadlocks

1. 一组进程互相等待对方发送的消息，但这些消息因丢失、延迟或逻辑错误永远无法到达

2. 解决方案：超时机制（Timeout）

6.7.3 活锁LiveLock

一组进程未阻塞，但通过无效的重复操作互相礼让资源，导致进程不会继续执行

6.7.4 饥饿Starvation

某个进程因资源长期被高优先级进程抢占而无法获得所需资源，导致任务延迟或无法完成

6.7.5 死锁Deadlock

一组进程因相互等待对方持有的资源而全部阻塞，无法继续执行