3.6 死锁

教学内容：

3.6.4 死锁的避免(△□) 3.6.5 死锁的检测和解除

教学时数：

2学时

教学进程：

3.6.4死锁的避免

银行家算法

银行家拥有一笔周转资金,客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款,银行家应谨慎的贷款，防止出现坏帐。

用银行家算法避免死锁

操作系统（银行家）

操作系统管理的资源(周转资金) 进程（要求贷款的客户）

单种资源的银行家算法

进程 P Q R 系统拥有某资源10个 已有资源数 4 2 2 还需资源数 4 2 7 对每个请求进行检查，是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准.

4个客户每个都有一个贷款额度

一个状态被称为是安全的

条件是存在一个状态序列能够使所有的客户均得到其所有的贷款。

上图所示状态是安全的，以使Marvin运行结束，释放所有的4个单位资金。这样下去便可满足Suzanne或Barbara的请求。

不安全的状态

考虑给Barbara另一个她申请的资源，则得到的状态是不安全的。

如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。

多种资源的银行家算法

总的资源E、 已分配资源P、 剩余资源A

查找右边矩阵是否有一行，其未被满足的设备数均小于或等于向量A。如果找不到，系统将死锁，任何进程都无法运行结束

若找到这样一行，可以假设它获得所需的资源并运行结束，将该进程标记为结束，并将资源加到向量A上重复以上两步，直到所有进程都标记为结束，则状态是安全的，否则将发生死锁

资源轨迹图

两阶段上锁算法

第一阶段，进程试图将其所需全部记录加锁，一次锁一个记录 若成功，则数据进行更新并解锁

若有些记录已被上锁，则它将已上锁的记录解锁并重新开始执行

银行家算法的数据结构

考虑一个系统有n个进程和m种不同类型的资源,现定义包含以下向量和矩阵的数据结构： ?系统每类资源总数--该m个元素的向量为系统中每类资源的数量 Resource=(R1,R2,?,Rm)

?每类资源未分配数量--该m个元素的向量为系统中每类资源尚可供分配的数量 Avilable=(V1,V2,?,Vm)

最大需求矩阵--每个进程对每类资源的最大需求量,Cij表示进程Pi需Rj类资源最大数

?C11?C?21Claim????????Cn1C12C22??Cn2????A12A22??An2????????C1m?C2m???? ???Cnm??????A1n?A2n???? ???Anm??分配矩阵—表示进程当前已分得的资源数,Aij表示进程Pi已分到Rj类资源的个数

?A11?A?21Allocation????????An1

银行家算法中

下列关系式确保成立

? Ri=Vi+∑Aki 对i=1,..,m,k=1,..,n; 表示所有资源要么已被分配、要么尚可分配 ? Cki ≤Rj 对i=1,..,m,k=1,..,n; 表示进程申请资源数不能超过系统拥有的资源总数

? Aki ≤Cki 对i=1,..,m,k=1,..,n; 表示进程申请任何类资源数不能超过声明的最大资源需求数

一种死锁避免策略

系统中若要启动一个新进程工作,其对资源Ri的需求仅当满足下列不等式： Ri ≥ C(n+1)I + ∑Cki 对i=1,..,m,k=1,..,n;

即应满足当前系统中所有进程对资源Ri的最大资源需求数加上启动的新进程的最大资源需求数不超过系统拥有的最大数。

系统安全性定义

在时刻T0系统是安全的,仅当存在一个进程序列P1,..,Pn,对进程Pk(k=1,..,n)满足公式 Cki-Aki≤Availablei+∑Aji , j=1,..,k;k=1,..,n;i=1,..,m

该序列称安全序列,公式左边表示进程Pk尚缺少的各类资源;Availablei是T0时刻系统尚可

用于分配且为Pk所想要的那类资源数; ∑Aji表示排在进程Pk之前的所有进程占用的Pk所需要的资源的总数。

实例说明系统所处的安全或不安全状态

如果系统中共有五个进程和A、B、C三类资源;A类资源共有10个,B类资源共有5个,C类资源共有7个。

在时刻T0,系统目前资源分配情况如下：

process Allocation Claim Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3

每个进程目前还需资源为Cki-Aki

process Cki-Aki

A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1

进程P1申请资源request1=(1,0,2) ,检查request1≤Available、比较(1,0,2) ≤(3,3,2),结果满足条件,试分配,得到新状态：

process Allocation Claim Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3

判定新状态是否安全?可执行安全性测试算法，找到一个进程序列{P1,P3,P4,P0,P2}能满足安全性条件,可正式把资源分配给进程P1;

系统若处在下面状态中, 进程P4请求资源(3,3,0),由于可用资源不足,申请被系统拒绝;此时, 系统能满足进程P0的资源请求(0,2,0);但可看出系统已处于不安全状态了。

银行家算法的基本思想

系统中的所有进程进入进程集合,在安全状态下系统收到进程的资源请求后,先把资源试探性分配给它。

系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。

把这个进程从集合中去掉, 系统的剩余资源更多了,反复执行上述步骤。

最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可实施本次分配;否则,有进程执行不完，系统处于不安全状态,本次资源分配暂不实施,让申请进程等待。