11:49
死锁死锁的定义鸵鸟算法死锁的防止死锁的避免死锁的检测解决死锁的混合策略
11:49
死锁的定义操作系统中的死锁基于如下假定：
任意一个进程要求资源的最大数量不超过系统能提供的最大量如果一个进程在执行中所提出的资源要求能够得到满足,那么它一定能在有限的时间内结束一个资源在任何时刻最多只为一个进程所占有一个进程一次申请一个资源,且只在资源得不到满足时才处于等待状态一个进程结束时释放它所占有的全部资源系统具有有限个进程和资源
11:49
死锁的定义操作系统中的死锁是指：系统中存在一组进程,其中每一个进程都在等待另一个进程所占有的且不可被强占的资源；即该组进程形成了循环等待资源的状态,这种等待永远不能结束死锁的产生是与资源分配策略和并发进程执行的速度有关
11:49
若干死锁的例子例１ 竞争资源产生死锁 。
设系统有打印机,读卡机各一台,它们被进程
Ｐ和Ｑ共享 。 两个进程并发执行,它们按下列次序请求和释放资源：
进程Ｐ 进程Ｑ
请求读卡机 请求打印机请求打印机 请求读卡机释放读卡机 释放读卡机释放打印机 释放打印机
11:49
例２ PV操作使用不当产生死锁进程 Q1 进程 Q2
……… ………
P(S1); P(s2);
P(s2); P(s1);
……… ………
使用 r1和 r2; 使用 r1和 r2
……… ………
V(S1); V(s2);
V(S2); V(S1);
11:49
例３ 资源分配不当引起死锁若系统中有 m个资源被 n个进程共享，
当每个进程都要求Ｋ个资源，而 m <
n·K时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。
11:49
例４ 对临时性资源使用不加限制引起的死锁在进程通信时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁。
11:49
3.6.3驼鸟算法最简单的方法是象鸵鸟一样对死锁视而不见
11:49
形成死锁的四个必要条件进程互斥使用资源申请新资源时不释放已占有资源一个进程不能抢夺其他进程占有的资源存在一组循环等待资源的进程
11:49
破坏第一个条件,使资源可同时访问而不是互斥使用,是个简单的办法,磁盘可用这种办法管理,
但有许多资源往往是不能同时访问的,所以这种做法许多场合行不通 。
采用剥夺式调度方法可以破坏第三个条件,但剥夺调度方法目前只适用于对主存资源和处理器资源的分配,当进程在申请资源未获准许的情况下,
如主动释放资源 (一种剥夺式 ),然后才去等待,以后再一起向系统提出申请,也能防止死锁,但这些办法不适用于所有资源 。
由于种种死锁防止办法施加于资源的限制条件太严格,会造成资源利用率和吞吐率低 。 下面介绍两种比较实用的死锁防止方法,它们能破坏第二个条件或第四个条件 。
11:49
静态分配策略（破坏条件 2）
所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源,
并且直到它所要的资源都得到满足后才开始执行 。
11:49
死锁的防止层次分配策略 （ 破坏条件 2和 4）
资源被分成多个层次当一个进程得到某一层的一个资源后,
它只能再申请较高层次的资源当一个进程要释放某层的一个资源时,
它必须先释放所占有的较高层次的资源当一个进程得到某一层的一个资源后,
它想申请该层的另一个资源时,必须先释放该层中的已占资源
11:49
层次 策略的一个变种是按序分配策略把系统的所有资源排一个顺序,例如,
系统若共有 n个进程,共有 m个资源,用 ri
表示第 i个资源,于是这 m个资源是：
r1,r2……,rm
规定如果进程不得在占用资源 ri(1≤ i≤ m)
后再申请 rj(j<i)。 不难证明，按这种策略分配资源时系统不会发生死锁。
11:49
反证法来证明按序分配不会产生死锁,
事实上,若在时刻 t1,进程 P1处于等资源 rk1的状态,则 rk1
必为另一进程假定是 P2所占用,若 P2在有限时间里可以运行结束,那么 P1就不会处于永远等待状态；所以一定在某个时刻 t2,进程 P2占有了资源 rk1而处于永远等待资源 rk2状态 。
如此推下去,按假定系统只有有限个进程,即必有某个 n，
在时刻 tn时,进程 Pn永远等待资源 rkn的状态,而 rkn必为前面的某一个进程 Pi占用 (1≤i<n)。 于是,按照上述的按序分配策略,当 P2占用了 rk1后再申请 rk2必有：
k1 ＜ k2
依此类推,可得：
k2 ＜ k3 ＜ … <ki<… ＜ kn
但是,由于进程 Pi是占有了 rkn却要申请 rki,那么,必定有：
kn < ki
这就产生了矛盾 。 所以按序分配策略可以防止死锁 。
11:49
死锁的避免银行家算法银行家拥有一笔周转资金客户要求分期贷款,如果客户能够得到各期贷款,就一定能够归还贷款,否则就一定不能归还贷款银行家应谨慎的贷款,防止出现坏帐用银行家算法避免死锁操作系统 （ 银行家 ）
操作系统管理的资源 (周转资金 )
进程 （ 要求贷款的客户 ）
11:49
单种资源的银行家算法对每一个请求进行检查,检查如果满足它是否会导致不安全状态 。 若是,则不满足该请求；
否则便满足检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户 。 如果可以,则这笔投资认为是能够收回的,然后接着检查下一个距最大需求最近的客户,如此反复下去 。 如果所有投资最终都被收回,则该状态是安全的,最初的请求可以批准系统拥有某类资源 10个进程 已有资源数 还要申请资源数
P 4 4
Q 2 2
R 2 7
11:49
4个客户，每个客户都有一个贷款额度
11:49
一个状态被称为是安全的其条件是存在一个状态序列能够使所有的客户均得到其所有的贷款 （ 即所有的进程得到所需的全部资源并终止 ） 。 图
5 -1（ b） 所示的状态是安全的,以使
Marvin运行结束,然后释放所有的 4个单位 资金 。 如 此这样下 去便可以 满足
Suzanne或者 Barbara的请求,等等 。
11:49
不安全的状态考虑假如给 Barbara另一个她申请的资源，
如图 3-8（ b）,则我们得到如图 3-8（ c）
所示的状态，该状态是不安全的。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。
11:49
资源轨迹图
11:49
多种资源的银行家算法总的资源 E,已分配资源 P,剩余资源 A
11:49
多种资源的银行家算法查找右边矩阵是否有一行,其未被满足的设备数均小于或等于向量 A。 如果找不到,则系统将死锁,因为任何进程都无法运行结束若找到这样一行,则可以假设它获得所需的资源并运行结束,将该进程标记为结束,并将资源加到向量 A上重复以上两步,直到所有的进程都标记为结束 。 若达到所有进程结束,则状态是安全的,否则将发生死锁
11:49
两阶段上锁算法第一阶段,进程试图将其所需的全部记录加锁,一次锁一个记录若成功,则数据进行更新并解锁若有些记录已被上锁,则它将已上锁的记录解锁并重新开始执行
11:49
3.6.5.4 银行家算法的数据结构和安全性测试算法考虑一个系统有 n个进程和 m种不同类型的资源,现定义包含以下向量和矩阵的数据结构：
11:49
l 系统每类资源总数 --该 m个元素的向量为系统中每类资源的数量 Resource=(R1,R2,…,Rm)
l 每类资源未分配数量 --该 m个元素的向量为系统中每类资源尚可供分配的数量：
Avilable=(V1,V2,…,Vm)
l 最大需求矩阵 --每个进程对每类资源的最大需求量,Cij表示进程 Pi需 Rj类资源最大数
C11 C12 C1m
C21 C22 C2m
．．．
Cn1 Cn2 Cnm
．．．
．．．
Claim=
11:49
l分配矩阵 — 表示进程当前已分得的资源数,Aij表示进程 Pi已分到 Rj类资源的个数
A11 A12 A1m
A21 A22 A2m
．．
．
An1 An2 Anm
．．
．
．．
．
Allocation=
11:49
于是下列关系式确保成立：
l Ri=Vi+∑Aki 对 i=1,..,m,k=1,..,n; 表示所有的资源要么已被分配,要么尚可分配
l Cki≤Rj 对 i=1,..,m,k=1,..,n; 表示进程申请资源数不能超过系统拥有的资源总数
l Aki ≤Cki 对 i=1,..,m,k=1,..,n; 表示进程申请任何类资源数不能超过声明的最大资源需求数
11:49
一种死锁避免策略：
系统中若要启动一个新进程工作,其对资源
Ri的需求仅当满足下列不等式：
Ri ≥ C (n+1)I + ∑C ki 对
i=1,..,m,k=1,..,n;
也就是说,应满足当前系统中所有进程对资源 Ri的最大资源需求数加上启动的新进程的最大资源需求数不超过系统拥有的最大数。该算法考虑了最坏的情况、即所有进程同时要使用他们声明的最大资源需求数。
11:49
系统安全性定义：
在时刻 T0系统是安全的,仅当存在一个进程序列 P1,..,Pn,对进程 Pk(k=1,..,n)满足公式
Cki-Aki≤Availablei+∑Aji
j=1,..,k-1;k=1,..,n;i=1,..,m
该序列称安全序列,其中公式左边表示进程 Pk尚缺少的各类资源 ;Availablei是 T0时刻系统尚可用于分配且为 Pk所想要的那类资源数 ;Aji的进程序列,则系统处于不安全状态 。
11:49
一个实例来说明系统所处的安全或不安全状态如果系统中共有五个进程和 A,B,C三类资源 ;A类资源共有 10个,B类资源共有 5
个,C类资源共有 7个 。 在时刻 T0,系统目前资源分配情况如下：
11:49
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
11:49
每个进程目前还需资源为 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
11:49
可以断言目前系统处于安全状态,因为,序列
{ P1,P3,P4,P2,P0}能满足安全性条件 。
11:49
现在假定进程 P1又要申请 1个 A类资源和 2个 C类资源,所以,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 1
11:49
我们要判定这个新状态是否安全?可以执行安全性测试算法,并且找到一个进程序列 {P1,P3,P4,P0,P2}能满足安全性条件,
因而,可正式把资源分配给进程 P1;然而,
系统若处在下面状态中,进程 P4请求资源
(3,3,0),由于可用资源不足,申请被系统拒绝 ;此时,系统能满足进程 P0的资源请求
(0,2,0);但可以看出系统已处于不安全状态了 。
11:49
银行家算法的基本思想是：
系统中的所有进程进入进程集合,在安全状态下系统收到一个进程的资源请求后,先把资源试探性分配给它。现在,系统用剩下的可用资源和每个进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。这时,把这个进程从集合中去掉,系统的剩余资源更多了,再反复执行上述步骤。最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可真正实施本次分配 ;否则,有进程执行不完，系统处于不安全状态,本次资源分配暂不实施,让申请进程等待。
11:49
银行家算法的程序及简短说明
Type state= record /*全局数据结构
resource,available:array[0… m-1]of integer;
claim,allocated:array[0… n-1,0… m-1]of
integer;
end /*资源分配算法
11:49
if alloc[i,*]+request[*]>claim[i,*] then <error> /*申请量超过最大需求量
else
if request[*]>available[*] then <suspend process.>
else /*模拟分配
< define newstate by:
allocation[i,*]:=allocation[i,*]+request[*]
available[*]:=available[*]-request[*] >
end;
if safe(newstate) then
< carry out allocation>
else
<restore original state>
< suspend process>
end
end
11:49
/*安全性测试算法 (banker’s algorithm)
function safe(state:s):boolean;
var currentavail:array{0… m-1} of integer;
rest:set of process;
begin
currentavail:=available;
rest:={all process};
possible:=true;
while possible do
find a Pk in rest such that
claim[k,*]-alloc[k,*]≤currentavail;
if found then
currentavail:=currentavail+allocation[k,*];
rest:=rest-[Pk];
else
possible:=false;
end
end;
safe:=(rest=null)
end.
11:49
再对上述算法作简短说明,
(1) 申请量超过最大需求量时出错,否则转 (2);
(2) 申请量超过目前系统拥有的可分配量时,挂起进程等待,否则转 (3);
(3) 系统对 Pi进程请求资源作试探性分配,执行：
allocation[i,*]:=allocation[i,*]+request[*]
available[*]:=available[*]-request[*]
(4) 执行安全性测试算法 (5),如果安全状态则承认试分配,否则抛弃试分配,进程 Pi等待 。
11:49
(5) 安全性测试算法
l定 义 工 作 向 量 currentavail 和 布 尔 型 标 志
possible; 初始化让
currentavail:=available,possible:=true;
l保持 possible:=true,从进 程集合 rest 中找出
claim[k,*]-alloc[k,*]≤currentavail的进程来,如找到,则释放这个进程 Pk的全部资源,执行以下操作 currentavail:=currentavail+allocation[k,*],把 Pk
从进程集合中去掉 rest:=rest-[Pk]; 否则
possible:=false,停止执行算法 ;
l最后查看进程集 rest,若为空集返回安全标记 ;
否则返回不安全标记 。
11:49
3.6.6 死锁的检测和解除第一种方法借助于死锁的安全性测试算法来实现 。
今定义布尔型向量 posible[k],k=1,..,n。 检测死锁算法如下：
currentavail:=available;
如果 claim[k,*]-alloc[k,*]=0,则 possible[k]:=true;否则
possible:=false;
在 rest中找一个进程 Pk,需满足条件：
(possible[k]=false&(request[*]≤currentavail)
若找到这样的 Pk便转 (4);否则转 (5);
currnetavail:=currentavail+allocation;possible[k]:=true;
然后转 (3);
如果对 k=1,..,n 若 possible[k]=true不成立,那么,系统出现了死锁,并且 possible[k]=false的 Pk为死锁进程 。
11:49
另一种死锁检测方法是可设置两张表格来记录进程使用资源的情况
11:49
死锁的检测进程占用资源表和进程等待资源表资源 占用进程
R1 P1
R2 P3
R3 P2
R4 P3
R5 P1
… …
… …
进程 等待资源
P1 R3
P2 R2
P3 R5
… …
11:49
死锁的检测进程等待占用关系矩阵
Bij 物理意义
1 Pi等待被 Pj占用的资源
0 Pi 和 Pj之间不存在等待占用关系
P1 P2 P3
P1 0 1 0
P2 0 0 1
P3 1 0 0
11:49
死锁的检测死锁的检测 —— Warshall传递闭包算法
For k,= 1 to n do
For i,= 1 to n do
For j,= 1 to n do
Bij,= Bij or (Bik and Bkj)
11:49
死锁的检测和解除往往配套使用,当死锁被检测到后，用各种办法解除系统的死锁，可采用以下一些办法。
l立即结束所有进程的执行,并重新启动操作系统 。
方法简单,但以前工作全部作废,损失可能很大 。
l撤销陷于死锁的所有进程,解除死锁继续运行 。
l逐个撤销陷于死锁的进程,回收其资源,直至死锁解除 。
l剥夺陷于死锁的进程占用的资源,但并不撤销它,
直至死锁解除 。
l根据系统保存的 checkpoint,让所有进程回退,直到足以解除死锁 。
l当检测到死锁时,如果存在某些未卷入死锁的进程,而这些进程随着建立一些新的抑制进程能执行到结束,则它们可能释放足够的资源来解除这个死锁 。
11:49
解决死锁的混合策略非死锁资源类：对某类资源 R采用一种分配策略后,任何时刻都不存在永远等待此类资源的进程,则在此分配策略下 R是非死锁资源类若规定占用 R类资源的进程在释放它所占用的 R类资源前不得申请任何资源,则 R类资源是非死锁资源类若允许从占用 R类资源的进程处强行夺取占用的 R类资源来重新分配,在适当时候再归还它,则 R类资源是非死锁资源类若规定占用 R类资源的进程在释放它所占用的 R类资源前不得申请 R类资源或其它任何死锁类资源,则 R类资源是非死锁资源类
11:49
解决死锁的混合策略安全资源组：对资源组中的各类资源规定分配策略后,若在任何时刻都不存在循环等待该组资源的进程队列,则该资源组是安全资源组若规定占用 R类资源的进程在释放它所占用的 R类资源前不得申请 R类资源,则 R类资源是安全的若对资源组 M的采用静态分配策略,则 M是安全的若对资源组 M的采用按序分配策略,则 M是安全的
11:49
解决死锁的混合策略无关资源组：对于两个资源组 M1和
M2,若在任何时刻都不同时存在两个进程,它们分别占用 M1和 M2中的资源而等待 M2和 M1中的资源,则说
M1和 M2是无关的若对资源组 M的采用静态分配策略,
则 M与任何资源组无关
11:49
解决死锁的混合策略性质 1：若 R1和 R2是非死锁资源类,则 R1
和 R2构成安全资源组性质 2：若 R是非死锁资源类,M是安全资源组,则 R和 M构成的资源组是安全的性质 3：若 M1和 M2是无关的安全资源组,
则 M1和 M2构成的资源组是安全的讨论：如果能把系统的全部资源划分成若干个非死锁资源类和若干个无关的安全资源组,那么在此种混合调度策略下,
系统的全部资源所组成的资源组是安全的,系统不会产生死锁
死锁死锁的定义鸵鸟算法死锁的防止死锁的避免死锁的检测解决死锁的混合策略
11:49
死锁的定义操作系统中的死锁基于如下假定：
任意一个进程要求资源的最大数量不超过系统能提供的最大量如果一个进程在执行中所提出的资源要求能够得到满足,那么它一定能在有限的时间内结束一个资源在任何时刻最多只为一个进程所占有一个进程一次申请一个资源,且只在资源得不到满足时才处于等待状态一个进程结束时释放它所占有的全部资源系统具有有限个进程和资源
11:49
死锁的定义操作系统中的死锁是指：系统中存在一组进程,其中每一个进程都在等待另一个进程所占有的且不可被强占的资源；即该组进程形成了循环等待资源的状态,这种等待永远不能结束死锁的产生是与资源分配策略和并发进程执行的速度有关
11:49
若干死锁的例子例１ 竞争资源产生死锁 。
设系统有打印机,读卡机各一台,它们被进程
Ｐ和Ｑ共享 。 两个进程并发执行,它们按下列次序请求和释放资源：
进程Ｐ 进程Ｑ
请求读卡机 请求打印机请求打印机 请求读卡机释放读卡机 释放读卡机释放打印机 释放打印机
11:49
例２ PV操作使用不当产生死锁进程 Q1 进程 Q2
……… ………
P(S1); P(s2);
P(s2); P(s1);
……… ………
使用 r1和 r2; 使用 r1和 r2
……… ………
V(S1); V(s2);
V(S2); V(S1);
11:49
例３ 资源分配不当引起死锁若系统中有 m个资源被 n个进程共享，
当每个进程都要求Ｋ个资源，而 m <
n·K时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。
11:49
例４ 对临时性资源使用不加限制引起的死锁在进程通信时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁。
11:49
3.6.3驼鸟算法最简单的方法是象鸵鸟一样对死锁视而不见
11:49
形成死锁的四个必要条件进程互斥使用资源申请新资源时不释放已占有资源一个进程不能抢夺其他进程占有的资源存在一组循环等待资源的进程
11:49
破坏第一个条件,使资源可同时访问而不是互斥使用,是个简单的办法,磁盘可用这种办法管理,
但有许多资源往往是不能同时访问的,所以这种做法许多场合行不通 。
采用剥夺式调度方法可以破坏第三个条件,但剥夺调度方法目前只适用于对主存资源和处理器资源的分配,当进程在申请资源未获准许的情况下,
如主动释放资源 (一种剥夺式 ),然后才去等待,以后再一起向系统提出申请,也能防止死锁,但这些办法不适用于所有资源 。
由于种种死锁防止办法施加于资源的限制条件太严格,会造成资源利用率和吞吐率低 。 下面介绍两种比较实用的死锁防止方法,它们能破坏第二个条件或第四个条件 。
11:49
静态分配策略（破坏条件 2）
所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源,
并且直到它所要的资源都得到满足后才开始执行 。
11:49
死锁的防止层次分配策略 （ 破坏条件 2和 4）
资源被分成多个层次当一个进程得到某一层的一个资源后,
它只能再申请较高层次的资源当一个进程要释放某层的一个资源时,
它必须先释放所占有的较高层次的资源当一个进程得到某一层的一个资源后,
它想申请该层的另一个资源时,必须先释放该层中的已占资源
11:49
层次 策略的一个变种是按序分配策略把系统的所有资源排一个顺序,例如,
系统若共有 n个进程,共有 m个资源,用 ri
表示第 i个资源,于是这 m个资源是：
r1,r2……,rm
规定如果进程不得在占用资源 ri(1≤ i≤ m)
后再申请 rj(j<i)。 不难证明，按这种策略分配资源时系统不会发生死锁。
11:49
反证法来证明按序分配不会产生死锁,
事实上,若在时刻 t1,进程 P1处于等资源 rk1的状态,则 rk1
必为另一进程假定是 P2所占用,若 P2在有限时间里可以运行结束,那么 P1就不会处于永远等待状态；所以一定在某个时刻 t2,进程 P2占有了资源 rk1而处于永远等待资源 rk2状态 。
如此推下去,按假定系统只有有限个进程,即必有某个 n，
在时刻 tn时,进程 Pn永远等待资源 rkn的状态,而 rkn必为前面的某一个进程 Pi占用 (1≤i<n)。 于是,按照上述的按序分配策略,当 P2占用了 rk1后再申请 rk2必有：
k1 ＜ k2
依此类推,可得：
k2 ＜ k3 ＜ … <ki<… ＜ kn
但是,由于进程 Pi是占有了 rkn却要申请 rki,那么,必定有：
kn < ki
这就产生了矛盾 。 所以按序分配策略可以防止死锁 。
11:49
死锁的避免银行家算法银行家拥有一笔周转资金客户要求分期贷款,如果客户能够得到各期贷款,就一定能够归还贷款,否则就一定不能归还贷款银行家应谨慎的贷款,防止出现坏帐用银行家算法避免死锁操作系统 （ 银行家 ）
操作系统管理的资源 (周转资金 )
进程 （ 要求贷款的客户 ）
11:49
单种资源的银行家算法对每一个请求进行检查,检查如果满足它是否会导致不安全状态 。 若是,则不满足该请求；
否则便满足检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户 。 如果可以,则这笔投资认为是能够收回的,然后接着检查下一个距最大需求最近的客户,如此反复下去 。 如果所有投资最终都被收回,则该状态是安全的,最初的请求可以批准系统拥有某类资源 10个进程 已有资源数 还要申请资源数
P 4 4
Q 2 2
R 2 7
11:49
4个客户，每个客户都有一个贷款额度
11:49
一个状态被称为是安全的其条件是存在一个状态序列能够使所有的客户均得到其所有的贷款 （ 即所有的进程得到所需的全部资源并终止 ） 。 图
5 -1（ b） 所示的状态是安全的,以使
Marvin运行结束,然后释放所有的 4个单位 资金 。 如 此这样下 去便可以 满足
Suzanne或者 Barbara的请求,等等 。
11:49
不安全的状态考虑假如给 Barbara另一个她申请的资源，
如图 3-8（ b）,则我们得到如图 3-8（ c）
所示的状态，该状态是不安全的。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。
11:49
资源轨迹图
11:49
多种资源的银行家算法总的资源 E,已分配资源 P,剩余资源 A
11:49
多种资源的银行家算法查找右边矩阵是否有一行,其未被满足的设备数均小于或等于向量 A。 如果找不到,则系统将死锁,因为任何进程都无法运行结束若找到这样一行,则可以假设它获得所需的资源并运行结束,将该进程标记为结束,并将资源加到向量 A上重复以上两步,直到所有的进程都标记为结束 。 若达到所有进程结束,则状态是安全的,否则将发生死锁
11:49
两阶段上锁算法第一阶段,进程试图将其所需的全部记录加锁,一次锁一个记录若成功,则数据进行更新并解锁若有些记录已被上锁,则它将已上锁的记录解锁并重新开始执行
11:49
3.6.5.4 银行家算法的数据结构和安全性测试算法考虑一个系统有 n个进程和 m种不同类型的资源,现定义包含以下向量和矩阵的数据结构：
11:49
l 系统每类资源总数 --该 m个元素的向量为系统中每类资源的数量 Resource=(R1,R2,…,Rm)
l 每类资源未分配数量 --该 m个元素的向量为系统中每类资源尚可供分配的数量：
Avilable=(V1,V2,…,Vm)
l 最大需求矩阵 --每个进程对每类资源的最大需求量,Cij表示进程 Pi需 Rj类资源最大数
C11 C12 C1m
C21 C22 C2m
．．．
Cn1 Cn2 Cnm
．．．
．．．
Claim=
11:49
l分配矩阵 — 表示进程当前已分得的资源数,Aij表示进程 Pi已分到 Rj类资源的个数
A11 A12 A1m
A21 A22 A2m
．．
．
An1 An2 Anm
．．
．
．．
．
Allocation=
11:49
于是下列关系式确保成立：
l Ri=Vi+∑Aki 对 i=1,..,m,k=1,..,n; 表示所有的资源要么已被分配,要么尚可分配
l Cki≤Rj 对 i=1,..,m,k=1,..,n; 表示进程申请资源数不能超过系统拥有的资源总数
l Aki ≤Cki 对 i=1,..,m,k=1,..,n; 表示进程申请任何类资源数不能超过声明的最大资源需求数
11:49
一种死锁避免策略：
系统中若要启动一个新进程工作,其对资源
Ri的需求仅当满足下列不等式：
Ri ≥ C (n+1)I + ∑C ki 对
i=1,..,m,k=1,..,n;
也就是说,应满足当前系统中所有进程对资源 Ri的最大资源需求数加上启动的新进程的最大资源需求数不超过系统拥有的最大数。该算法考虑了最坏的情况、即所有进程同时要使用他们声明的最大资源需求数。
11:49
系统安全性定义：
在时刻 T0系统是安全的,仅当存在一个进程序列 P1,..,Pn,对进程 Pk(k=1,..,n)满足公式
Cki-Aki≤Availablei+∑Aji
j=1,..,k-1;k=1,..,n;i=1,..,m
该序列称安全序列,其中公式左边表示进程 Pk尚缺少的各类资源 ;Availablei是 T0时刻系统尚可用于分配且为 Pk所想要的那类资源数 ;Aji的进程序列,则系统处于不安全状态 。
11:49
一个实例来说明系统所处的安全或不安全状态如果系统中共有五个进程和 A,B,C三类资源 ;A类资源共有 10个,B类资源共有 5
个,C类资源共有 7个 。 在时刻 T0,系统目前资源分配情况如下：
11:49
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
11:49
每个进程目前还需资源为 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
11:49
可以断言目前系统处于安全状态,因为,序列
{ P1,P3,P4,P2,P0}能满足安全性条件 。
11:49
现在假定进程 P1又要申请 1个 A类资源和 2个 C类资源,所以,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 1
11:49
我们要判定这个新状态是否安全?可以执行安全性测试算法,并且找到一个进程序列 {P1,P3,P4,P0,P2}能满足安全性条件,
因而,可正式把资源分配给进程 P1;然而,
系统若处在下面状态中,进程 P4请求资源
(3,3,0),由于可用资源不足,申请被系统拒绝 ;此时,系统能满足进程 P0的资源请求
(0,2,0);但可以看出系统已处于不安全状态了 。
11:49
银行家算法的基本思想是：
系统中的所有进程进入进程集合,在安全状态下系统收到一个进程的资源请求后,先把资源试探性分配给它。现在,系统用剩下的可用资源和每个进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。这时,把这个进程从集合中去掉,系统的剩余资源更多了,再反复执行上述步骤。最后,检查进程集合,若为空表明本次申请可行,系统处于安全状态,可真正实施本次分配 ;否则,有进程执行不完，系统处于不安全状态,本次资源分配暂不实施,让申请进程等待。
11:49
银行家算法的程序及简短说明
Type state= record /*全局数据结构
resource,available:array[0… m-1]of integer;
claim,allocated:array[0… n-1,0… m-1]of
integer;
end /*资源分配算法
11:49
if alloc[i,*]+request[*]>claim[i,*] then <error> /*申请量超过最大需求量
else
if request[*]>available[*] then <suspend process.>
else /*模拟分配
< define newstate by:
allocation[i,*]:=allocation[i,*]+request[*]
available[*]:=available[*]-request[*] >
end;
if safe(newstate) then
< carry out allocation>
else
<restore original state>
< suspend process>
end
end
11:49
/*安全性测试算法 (banker’s algorithm)
function safe(state:s):boolean;
var currentavail:array{0… m-1} of integer;
rest:set of process;
begin
currentavail:=available;
rest:={all process};
possible:=true;
while possible do
find a Pk in rest such that
claim[k,*]-alloc[k,*]≤currentavail;
if found then
currentavail:=currentavail+allocation[k,*];
rest:=rest-[Pk];
else
possible:=false;
end
end;
safe:=(rest=null)
end.
11:49
再对上述算法作简短说明,
(1) 申请量超过最大需求量时出错,否则转 (2);
(2) 申请量超过目前系统拥有的可分配量时,挂起进程等待,否则转 (3);
(3) 系统对 Pi进程请求资源作试探性分配,执行：
allocation[i,*]:=allocation[i,*]+request[*]
available[*]:=available[*]-request[*]
(4) 执行安全性测试算法 (5),如果安全状态则承认试分配,否则抛弃试分配,进程 Pi等待 。
11:49
(5) 安全性测试算法
l定 义 工 作 向 量 currentavail 和 布 尔 型 标 志
possible; 初始化让
currentavail:=available,possible:=true;
l保持 possible:=true,从进 程集合 rest 中找出
claim[k,*]-alloc[k,*]≤currentavail的进程来,如找到,则释放这个进程 Pk的全部资源,执行以下操作 currentavail:=currentavail+allocation[k,*],把 Pk
从进程集合中去掉 rest:=rest-[Pk]; 否则
possible:=false,停止执行算法 ;
l最后查看进程集 rest,若为空集返回安全标记 ;
否则返回不安全标记 。
11:49
3.6.6 死锁的检测和解除第一种方法借助于死锁的安全性测试算法来实现 。
今定义布尔型向量 posible[k],k=1,..,n。 检测死锁算法如下：
currentavail:=available;
如果 claim[k,*]-alloc[k,*]=0,则 possible[k]:=true;否则
possible:=false;
在 rest中找一个进程 Pk,需满足条件：
(possible[k]=false&(request[*]≤currentavail)
若找到这样的 Pk便转 (4);否则转 (5);
currnetavail:=currentavail+allocation;possible[k]:=true;
然后转 (3);
如果对 k=1,..,n 若 possible[k]=true不成立,那么,系统出现了死锁,并且 possible[k]=false的 Pk为死锁进程 。
11:49
另一种死锁检测方法是可设置两张表格来记录进程使用资源的情况
11:49
死锁的检测进程占用资源表和进程等待资源表资源 占用进程
R1 P1
R2 P3
R3 P2
R4 P3
R5 P1
… …
… …
进程 等待资源
P1 R3
P2 R2
P3 R5
… …
11:49
死锁的检测进程等待占用关系矩阵
Bij 物理意义
1 Pi等待被 Pj占用的资源
0 Pi 和 Pj之间不存在等待占用关系
P1 P2 P3
P1 0 1 0
P2 0 0 1
P3 1 0 0
11:49
死锁的检测死锁的检测 —— Warshall传递闭包算法
For k,= 1 to n do
For i,= 1 to n do
For j,= 1 to n do
Bij,= Bij or (Bik and Bkj)
11:49
死锁的检测和解除往往配套使用,当死锁被检测到后，用各种办法解除系统的死锁，可采用以下一些办法。
l立即结束所有进程的执行,并重新启动操作系统 。
方法简单,但以前工作全部作废,损失可能很大 。
l撤销陷于死锁的所有进程,解除死锁继续运行 。
l逐个撤销陷于死锁的进程,回收其资源,直至死锁解除 。
l剥夺陷于死锁的进程占用的资源,但并不撤销它,
直至死锁解除 。
l根据系统保存的 checkpoint,让所有进程回退,直到足以解除死锁 。
l当检测到死锁时,如果存在某些未卷入死锁的进程,而这些进程随着建立一些新的抑制进程能执行到结束,则它们可能释放足够的资源来解除这个死锁 。
11:49
解决死锁的混合策略非死锁资源类：对某类资源 R采用一种分配策略后,任何时刻都不存在永远等待此类资源的进程,则在此分配策略下 R是非死锁资源类若规定占用 R类资源的进程在释放它所占用的 R类资源前不得申请任何资源,则 R类资源是非死锁资源类若允许从占用 R类资源的进程处强行夺取占用的 R类资源来重新分配,在适当时候再归还它,则 R类资源是非死锁资源类若规定占用 R类资源的进程在释放它所占用的 R类资源前不得申请 R类资源或其它任何死锁类资源,则 R类资源是非死锁资源类
11:49
解决死锁的混合策略安全资源组：对资源组中的各类资源规定分配策略后,若在任何时刻都不存在循环等待该组资源的进程队列,则该资源组是安全资源组若规定占用 R类资源的进程在释放它所占用的 R类资源前不得申请 R类资源,则 R类资源是安全的若对资源组 M的采用静态分配策略,则 M是安全的若对资源组 M的采用按序分配策略,则 M是安全的
11:49
解决死锁的混合策略无关资源组：对于两个资源组 M1和
M2,若在任何时刻都不同时存在两个进程,它们分别占用 M1和 M2中的资源而等待 M2和 M1中的资源,则说
M1和 M2是无关的若对资源组 M的采用静态分配策略,
则 M与任何资源组无关
11:49
解决死锁的混合策略性质 1：若 R1和 R2是非死锁资源类,则 R1
和 R2构成安全资源组性质 2：若 R是非死锁资源类,M是安全资源组,则 R和 M构成的资源组是安全的性质 3：若 M1和 M2是无关的安全资源组,
则 M1和 M2构成的资源组是安全的讨论：如果能把系统的全部资源划分成若干个非死锁资源类和若干个无关的安全资源组,那么在此种混合调度策略下,
系统的全部资源所组成的资源组是安全的,系统不会产生死锁
