操作系统之死锁

在同步问题中的哲学家就餐问题中，通过信号量我们没有合适的解决方法，因为那会造成死锁，今天我就复习一下死锁。

死锁特征

由于竞争资源或者通信关系 两个或更多线程在执行中出现 用于相互等待只能由其他进程引发的事件

互斥：任何时刻只能由一个进程使用资源实例

占有并等待：进程保持至少一个资源别难过正在等待其他进程的资源

非抢占：资源只能在进程使用后资源释放

循环等待：字面意思

资源分配图：

没有死锁是因为P4可能释放资源类型R2的实例

死锁处理方法

通常操作系统忽略死锁 由应用进程处理死锁

死锁预防(Deadlock Prevention)：确保死锁的至少一个必要条件不成立

• 确保系统永远不会进入死锁状态

死锁避免(Deadlock Avoidance)

• 在使用前进行判断 只允许不会出现死锁的进程请求资源

死锁检测和恢复(Deadlock Detection & Recovery)

• 在检测到系统进入死锁状态后 进行恢复

死锁预防

限制并发进程对资源的请求 使系统在任何时刻都不满足死锁的必要条件，但是会导致资源的利用率低。

互斥

• 把互斥的共享资源封装成可同时访问

  持有并等待

• 进程请求资源时 要求它不持有任何其他资源

• 仅允许进程在开始执行时 一次请求所有需要的资源

• 非抢占

• 如进程请求不能立即分配的资源 则释放已占有资源

• 只在能够同时获得所有需要资源时 才执行分配操作

循环等待

• 对资源排序 要求进程按顺序请求资源

死锁避免

构造一个算法以确保系统绝不会进入死锁状态，一直处于安全状态。

安全状态

系统处于安全状（以某种序列分配资源能避免死锁）

• 针对所有已占有进程存在安全序列

序列<P1, P2, …, PN> 是安全的

• Pi要求的资源 <= 当前可用资源 + 所有Pj持有资源 其中 j < i
• 如Pi的资源请求不能立即分配 则Pi等待所有Pj(j < i) 完成
• Pi完成后 Pi + 1 可得到所需资源 执行并释放所分配的资源
• 最终整个序列的所有Pi都能获得所需资源

资源分配图方法

每个资源有多个实例的时候这种方法就不适用了

只有在将申请边变成分配边而不会导致资源分配图成环时，才安全。

银行家算法

不能满足所有客户的需求时，不分配现金。

当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

数据结构实现：

n = 线程数量
m = 资源类型数量

• Max(总需求量) = n x m 矩阵
• Available(剩余空闲量) 长度为 m 的向量
• Allocation(已分配量) = n x m 矩阵
• Need(未来需要量) = n x m 矩阵

Need[i, j] = Max[i, j] - Allocation[i, j]

安全状态判断：

初始化：

• Work = Available // 当前资源剩余空闲量
  Finish[i] = false for i : 1, 2, ..., n // 线程i有没有完成

1. 寻找线程Ti:
   • Finish[i] = false
   • Need[i] <= Work
   • 去 步骤2
2. 找到线程Ti
   • Work = Work + Allocation[i]
   • Finish[i] = true
   • 回到 步骤1

查所有线程是否满足 Finish[i] == true

• 若等 则系统处于安全状态

资源分配算法：

init: Requesti 线程Ti的资源请求向量
      Requesti[j] 线程Ti请求资源Rj的实例
do-while:
1.如果 Requesti ≤ Need[i], 转到步骤2。否则, 拒绝资源申请, 因为线程已经超过了其最大要求
2.如果 Requesti ≤ Available, 转到步骤3。否则, Ti 必须等待, 因为资源不可用
3.通过安全状态判断来确定是否分配资源给Ti: 生成一个需要判断状态是否安全的资源分配环境
Available = Available - Requesti;
Allocation[i] = Allocation[i] + Requesti;
Need[i]= Need[i] – Requesti;
若安全 则分配资源给Ti
若不安全 则拒绝Ti的资源请求

实例：