Untitled

系统模型

资源类型（Recourse types）包括 CPU 周期、文件、I/O 设备等

每个资源类型有一定数量的实例

每个进程只能按如下顺序使用资源：
- 申请（request）
- 使用（use）
- 释放（release）

死锁特征

必要条件

如果在一个系统中以下四个条件同时成立，就能引起死锁：
- 互斥（mutual exclusion）：至少有一个资源必须处于非共享模式，即一次只有一个进程可使用。如果另一进程申请该资源，那么申请进程应等到该资源释放为止
- 占有并等待（hold and wait）：一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有
- 非抢占（no preemption）：资源不能被强占，即资源只能被进程在完成任务后自愿释放
- 循环等待（circular wait）：有一组等待进程 $\{P_0,P_1,\cdots,P_n\}$ ， $P_0$ 等待的资源为 $P_1$ 占有， $P_1$ 等待的资源为 $P_2$ 占有，…， $P_{n-1}$ 等待的资源为 $P_n$ 占有， $P_n$ 等待的资源为 $P_0$ 占有

资源分配图

系统所有活动进程的集合 $P=\{P_1,P_2,\cdots,P_n\}$

系统所有资源类型的集合 $R=\{R_1,R_2,\cdots,R_n\}$

申请边（request edge） $P_i\rarr R_j$ 表示进程 $P_i$ 已经申请了资源 $R_j$ 的一个实例，并且正在等待这个资源

分配边（assignment edge） $R_j\rarr P_i$ 表示资源类型 $R_j$ 的一个实例已经分配给了进程 $P_i$

存在死锁的资源分配图

具有环的并未死锁的资源分配图

如果资源分配图不存在有向环路，则不存在死锁

死锁处理方法

处理死锁问题有三种方法：
- 通过协议来预防或避免死锁，确保系统不会进入死锁状态
- 可以允许系统进入死锁状态，然后检测它，并加以修复
- 可以忽视这个问题，认为死锁不可能在系统内发生

死锁预防

只要确保四个必要条件至少一个不成立就能预防死锁发生

副作用：设备使用率低、系统吞吐率低

破坏互斥条件

可共享资源不要求互斥访问，但对于非共享资源互斥条件必须成立

破坏互斥条件的方法不可行

破坏持有并等待条件

为了确保持有并等待条件不出现在系统中，应保证当每个进程申请一个资源时，不能占有其它资源

可采用的两种协议：
- 每个进程在执行前申请并获得所有资源（通过要求进程申请资源的系统调用在所有其他系统调用之前进行来）
- 允许进程仅在没有资源时才可以申请资源（在申请更多其他资源前应释放现已分配的所有资源）
主要缺点：
- 资源利用率比较低
- 可能发生饥饿

破坏无抢占条件

如果一个进程持有资源并申请另一个不能被立即分配的资源，那么它现在分配的资源都可被抢占（资源被隐式释放）。

被抢占资源添加到进程等待的资源列表上

只有当进程获得其原有资源和申请的新资源时才可以重新执行

反复申请和释放资源会增加系统开销，降低系统吞吐量

适用于状态易于保存和恢复的资源，如 CPU 的寄存器及内存资源，不适用于打印机之类的资源

破坏循环等待条件

顺序资源分配法：对所有资源类型进行完全排序，要求每个进程按递增顺序来申请资源

通过反证法可以证明循环等待不成立， $F(R_0)<F(R_1)<\cdots<F(R_n)<F(R_0)$

主要缺点：
- 编号必须相对稳定，限制了新类型设备的增加
- 可能发生作业使用资源的顺序与系统规定的顺序不同的情况，造成资源浪费

死锁避免

死锁仍有可能发生

避免死锁需要额外信息，即如何申请资源

最简单且最有用的模型要求每个进程都应声明可能需要的每种类型资源的最大数量

死锁避免算法动态地检查资源分配状态，以便确保循环等待条件不能成立

资源分配状态包括可用的资源、已分配的资源及进程的最大需求

安全状态

如果系统能按一定顺序为每个进程分配资源（不超过它的最大需求），仍然避免死锁，那么系统是安全的。

进程序列 $<P_1,P_2,\cdots,P_n>$ 在当前分配状态下为安全序列是指对于每个 $P_i$ ， $P_i$ 仍可以申请的资源数小于当前可用的资源加上所有进程 $P_j(j<i)$ 所占有的资源

只有存在一个安全序列，系统才处于安全状态

安全状态不是死锁状态，死锁状态是非安全状态，但不是所有的非安全状态都能导致死锁状态

Untitled

采用死锁避免算法来确保系统始终处于安全状态，就能避免非安全（和死锁）状态

资源分配图算法

每种资源类型只有一个实例

需求边（claim edge） $P_i\rarr R_j$ 表示进程 $P_i$ 可能在将来某个时候申请资源 $R_j$ ，用虚线表示

当进程 $P_i$ 申请资源 $R_j$ 时，需求边 $P_i\rarr R_j$ 变成了申请边 $P_i\rarr R_j$

当进程 $P_i$ 释放资源 $R_j$ 时，分配边 $R_j\rarr P_i$ 变成了需求边 $P_i\rarr R_j$

如果没有环路存在，那么资源的分配会使得系统处于安全状态，否则系统处于非安全状态

若系统中每类资源都只有一个实例，则资源分配图含环成为系统死锁的充分必要条件

银行家算法

假设：
- 每种资源类型有多个实例
- 每个进程声明所需资源的最大数量
- 一个进程发出请求时可能需要等待
- 一个进程获得所有所需资源后必须在有限时间内归还
实现银行家算法所需的数据结构（n 为系统进程的数量，m 为资源类型的种类）：
- Available： $m$ 元数组，每个元素代表一类可用的资源数目
- Max： $n\times m$ 矩阵，定义系统中 $n$ 个进程中的每个进程对 $m$ 类资源的最大需求
- Allocation： $n\times m$ 矩阵，定义系统中每类资源当前已分配给将每个进程的资源数目
- Need = Max - Allocation： $n\times m$ 矩阵，表示每个进程接下来还需要多少资源

安全算法（判断系统是否处于安全状态）

令 Work 和 FInish 分别为长度 m 和 n 的向量，初始化 Work = Available 和 Finish[i] = false
查找下标 i 满足 Finish[i] == false && Need[i] ≤ Work，即每种资源的需求都不超过可分配的数量。如果不存在这样的 i 则跳转到第 4 步
Work = Work+Allocation[i], Finish[i] = true，即第 i 个进程在分配到资源之后成功执行，并且释放了所有占有的资源。返回第 2 步
如果所有的 i，Finish[i] == true 都成立，则系统处于安全状态，否则处于非安全状态

资源请求算法（判断是否安全允许请求）

令 Request[i, j]=k 表示进程 i 需要资源 j 的 k 个实例，必须要保证 Request[i] 不超过 Need[i] 和Available[i]，否则就出现错误了
假设将第 i 个进程所需要的资源都分配给了它，即进行了如下操作：
Available -= Request[i]
Allocation[i] += Request[i]
Need[i] -= Request[i]
调用安全算法来检测进行了上面的操作之后系统是否处于安全状态，如果是就将资源分配给 $P_i$ ，否则 $P_i$ 必须进入等待状态

死锁检测

每种资源类型只有单个实例

如果每种资源只有一个实例，可以使用等待（wait-for）图，如果有环就表明系统存在死锁

Untitled

从图中检测环的算法需要 $n^2$ 数量级的操作（ $n$ 为节点数）

每种资源类型可有多个实例

如果每种资源可以有多个实例，可以用类似于安全算法的方式来检测是否存在死锁

所需的数据结构（n 为系统进程的数量，m 为资源类型的种类）：
- Available： $m$ 元数组，每个元素代表一类可用的资源数目
- Allocation： $n\times m$ 矩阵，定义系统中每类资源当前已分配给将每个进程的资源数目
- Request： $n\times m$ 矩阵，表示当前每个进程的每种资源的当前请求

令 Work 和 FInish 分别为长度 m 和 n 的向量，初始化 Work = Available。对 i = 0, 1, … , n-1，如果 Allocation[i] 不为 0，则 Finish[i] = false，否则 Finish[i] = true
查找下标 i 满足 Finish[i] == false && Request[i] ≤ Work，即每种资源的当前请求都不超过可分配的数量。如果不存在这样的 i 则跳转到第 4 步
Work = Work+Allocation[i], Finish[i] = true，即第 i 个进程在分配到资源之后成功执行，并且释放了所有占有的资源。返回第 2 步
若存在 Finish[i] == false 则第 i 个进程死锁，系统死锁