C++银行家算法代码实现 |21xrx.com

C++银行家算法代码实现

2023-07-06 08:38:19 深夜i -- --

C++ 银行家算法代码实现计算机科学操作系统

银行家算法（Banker's algorithm）是解决进程控制中的资源分配与回收问题的经典算法，它可以避免死锁的产生。在本文中，我们将介绍如何使用C++实现银行家算法。

首先，我们需要了解银行家算法的原理。银行家算法的核心思想是通过预测系统对进程请求资源的需求量，来判断该进程是否可以安全地分配资源。银行家算法的主要步骤包括：

1. 初始化进程及资源的状态。

2. 模拟进程请求资源的过程。

3. 判断该进程是否可以安全地分配资源，如果可以，则分配资源，并更新系统状态，反之则拒绝分配，并终止该进程。

下面是实现银行家算法的C++代码：


#include <iostream>
using namespace std;
const int P = 5; // 进程数
const int R = 3; // 资源种类数
void calculateNeed(int need[][R], int maximum[][R], int allocation[][R]) { // 计算需求矩阵
  for (int i = 0; i < P; i++) {
    for (int j = 0; j < R; j++) {
      need[i][j] = maximum[i][j] - allocation[i][j];
    }
  }
}
bool isSafe(int available[], int need[][R], int allocation[][R]) { // 判断是否安全
  bool finish[P] = {0}; // 初始化进程状态
  int work[R];
  for (int i = 0; i < R; i++) { // 获取可用资源数量
    work[i] = available[i];
  }
  int count = 0;
  while (count < P) {
    bool found = false;
    for (int i = 0; i < P; i++) {
      if (!finish[i]) { // 找到未完成的进程
        int j;
        for (j = 0; j < R; j++) {
          if (need[i][j] > work[j]) // 判断该进程需求是否大于可用数量
            break;
        }
        if (j == R) { // 此时该进程可以完成
          for (int k = 0; k < R; k++) {
            work[k] += allocation[i][k]; // 更新可用资源数量
          }
          finish[i] = true; // 更新该进程状态已完成
          found = true;
          count++;
        }
      }
    }
    if (!found)
      return false;
  }
  return true;
}
void requestResources(int available[], int need[][R], int allocation[][R], int pid, int request[]) { // 请求资源
  if (request[0] > need[pid][0] || request[1] > need[pid][1] || request[2] > need[pid][2]) // 判断请求是否大于需求
    cout << "Error: the process has exceeded its maximum claim." << endl;
    return;
  
  if (request[0] > available[0] || request[1] > available[1] || request[2] > available[2]) since the resources are not available." << endl;
    return;
  
  for (int i = 0; i < R; i++) {
    available[i] -= request[i]; // 更新可用资源数量
    allocation[pid][i] += request[i]; // 更新分配资源数量
    need[pid][i] -= request[i]; // 更新需求资源数量
  }
  if (isSafe(available, need, allocation)) // 判断是否安全
    cout << "Resources have been allocated." << endl;
  else { // 分配后不安全，回滚操作
    for (int i = 0; i < R; i++) {
      available[i] += request[i];
      allocation[pid][i] -= request[i];
      need[pid][i] += request[i];
    }
    cout << "Allocation would lead to an unsafe state." << endl;
  }
}
int main() {
  int available[R] = 2; // 可用资源数量
  int maximum[P][R] = { 3, 2, 9, 2, 3}; // 最大需求矩阵
  int allocation[P][R] = {0, 2, 3, 2, 2}; // 已分配矩阵
  int need[P][R]; // 需要矩阵
  calculateNeed(need, maximum, allocation); // 计算需求矩阵
  //输出资源状态
  cout << "Available resources:\n\tA B C\n\t";
  for (int i = 0; i < R; i++) {
    cout << available[i] << " ";
  }
  cout << endl;
  cout << "Maximum demand of each process:\n\tA B C\n";
  for (int i = 0; i < P; i++) {
    cout << "P" << i << "\t";
    for (int j = 0; j < R; j++) {
      cout << maximum[i][j] << " ";
    }
    cout << endl;
  }
  cout << "Allocated resources:\n\tA B C\n";
  for (int i = 0; i < P; i++) {
    cout << "P" << i << "\t";
    for (int j = 0; j < R; j++) {
      cout << allocation[i][j] << " ";
    }
    cout << endl;
  }
  // 请求资源
  int request1[] = 0;
  int request2[] = 2;
  requestResources(available, need, allocation, 1, request1); // 不分配
  requestResources(available, need, allocation, 4, request2); // 分配
  return 0;
}

在上述代码中，我们先定义了进程数和资源数。接着，实现了三个函数：calculateNeed()、isSafe()和requestResources()。

calculateNeed()函数用于计算需求矩阵，需要用到最大需求矩阵和已分配矩阵。通过它可以获取每个进程需要的资源数量。

isSafe()函数判断系统分配资源后是否为安全状态。它的核心是利用贪心算法把进程状态不断地更新到已完成状态，并判断它们是否已经全部完成。如果可以全部完成，则说明分配后不会出现死锁现象。

requestResources()函数实现了进程请求资源的功能。首先判断请求的资源数量是否符合要求，然后判断是否有足够的资源可分配。如果可以分配，就更新系统状态，调用isSafe()函数判断是否安全，如果安全就分配资源，否则回滚分配。

最后在主函数中定义了系统的资源状态，计算需求矩阵，并请求两个不同进程的资源。分配后可以看到系统状态的变化，也可以看到请求资源是否安全。

综上所述，银行家算法是一种有效避免死锁的算法。使用C++实现银行家算法，可以有效预判系统状态，更好地控制资源分配与回收。

上一篇: idea打包java可执行jar包

下一篇: C++ 在 QT 界面中输出

评论区

()

相似文章