银⾏家算法（使⽤DFS出所有安全序列）
背景
银⾏家算法
银⾏家算法是⼀种最有代表性的避免死锁的算法。在避免死锁⽅法中允许进程动态地申请资源，但系统在进⾏资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进⼊不安全状态，则分配，否则等待。为实现银⾏家算法，系统必须设置若⼲数据结构。
安全状态
系统能按某种进程推进顺序{P1，…，P n}为每个进程P i分配其所需资源，直⾄满⾜每个进程对资源的最⼤需求，使每个进程都可顺利地完成。
此时称{P1，…，P n}为安全序列。如果系统⽆法到这样⼀个安全序列，则称系统处于不安全状态。
并⾮所有不安全状态都必然会转为死锁状态，但当系统进⼊不安全状态后，就有可能进⼊死锁状态。反之，只要系统处于安全状态，系统便不会进⼊死锁状态。
因此，避免死锁的实质在于，系统在进⾏资源分配时，应⽤系统不进⼊不安全状态。cstring转为int
数据结构
1. 可利⽤资源向量Available
是个含有m个元素的数组，其中的每⼀个元素代表⼀类可利⽤的资源数⽬。如果Available[j]=K，则表⽰系统中现有Rj类资源K个。2. 最⼤需求矩阵Max
这是⼀个n×m的矩阵，它定义了系统中n个进程中的每⼀个进程对m类资源的最⼤需求。如果Max[i,j]=K，则表⽰进程i需要R j类资源的最⼤数⽬为K。
3. 分配矩阵Allocation
这也是⼀个n×m的矩阵，它定义了系统中每⼀类资源当前已分配给每⼀进程的资源数。如果Allocation[i,j]=K，则表⽰进程i当前已分得R j类资源的数⽬为K。
4. 需求矩阵Need。
这也是⼀个n×m的矩阵，⽤以表⽰每⼀个进程尚需的各类资源数。如果Need[i,j]=K，则表⽰进程i还需要R j类资源K个，⽅能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]
银⾏家算法
设Request i是进程P i的请求向量，如果Request i[j]=K，表⽰进程P i需要K个R j类型。当P i发出资源请求后，系统按下输步骤进⾏检查:
1. 如果Request i[j] <= Need[i][j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最⼤值
2. 如果Request i[j] <= Available[i][j]，便转向步骤3；否则表⽰尚⽆⾜够资源，P i需等待
3. 系统试探着把资源分配给进程P i，并修改下⾯数据结构中的数值:
1. Available[j] -= Request i[j]
2. Allocation[i][j] += Request i[j]
3. Need[i][j] -= Request i[j]
4. 系统执⾏安全性算法，检查此次资源分配后系统是否处于安全状态.若安全，正式将资源分配给进程P i，以完成本次分配；否则，讲将
本次的试探分配作废，恢复原来的资源分配状态，让进程P i等待
1 2 3 4 5 6 7 8 9 10bool check_bank(int i, int Request[]) //按照银⾏家算法检查资源请求 { for(int j = 0; j < m; j++) { if(Request[j] > Need[i][j] || Request[j] > Available[j]) return false; } update(i, Request); return true; }
尝试分配资源/恢复原来的资源分配状态尝试分配资源
1 2 3 4 5 6 7 8 9void update(int i, int Request[]) //更新数据 { for(int j = 0; j < m; j++) { Available[j] -= Request[j]; Allocation[i][j] += Request[j]; Need[i][j] -= Request[j]; } }
恢复原来的资源分配状态
1 2 3 4 5 6 7 8 9void recovery(int i, int Request[])//还原数据 { for(int j = 0; j < m; j++) { Available[j] += Request[j]; Allocation[i][j] -= Request[j]; Need[i][j] += Request[j]; } }
安全性算法
1. 设置两个⼯作向量:
① ⼯作向量WORK，它表⽰系统可提供给进程继续运⾏所需的各类资源数⽬，它含有m个元素，在执⾏安全算法开始
时，WORK:=Available
② Finish：它表⽰系统是否有⾜够的资源分配给进程，使之运⾏完成。初始Finish[i]: = false；当有⾜够资源分配给进程时，再令
Finish[i]：=true。
2. 从进程集合中出⼀个满⾜下列条件的进程：
① Finish[i] = false
② Need[i][j] <= work[j]
若到，执⾏3，否则，执⾏步骤4
3. 当进程p i获得资源后，可顺利执⾏，直⾄完成，并释放出分配给它的资源，故应执⾏:
Finish[i] = true
WORK[j] += Allocation[i][j]
go to step 2
1. 如果所有进程的Finish[i] = true，则表⽰系统处于安全性状态，否则，系统处于不安全状态。
1 2 3 4 5 6 7 8 9 10 11 12 13int check_safe(int i, int Request[]) //检查系统安全性 { int Work[MaxNumber]; bool Finished[MaxNumber]; memset(Finished, false, sizeof(Finished)); for(int i = 0; i < m; i++) Work[i] = Available[i]; sta = UnSafe; Dfs(0, Work, Finished); if(sta==UnSafe) recovery(i, Request);//还原数据 return sta; }
复杂度分析：安全性检查算法，有两种for循环，最内层for循环每次继续向下⼀层搜索，故时间复杂度为O((n * m)^ n)利⽤Dfs出所有安全序列
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 47void Dfs(int i, int Work[], bool Finished[])//深度优先搜索，到所有的安全序列 { if(i == n) { for(int j = 0; j < n; j++) {
if(Finished[j] == false) { return ; } } sta = Safe; SafeOrder.push_back(temp); //temp.clear(); return; } for(int j = 0; j < n; j++) { if(Finished[j] == false) { bool t = true; for(int k = 0; k < m; k++) { if(Need[j][k] > W
ork[k]) { t = false; break; } } if(t == true) { for(int k = 0; k < m; k++) Work[k] += Allocation[j][k]; Finished[j] = true; temp.push_back(j); Dfs(i + 1, Work, Finished); temp.pop_back(); //回溯，将第i个进程所做的改变恢复 for(int k = 0; k < m; k++) { Work[k] -= Allocation[j][k]; } Finished[j] = false; } } } return ; }
测试数据
3
A 3
B 3
C 2
5
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
0 1 0
2 0 0
3 0 2
2 1 1
0 0 2
2
1
1
2
实验截图
合理且安全的资源请求
不合理的资源请求
会导致系统处于不安全状态的资源请求完整代码
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
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 1
64 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 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299/* Problem：银⾏家算法 Author:QiZhao Data:2018-05-31 Description：预防进程死锁的银⾏家算法 Copyright 2018 QiZhao. All rights reserved. */ #include<iostream> #include<vector>//提供vector #include<cstring>//提供memset函数#include<cstdio>//提供fflush函数 #include<cstdlib>//提供exit函数 using namespace std; enum status {Safe, UnSafe};//安全性检查的结果 const int MaxNumber = 100;//进程数量的最⼤值 int Available[MaxNumber];//每种资源的可⽤数量 int Max[MaxNumber][MaxNumber];//n*m的矩阵，表⽰每个进程所需的最⼤资源量 string name[MaxNumber];//n个进程的进程名 int Allocation[MaxNumber][MaxNumber];//n*m的矩阵，表⽰每个进程每种资源已经分配的量 int Need[MaxNumber] [MaxNumber];//n*m的矩阵，表⽰每个进程还需的每种资源量 int Request[MaxNumber];//所请求的每种资源的资源量vector<vector<int> > SafeOrder;//存储所有的安全序列 vector<int> temp;//存储⼀个临时安全序列 int n, m;//进程数，资源种类数 status sta = UnSafe;//安全性检查的结果 //函数声明 void input(); void init(); void show(); void update(int i, int Request[]); void reco
very(int i, int Request[]); bool check_bank(int i, int Request[]); int check_safe(int i, int Request[]); void request(); void choose(); void Dfs(int i,int Wordk[],bool Finished[]); void menu(); //函数实现 void input()//读⼊数据 { cout << "请输⼊系统资源的种类数:"; cin >> m; cout << "请依次输⼊" << m << "种系统资源的名称与数量:" << endl; for(int i = 0; i < m; i++) cin >> name[i] >> Available[i]; cout << "请输⼊进程的数量:"; cin >> n; cout << "请输⼊各个进程的最⼤需求量<" << n << "*" << m << "矩阵>[MAX]" << endl; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) cin >> Max[i][j]; } cout << "请输⼊各进程已申请的资量<" << n << "*" << m << "矩阵>[Allocation]" << endl; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) cin >> Allocation[i][j]; } } void init()//计算Need { for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { Need[i][j] = Max[i][j] - Allocation[i][j]; } } } void show()//显⽰资源使⽤情况 { cout << " Max\tAllocation\tNeed\tAvaliable" << endl;
for(int j = 0; j < 4; j++) { if(j==3) cout<<" "; for(int i = 0; i < m; i++) { cout << name[i] << " "; if(j == 1) cout << " "; } cout << "\t"; } cout<<endl; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cout << Max[i][j] << " "; } cout << "\t"; for(int j = 0; j < m; j++) { cout << Allocation[i][j] << " "; } cout << "\t"; for(int j = 0; j < m; j++) { cout << Need[i][j] << " "; } cout << "\t ";
for(int j = 0; j < m; j++) { cout << Available[j] << " "; } cout << endl; } } void update(int i, int Request[]) //更新数据 { for(int j = 0; j < m; j++) { Available[j] -= Request[j]; Allocation[i][j] += Request[j]; Need[i][j] -=
Request[j]; } } void recovery(int i, int Request[])//还原数据 { for(int j = 0; j < m; j++) { Available[j] += Request[j]; Allocation[i][j] -= Request[j]; Need[i][j] += Request[j]; } } bool check_bank(int i, int Request[]) //按照银⾏家算法检查资源请求 { for(int j = 0; j < m; j++) {
if(Request[j] > Need[i][j] || Request[j] > Available[j]) return false; } update(i, Request); return true; } void Dfs(int i, int Work[], bool Finished[])//深度优先搜索，到所有的安全序列 { if(i == n) { for(int j = 0; j < n; j++) { if(Finished[j] == false) { return ; } } sta = Safe; SafeOrder.push_back(temp); //temp.clear(); return; } for(int j = 0; j < n; j++) { if(Finished[j] == false) { bool t = true; for(int k = 0; k < m; k++) { if(Need[j][k] > Work[k]) { t = false; break; } } if(t == true) { for(int k = 0; k < m; k++) Work[k] += Allocation[j][k]; Finished[j] = true; temp.push_back(j); Dfs(i + 1, Work, Finished);
temp.pop_back(); //回溯，将第i个进程所做的改变恢复 for(int k = 0; k < m; k++) { Work[k] -= Allocation[j][k]; } Finished[j] = false; } } } return ; } int check_safe(int i, int Request[]) //检查系统安全性 { int Work[MaxNumber]; bool
Finished[MaxNumber]; memset(Finished, false, sizeof(Finished)); for(int i = 0; i < m; i++) Work[i] = Available[i]; sta = UnSafe; Dfs(0, Work, Finished); if(sta==UnSafe) recovery(i, Request);//还原数据 return sta; } void request()//某个进程申请资源 { int i; memset(Request, 0, sizeof(Request)); cout << "请
输⼊要请求分配资源的进程号<0~" << n << ">:"; cin >> i; cout << "请输⼊进程" << i << "申请的资源数⽬" << endl; for(int j = 0; j < m; j++) { cout << name[j] << ":"; cin >> Request[j]; } SafeOrder.clear(); if(check_bank(i, Request) == true) { if(check_safe(i, Request) == Safe) { cout << "系统是安全的!" << endl; cout << "安全序列有:"<<SafeOrder.size()<<"种"<<endl; for(int j = 0; j < SafeOrder.size(); j++)//输出所有的安全序列 { for(int k = 0; k < SafeOrder[j].size(); k++) { cout << "P" << SafeOrder[j][k]; if(k != SafeOrder[j].size() -1) cout << "->"; } if(SafeOrder[j].size()!=0) cout << endl; } return; } else { cout << "系统不安全，恢复原来状态!" << endl; return; } } else cout << "资源请求不合理!" << endl; return; } void choose()//选择菜单 { char i = -1; while(true) {
fflush(stdin); cout << "请选择你要进⾏的操作" << endl; cin >> i; switch(i) { case '0': exit(0); break; case '2': request(); break; case '1': show(); break; default: cout << "输⼊有误，请重新输⼊" << endl; } menu(); } } void menu()//显⽰菜单 { cout << "****************银⾏家算法演⽰***************" << endl; cout << "\t\t1：显⽰各个矩阵的内容" << endl; cout << "\t\t2：进程请求系统分配资源" << endl; cout << "\t\t0：退出程序" << endl; cout << "*********************************************" << endl; } int main() { //freopen("in.txt", "r", stdin); //freopen("", "w", stdout); input(); init(); menu(); choose(); return 0; }
参考资料
，汤⼩丹，西安电⼦科技⼤学出版社，2014.5

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。