非剥夺资源的竞争和进程的不恰当推进顺序会导致死锁。
有 3 种方式可以解决死锁问题:
今天要讲的银行家算法就属于死锁避免。
银行家算法是最著名的死锁避免算法。
可用资源向量:Available
,是一个数组,表示现在系统中总共还有多少可用的资源。
例如:A B C 的 Available 是 [1,2,3]
表示现在系统中还有 A 类资源 1 个,B 类资源 2 个,C 类资源 3 个。
最大需求: Max
,是一个矩阵,表示某进程最多需要多少某资源,一行代表一个进程,一列代表一个资源。
例如:
A B C
P1 1 2 3
P2 4 5 6
P3 7 8 9
//P3 进程最多需要 C 类资源 9 个.
//P2 进程最多需要 B 类资源 5 个.
分配矩阵:Allocation
表示系统中现在某类资源分配给某进程的数量。
A B C
P1 1 2 3
P2 4 5 6
P3 7 8 9
//P3 进程现在已经分配了 C 类资源 9 个.
//P1 进程现在已经分配了 A 类资源 1 个.
需求矩阵:Need
,表示现在进程中尚需的各类资源数。
A B C
P1 1 2 3
P2 4 5 6
P3 7 8 9
//P1 进程现在还需要 C 类资源 3 个.
//P2 进程现在还需要 B 类资源 5 个.
Need 矩阵 = Max 矩阵 - Allocation 矩阵。
也很好理解,最多需要的数量减去现在已经给的数量就是还需要的数量。
矩阵的减法直接 对应位置
相减即可。
一般情况下,Max 矩阵和 Alocation 矩阵都是已知条件,求出 Need 矩阵是解题的第一步。
设 request
是进程 P 的请求向量,request[A] = K
表示进程 P 需要 A 类资源 K 个。
当 P 发出资源请求后,系统按照以下步骤进行检查。
request[A]
的值小于 need[P,A]
,也就是说如果现在请求的数量小于 need
矩阵中规定的他所需要的数量,那么就转到步骤 2 ;否则认为出错,因为他所请求的数量已经超过了他所宣布的最大值。
request[A]
的值小于 available[A]
,也就是说请求的值小于现在系统中有的值,则转向步骤 3 ;否则表示尚足够资源,进程 P 需要等待。
试探
着把资源分配给进程 P,并修改下面数据结构中的值:
Available = Available - request
;Allocation[P,A] = Allocation[P,A] + request[A]
;Need[P,A] = Need[P,A] - request[A]
;接下来看一下安全性算法是什么 ?
安全序列
为空;安全序列
;若找不到,则执行步骤 4;安全序列
后,可顺利执行,直至完成,并释放分配给它的资源,故应执行 Available = Available + Allocation[P]
,其中 Allocation[P]
表示进程 P 在 Allocation
矩阵中对应的行,返回步骤 2 。下面以一个例子来看一下:
假定系统中有 5 个进程 {P0,P1,P2,P3,P4}
和 3 类资源 {A,B,C}
,各类资源的数量分别是 10,5,7
,在 T0 时刻的资源分配表如下:
下面来做几道题目练习一下:
下面是我手写的解题过程,大家可以参考。
下面是我手写的解题过程,大家可以参考。
下面是我手写的解题过程,大家可以参考。