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

一、实验内容

银行家算法的实现。

二、实验目的

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

三、实验原理

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、安全性算法

四、算法流程图

五、代码实现

六、测试用例及结果

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

模拟实现银行家算法

一、实验内容

二、实验目的

三、实验原理

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

3.2、银行家算法

3.3、安全性算法

四、算法流程图

五、代码实现

六、测试用例及结果

热门文章

最新文章

相关课程

相关电子书

相关实验场景