目录
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，Allocation
SucceesName.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;
}
}
}
4.测试分析