资源类型R1，R2，R3，。。。，Rm
CPU cycles，memory space，I/O devices
每个资源类型Ri有Wi实例
每个进程使用资源如下

request/get < – free resource

use/hold < – requested/used resource

release < – free resource

可重复使用的资源

在一个时间只能一个进程使用且不能被删除
进程获得资源，后来释放由其他进程重用
处理器，I/O通道，主和副存储器，设备和数据结构，如文件，数据库和信号量
如果每个进程拥有一个资源并请求其他资源，死锁可能发生

使用资源

创建和销毁
在I/O缓存区的中断，信号，消息，信息
如果接收消息阻塞可能会发生死锁
可能少见的组合事件会引起死锁

资源分配图

一组顶点V和边E的集合

V有两种类型

P={P1，P2，。。。，Pn}集合包括系统中的所有进程

R={R1，R2，。。。，Rm}集合包括系统中的所有资源类型
requesting/claiming edge - directed edge Pi –> Rj
assignment/holding edge - directed edge Rj –> Pi

资源分配举例说明

可以看到下图11-1中，有P1，P2，P3三个进程，还有资源R1，R2，R3，R4四个资源，且R2资源有两个类型，R4资源有四个类型。这里面的箭头表示进程和资源的关系，R2的两种类型的资源分配给P1和P2，同时P1需要R1的资源，但是R1的资源已经分配给P2。同理R2同时需要R3的资源，但是R3的资源已经分配给P3。

图11-1 资源分配图

上图不存在死锁现象。

这里P1和P2拿不到R1和R3的资源。进程使用资源过一段时间会释放资源，进程P3运行到一段时间，会释放R3的资源，这个时候P2就会去申请使用R3资源，P2就会把资源R1，R2，R3占用，过了一段时间，P2释放R1资源，进程P1这个时候就可以去申请试用R1的资源了。

相反，如果图中的箭头形成一个环之后，就会发生死锁现象。

这里有两个环，P1–>R1–>P2–>R3–>P3–>R2–>P1和P2–>R3–>P3–>R2–>P2

在当前进程申请资源的过程中，由于资源被其他进程占用，所以只能等待，其他进程需要的资源又被当前进程占用，也只能等待申请，所以出现死锁现象。

有循环的资源分配还不一定死锁

显然下图11-2所示是有环的，P1–>R1–>P3–>R2–>P1

这里的P2是不需要在申请其他资源，也就是P2资源使用完成之后就会释放R1资源，而P1正在申请R1资源，那么P1就可以申请试用到R1资源，就不会存在死锁的情况

图11-2 有循环的资源分配不死锁图

总结

如果图中不包含循环，那么就没有死锁
如果图中有循环，且每个资源只有一个实例，那么死锁；如果每个资源有多个实例，可能死锁。
成环是死锁的必要不充分条件

11.3死锁特征

如果四个条件都满足可能出现死锁，如果死锁出现；如果死锁，那么四个条件都满足。

互斥

在一个时间只有一个进程使用资源
持有并等待

进程保持至少一个资源正在等待获取其他进程所持有的的额外资源
无抢占

一个资源只能被进程自愿释放，进程已经完成了它的任务之后
循环等待

存在等待进程集合{P0，P1，。。。，Pn}，P0正在等待P1所占用的资源，P1正在等待P2所占用的资源，Pn-1在等待Pn所占用的资源，Pn正在等待P0所占用的资源。

如下图11-3所示，左边的图满足四个条件，右边的图不满足第二个条件，P2和P4持有了但并不等待，所以不会死锁。

图11-3 没有死锁图

11.4死锁处理方法

确保系统永远不会进入死锁状态
运行系统进入死锁状态，然后恢复
忽略这个问题，假装系统中从来没有发生死锁；用于大多数操作系统，包括UNIX

11.4.1死锁预防

限制申请方式

互斥 - 共享资源不是必须的，必须占用非共享资源
占用并等待 - 必须保证当一个进程请求的资源，它不持有任何其他资源

需要进程请求并分配其所有资源，他开始执行之前或允许进程请求资源仅当进程没有资源

资源利用率低：可能发生饥饿
无抢占

如果进程占用某些资源，并请求其他不能被立即分配的资源，则释放当前正占有的资源

被抢占资源添加到资源列表中

只有当它能够获得旧的资源以及它请求新的资源，进程可以得到执行
循环等待 - 对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请

11.4.2死锁避免

需要系统具有一些额外的先验信息提供

最简单和最有效的模式是要求每个进程声明它可能需要的每个类型的最大数目
资源的分配状态是通过限定提供与分配的资源数量，和进程的最大需求
死锁避免算法动态检查的资源分配状态，以确保永远不会有一个环形等待状态
当一个进程请求可用资源，系统必须判断立即分配是否能使系统处于安全状态
系统处于安全状态：针对所有进程，存在安全序列
序列<P1, P2, P3,…,Pn>是安全的：针对每个Pi，Pi要求的资源能够由当前可用的资源+所有的Pj持有的资源来满足，其中j<i

如果Pi资源的需求不是立即可用，那么Pi可以等到所有Pj完成

当Pi完成后，Pi+1可以得到所需要的资源，执行，返回所分配的资源，并终止

用同样的方法，Pi+2，Pi+3和Pn能获得所需的资源
如果系统处于安全状态===>无死锁
如果系统处于不安全状态===>可能死锁
避免死锁：确保系统永远不会进入不安全状态

如下图11-4，死锁避免机制检验下一时刻的状态是否安全，然后根据情况将edge转换（图中实现虚线的转换，即尽管你有请求意图，但是可能并不允许占用）。

图11-4 死锁避免机制检验图

银行家算法

银行家算法（Banker’s Algorithm）是一个死锁避免的著名算法，是由爱兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

背景

在银行系统中，客户完成项目需要申请贷款的数量是有限的，每个客户在第一次申请贷款时声明完成该项目所需的最大资金量，在满足所有贷款要求并完成项目时，客户应及时归还。

银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。

在这样的描述中，银行就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

银行家算法前提条件

多个实例

每个进程都必须能最大限度的利用资源

当一个进程请求一个资源，就不得不等待

当一个进程获得所有的资源就必须在一段有限的时间释放它们

基于上述前提条件，银行家算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返回给系统）的进程请求的一个理想执行时序，来决定一个状态是否是安全的；不存在这满足要求的执行时序的状态都是不安全的。

银行家算法数据结构

n= 进程数量，m=资源类型数量

Max（总需求量）

nxm矩阵，如果Max[i,j] = k,表示进程Pi最多请求资源类型Rj的k个实例。

Available（剩余空闲量）

长度为m的向量。如果Available[j] = k，有空格类型Rj的资源实例可用。

Allocation（已分配量）

nxm矩阵，如果Allocation[i,j] = k,则Pi当前分配了k个Rj的实例

Need（未来需要量）

nxm矩阵，如果Need[i,j] = k，则Pi可能需要至少k个Rj实例完成任务
1Need[i, j] = Max[i ,j] - Allocation[i ,j]
安全状态的银行家算法
Work和Finish分别是长度m和n的向量

初始化
1Work = Avaliable;			//当前资源剩余空闲量
2Finish[i] = false; for 1-n	//线程i没结束
找这样的i
1(a)Finish[i] = false;
2(b)Need <= Work
没找到这样的i，转4
1Work = Work + Allocation;	//进程i的资源需求量小于当前剩余空闲资源量，所以配置给它在回收
2Finish[i] = true;
转2
1if Finish[i] == true; for all i //所有进程的Finish为true，表明系统处于安全状态
2Then the system is in a safe state.
举例说明

Max为所有进程需要资源矩阵，Need为所有进程当前需要资源矩阵。首先查找是否存在一个进程向量是小于等于可获取资源向量V的向量。

很明显可以找到这个P2的资源，然后等待P2进程结束，并释放对应的P2的资源。释放完成后，可可获取资源向量V就会增加到{6， 2, 3}。

这个时候查找是否存在一个进程向量是小于等于可获取资源向量V的向量，很明显P1进程。然后等待P1进程结束，并释放对应的P1的资源。释放完成后，可可获取资源向量V就会增加到{7， 2, 3}。

同理，可以找到P3进程。然后等待P3进程结束，并释放对应的P3的资源。释放完成后，可可获取资源向量V就会增加到{9， 3, 4}。

因此，这个得到的安全序列是P2–>P1–>P3–>P4。

但是，如果如果在当前某一时刻查找是否存在一个进程向量是小于等于可获取资源向量V的向量，找不到，那么就是不安全的状态。

11.4.3死锁检测

允许系统进入死锁状态
死锁检测算法

把资源分配图简化为等待图

资源类型的数据结构

Available

长度为M的向量表示每种类型可用资源的数量
Allocation

一个nxm矩阵定义了当前分配给各个进程每种类型资源的数量。如果Allocation[i, j] = k，进程Pi拥有资源Rj的k个实例
Request

一个nxm矩阵表示各进程的当前请求。如果Request[i, j] = k，表示进程Pi请求k个资源Rj的实例

死锁检测算法

虽然说死锁是可以被检测出来，但是检测的花销比较大，所以一般操作系统不回去检查

举例说明

可以看到下图11-5所示，资源ABC，分别资源类型为7,2,6种。可以看到在当前时候由于P0不需要额外的资源，等待P0结束，资源B的一个类型实例可以释放出来，同理P2也是不需要额外资源，等待P2资源释放，资源向量为{3, 1, 3}。那么剩余的进程中找是否存在申请资源小于可获得的资源，显然存在。那么以此类推可以得到序列P0–>P2–>P1–>P3–>P4

图11-5 死锁检测算法图

与刚才的例子相似，发现没有一个进程它所需要的资源能够得到满足，这种情况下可能会产生死锁。

检测算法使用

何时、使用什么样的频率来检测依赖于

死锁多久可能会发生

多少金城需要被回滚
如果检测算法多次被调用，有可能是资源图有多个循环，所以我们无法分辨出多个可能死锁进程中的哪些造成死锁。

11.4.4死锁恢复

终止所有的死锁进程
在一个时间内终止一个进程直到死锁消除
终止进程的顺序应该是

进程的优先级

进程运行了多久以及需要多少时间才能完成

进程占用的资源

进程完成需要的资源

多少进程需要被终止

进程是交互还是批处理
选择一个受害者-最小的成本
回滚-返回到一些安全状态，重启进程到安全状态
饥饿- 同以进程可能一直被选作受害者，包括回滚的数量

操作系统学习笔记 11死锁

400 Words|Read in about 2 Min|本文总阅读量次

0猜你喜欢

11死锁

11.1死锁问题

11.2系统模型