在C语言中使用银行家算法预防死锁
银行家算法是一种资源分配和避免死锁的算法,在执行 “s-state “检查以寻找潜在活动并确定是否应允许继续分配之前,模拟所有资源的预定最大可能量的资源分配。
为什么银行家的算法被称为
银行家的算法之所以有这样的标题,是因为它被运用于银行业,以确定是否授权向个人提供贷款。假设一家银行有n个账户持有人,每个人的个人余额为S。当有人要求贷款时,银行首先从其拥有的资金总额中扣除贷款金额,只有当余额超过S时才会批准贷款。之所以这样做,是因为如果每个账户持有人都来取钱,银行就能简单地做到。换句话说,银行绝不会以妨碍其满足所有客户要求的方式安排其资金。银行会努力在任何时候都保持安全。
银行家的算法是用以下数据结构实现的。
设n为系统中进程的数量,m为资源种类的数量。
可用的。
- 这个大小为’m’的1-d数组列出了当前可用的每一类资源的数量。
- 如果Available[j] = Rj,则有’k’个资源类型的实例。
最大。
- 系统中每个进程的最大需求由一个大小为’n*m’的二维数组指定。
- 如果Max[i, j] = k,则进程Pi最多可以请求’k’个资源类型Rj的实例。
分配。
- 当前分配给每个进程的每种资源的数量由一个大小为’n*m’的二维数组指定。
- 进程由Allocation[i, j] = k表示,Pi此时已经获得了’k’个资源类型的实例。Rj
需要。
- 每个进程的剩余资源需求显示在一个大小为’n*m’的二维数组中。
- 进程用Need[i, j] = k表示。现在,Pi需要 “k “个资源类型的实例。Rj
- Allocation[i, j] – Maximum[i, j] = Need[i, j)
现在分配给进程Pi的资源由Allocationi标识,而进程Pi为了完成工作可能还需要的额外资源则由Needi标识。
安全算法和资源请求算法构成了银行家的算法。
安全的算法
以下是对确定系统是否处于安全状态的方法的描述。
1) 假设Work和Finish是两个向量,每个向量的长度为m和n。
初始化。Work = Available
当i=1, 2, 3, 4...n时,Finish[i]为假。
2) 找到一个I,使其同时
a) Finish[i] = false
b) Needi <= Work
如果这样的I不存在,则转到步骤(4)
3) Work = Work + Allocation[i)
完成[i] = true
转到第(2)步
4) 如果每一个i的Finish[i] = true
那么系统就处于安全状态。
资源请求的算法
让Requesti代表进程Pi的请求阵列。进程Pi请求K个资源类型Rj的实例,用Requesti [j] = k表示。当进程Pi提出资源请求时,会发生以下事情。
1) 如果Requesti >= Needi,则进入第2步;否则,报告一个错误条件,因为该过程提出的要求超过了它所能处理的范围。
2) 如果Requesti <= Accessible,则进入步骤(3);否则,Pi将不得不等待,因为资源不可用。
3) 改变状态,使系统看起来已经给了Pi所需的资源。
请求-可用=可用
Allocationi = Allocationi + Requesti
Needi = Needi - Requesti
以下是银行家的算法的执行情况
// Banker's Algorithm
#include
int main()
{
// P0 , P1 , P2 , P3 , P4 are the Process names here
int n , m , i , j , k;
n = 5; // Number of processes
m = 3; // Number of resources
int alloc[ 5 ] [ 3 ] = { { 0 , 1 , 0 }, // P0 // Allocation Matrix
{ 2 , 0 , 0 } , // P1
{ 3 , 0 , 2 } , // P2
{ 2 , 1 , 1 } , // P3
{ 0 , 0 , 2 } } ; // P4
int max[ 5 ] [ 3 ] = { { 7 , 5 , 3 } , // P0 // MAX Matrix
{ 3 , 2 , 2 } , // P1
{ 9 , 0 , 2 } , // P2
{ 2 , 2 , 2 } , // P3
{ 4 , 3 , 3 } } ; // P4
int avail[3] = { 3 , 3 , 2 } ; // Available Resources
int f[n] , ans[n] , ind = 0 ;
for (k = 0; k < n; k++) {
f[k] = 0;
}
int need[n][m];
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
need[i][j] = max[i][j] - alloc[i][j] ;
}
int y = 0;
for (k = 0; k < 5; k++){
for (i = 0; i < n; i++){
if (f[i] == 0){
int flag = 0;
for (j = 0; j < m; j++) {
if(need[i][j] > avail[j]){
flag = 1;
break;
}
}
if ( flag == 0 ) {
ans[ind++] = i;
for (y = 0; y < m; y++)
avail[y] += alloc[i][y] ;
f[i] = 1;
}
}
}
}
int flag = 1;
for(int i=0;i " , ans[i]);
printf(" P%d ", ans[n - 1]);
}
return(0);
}
输出
Following is the SAFE Sequence
P1 -> P3 -> P4 -> P0 -> P2
........................................................
Process execute din 1.33 seconds
Press any key to continue.
解释。
- 进程在进入系统时必须预测所需资源的最大数量,这可能在合理的时间内完成。
- 与交互式系统相比,这种方法保持了固定数量的进程。
- 必须有特定数量的资源可供分配,才能使这种技术发挥作用。如果一个小工具坏了,意外下线,该算法将无法运作。
- 该方法将产生开销成本,因为当有几个进程和资源时,必须为每个进程调用该方法。