银行家算法代码实现， 以及求出全部的安全序列。

银行家算法

概述银行家算法概述

银行家算法就是一种避免死锁的一种机制，能够让进程有效的合理的分配资源

代码实现

不说废话，代码实现方式 ，解析日后：

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
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e3 + 10;
int m , n;
int Max[N][N], Allocation[N][N], Need[N][N], Available[N], temp[N];
bool finish[N], notExistSeq = true;
string ans;
/**
 * 银行家算法 ：
 * 声明几个对应的数组含义
 * max表示不同进程 对不同的资源 需要的最大的资源的个数
 * Allocation 表示已经分配的资源
 * need 表示 还需要分配的资源的个数
 * available 表示当前 可用的资源个数
 * m 表示列的个数 列代表对应的资源的种类的数量 资源 A  B  C .....
 * n 表示 行的个数， 对应代表了进程种类的数量 p0 p1 p2 p3  .....
 * ans 表示安全序列中一个答案
 */
void init() {
    cout << "依次 输入进程数量 和资源的数量 " << endl;
    cin >> n >> m;

    cout << "输入当前的可用资源" << endl;
    for (int i = 0; i < m; ++i)
        cin >> Available[i];

    cout << "依次输入最大的分配" << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> Max[i][j];


    cout << "依次输入当前已经分配的资源" << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++ )
            cin >> Allocation[i][j];

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++ )
            Need[i][j] = Max[i][j] - Allocation[i][j];
    // 矩阵转置
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
              // printf("%d  ", Allocation [j][i]);
               Available[i] -= Allocation [j][i];
        }
        temp[i] = Available[i];
    }
}
void showbaseinfo(){
    printf("\n  Max           Allocation      Need\n");
    for (int i = 0; i < n; i++ ){
        for (int j = 0; j < m; j++)
            printf("%3d", Max[i][j]);
        printf("%*s", 6, "");
        for (int j = 0; j < m; j++)
            printf("%3d",  Allocation[i][j]);
        printf("%*s", 6, "");
        for (int j = 0; j < m; j++)
            printf("%3d", Need[i][j]);
        printf("\n");
    }
    printf("\n初始的当前资源可用值为: \n");
    for (int i = 0; i < m; i++)
        printf("%d ", Available[i]);
    puts("");
}

void release(int row){
    for(int i = 0; i < m; i++)
        Available[i] += Allocation[row][i];
    finish[row] = true;
    ans += row + '0';
}

void rollBack(int row){
    for(int i = 0; i < m; i++)
        Available[i] -= Allocation[row][i];
    finish[row] = false;
    ans = string(ans, 0, ans.size() - 1);
}

bool couldRecheak(){
    for (int i = 0; i < n; i++)
        if (finish[i] == false) return true;
    return false;
}

bool getSafeSequence(){
    notExistSeq = true;
    for (int i = 0; i < n ; i++){
        if (finish[i] == false){
            bool flag = true;
            for (int j = 0; j < m; j++)
                if (Need[i][j] > Available[j])  flag = false;
            if (flag) release(i), notExistSeq = false;
        }
    }
    return !notExistSeq;
}

void recheak(){
    while (couldRecheak() && getSafeSequence());
}

void setdefault(){
    for (int i = 0; i < m; i ++) Available[i] = temp[i];
    for (int i = 0; i < n; i ++) finish[i] = false;
    ans = "";
}
/*
获取安全序列的同时需要检查
每次资源的分配 同时需要判断是否存在安全不能求解的情况
如果本次 两种for 都没有找到的的说明当前没有安全序列 可以求出 那么直接返回
对每次的获取完安全值的是时候需要进行安全序列的判断
确保能够输出安全序列的条件就是 当前的所有的进程全部 =执行完成即 资源在分配的过程中没有出现异常的形况
*/

void dfs(int cur){
     //递归的出口
     if (cur == n){
         printf("安全序列为%s\n", ans.c_str());
         return;
     }
     for (int i = 0 ; i < n; i ++){
        if (!finish[i]){
            bool flag = true;
            for (int j = 0; j < m; j++)
                if (Need[i][j] > Available[j])  flag = false;
            if (flag){
                release(i);
                dfs(cur + 1);
                rollBack(i);
            }
        }
     }
}
int main() {
    init();
    showbaseinfo();
    getSafeSequence();
    recheak();
    if (!notExistSeq){
        printf("当前资源分配的安全序列之一为%s", ans.c_str());
        printf("是否要出输全部的安全序列呢 ？yes(1) or (0)\n");
        int a;
        scanf("%d", &a);
        if (a) setdefault(), dfs(0);
        else printf("欢迎下次使用\n");
    }
    else printf("不存在安全的序列\n");
    return 0;
}

样例测试

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
/*

书中的案例：
5  3
10 5 7

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

如果分配为 不存在安全序列的值

5  3
0 1 0

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

*/