当前位置：首页 > ai >正文

C++实现银行家算法

ai 2025/6/30 20:26:12

1.需求分析

2.概要设计

2.1算法数据结构

2.2银行家算法

2.3安全性算法

3.C++代码实现

4.测试分析

1.需求分析

银行家算法是最具代表性的避免死锁的算法，由Dijkstra提出。该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS中也可以用他来实现避免死锁。

为实现此算法，每一个新进程在进入系统时，必须声明在运行过程中可能需要每种资源类型的最大单元数目，其数目不应该超过系统所拥有的资源总量。当进程请求某资源时，系统必须首先确定是否有足够的资源分配给该进程。如果有再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才会将资源分配给他。

2.概要设计

2.1算法数据结构

为了实现银行家算法，在系统中必须设置四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

Avaliable：可利用资源向量。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
Max：最大需求矩阵。这是一个n*m的矩阵，他定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i][j]=K,则表示进程i需要Rj类资源的最大数目是K。
Allocation：分配矩阵。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i][j]=K，则表示进程i当前已经分得Rj类资源的数目为K。
Need：需求矩阵。这是一个n*m的矩阵，它表示每一进程尚需的各类资源数目。如果Need[i][j]=K，则表示进程i还需要K个Rj类资源，才能完成其任务。

上述三个矩阵间存在下述关系：

Need[i,j]=Max[i,j]-Allocation[i,j]

2.2银行家算法

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

如果Requesti[j]<=Need[i][j]，便转向Step(2)；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。
如果Requesti[j]<=Available[j]，便转向Step(3)；否则，表示尚无足够资源，Pi必须等待。
系统试探着把资源分配给进程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等待。

2.3安全性算法

系统所执行的安全性算法可描述如下：

设置两个向量：①工作向量Work，它表示系统可提供给进程继续执行所需的各类资源数目，它含有吗m个元素，在执行安全算法开始时，Work=Available；②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。
从进程集合中找到一个能满足下述条件的进程：
- Finish[i]=false；
- Need[i][j]<=Work[j]；若找到，执行Step(3)，否则，执行步骤(4)。
当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[i]=Work[j]+Allocation[i][j];

Finish[i]=true;

go to step 2;

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

3.C++代码实现

// 银行家算法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<vector>
#include<algorithm>
#include <iomanip>using namespace std;
int num_Process = 0;
int num_Source = 0;
vector<int>TotalSource;
vector<int>Available ;
vector<int>Request;
vector<char> nameSource;
vector<int>SucceesName;
vector<int> work;
vector<int> workallocation;class BankObject
{
private:char name;vector<int> max;vector<int> allocation;vector<int> need;bool finish;
public:BankObject(char pname,vector<int>pmax, vector<int>pallocation,vector<int>pneed) :name(pname),max(pmax), allocation (pallocation),need(pneed){finish = 0;}operator vector<int>() const{return need;}vector<int>& Max(){return max;}const vector<int>& Max()const {return max;}char& Name(){return name;}const char& Name()const{return name;}vector<int>& Allocation(){return allocation;}const vector<int>& Allocation()const{return allocation;}vector<int>& Need(){return need;}const vector<int>& Need()const{return need;}bool & Finish(){return finish;}const  bool & Finish()const{return finish;}
};
class Manage
{
private:vector<BankObject> ProList;
public://初始化各个进程的Max，Allocation，Need向量void Add(BankObject process){ProList.push_back(process);}void SetWorkAvailable(){for (int i = 0; i < num_Source; i++){for (int j = 0; j < num_Process; j++){Available[i] = Available[i] - ProList[j].Allocation()[i];}}		work = Available;}void CalTotolSource(){TotalSource = Available;for (int i = 0; i < num_Source; i++){for (int j = 0; j < num_Process; j++){TotalSource.push_back( TotalSource[i] + ProList[j].Allocation()[i]);}}}void CalMax(){for (int i = 0; i < num_Process; i++){for (int j = 0; j < num_Source; j++){ProList[i].Max()[j] = ProList[i].Allocation()[j] + ProList[i].Need()[j];}}}void CalNeed(){for (int i = 0; i < num_Process; i++){for (int j = 0; j < num_Source; j++){ProList[i].Need()[j] = ProList[i].Max()[j] - ProList[i].Allocation()[j];}}}void CalAllocation(){for (int i = 0; i < num_Process; i++){for (int j = 0; j < num_Source; j++){ProList[i].Allocation()[j] = ProList[i].Max()[j] - ProList[i].Need()[j];}}}bool Compare(BankObject obj1, vector<int>work){bool success = true;for (int i = 0; i < num_Source; i++){if (obj1.Need()[i] > work[i])//安全性算法Step1：比较不成功{success = false;}}return success;}bool SafeCheak(){cout << "资源  " << setw(2) << "Work" << setw(8) << "Need" << setw(13) << "Allocation" << setw(17) << "Work+Allocation" << setw(8) << "Finish" << endl;cout << "进程" << setw(4);for (int j = 0; j < 4; j++){cout << setw(3);if (j == 2){cout << setw(4);}if (j == 3){cout << setw(8);}for (int i = 0; i < num_Source; i++){cout << nameSource[i] << " ";}}cout << endl;bool success = 0;int tag = 0;//Step1：设置两个工作向量（已完成）//Step2：从进程集合中找满足条件的进程for (int k = 0, count = 0; k < num_Process; k++){for (int i = 0; i < num_Process; i++){if (ProList[i].Finish() == 0 && Compare(ProList[i], work)){//打印通过安全检查进程的Work，Need，AllocationSucceesName.push_back(i);cout << "P" << i << setw(4) << "|";for (int j = 0; j < num_Source; j++){cout << work[j];if (j + 1 == num_Source){cout << "|";break;}cout << " ";}cout << setw(2) << "|";for (int j = 0; j < num_Source; j++){cout << ProList[i].Need()[j];if (j + 1 == num_Source){cout << "|";break;}cout << " ";}ProList[i].Finish() = 1;//打印Work+Allocation矩阵，cout << setw(3) << "|";for (int j = 0; j < num_Source; j++){cout << ProList[i].Allocation()[j];if (j + 1 == num_Source){cout << "|";break;}cout << " ";}for (int j = 0; j < num_Source; j++){work[j] = work[j] + ProList[i].Allocation()[j];}cout << setw(7) << "|";for (int j = 0; j < num_Source; j++){cout << work[j];if (j + 1 == num_Source){cout << "|";break;}cout << " ";}cout << setw(10) << "|" << ProList[i].Finish() << "|" << endl;count++;//找到一个安全序列if (count == num_Process)//找到所有的安全序列{success = 1;//打印安全序列cout << "------------***^*^***-------------" << endl;cout << "系统处于安全状态，可以找到一个安全序列{";for (int j = 0; j < num_Process; j++){cout << "P";cout << SucceesName[j] << "，";}cout << "}" << endl;cout << "------------***^*^***-------------" << endl;goto end;}}}}if (success == 0)//没有找到安全序列{cout << "------------***^*^***-------------" << endl;cout << "该系统未处于安全状态！" << endl;cout << "------------***^*^***-------------" << endl;}end:for (int i = 0; i < num_Process; i++){ProList[i].Finish() = 0;}return success;}//processi是要请求的进程序列void BankAlgorithm(int processi){//Step1：bool success = 1;for (int j = 0; j < num_Source; j++){if (Request[j] > ProList[processi].Need()[j]){success = 0;cout << "该进程所申请的资源数量已经超过他所宣布的最大值！" << endl;}}//其余步骤都是在step1执行成功的条件下执行的//Step2：if (success){for (int j = 0; j < num_Source; j++){if (Request[j] > Available[j]){success = 0;cout << "系统尚无足够资源！P"<<processi<<"进程须等待！" << endl;}}}//Step3：系统试分配if (success){for (int j = 0; j < num_Source; j++){Available[j] = Available[j] - Request[j];ProList[processi].Allocation()[j] = ProList[processi].Allocation()[j] + Request[j];ProList[processi].Need()[j] = ProList[processi].Need()[j] - Request[j];}work = Available;success = SafeCheak();if (success == 0)//安全性检查未通过{//回收刚才试分配的资源for (int j = 0; j < num_Source; j++){Available[j] = Available[j] + Request[j];ProList[processi].Allocation()[j] = ProList[processi].Allocation()[j] - Request[j];ProList[processi].Need()[j] = ProList[processi].Need()[j] + Request[j];}work = Available;}}}void Print_T0(){cout << "资源  " << setw(3) << "Max" << setw(13) << "Allocation" << setw(6) << "Need" << setw(11) << "Available" << endl;cout << "进程" << setw(4);for (int j = 0; j < 4; j++){cout << setw(3);if (j == 2){cout << setw(4);}if (j == 3){cout << setw(5);}for (int i = 0; i < num_Source; i++){cout << nameSource[i] << " ";}}cout << endl;for (int i = 0; i < num_Process; i++){cout << "P" << i << setw(4) << "|";for (int j = 0; j < num_Source; j++){cout << ProList[i].Max()[j];if (j + 1 == num_Source){cout << "|";break;}cout << " ";}cout << setw(2) << "|";for (int j = 0; j < num_Source; j++){cout << ProList[i].Allocation()[j];if (j + 1 == num_Source){cout << "|";break;}cout << " ";}cout << setw(3) << "|";for (int j = 0; j < num_Source; j++){cout << ProList[i].Need()[j];if (j + 1 == num_Source){cout << "|";break;}cout << " ";}if (0 == i){cout << setw(3) << "|";for (int j = 0; j < num_Source; j++){cout << Available[j] << setw(2);}cout << "|";}cout << endl;}}void Menu(){cout << "**********^^^*^^^********" << endl;cout << "1.显示当前资源情况" << endl;cout << "2.安全性检查" << endl;cout << "3.请求资源" << endl;cout << "4.退出本系统" << endl;cout << "**********^^^*^^^********" << endl;}void InitMenu(){cout << "1.输入Max，allocation，totalsource" << endl;cout << "2.输入allocation，need，available" << endl;cout << "3.输入Max，Need，available" << endl;}
};
void CharName()
{for (int i = 0; i < num_Source; i++){nameSource.push_back(i + 65);}
}int main()
{Manage process;bool success;int choose = 0;int processi = 0;char end = 'y';vector<int> num_Max;vector<int> num_Allocation;vector<int> num_Need;int requestsourcenum = 0;cout<<"现在开始进行初始化："<<endl;cout << "请输入进程的数量：";cin >> num_Process;cout << "请输入资源的数量：";cin >> num_Source;CharName();int valueAvailable = 0;int valueMax = 0, valueAllocation = 0, valueNeed = 0;int init = 0;process.InitMenu();way:cout << "请选择初始化方式：";cin >> init;if (1 == init){for (int i = 0; i < num_Source; i++){cout << "请输入资源" << nameSource[i] << "的总量：";cin >> valueAvailable;TotalSource.push_back(valueAvailable);}for (int i = 0; i < num_Process; i++){cout << "请输入进程P" << i << "的Max：";for (int j = 0; j < num_Source; j++){cin >> valueMax;num_Max.push_back(valueMax);}cout << "请输入进程P" << i << "的Allocation：";for (int j = 0; j < num_Source; j++){cin >> valueAllocation;num_Allocation.push_back(valueAllocation);num_Need.push_back(0);}BankObject obj1(i, num_Max, num_Allocation,num_Need);process.Add(obj1);num_Max.clear();num_Allocation.clear();num_Need.clear();}		Available = TotalSource;process.CalNeed();process.SetWorkAvailable();}else if(2==init){for (int i = 0; i < num_Process; i++){cout << "请输入进程P" << i << "的Allocation：";for (int j = 0; j < num_Source; j++){cin >> valueAllocation;num_Allocation.push_back(valueAllocation);}cout << "请输入进程P" << i << "的Need：";for (int j = 0; j < num_Source; j++){cin >> valueNeed;num_Need.push_back(valueNeed);num_Max.push_back(0);}BankObject obj1(i, num_Max, num_Allocation,num_Need);process.Add(obj1);num_Max.clear();num_Allocation.clear();num_Need.clear();}for (int i = 0; i < num_Source; i++){cout << "请输入资源" << nameSource[i] << "的available：";cin >> valueAvailable;Available.push_back(valueAvailable);}//计算各资源的总数process.CalTotolSource();process.CalMax();work = Available;}else if (3 == init){for (int i = 0; i < num_Process; i++){cout << "请输入进程P" << i << "的Max：";for (int j = 0; j < num_Source; j++){cin >> valueMax;num_Max.push_back(valueMax);}cout << "请输入进程P" << i << "的Need：";for (int j = 0; j < num_Source; j++){cin >> valueNeed;num_Need.push_back(valueNeed);num_Allocation.push_back(0);}BankObject obj1(i, num_Max, num_Allocation, num_Need);process.Add(obj1);num_Max.clear();num_Allocation.clear();num_Need.clear();}for (int i = 0; i < num_Source; i++){cout << "请输入资源" << nameSource[i] << "的available：";cin >> valueAvailable;Available.push_back(valueAvailable);}//计算各资源的总数process.CalTotolSource();process.CalAllocation();work = Available;}else{cout << "请重新输入初始化方式！" << endl;goto way;}while (1){process.Menu();cout << "请输入你的选择：";cin >> choose;if (choose < 0 || choose>4){cout << "请重新输入你的选择！" << endl;}switch (choose){case 1:process.Print_T0();break;case 2:process.SafeCheak();break;case 3:cout << "进程列表：" << endl;for (int i = 0; i < num_Process; i++){cout << "P" << i << "-->" << i << endl;}process:cout << "请输入要申请资源的进程：";cin >> processi;if (processi<0 || processi>num_Process){cout << "对不起，请重新输入进程！！！" << endl;goto process;}cout << "请输入要申请的各种资源数量：";for (int i = 0; i < num_Source; i++){cin >> requestsourcenum;Request.push_back(requestsourcenum);}process.BankAlgorithm(processi);Request.clear();break;case 4:return 0;break;}}}