# 死锁

# 死锁定义

死锁是指并发进程由于互相等待独占性资源而无限期陷入僵局的一种局面

# 死锁产生

# 互斥访问

系统中存在临界资源，进程应互斥地使用这些资源

# 占有与等待

进程在请求资源得不到满足而等待时，不释放已有资源

# 非剥夺

已被占用的资源只能由属主在使用完时自愿释放，而不允许被其他进程剥夺

# 循环等待

存在循环等待链，每个进程在链中等待下一个进程所持有的资源，造成这组进程处于永远等待状态。

# 解决死锁问题

# 死锁防止

采用一种资源分配策略，消除造成死锁产生的 4 个条件之一

# 破坏互斥条件

使资源可同时访问而非互斥使用，也就没有进程会阻塞在资源上，从而不发生死锁。
可重入程序、只读数据文件、时钟、磁盘等资源可以非互斥使用
但可写文件、磁带机等只能互斥占有

# 破坏占有和等待条件

要求进程在执行之前就申请所需要的全部资源，且直到所有资源都得到满足后才开始执行。进程在执行过程中不再申请资源，就不会出现占有某些资源再等待另一些资源的情况。
易于实现，但缺点在于严重降低资源利用率。
需要进程知道运行过程中将使用到的所有资源

# 破坏非剥夺条件

方法一：如果拥有资源的进程在申请新资源时未得到满足，则进程放弃所有已占用资源（隐式剥夺），若仍需要占用上述资源，则应向系统重新提出申请，同时申请原有资源和新资源；
方法二：当一个进程 A 申请当前被另一个进程 B 占用的资源，而 B 正等待其它资源时，操作系统可以剥夺 B 进程，要求其释放资源（显式剥夺）。
该方法仅适用于资源的状态可以很容易被保存和恢复的资源，如处理器

# 破坏循环等待条件

可以为资源类型排序，并采用按序分配策略，即进程只能按照规定的顺序申请资源

# 死锁避免

依据当前资源分配的状态作出动态资源分配选择，以避免进入死锁状态。如银行家算法

允许系统中同时存在前三个必要条件，通过合适的资源分配算法确保不会出现进程循环等待条件

# 银行家算法

假设系统中 n 个进程和 m 类资源

系统中资源总数向量为 $Resouce=(R_1,R_2\dots,R_m)$

系统中当前可用资源数向量为 $Available=(V_1,V_2\dots,V_m)$

进程对各类资源的最大需求矩阵

$Claim=\begin{bmatrix} C_{11}&C_{12}&\dots&C_{1m}\\ C_{21}&C_{22}&\dots&C_{2m}\\ \vdots&\vdots&\vdots&\vdots\\ C_{n1}&C_{n2}&\dots&C_{nm}\\ \end{bmatrix}$

系统中当前资源已分配情况矩阵

$Allocation=\begin{bmatrix} A_{11}&A_{12}&\dots&A_{1m}\\ A_{21}&A_{22}&\dots&A_{2m}\\ \vdots&\vdots&\vdots&\vdots\\ A_{n1}&A_{n2}&\dots&A_{nm}\\ \end{bmatrix}$

# 安全状态和安全序列

安全状态是指在一个系统中，所有进程都能按照某种顺序顺利完成执行，而不会发生死锁。在安全状态下，系统能够保证所有进程都能够获得它们所需的资源，而不会发生资源竞争或死锁。

一个系统处于安全状态的条件是，存在一种安全序列，使得按照这个序列分配资源后，所有进程都能够顺利执行完毕。安全状态的判断通常使用银行家算法等方法。

# 银行家算法描述

输入：当前状态、进程 $P_i$ 的资源申请请求 Request

若 $Request>Claim_i-Allocation$ , 报错，否则进入步骤 2
若 $Request>Available$ ，表示资源不够，进程等待，否则进入步骤 3
系统对 $P_i$ 进程的资源请求进行试探性分配，执行 $Availble=Available-Request;Allocation=Allocation+Request$
执行安全性测试算法，若状态安全则接受试分配。

# 死锁检测和解除

检测死锁的存在，并采用恢复机制将系统恢复到非死锁状态

# 资源分配图

节点集：由所有进程和资源类组成
边集
- 请求边： $P_i\rightarrow R_q$ , 进程 $P_i$ 向资源类 $R_q$ 请求
- 分配边： $R_q\rightarrow P_i$ , 资源类 $R_q$ 分配一个资源给进程 $P_i$

# 死锁检测算法

与银行家算法中安全性检测类似

需要先查找所有未完成分配的进程，判断每个进程还需要的请求分配 $Claim_k-Allocation_k$ 若不存在这样的 k 说明该进程在死锁链中
若存在 k，则将其分配处理完成后回收分配空间，重复 1 操作

Operating System