C++实现银行家算法 - LINKONG's Blog

出现背景#

用来避免操作系统在资源调度中出现的死锁问题。并由此诞生的安全性检测，用来进行模拟资源分配。在资源分配给进程之前，判断当前系统是否可以找到满足条件的安全队列。

死锁: 请求资源的进程的不到必要的资源，并且自身占有其它进程所请求的资源，却不释放所导致的系统资源卡死。

属性分析#

每个进程拥有: Max, Allocation属性，前者代表进程申请的每种资源的最大值，后者代表进程当前已经占有的各种资源数量。多个进程Max属性会构成二维Max矩阵，多个进程Allocation属性会构成二维Allocation矩阵。
计算机拥有: Availbale，用于记录当前计算机中每种资源所拥有的数量。

安全性检查#

实现逻辑:

由Max矩阵与Allocation矩阵相减，得到进程当前剩余需求的二维Need矩阵。
创建Available的副本work用于模拟资源调度。
将当前所有进程的状态信息标记为false并记录在一维finish矩阵中，等待调用。
在二维Need矩阵中循环查找满足条件work[i] >= Need[~][i]的进程，分配并回收资源至work矩阵中，将该进程记录进满足的输出队列safeSequence中，同时将该进程的状态信息标记为true修改对应的finish矩阵中。
循环 步骤4 直至全部进程状态被标记为true或者找不到符合的目标进程时，退出程序，并根据程序进行判断。

参考代码#

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
const int MAX_PROCESS = 5;
7
const int MAX_RESOURCE = 3;
8

9
void need(vector<vector<int>> &Max, vector<vector<int>> &Allocation,
10
          vector<vector<int>> &Need) {
11
  for (int i = 0; i < MAX_PROCESS; i++) {
12
    for (int j = 0; j < MAX_RESOURCE; j++) {
13
      Need[i][j] = Max[i][j] - Allocation[i][j];
14
    }
15
  }
16
}
17

18
bool isSafe(vector<int> &Available, vector<vector<int>> &Allocation,
19
            vector<vector<int>> &Need, vector<int> &safeSequence) {
20
  int n = Allocation.size();
21
  int m = Available.size();
22

23
  vector<bool> finish(n, false);
24
  vector<int> work = Available;
25
  safeSequence.clear();
26

27
  int count = 0;
28
  while (count < n) {
29
    bool found = false;
30
    for (int i = 0; i < n; i++)
31
      if (!finish[i]) {
32
        bool canAllocate = true;
33
        for (int j = 0; j < m; j++) {
34
          if (work[j] < Need[i][j]) {
35
            canAllocate = false;
36
            break;
37
          }
38
        }
39

40
        if (canAllocate) {
41
          for (int j = 0; j < m; j++) {
42
            work[j] += Allocation[i][j];
43
          }
44
          finish[i] = true;
45
          count++;
46
          found = true;
47
          safeSequence.push_back(i);
48
        }
49
      }
50
      if (!found) return false;
51
    }
52
  return true;
53
}
54

55
int main() {
56
  vector<int> Available = {3, 3, 2};
57
  vector<vector<int>> Max = {
58
      {7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
59
  vector<vector<int>> Allocation = {
60
      {0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
61

62
  vector<vector<int>> Need(MAX_PROCESS, vector<int>(MAX_RESOURCE));
63
  need(Max, Allocation, Need);
64

65
  vector<int> safeSequence;
66
  if (isSafe(Available, Allocation, Need, safeSequence)) {
67
    cout << "safe:";
68
    for (int i = 0; i < safeSequence.size(); i++)
69
      cout << safeSequence[i] << ' ';
70
    cout << endl;
71
  } else {
72
    cout << "note safe" << endl;
73
  }
74
}