死锁：一组阻塞的进程持有一种资源，等待获取另一个进程所占有的一个资源
1.系统模型
资源类型：CPU cycles，memory space，I/O devices
每个进程使用资源：
- request/get <—— free resource
- use/hold <—— requested/used resource
- release <—— free resource
资源分配图：
一组顶点V和边E的集合
V有两种类型
- P = {P1, P2, ... , Pn}，集合包括系统所有的进程
- R = {R1, R2, ... ,Rn}，集合包括资源中所有的资源类型
边也有两种类型：
- requesting/claiming edge——directed edge: Pi->Rj；
- assignment/holding edge——directed edge: Rj->Pi
基本情况：
- 途中不包括循环——没有死锁
- 图中包括循环
· 每个资源只有一个实例——死锁
· 每个资源有几个实例——可能死锁
2.死锁的特征
如果以下四个条件同时成立，死锁可能出现。以下4个条件是死锁出现的充分不必要条件
- 互斥：同一时间内只能有一个进程使用资源
- 持有并等待：进程持有至少一个资源正在等待其他进程持有的额外资源
- 无抢占：一个资源只能被进程自愿释放（进程以及完成任务）
- 循环等待：进程间的等待形成一个环
3.死锁的处理办法
1.死锁预防
限制申请方式，从产生死锁的4个必要条件开始
1.1 互斥
共享资源不是必须的，必须占用非共享资源
1.2 占用并等待
必须保证当一个进程请求资源时，他不持有任何其他资源
只有当一个进程获得所需求的所有资源时才会运行，否则释放其持有的资源
问题：资源利用率低，可能会发生饥饿
1.3 无抢占
- 若进程占用某些资源，并请求其他不能被立即分配的资源，则释放当前占有的资源
- 被抢占的资源添加到资源列表中
- 只有当它能够获得旧的资源以及它请求的新资源，进程可以得到执行
1.4 循环等待
对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请
2.死锁避免
需要系统具有一定额外的先验信息提供
- 最简单和最有效的模式：要求进程声明他可能需要的每一资源类型的最大数目
- 资源的分配状态是通过限定提供与分配的资源数量和进程的最大需求
- 死锁避免算法动态检查资源的分配状态，以确保永远不会有一个环形等待的状态
当一个进程请求可用资源时，系统必须判断立即分配能否使得系统处于安全状态
系统处于安全状态是指：针对所有进程，存在安全序列
安全序列：系列<P1, P2, ... , P3>是安全的 [latex] \rightleftharpoons [/latex] 针对每一个Pi，Pi要求的资源能够由当前可用资源加上所有 Pj 持有的资源来满足，其中 i < j
如果系统处于安全状态——无死锁；若系统处于不安全的状态——可能存在死锁
避免死锁：系统永远不会处于不安全的状态
银行家算法/Banker's Algorithm
前提条件：
- 资源拥有多个实例
- 每个线程必须最大限度的利用资源
- 一个进程请求一个资源，得不到就等待
- 当一个进程获得所有资源就必须在一段时间内释放它们
数据结构：
n=进程数；m = 资源类型数量
- Max/总需求量——[latex] n \times m [/latex]矩阵
[latex] Max[i,j] = k; [/latex], 最多需要k个 - Available/剩余空闲量——长为m的向量
[latex]Available[j] = k;[/latex] 还有k个可用 - Allocation/已分配量——[latex] n \times m [/latex]矩阵
[latex] Allocation[i,j] = k; [/latex], 已经分配了k个 - Need/未来需要量——[latex] n \times m [/latex]矩阵
[latex] Need[i,j] = k; [/latex], 未来可能需要k个
算法：
1.初始化
Work = Available;
for(int i=1; i<=n; i++)
Finish[i] = false;2.寻址 i 满足
Finish[i] = false;- [latex] Need_i \leq Work [/latex]
没有找到——转4；找到了——转3
3. Work = Work + Allocation; Finish[i] = true; 转2
4. 判断
For all i， if Finish[i] = true; ——os处于安全状态；否则不安全。
进入算法前的处理
- 进程请求 [latex] request_i \leq Need_i [/latex] ——>转2；否则提出错误条件，因为进程的请求超出了最大需求
- [latex] request_i \leq Available_i [/latex]——>转3；否则 Pi 必须等待。因为资源不可用
- 假设给 Pi 分配其所需的资源 //生成一个需要判断状态是否安全的环境
Available = Available - request；
Allocation = Allocation + request；
[latex] Need_i = Need_i - request [/latex]
3.死锁检测
- 允许系统进入死锁状态
- 死锁检测算法
- 恢复机制
死锁回复：
- 终止所有进程
- 在一段时间内终止一个进程直到死锁解除
终止进程的顺序：进程优先级；进程占用的资源；进程运行了多久；进程需要的资源，......
1.选择一个受害者——最小成本；
2.回滚——重启进程到安全状态
3.饥饿——同一进程一直被选为受害者
Comments | NOTHING