1.1银行家算法的简介
我们可以把操作系统看作是银行家，操作系统管 理的资源相当于银行家管理的资金，进程向操作系统 请求分配资源相当于用户向银行家贷款。操作系统按 照银行家制定的规则为进程分配资源，当进程首次申 请资源时，要测试该进程对资源的最大需求量，如果 系统现存的资源可以满足它的最大需求量则按当前的 申请量分配资源，否则就推迟分配。当进程在执行中 继续申请资源时，先测试该进程已占用的资源数与本 次申请的资源数之和是否超过了该进程对资源的最大 需求量。若超过则拒绝分配资源，若没有超过则再测 试系统现存的资源能否满足该进程尚需的最大资源量， 若能满足则按当前的申请量分配资源，否则也要推迟 分配。
2，0，1，2
P4
4，3，6，6
P5
4，6，9，8
• P5执行后，不能继续执行下去，则该状态不安全，系统将拒绝资源请求。
1.4银行家算法的实现
1.3银行家算法
3) Work:=Work+Allocation[i]; Finish[i]:=true; 转(1)
(4) 若对所有i,Finish[i]=true,则系统处 于安全状态，否则处于不安全状态
1.3银行家算法
例题：假设某系统中有4个 资源(R1、R2、R3、R4)， 在某个时刻系பைடு நூலகம்中共有5个
进程等待
1.3银行家算法
为进行安全性检查，定义数据结构： Work:ARRAY[1..m] of integer; Finish:ARRAY[1..n] of Boolean; 安全性检查的步骤： (1) Work:=Available;
Finish:=false; (2) 寻找满足条件的i：
a.Finish[i]=false; b.Need[i]≤Work; 如果不存在，则转(4)
（1）若Request[i]≤Need[i],转（2）； 否则错误返回
（2）若Request[i]≤Available, 转（3）；否则进程等待
1.3银行家算法
(3）假设系统分配了资源，则有： Available:=Available-Request[i]; Allocation[i]:=
Allocation[i]+Request[i]; Need[i]:=Need[i]-Request[i] 若系统新状态是安全的，则分配完成 若系统新状态是不安全的，则恢复原状态，
0,0,0,0
P2 2,0,0,0 2,7,5,0
0,7,5,0
P3 0,,3,4
6,6,5,6
6,5,2,2
P4 2,3,5,4 4,3,5,6
2,0,0,2
P5 0,3,3,2 0,6,5,2
0,3,2,0
1.3银行家算法
则新的执行过程如下表所示：
进程
可用资源数（剩余资源数+已分配资源数）
P1
2，1，1，2
P4
4，4，6，6
P5
4，7，9，8
P2
P3
• 则该状态是安全的
6，7，9，8 6，7，12，12
1.3银行家算法
（2）假设P3发出资源请求（0，1，0，0），系统分配给它，则系统还剩 余资源（2，0，0，0），并且状态如下表所示：
进程 已分配资 最大资源需求 仍需要资源 源
P1 0,0,1,2 0,0,1,2
进程 已分配 资源
进程，进程P1，P2，P3， P4，P5的最大资源需求数
P1
0,0,1,2
向量和此时已经分配到的 资源数向量分别如表所示：
P2
2,0,0,0
系统中当前可用资源向量 为（2，1，0，0），问：
P3 0,0,3,4
（1）当前系统是否安全 ? P4
（2）如果进程p3发出资源
请求向量（0，1，0，0）， P5
(安全状态一定是没有死锁发生的)
1.3银行家算法
n：系统中进程的总数 m：资源类总数 Available:
ARRAY[1..m] of integer; Max:
ARRAY[1..n,1..m] of integer;
1.3银行家算法
Allocation: ARRAY[1..n,1..m] of integer;
1.2银行家算法的用途
银行家算法是一种用来避免死锁的算法。
1.2.1死锁的定义
一组进程中，每个进程都无限等待 被该组进程中另一进程所占有的资源， 因而永远无法得到的资源，这种现象 称为进程死锁，这一组进程就称为死 锁进程。
1.2.2死锁的避免
定义： 在系统运行过程中，对进程发出的每
一个系统能够满足的资源申请进行动 态检查，并根据检查结果决定是否分 配资源，若分配后系统可能发生死锁， 则不予分配，否则予以分配。
P2 2,0,0,0 2,7,5,0
0,7,5,0
P3 0,0,3,4 6,6,5,6
6,6,2,2
P4 2,3,5,4 4,3,5,6
2,0,0,2
P5 0,3,3,2 0,6,5,2
0,3,2,0
1.3银行家算法
则存在以下执行序列，执行过程列表如下：
进程 P1
可用资源数（剩余资源数+已分配资 源数）
系统能否将资源分配给它？
2,3,5,4 0,3,3,2
最大资 源需求
0,0,1,2 2,7,5,0 6,6,5,6
4,3,5,6 0,6,5,2
1.3银行家算法
解：（1）调整表格如下：可用资源（2，1，0，0）
进程 已分配资源 最大资源需 仍需要资源 求
P1 0,0,1,2 0,0,1,2
0,0,0,0
1.2.2死锁的避免
安全状态：如果存在一个由系统中所有进 程构成的安全序列P1，…，Pn，则系统处 于安全状态。安全状态一定是没有死锁发 生。
不安全状态:不存在一个安全序列。不安全 状态一定导致死锁。
1.2.2死锁的避免
安全序列： 一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程 Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余 资源量与所有进程Pj ( j < i )当前占有资源量之和，系统处 于安全状态。
Need: ARRAY[1..n,1..m] of integer;
Request: ARRAY[1..n,1..m] of integer;
1.3银行家算法
简记符号： Available[i] Max[i] Allocation[i] Need[i] Request[i]
1.3银行家算法
当进程pi提出资源申请时，系统执行下 列步骤：