网上有很多银行家算法的源代码，下面是本人自己写的，基本算法模型参考教材。
介绍
银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉（Edsger Wybe Dijkstra）在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
背景简介
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态
不存在一个安全序列。不安全状态不一定导致死锁。
标题实现
要求
-
建立银行家算法的数据结构描述；
-
将初始数据放在文件中，算法运行时读出；
-
对给定的资源请求，使用算法判断是否允许；
-
输出每次判断产生的执行序列。
开发环境
windows C++ Code Blocks
程序实现
数据结构
Available[PROGRESS];
//定义可用资源向量
sign[PROGRESS],work[PROGRESS][REC_NUM],workAll[PROGRESS][REC_NUM];
//记录成功的安全序列,并定义工作矩阵和可用资源矩阵
Max[PROGRESS][REC_NUM],Allocation[PROGRESS][REC_NUM],Need[PROGRESS][REC_NUM];
//定义最大需求矩阵Max，分配矩阵Allocation，需求矩阵Need
Request[PROGRESS][REC_NUM];
//定义请求矩阵Requset
运行步骤
//读取文件数据并打印,然后将数据存入到相应矩阵中
Read_file();
//任务开始
int i,N=0; // 'N'表示请求资源次数
int Request[PROGRESS][REC_NUM]; //定义请求矩阵Requset
while(N!=999) {
cout<<endl<<"请输入请求资源Request[进程标号i][资源类型j]:"<<endl;
cout<<"进程i=：";
cin>>i;
cout<<"各类资源数量(A B C)=: ";
for(int m = 0;m < REC_NUM;m++)
cin>>Request[i][m];
cout<<endl;
//执行银行家算法
int result = Banker_Algorithm(i,Request);
//输出每次判断产生的执行序列
cout<<endl<<"资源分配表："<<endl;
Print_Run_Order(result);
cout<<endl<<"请输入N(当N=999退出)："<<endl;
cin>>N;
}
安全性算法设计思路
开始将可用资源数目赋给工作向量Work
for(int r = 0;r < REC_NUM;r++) Work[r] = Available[r]；
执行while循环，只有满足条件（4行，6行）才将Finish置为1(true)，并释放进程占有所有资源，这时用数组sign（13行）保存此进程标号，用于输出安全序列。
注意每当找到符合条件的进程，就将i置为-1，并i++，重新开始扫描进程，因为当某个进程释放资源后，标号为0的进程可能符合条件（14行）。
1 while(i < PROGRESS) {
2 if(Finish[i] == 0){
3 //满足条件释放资源，并从头开始扫描进程集合
4 while(j < REC_NUM && Need[i][j] <= Work[j] )
5 j++;
6 if(j == REC_NUM) {
7 for(int k = 0;k < REC_NUM;k++){
8 work[i][k] = Work[k];
9 Work[k] = Work[k]+Allocation[i][k];
10 workAll[i][k] = Work[k];
11 }
12 Finish[i]=1;
13 sign[m]=i; //保存安全序列
14 i=-1;m++;
15 }
16 }
17 j=0;i++;
18 }
循环结束后，返回Finsih 中true的个数
for(int p = 0;p < PROGRESS;p++){
if(Finish[p] == 1)
n++; //记录'true'个数
}
return n; //返回'true'个数
附程序源代码
//如要引用请附上以下说明
/**
* 操作系统课程设计
* 题目：11.银行家算法
* 输入请求资源，判断安全状态;
* 打印资源分配表
* 作者：易树
* 版本：3.0 （完成时间 2016.12.20）
*/
#include <iostream>
#include <fstream>
#define PROGRESS 5 //进程数量
#define REC_NUM 3 //资源种类数量
using namespace std;
//定义数据结构
int Available[PROGRESS]; //定义可用资源向量Available
int sign[PROGRESS],work[PROGRESS][REC_NUM],workAll[PROGRESS][REC_NUM];
//记录成功的安全序列,并定义工作矩阵和可用资源矩阵
int Max[PROGRESS][REC_NUM],Allocation[PROGRESS][REC_NUM],Need[PROGRESS][REC_NUM];
//定义最大需求矩阵Max，分配矩阵Allocation，需求矩阵Need
void Read_file(); //读取文件
int Banker_Algorithm(int,int [][REC_NUM]); //银行家算法
int Safe_Algorithm(int [],int [][REC_NUM],int [][REC_NUM]); //安全性算法
void Print_Run_Order(int); //打印判断执行序列
int main()
{
//读取文件数据并打印,然后将数据存入到相应矩阵中
Read_file();
//任务开始
int i,N=0; // 'N'表示请求资源次数
int Request[PROGRESS][REC_NUM]; //定义请求矩阵Requset
while(N!=999) {
cout<<endl<<"请输入请求资源Request[进程标号i][资源类型j]:"<<endl;
cout<<"进程i=：";
cin>>i;
cout<<"各类资源数量(A B C)=: ";
for(int m = 0;m < REC_NUM;m++)
cin>>Request[i][m];
cout<<endl;
//执行银行家算法
int result = Banker_Algorithm(i,Request);
//输出每次判断产生的执行序列
cout<<endl<<"资源分配表："<<endl;
Print_Run_Order(result);
cout<<endl<<"请输入N(当N=999退出)："<<endl;
cin>>N;
}
}
//读取文件数据，打印到控制台，并将数据存入到相应矩阵中
void Read_file(){
//读取完整文件并打印
ifstream inFile1("Alldata.txt",ios::in); //创建文件流对象
if(!inFile1) //判断对象inFile打开文件成功与否
cerr<<"File open error."<<endl; //使用错误流对象输出错误信息
else {
char c;
while((c=inFile1.get())!=EOF) //按字符读取文件内容，到达末尾停止
cout<<c;
cout<<endl;
inFile1.close();
}
//读取只有数字的文件并存入矩阵中
ifstream inFile2("data.txt",ios::in);
if(!inFile2)
cerr<<"File open error."<<endl;
else{
int data;
//读取数字并存入矩阵
for(int j = 0;j < PROGRESS;j++) {
for(int i = 0;i < REC_NUM;i++) {
inFile2>>data;
Max[j][i]=data;
}
for(int i = 0;i < REC_NUM;i++) {
inFile2>>data;
Allocation[j][i]=data;
}
for(int i = 0;i < REC_NUM;i++) {
inFile2>>data;
Need[j][i]=data;
}
if(j==0) {
for(int i = 0;i < REC_NUM;i++) {
inFile2>>data;
Available[i]=data;
}
}
}
inFile2.close();
}
}
//银行家算法
int Banker_Algorithm (int i,int Request[][REC_NUM]){
for(int m = 0;m < REC_NUM;m++) {
if(Request[i][m] > Need[i][m]){
cout<<"所需资源数超出其宣布的最大值!"<<endl;
return 0;
} else if(Request[i][m] > Available[m]) {
cout<<"无足够资源，p["<<i<<"]需等待!"<<endl;
return 0;
}
}
//尝试为进程分配资源
for(int j = 0;j < REC_NUM;j++) {
Available[j] = Available[j] - Request[i][j];
Allocation[i][j] = Allocation[i][j] + Request[i][j];
Need[i][j] = Need[i][j] - Request[i][j];
}
//执行安全性算法
int n = Safe_Algorithm(Available,Need,Allocation);
cout<<endl;
if(n == PROGRESS) {//有5个'true'返回1，表示此时刻安全
cout<<"此时刻是安全状态，可以分配资源给"<<"P["<<i<<"]!"<<endl;
}else {
//把给进程P[i]分配过的资源还给系统
for(int j = 0;j < REC_NUM;j++) {
Available[j] = Available[j] + Request[i][j];
Allocation[i][j] = Allocation[i][j] - Request[i][j];
Need[i][j] = Need[i][j] + Request[i][j];
}
cout<<"此时刻不是安全状态，不能将资源分配给"<<"P["<<i<<"]!"<<endl;
}
return n;
}
//安全性算法
int Safe_Algorithm(int Available[],int Need[][REC_NUM],int Allocation[][REC_NUM]) {
int i=0,j=0,m=0,n=0;
int Work[REC_NUM],Finish[PROGRESS] = {0,0,0,0,0};
for(int r = 0;r < REC_NUM;r++) //将可用资源数目赋给工作向量Work
Work[r] = Available[r];
while(i < PROGRESS) {
if(Finish[i] == 0){
//满足条件释放资源，并从头开始扫描进程集合
while(j < REC_NUM && Need[i][j] <= Work[j] )
j++;
if(j == REC_NUM) {
for(int k = 0;k < REC_NUM;k++){
work[i][k] = Work[k];
Work[k] = Work[k]+Allocation[i][k];
workAll[i][k] = Work[k];
}
Finish[i]=1;
sign[m]=i; //保存安全序列
i=-1;m++;
}
}
j=0;i++;
}
for(int p = 0;p < PROGRESS;p++){
if(Finish[p] == 1)
n++; //记录'true'个数
}
return n; //返回'true'个数
}
//打印安全性检查的执行序列
void Print_Run_Order(int result) {
if(result == PROGRESS) {
cout<<" 进程\\资源情况"<<" Work(A B C)"<<" Need(A B C)"
<<" Allocation(A B C)"<<" Work+Available(A B C)"<<" Finish";
cout<<endl;
for(int i = 0;i < PROGRESS;i++) {
cout<<" "<<"P["<<sign[i]<<"] "<<'\t';
for(int j = 0;j < REC_NUM;j++)
cout<<work[sign[i]][j]<<" ";
cout<<'\t'<<'\t';
for(int j = 0;j < REC_NUM;j++)
cout<<Need[sign[i]][j]<<" ";
cout<<'\t'<<'\t';
for(int j = 0;j < REC_NUM;j++)
cout<<Allocation[sign[i]][j]<<" ";
cout<<'\t'<<'\t';
for(int j = 0;j < REC_NUM;j++)
cout<<workAll[sign[i]][j]<<" ";
cout<<'\t'<<'\t';
cout<<"true"<<endl;
}
cout<<endl<<"找到安全序列｛P["<<sign[0]<<"]";
for(int m = 1;m < PROGRESS;m++){
cout<<", P["<<sign[m]<<"]";
}
cout<<"}"<<endl;
} else {
cout<<" 进程\\资源情况 "<<" Allocation(A B C)"<<" Need(A B C)"<<" Available(A B C)";
cout<<endl;
for(int k = 0;k < 5;k++){
cout<<'\t'<<"P["<<k<<"]"<<'\t'<<'\t';
for(int j = 0;j < 3;j++)
cout<<Allocation[k][j]<<" ";
cout<<'\t'<<'\t';
for(int j = 0;j < 3;j++)
cout<<Need[k][j]<<" ";
cout<<'\t'<<'\t';
if(k == 0) {
for(int j = 0;j < 3;j++)
cout<<Available[j]<<" ";
}
cout<<endl;
}
}
}
运行截图
项目地址
github地址
csdn下载
参考文献
- 《 计算机操作系统》 汤小丹 梁红兵 哲风屏 汤子灜 编著
- 百度百科-银行家算法
网上有很多银行家算法的源代码，下面是本人自己写的，基本算法模型参考教材。
介绍
银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉（Edsger Wybe Dijkstra）在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
背景简介
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态
不存在一个安全序列。不安全状态不一定导致死锁。
标题实现
要求
-
建立银行家算法的数据结构描述；
-
将初始数据放在文件中，算法运行时读出；
-
对给定的资源请求，使用算法判断是否允许；
-
输出每次判断产生的执行序列。
开发环境
windows C++ Code Blocks
程序实现
数据结构
Available[PROGRESS];
//定义可用资源向量
sign[PROGRESS],work[PROGRESS][REC_NUM],workAll[PROGRESS][REC_NUM];
//记录成功的安全序列,并定义工作矩阵和可用资源矩阵
Max[PROGRESS][REC_NUM],Allocation[PROGRESS][REC_NUM],Need[PROGRESS][REC_NUM];
//定义最大需求矩阵Max，分配矩阵Allocation，需求矩阵Need
Request[PROGRESS][REC_NUM];
//定义请求矩阵Requset
运行步骤
//读取文件数据并打印,然后将数据存入到相应矩阵中
Read_file();
//任务开始
int i,N=0; // 'N'表示请求资源次数
int Request[PROGRESS][REC_NUM]; //定义请求矩阵Requset
while(N!=999) {
cout<<endl<<"请输入请求资源Request[进程标号i][资源类型j]:"<<endl;
cout<<"进程i=：";
cin>>i;
cout<<"各类资源数量(A B C)=: ";
for(int m = 0;m < REC_NUM;m++)
cin>>Request[i][m];
cout<<endl;
//执行银行家算法
int result = Banker_Algorithm(i,Request);
//输出每次判断产生的执行序列
cout<<endl<<"资源分配表："<<endl;
Print_Run_Order(result);
cout<<endl<<"请输入N(当N=999退出)："<<endl;
cin>>N;
}
安全性算法设计思路
开始将可用资源数目赋给工作向量Work
for(int r = 0;r < REC_NUM;r++) Work[r] = Available[r]；
执行while循环，只有满足条件（4行，6行）才将Finish置为1(true)，并释放进程占有所有资源，这时用数组sign（13行）保存此进程标号，用于输出安全序列。
注意每当找到符合条件的进程，就将i置为-1，并i++，重新开始扫描进程，因为当某个进程释放资源后，标号为0的进程可能符合条件（14行）。
1 while(i < PROGRESS) {
2 if(Finish[i] == 0){
3 //满足条件释放资源，并从头开始扫描进程集合
4 while(j < REC_NUM && Need[i][j] <= Work[j] )
5 j++;
6 if(j == REC_NUM) {
7 for(int k = 0;k < REC_NUM;k++){
8 work[i][k] = Work[k];
9 Work[k] = Work[k]+Allocation[i][k];
10 workAll[i][k] = Work[k];
11 }
12 Finish[i]=1;
13 sign[m]=i; //保存安全序列
14 i=-1;m++;
15 }
16 }
17 j=0;i++;
18 }
循环结束后，返回Finsih 中true的个数
for(int p = 0;p < PROGRESS;p++){
if(Finish[p] == 1)
n++; //记录'true'个数
}
return n; //返回'true'个数
附程序源代码
//如要引用请附上以下说明
/**
* 操作系统课程设计
* 题目：11.银行家算法
* 输入请求资源，判断安全状态;
* 打印资源分配表
* 作者：易树
* 版本：3.0 （完成时间 2016.12.20）
*/
#include <iostream>
#include <fstream>
#define PROGRESS 5 //进程数量
#define REC_NUM 3 //资源种类数量
using namespace std;
//定义数据结构
int Available[PROGRESS]; //定义可用资源向量Available
int sign[PROGRESS],work[PROGRESS][REC_NUM],workAll[PROGRESS][REC_NUM];
//记录成功的安全序列,并定义工作矩阵和可用资源矩阵
int Max[PROGRESS][REC_NUM],Allocation[PROGRESS][REC_NUM],Need[PROGRESS][REC_NUM];
//定义最大需求矩阵Max，分配矩阵Allocation，需求矩阵Need
void Read_file(); //读取文件
int Banker_Algorithm(int,int [][REC_NUM]); //银行家算法
int Safe_Algorithm(int [],int [][REC_NUM],int [][REC_NUM]); //安全性算法
void Print_Run_Order(int); //打印判断执行序列
int main()
{
//读取文件数据并打印,然后将数据存入到相应矩阵中
Read_file();
//任务开始
int i,N=0; // 'N'表示请求资源次数
int Request[PROGRESS][REC_NUM]; //定义请求矩阵Requset
while(N!=999) {
cout<<endl<<"请输入请求资源Request[进程标号i][资源类型j]:"<<endl;
cout<<"进程i=：";
cin>>i;
cout<<"各类资源数量(A B C)=: ";
for(int m = 0;m < REC_NUM;m++)
cin>>Request[i][m];
cout<<endl;
//执行银行家算法
int result = Banker_Algorithm(i,Request);
//输出每次判断产生的执行序列
cout<<endl<<"资源分配表："<<endl;
Print_Run_Order(result);
cout<<endl<<"请输入N(当N=999退出)："<<endl;
cin>>N;
}
}
//读取文件数据，打印到控制台，并将数据存入到相应矩阵中
void Read_file(){
//读取完整文件并打印
ifstream inFile1("Alldata.txt",ios::in); //创建文件流对象
if(!inFile1) //判断对象inFile打开文件成功与否
cerr<<"File open error."<<endl; //使用错误流对象输出错误信息
else {
char c;
while((c=inFile1.get())!=EOF) //按字符读取文件内容，到达末尾停止
cout<<c;
cout<<endl;
inFile1.close();
}
//读取只有数字的文件并存入矩阵中
ifstream inFile2("data.txt",ios::in);
if(!inFile2)
cerr<<"File open error."<<endl;
else{
int data;
//读取数字并存入矩阵
for(int j = 0;j < PROGRESS;j++) {
for(int i = 0;i < REC_NUM;i++) {
inFile2>>data;
Max[j][i]=data;
}
for(int i = 0;i < REC_NUM;i++) {
inFile2>>data;
Allocation[j][i]=data;
}
for(int i = 0;i < REC_NUM;i++) {
inFile2>>data;
Need[j][i]=data;
}
if(j==0) {
for(int i = 0;i < REC_NUM;i++) {
inFile2>>data;
Available[i]=data;
}
}
}
inFile2.close();
}
}
//银行家算法
int Banker_Algorithm (int i,int Request[][REC_NUM]){
for(int m = 0;m < REC_NUM;m++) {
if(Request[i][m] > Need[i][m]){
cout<<"所需资源数超出其宣布的最大值!"<<endl;
return 0;
} else if(Request[i][m] > Available[m]) {
cout<<"无足够资源，p["<<i<<"]需等待!"<<endl;
return 0;
}
}
//尝试为进程分配资源
for(int j = 0;j < REC_NUM;j++) {
Available[j] = Available[j] - Request[i][j];
Allocation[i][j] = Allocation[i][j] + Request[i][j];
Need[i][j] = Need[i][j] - Request[i][j];
}
//执行安全性算法
int n = Safe_Algorithm(Available,Need,Allocation);
cout<<endl;
if(n == PROGRESS) {//有5个'true'返回1，表示此时刻安全
cout<<"此时刻是安全状态，可以分配资源给"<<"P["<<i<<"]!"<<endl;
}else {
//把给进程P[i]分配过的资源还给系统
for(int j = 0;j < REC_NUM;j++) {
Available[j] = Available[j] + Request[i][j];
Allocation[i][j] = Allocation[i][j] - Request[i][j];
Need[i][j] = Need[i][j] + Request[i][j];
}
cout<<"此时刻不是安全状态，不能将资源分配给"<<"P["<<i<<"]!"<<endl;
}
return n;
}
//安全性算法
int Safe_Algorithm(int Available[],int Need[][REC_NUM],int Allocation[][REC_NUM]) {
int i=0,j=0,m=0,n=0;
int Work[REC_NUM],Finish[PROGRESS] = {0,0,0,0,0};
for(int r = 0;r < REC_NUM;r++) //将可用资源数目赋给工作向量Work
Work[r] = Available[r];
while(i < PROGRESS) {
if(Finish[i] == 0){
//满足条件释放资源，并从头开始扫描进程集合
while(j < REC_NUM && Need[i][j] <= Work[j] )
j++;
if(j == REC_NUM) {
for(int k = 0;k < REC_NUM;k++){
work[i][k] = Work[k];
Work[k] = Work[k]+Allocation[i][k];
workAll[i][k] = Work[k];
}
Finish[i]=1;
sign[m]=i; //保存安全序列
i=-1;m++;
}
}
j=0;i++;
}
for(int p = 0;p < PROGRESS;p++){
if(Finish[p] == 1)
n++; //记录'true'个数
}
return n; //返回'true'个数
}
//打印安全性检查的执行序列
void Print_Run_Order(int result) {
if(result == PROGRESS) {
cout<<" 进程\\资源情况"<<" Work(A B C)"<<" Need(A B C)"
<<" Allocation(A B C)"<<" Work+Available(A B C)"<<" Finish";
cout<<endl;
for(int i = 0;i < PROGRESS;i++) {
cout<<" "<<"P["<<sign[i]<<"] "<<'\t';
for(int j = 0;j < REC_NUM;j++)
cout<<work[sign[i]][j]<<" ";
cout<<'\t'<<'\t';
for(int j = 0;j < REC_NUM;j++)
cout<<Need[sign[i]][j]<<" ";
cout<<'\t'<<'\t';
for(int j = 0;j < REC_NUM;j++)
cout<<Allocation[sign[i]][j]<<" ";
cout<<'\t'<<'\t';
for(int j = 0;j < REC_NUM;j++)
cout<<workAll[sign[i]][j]<<" ";
cout<<'\t'<<'\t';
cout<<"true"<<endl;
}
cout<<endl<<"找到安全序列｛P["<<sign[0]<<"]";
for(int m = 1;m < PROGRESS;m++){
cout<<", P["<<sign[m]<<"]";
}
cout<<"}"<<endl;
} else {
cout<<" 进程\\资源情况 "<<" Allocation(A B C)"<<" Need(A B C)"<<" Available(A B C)";
cout<<endl;
for(int k = 0;k < 5;k++){
cout<<'\t'<<"P["<<k<<"]"<<'\t'<<'\t';
for(int j = 0;j < 3;j++)
cout<<Allocation[k][j]<<" ";
cout<<'\t'<<'\t';
for(int j = 0;j < 3;j++)
cout<<Need[k][j]<<" ";
cout<<'\t'<<'\t';
if(k == 0) {
for(int j = 0;j < 3;j++)
cout<<Available[j]<<" ";
}
cout<<endl;
}
}
}
运行截图
项目地址
github地址
csdn下载
参考文献
- 《 计算机操作系统》 汤小丹 梁红兵 哲风屏 汤子灜 编著
- 百度百科-银行家算法