Banker's Algorithm
银行家算法是一种死锁避免算法
安全状态 ：存在一个进程序列<P1,P2,P3…Pn>，如果对于每个Pi可以申请的资源数小于当前可用资源加上所有进程占有的资源，那么就称这一顺序为安全序列，如果系统有一个安全序列，则处于安全状态
系统维护几种数据结构
avaliable ：表示某种资源现有的实例个数，若avaliable[i] = k，表示资源 j 有 k 个
max ：N * M 阶矩阵，若max[i][j] = k，表示进程i最多可申请 k 个资源 j
allocation ：N * M 阶矩阵，若allocation[i][j] = k，表示进程 i 已经分配了 k 个资源 j
need： N * M 阶矩阵，若need[i][j] = k，表示进程 i 还需要 k 个资源 j
对于进程 i 的请求 request 向量，先使用资源请求算法模拟资源分配，然后使用安全性算法检查系统是否处于安全状态，如果是则完成请求，否则恢复状态并等待
核心代码
1
2
3
4
5
6
7
#define PROCESS_NUMS 5
#define SOURCE_NUMS 3
std::vector<int> avaliable;
std::vector<std::vector<int>> max;
std::vector<std::vector<int>> allocation;
std::vector<std::vector<int>> need;
安全性算法
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
bool isSafe() {
std::vector<int> work(avaliable);
std::vector<bool> finish(PROCESS_NUMS, false);
while (true) {
bool found = false;
for (int i = 0; i != PROCESS_NUMS; ++i) {
if (finish[i] == false) {
int num = 0;
for (int j = 0; j != SOURCE_NUMS; ++j){
if (need[i][j] <= work[j])
num++;
}
if (num == SOURCE_NUMS) {
finish[i] = true;
for (int j = 0; j != SOURCE_NUMS; ++j)
work[j] += allocation[i][j];
found = true;
}
}
}
if (found == false)
break;
}
for (int i = 0; i != PROCESS_NUMS; ++i)
if (finish[i] == false)
return false;
return true;
}
资源请求算法
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
int request(int pid, std::vector<int>& request) {
for (int i = 0; i != SOURCE_NUMS; ++i)
if (request[i] > need[pid - 1][i])
/* 报错 */
return -1;
for (int i = 0; i != SOURCE_NUMS; ++i)
if (request[i] > avaliable[i])
/* 等待 */
return 0;
std::vector<int> avaliable_cp(avaliable);
std::vector<int> allocation_cp(PROCESS_NUMS);
std::vector<int> need_cp(PROCESS_NUMS);
for (int i = 0; i != SOURCE_NUMS; ++i) {
/* 保存状态 */
allocation_cp[i] = allocation[pid - 1][i];
need_cp[i] = need[pid - 1][i];
/* 模拟分配 */
avaliable[i] -= request[i];
allocation[pid - 1][i] += request[i];
need[pid - 1][i] -= request[i];
}
/* 安全,完成分配 */
if (isSafe())
return 1;
/* 不安全,恢复状态 */
else {
for (int i = 0; i != SOURCE_NUMS; ++i) {
avaliable[i] = avaliable_cp[i];
allocation[pid - 1][i] = allocation_cp[i];
need[pid - 1][i] = need_cp[i];
}
return 0;
}
}