Deadlock Definition

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进得现象，就是“死锁”
规范定义：如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁的。

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象
死循环：进程执行过程中一直跳不出某个循环的现象

死锁的原因

• 抢占资源，资源不可剥夺
• 多个进程的运行顺序非法
• 信号量使用不当
  对不可剥夺资源分配不合理，就会发生死锁。

  资源

  就是资源导致死锁
  硬件、软件、信息
  抢占式、非抢占式

  非抢占式（Nonpreemptable）资源

  在不引起相关计算失败的情况下，无法把它从占有的进程抢占过来。

  抢占式（Preemptable）资源

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

  使用资源的顺序：

1. 请求资源
2. 使用资源
3. 释放资源

死锁的处理

1. 忽略该问题（鸵鸟算法）
2. 检测死锁并恢复
3. 仔细对资源进行分配，动态地避免死锁
4. 通过破坏引起死锁的四个必要条件之一，防止死锁的产生

Deadlock Conditions

死锁产生的条件

• 互斥条件：只有对互斥使用的资源争抢才会导致死锁
• 不可抢占条件：进程所获得的资源在未完成前，不能由其他进程强行夺走
• 占有和等待（请求和保持）条件：进程已经保持了至少一个资源，但又提出了新的资源请求
• 循环等待条件：有一种进程资源的循环等待链，链中每个进程已经获得的资源同时被下一个进程所请求。循环等待未必死锁，死锁 必 循环等待

Deadlock Modeling

死锁的模型

• 使用有向无环图来描述死锁中进程和资源的关系。其中，进程用圆圈⚪表示，资源用方块■表示。

请求边：进程节点 -> 资源节点
分配边：资源节点 -> 进程节点

Deadlock Detection

死锁检测和死锁恢复
构建一张资源分配图

从图中可以看到，已经构成环，所以就出现了死锁。

死锁检测算法——每种类型一个资源

1. 对图中每个节点N，将N作为起始点执行下面5个步骤
2. 将L初始化为空表，并清除所有的有向边标记
3. 将当前节点添加到L的尾部，并检查该节点是否在L中已经出现过两次。如果是，那么该图包含了一个环（已经列在L中），算法结束
4. 从给定节点开始，检测是否存在没有标记的从该节点出发的有向边。如果存在的话，执行(5)；如果不存在，执行(6)
5. 随机选取一条没有标记的从该节点出发的有向边，标记它。然后顺着这条有向边找到新的当前节点，返回(3)
6. 如果该节点是起始节点，那么表明途中不存在任何环，算法结束。否则意味着走进了死胡同，所以需要移走该节点，返回到前一个节点，即当前节点前面的一个节点，并把它作为新的当前节点，同时转到(3)

死锁检测算法——每种类型多个资源

数据结构：E向量（现有资源）、A向量（可用资源）、C矩阵（分配矩阵）、R矩阵（请求矩阵）

1. 寻找一个没有标记的进程Pi，对于他而言R矩阵的第i行向量≤A
2. 如果找到这样一个进程，那么将C矩阵的第i行向量加入A中，标记该步骤，并转到第一步
3. 如果没有这样的进程，那么算法终止
   算法结束时，所有没有标记过的进程都是死锁进程

   Deadlock Recovery

   利用抢占恢复

   挂起死锁进程，并抢占它的资源，将这些资源分配给其他的死锁线程。

   利用回滚恢复

   让一个或多个死锁进程回退到足以避免死锁的地步。要求系统记录进程历史信息，设置还原点。

   利用杀死进程恢复

   强制撤销部分、全部死锁的进程，并剥夺进程资源。实现简单，但是代价可能会很大。

对谁动手：考虑 进程优先级、已执行时间、还要多久能完成、进程占用了多少资源、进程是交互式or批处理

Deadlock Avoidance

• 安全序列：如果系统按照安全序列分配资源，则每个进程都能顺利完成。（安全序列不唯一）
• 安全状态：如果当前可以得到一个安全序列执行完全部进程，那么该状态就是一个安全状态。
• 不安全状态：如果当前没有一个安全序列可以执行完全部进程，那么该状态就是不安全状态。
  （不安全状态不一定发生死锁，但是死锁一定是在不安全状态）
  

  银行家算法

1. 查找右边矩阵是否有一行，其没有被满足的资源数均≤A。如果不存在，那么系统将可能死锁。
2. 假若找到这样一行，那么可以假设它获得所需的资源并运行结束，将该进程标记为终止，并将其资源加到向量A上
3. 重复以上两步，或者直到所有的进程都标记为终止，其初始状态是安全的；或者所有进程的资源需求都得不到满足，此时就是发生了死锁。

需要的数据结构：Max矩阵（描述进程最大需求）、Allocation矩阵（描述进程已分配资源）、Need矩阵（描述进程仍然需要的资源）、Available向量（描述当前系统可用资源）、Request向量（描述本次申请的各种资源量）

Deadlock Prevention

破坏互斥条件

使用SPOOLing技术，把独占设备在逻辑上改造成共享设备。
缺点：不是所有资源都可以改造成共享设备

破坏非抢占式条件

• 方案一：当某个进程请求新资源得不到满足，就立即释放保持的所有资源，等待以后需要的时候再重新申请。
• 方案二：某个进程需要的资源被其他所有进程占有时，可以由操作系统协助，将想要的资源强制剥夺。这种方式考虑各进程的优先级

缺点：

1. 实现复杂
2. 释放已获得资源可能会导致前一阶段工作失效，所以只适用于易保存、恢复状态的资源，如CPU
3. 反复申请和释放回增加系统开销，降低吞吐量。
4. 若方案一，每次释放自己全部资源，然后需要一个一个重新申请回来，这样就可能会导致进程饥饿。

破坏占有和等待条件

用静态分配方法，即在进程运行之前一次性申请完所有需要的全部资源，则在资源未满足前，不让它投入运行。一旦投入运行，资源一直占有，不会请求别的资源。

缺点：

1. 有些资源可能仅仅需要很短的时间，那一直保持所有资源，就会造成严重的浪费，资源利用率低。
2. 可能导致某些进程饥饿

破坏循环等待条件

采用顺序资源分配法，给系统资源编号，规定每个进程按照编号递增的顺序请求资源，同类资源一次申请完。
原理分析：一个进程只有己占有小编号的资源时，才有资格申请电大编号的资源。按此规则，己持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

缺点：

1. 不方便增加新设备，因为可能要重更新分配所有编号
2. 进程实际使用资源的顺序可能和编号递增顺序不一致，会造成资源浪费
3. 必须按规定次序申请资源，编程麻烦

Other

两阶段加锁：在第一阶段，进程试图对所有所需的记录进行加锁，一次锁一个记录。如果第一阶段加锁成功，就开始第二阶段，完成更新然后释放锁。在第一阶段并没有做实际的工作。
通信死锁
活锁：忙等待可能导致
饥饿