算法简介
银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
算法目的
为了了解系统的资源分配情况，假定系统的任何一种资源在任意时刻只能被一个进程使用，任何进程已经占用的资源只能由进程自己释放，而不能由其他进程抢占，当进程申请的资源不能满足时，必须等待。因此只要资源分配算法能保证进程的资源请求，且不出现循环等待，则系统不会出现死锁。
算法原理
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
- (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
- (2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
- (3)系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
- (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
安全性检查算法
- （1）设置两个工作向量Work=AVAILABLE;FINISH
- （2）从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<=Work;
如找到，执行（3)；否则，执行（4)
- (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work=Work+ALLOCATION;
Finish=true;
GOTO 2
算法流程图
算法C语言实现版本1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 |
#include<stdio.h> #define true 1 #define false 0 #define processNum 5 #define resourceNum 3 #define MAXINT 9999 typedef int bool; int available[resourceNum]={3,3,2}; int maxRequest[processNum][resourceNum]={7,5,3,3,2,2,9,0,2,2,2,2,4,3,3}; int allocation[processNum][resourceNum]={0,1,0,2,0,0,3,0,2,2,1,1,0,0,2}; int need[processNum][resourceNum]={7,4,3,1,2,2,6,0,0,0,1,1,4,3,1}; bool Finish[processNum]; int safeSeries[processNum]={MAXINT, MAXINT , MAXINT , MAXINT , MAXINT}; int request[resourceNum]; void Init() { int i, j; printf("输入进程数量、资源数量\n"); //scanf("%d %d",&processNum,&resourceNum); printf("输入当前资源可用数目\n"); for(i = 0; i < resourceNum; i++){ scanf("%d",&available[i]); } printf("输入最大需求矩阵\n"); for(i = 0; i < processNum; i++){ for(j = 0; j < resourceNum; j++){ scanf("%d",&maxRequest[i][j]); } } printf("输入分配矩阵\n"); for(i = 0; i < processNum; i++){ for(j = 0; j < resourceNum; j++){ scanf("%d",&allocation[i][j]); } } printf("输入当前需求矩阵\n"); for(i = 0; i < processNum; i++){ for(j = 0; j < resourceNum; j++){ scanf("%d",&need[i][j]); } } } void showInfo() { int i,j; printf("当前资源剩余："); for(j = 0; j < resourceNum; j++){ printf("%d ",available[j]); } printf("\n"); printf(" PID\t Max\t\tAllocation\tNeed\n"); for(i = 0; i < processNum; i++){ printf(" P%d\t",i); for(j = 0; j < resourceNum; j++){ printf("%d ",maxRequest[i][j]); } printf("\t\t"); for(j = 0; j < resourceNum; j++){ printf("%d ",allocation[i][j]); } printf("\t\t"); for(j = 0; j < resourceNum; j++){ printf("%d ",need[i][j]); } printf("\n"); } } bool isSafe() { int i,j,k; int trueFinished = 0; int work[resourceNum]; for(i = 0; i < resourceNum; i++){ work[i]=available[i]; } for(i = 0; i < processNum; i++){ Finish[i]=false; } i = 0; int temp = 0; while(trueFinished != processNum){ int j =0; if(Finish[i]!= true){ for(j = 0; j < resourceNum; j++){ if(need[i][j] > work[j]){break;} } } if(j == resourceNum){ Finish[i]=true; SafeInfo(work,i); for(k = 0; k < resourceNum; k++){ work[k]+=allocation[i][k]; } int k2; safeSeries[trueFinished++] = i; } i++; if(i >= processNum) { i = i % processNum; if(temp == trueFinished) break; } temp = trueFinished; } if(trueFinished == processNum){ printf("\n系统安全！\n\n安全序列为："); for(i = 0; i < processNum; i++){ printf("%d ",safeSeries[i]); } return true; } printf("******系统不安全！******\n"); return false; } void SafeInfo(int *work, int i) { int j; printf(" P%d\t",i); for(j = 0; j < resourceNum; j++){ printf("%d ",work[j]); } printf("\t\t"); for(j = 0; j < resourceNum; j++){ printf("%d ",need[i][j]); } printf("\t "); for(j = 0; j < resourceNum; j++){ printf("%d ",allocation[i][j]); } printf("\t\t"); for(j = 0; j < resourceNum; j++){ printf("%d ",allocation[i][j]+work[j]); } printf("\n"); } int main() { int i,j,curProcess; int wheInit = 0; printf("是否使用内置数据？0是，1否："); scanf("%d",&wheInit); if(wheInit) Init(); //可以不使用，选用内置的数据进行测试 printf("---------------------------------------------------------\n"); showInfo(); printf("\n系统安全情况分析\n"); printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n"); isSafe(); while(true){ printf("\n---------------------------------------------------------\n"); printf("\n输入要分配的进程："); scanf("%d",&curProcess); printf("\n输入要分配给进程P%d的资源：",curProcess); for(j = 0; j < resourceNum; j++){ scanf("%d", &request[j]); } for(j = 0; j < resourceNum; j++){ if(request[j] <= need[curProcess][j])continue; else{printf("ERROR！\n");break;} } if(j == resourceNum){ for(j = 0; j < resourceNum; j++){ if(request[j] <= need[curProcess][j])continue; else{printf("资源不足，等待中！\n");break;} } if(j == resourceNum){ for(j = 0; j < resourceNum; j++){ available[j] -= request[j]; allocation[curProcess][j] += request[j]; need[curProcess][j] -= request[j]; } printf("\n系统安全情况分析\n"); printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n"); if(isSafe()){ printf("分配成功！\n"); showInfo(); }else{ for(j = 0; j < resourceNum; j++){ available[j] += request[j]; allocation[curProcess][j] -= request[j]; need[curProcess][j] += request[j]; } printf("分配失败！\n"); showInfo(); } } } } } |
实现效果
安全性检查
分配资源与安全性检查
网站所有原创代码采用Apache 2.0授权
网站文章采用知识共享许可协议BY-NC-SA4.0授权
© 2018 • OmegaXYZ-版权所有 转载请注明出处
