1. 全栈程序员必看首页

银行家算法C++实现

全栈程序员-用户IM • • 未分类

银行家算法C++实现网上有很多银行家算法的源代码，下面是本人自己写的，基本算法模型参考教材。介绍银行家算法（Banker’sAlgorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉（EdsgerWybeDijkstra）在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。背景简介在银行中…

大家好，又见面了，我是你们的朋友全栈君。

网上有很多银行家算法的源代码，下面是本人自己写的，基本算法模型参考教材。

介绍

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉（Edsger Wybe Dijkstra）在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

背景简介

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态
不存在一个安全序列。不安全状态不一定导致死锁。

标题实现

要求

  1. 建立银行家算法的数据结构描述；

  2. 将初始数据放在文件中，算法运行时读出；

  3. 对给定的资源请求，使用算法判断是否允许；

  4. 输出每次判断产生的执行序列。

开发环境

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下载

参考文献

  1. 《 计算机操作系统》 汤小丹 梁红兵 哲风屏 汤子灜 编著
  2. 百度百科-银行家算法
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/163219.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

  • Java+SQLServer实现——网上图书馆借还管理系统

    Java+SQLServer实现——网上图书馆借还管理系统

    Java+SQLServer实现——网上图书馆借还管理系统完整版zip：http://download.csdn.net/detail/wsk1103/9702747PS:这是刚学Java时自己手写的一个垃圾项目，质量低，但是可以运行。已经放弃维护。。。。。。。。。1概述网络的发展越来越快，网上图书馆也毫不例外。因此，网上图书馆就此诞生了，学生对知识的渴望也是越来越大，并且通过网络来订阅图书是一件非常轻松的事情。本系统是一个…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年5月22日
  • Ural 1025-Democrary in Danger

    Ural 1025-Democrary in Danger

    Ural 1025-Democrary in Danger

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年9月14日
  • 表格存储：使用TableStoreWriter进行高并发、高吞吐的数据写入

    表格存储：使用TableStoreWriter进行高并发、高吞吐的数据写入

    表格存储：使用TableStoreWriter进行高并发、高吞吐的数据写入

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年9月15日
  • 快速幂的大数运算_快速幂模

    快速幂的大数运算_快速幂模

    快速幂的大数运算_快速幂模快速幂运算1.什么是快速幂2.快速幂的“小数”运算3.高精度（大数）的快速幂1.什么是快速幂快速幂，是指在进行幂运算的时候，用一种快速方法得出答案。比如，要求2^100的值，那按照最简单的方式，就是一个一个2去相乘，然后最终得到答案，那么这样就要计算100次，非常浪费时间，那么快速幂就是使用一种技巧使得将其计算次数减少，快速得到答案。2.快速幂的“小数”运算对于系统内置类型的整型，暂且叫他“小数”，这个时候进行快速幂运算，代码如下:#include<cstdio>#include&l

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月27日
  • 逻辑

    逻辑

    逻辑

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年1月13日
  • sublime text3激活码【2021最新】 idea

    sublime text3激活码【2021最新】

    (sublime text3激活码)好多小伙伴总是说激活码老是失效，太麻烦，关注/收藏全栈君太难教程，2021永久激活的方法等着你。IntelliJ2021最新激活注册码，破解教程可免费永久激活，亲测有效，下面是详细链接哦~https://javaforall.cn/100143.html0VOERWDQ5R-eyJsaWNlbnNlSWQi…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年3月30日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号