模拟实现银行家算法-阿里云开发者社区

一、实验内容

银行家算法的实现。

二、实验目的

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。通过编写一个模拟动态资源分配的银行家算法程序，帮助学生进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。

三、实验原理

3.1、银行家算法中的数据结构

1）可利用资源向量Available

是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available［j］=K，则表示系统中现有Rj类资源K个。

2）最大需求矩阵Max

这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。

3）分配矩阵Allocation

这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。

4）需求矩阵Need。

这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

Need［i,j］=Max［i,j］-Allocation［i,j］

3.2、银行家算法

设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1)如果Requesti［j］≤Need［i,j］，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布最大值。

(2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。

(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available［j］=Available［j］-Requesti［j］；
        Allocation［i,j］=Allocation［i,j］+Requesti［j］;  
        Need［i,j］=Need［i,j］-Requesti［j］;

系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3.3、安全性算法

1）设置两个向量：

工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;

工作向量Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］=false; 当有足够资源分配给进程时，再令Finish［i］=true。

2）从进程集合中找到一个能满足下述条件的进程：

Finish［i］=false;
        Need［i,j］≤Work［j］；若找到，执行 (3)，否则，执行 (4)

3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work［j］=Work[[j]+Allocation［i,j］;
        Finish［i］=true;
        go to step 2;

4）如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态

四、算法流程图

五、代码实现

#include<iostream>
#include<vector>
using namespace std;
class Banker {
public:
  Banker(vector<string>resName, vector<int>available, vector<vector<int>>Max, vector<vector<int>>allocation)
  :_ResName(resName)
  , _Available(available)
  , _Max(Max)
  , _Allocation(allocation)
  , _Need(_Max.size(), vector<int>(_Max[0].size(), 0))
  , _ProNumber(_Max.size())
  , _ResNumber(_Max[0].size())
  , _SafeQueue(_ProNumber, 0)
  {
  //计数需求各类资源数
  for (int i = 0; i < _ProNumber; i++) {
    for (int j = 0; j < _ResNumber; j++) {
    _Need[i][j] = _Max[i][j] - _Allocation[i][j];
    }
  }
  }
public:
  vector<int>_Available;//可利用资源矩阵
  vector<string>_ResName;//资源名
  vector<vector<int>>_Allocation;//分配矩阵
  vector<vector<int>>_Max;//最大需求矩阵，每一个进程对资源的最大需求
  vector<vector<int>>_Need;//需求矩阵
  vector<int>_SafeQueue;//安全序列
  int _ProNumber;//进程数
  int _ResNumber;//资源数
};
Banker* InitBanker() {//初始化对象
  int proNumber;//进程数
  int resNumber;//资源种类数
  cout << "请输入进程数：";
  cin >> proNumber;
  cout << endl << "请输入资源种类数量：";
  cin >> resNumber;
  vector<string>resName(resNumber);//资源名
  vector<int>available(resNumber);//可利用资源矩阵
  vector<vector<int>>Max(proNumber, vector<int>(resNumber, 0)); // 最大需求矩阵，每一个进程对资源的最大需求
  vector<vector<int>>allocation(proNumber, vector<int>(resNumber, 0));//分配矩阵
  cout << endl << "请输入资源名：";
  for (int i = 0; i < resNumber; i++) {
  cin >> resName[i];
  }
  cout << endl << endl << "请输入该资源空闲数量：";
  for (int i = 0; i < resNumber; i++) {
  cin >> available[i];
  }
  cout << endl << endl;
  for (int i = 0; i < proNumber; i++) {
  cout << endl << "请输入进程" << i << "中资源最大需求量：";
  for (int j = 0; j < resNumber; j++) {
    cin >> Max[i][j];
  }
  }
  cout << endl << endl;
  for (int i = 0; i < proNumber; i++) {
  cout << endl << "请输入进程" << i << "中已分配资源数量：";
  for (int j = 0; j < resNumber; j++) {
    cin >> allocation[i][j];
  }
  }
  cout << "资源初始化完毕！" << endl;
  cout << "-----------------------------------------" << endl;
  Banker* banker = new Banker(resName, available, Max, allocation);
  return banker;
}
void PrintInterface() {
  cout << "-------------------------------" << endl;
  cout << "    1.判断当前系统安全状态。" << endl;
  cout << "    2.申请资源。" << endl;
  cout << "    0.退出系统。" << endl;
  cout << "-------------------------------" << endl;
}
bool Is_SafeBanker(Banker& banker) {//判断当前系统安全状态
  vector<int>Work(banker._Available);//系统可提供给进程继续运行所需的各类资源数量
  vector<bool>Finish(banker._ProNumber, false);//系统是否有足够的资源分配给进程
  while (1) {
  int count = 0;
  for (; count < banker._ProNumber; count++) {//检查是否每个进程都处于安全状态
    if (Finish[count] == false) {
    break;
    }
  }
  if (count == banker._ProNumber) {//全部处于安全状态—>系统处于安全状态
    cout << "系统处于安全状态！" << endl;
    return true;
  }
  for (count = 0; count < banker._ProNumber; count++) {
    if (Finish[count] == true) {
    continue;//跳过已执行过的进程
    }
    bool flag = true;//标记为当前进程分配资源后，系统是否安全
    for (int j = 0; j < banker._ResNumber; j++) {
    if (banker._Need[count][j] > Work[j]) {//资源分配不足，当前进程不能执行,继续判断后续进程
      flag = false;
      break;
    }
    }
    if (flag == true) {
    cout << "执行进程" << count << "；系统可利用资源更新" << endl;
    banker._SafeQueue.push_back(count);//加入安全序列
    for (int i = 0; i < banker._ResNumber; i++) {//调度运行进程，并释放资源
      Work[i] += banker._Allocation[count][i];
      Finish[count] = true;
      cout << "可以利用资源" << banker._ResName[i] << "更新为：" << Work[i] << endl;
    }
    break;//进行下一轮查找安全进程
    }
  }
  //遍历完全部进程，没有进程能够执行，此时系统处于不安全状态
  if (count == banker._ProNumber) {
    cout << "系统此时为不安全状态！" << endl;
    return false;
  }
  }
}
void PrintBanker(Banker& banker) {//资源、进程信息打印函数
  cout << "-----------------------------------------------------" << endl;
  cout << "当前进程数：" << banker._ProNumber << "     资源种类数：" << banker._ResNumber << endl << endl;
  for (int i = 0; i < banker._ResNumber; i++) {
  cout << "资源：" << banker._ResName[i] << "   可利用数量：" << banker._Available[i] << endl;
  }
  for (int i = 0; i < banker._ResNumber; i++) {
  cout << endl << "------------------------------" << endl;
  cout << "进程：" << i << endl;
  for (int j = 0; j < banker._ResNumber; j++) {
    cout << "资源：" << banker._ResName[j] << "最大需求量：" << banker._Max[i][j] << "  当前分配数量：" << banker._Allocation[i][j]
    << "  剩余需求量：" << banker._Need[i][j] << endl;
  }
  cout << endl << "------------------------------" << endl;
  }
  cout << "-----------------------------------------------------" << endl;
}
bool CheckRequesti(size_t pid, vector<int> request, Banker& banker) {//进程请求检测
  //1.检测请求是否合法
  for (int i = 0; i < banker._ResNumber; i++) {//检测请求是否合法
  if (request[i] > banker._Need[pid][i]) {
    cout << "请求资源数超过最大值！" << endl;
    return false;
  }
  if (request[i] > banker._Available[i]) {
    cout << "可利用资源不足！进程需等待！" << endl;
    return false;
  }
  }
  //2.尝试分配资源
  for (int i = 0; i < banker._ResNumber; i++) {
  banker._Available[i] -= request[i];
  banker._Allocation[pid][i] += request[i];
  banker._Need[pid][i] -= request[i];
  }
  //3.检测资源分配后系统是否安全
  if (Is_SafeBanker(banker) == true) {//分配后系统安全,完成分配
  cout << "进程" << pid << "请求资源分配成功！" << endl;
  PrintBanker(banker);//打印资源、进程信息
  return true;
  }
  else {//分配后系统不安全，取消分配
  cout << "本次资源分配后系统将不安全，取消分配！" << endl;
  for (int i = 0; i < banker._ResNumber; i++) {
    banker._Available[i] += request[i];
    banker._Allocation[pid][i] -= request[i];
    banker._Need[pid][i] += request[i];
  }
  PrintBanker(banker);//打印资源、进程信息
  return false;
  }
}
void PrintSafeQueue(Banker& banker) {//打印安全序列
  cout << "----------------" << endl;
  cout << "安全序列：";
  for (size_t i = 0; i < banker._SafeQueue.size(); i++) {
  cout << ' ' << banker._SafeQueue[i];
  }
  cout << endl;
}
void TestBanker() {
  Banker* _banker = InitBanker();
  while (1) {
  Banker banker = *_banker;
  PrintInterface();//打印操作界面
  bool flag;
  int choose;
  cin >> choose;
  switch (choose) {
  case 1:
    flag = Is_SafeBanker(banker);
    break;
  case 2:
  {
    size_t pid;//标记进程号
    vector<int>Requesti(banker._ResNumber, 0);//进程请求向量
    cout << "请输入请求进程号：";
    cin >> pid;
    cout << endl << "请输入请求资源数：";
    for (size_t i = 0; i < Requesti.size(); i++) {
    cin >> Requesti[i];
    }
    flag = CheckRequesti(pid, Requesti, banker);//请求检测
    break;
  }
  case 0:
    exit(0);
  default:
    cout << "您的输入有误，请重新输入！" << endl;
    continue;
  }
  if (flag == true) {
    cout << "资源分配成功！系统处于安全状态！" << endl;
    PrintSafeQueue(banker);//打印安全序列
  }
  else {
    cout << "资源分配失败，此时系统不安全！" << endl;
  }
  }
}
int main() {
  TestBanker();
  return 0;
}

模拟实现银行家算法

一、实验内容

二、实验目的

三、实验原理

3.1、银行家算法中的数据结构

3.2、银行家算法

3.3、安全性算法

四、算法流程图

五、代码实现

六、测试用例及结果

热门文章

最新文章

相关课程

相关电子书

相关实验场景