« | August 2025 | » | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | | | |
|
公告 |
My blog is about my major : network security.the most papers are talk about it ,I like my major ,i wish you could find what's you need in it. |
统计 |
blog名称:我的IT人生 日志总数:78 评论数量:185 留言数量:-1 访问次数:523978 建立时间:2006年4月5日 |
| 
|
本站首页 管理页面 写新日志 退出
[C/C++]银行家算法 |
转自:http://dev.csdn.net/article/52/52226.shtm
特别申明:转载一位大哥的程序一.算法介绍:**数据结构:1.可利用资源向量Available2.最大需求矩阵Max3.分配矩阵Allocation4.需求矩阵Need **功能介绍:模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成:第一部分:银行家算法(扫描)1.如果Request<=Need,则转向2;否则,出错2.如果Request<=Available,则转向3,否则等待3.系统试探分配请求的资源给进程4.系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finish[i]=False&&Need<=Work,则执行3;否则执行4(I为资源类别)3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:Work=Work+Allocation;Finish[i]=true;转24. 若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!
二.原代码及注释:#include<iostream.h>#include<fstream.h>#include<stdlib.h>#include "windows.h"#define MAX_PROCESS 32 //最大进程数#define MAX_COURCE 64 //最大资源类别
int MAX_FACT_PROCESS; //实际总进程数int MAX_FACT_COURCE; //实际资源类别数int Available[MAX_COURCE]; //可利用资源向量int Max[MAX_PROCESS][MAX_COURCE]; //最大需求矩阵int Allocation[MAX_PROCESS][MAX_COURCE]; //分配矩阵int Need[MAX_PROCESS][MAX_COURCE]; //需求矩阵
int Request_PROCESS; //发出请求的进程int Request_COURCE; //被请求资源类别int Request_COURCE_NEMBER; //请求资源数
struct COMP{int value;int num;int next;};int flag=0;void Read_Initiate(void){ //读入初始化文档ifstream infile("Initiate.txt"); if(!infile){cout<<"不能打开输入文件:"<<"Initiate.txt"<<'\n';exit(1);}cout<<"开始读入初始化文档"<<'\n';int ch;int Array[MAX_PROCESS*MAX_COURCE*2];int num=0;while(infile>>ch) Array[num++]=ch;num=0; MAX_FACT_COURCE=Array[num++]; for(int j=0;j<MAX_FACT_COURCE;j++)Available[j]=Array[num++]; MAX_FACT_PROCESS=Array[num++];for(int i=0;i<MAX_FACT_PROCESS;i++){for(int j=0;j<MAX_FACT_COURCE;j++)Max[i][j]=Array[num++];}infile.close();}
void Write_Initiate(void){ //写入初始化文档(分配资源ofstream outfile("Initiate.txt");if(!outfile){cout<<"不能打开初始化文档:"<<'\n';exit(1);}int Array[MAX_PROCESS*MAX_COURCE*2];int num=0;Array[num++]=MAX_FACT_COURCE; for(int i=0;i<MAX_FACT_COURCE;i++)Array[num++]=Available[i];Array[num++]=MAX_FACT_PROCESS;for(i=0;i<MAX_FACT_PROCESS;i++)for(int j=0;j<MAX_FACT_COURCE;j++)Array[num++]=Max[i][j];
num=0;outfile<<Array[num++]<<" ";for(i=0;i<MAX_FACT_COURCE;i++)outfile<<Array[num++]<<" ";outfile<<'\n'<<Array[num++]<<endl;for(i=0;i<MAX_FACT_PROCESS;i++){for(int j=0;j<MAX_FACT_COURCE;j++)outfile<<Array[num++]<<" ";outfile<<endl;}DWORD m_delay=3000;Sleep(m_delay);outfile.close();cout<<"修改初始化文档成功!"<<endl;}
void Allocated_list(void){ //读入已分配资源列表ifstream infile("Allocated_list.txt"); if(!infile){cout<<"不能打开输入文件:"<<"Allocated_list.txt"<<'\n';exit(1);}cout<<"开始读入已分配资源列表"<<'\n';int ch,num=0;int Array[MAX_PROCESS*MAX_COURCE];while(infile>>ch)Array[num++]=ch;num=0;for(int i=0;i<MAX_FACT_PROCESS;i++)for(int j=0;j<MAX_FACT_COURCE;j++)Allocation[i][j]=Array[num++];infile.close();}
void Set_Need(void){ //设置需求矩阵cout<<"设置需求矩阵"<<'\n';for(int i=0;i<MAX_FACT_PROCESS;i++)for(int j=0;j<MAX_FACT_COURCE;j++)Need[i][j]=Max[i][j]-Allocation[i][j];}
void Read_Request(void){ //读入请求向量ifstream infile("Request_list.txt"); if(!infile){cout<<"不能打开输入文件:"<<"Request_list.txt"<<'\n';exit(1);} cout<<"开始读入请求向量"<<'\n';int Array[3];int num=0,ch;while(infile>>ch) Array[num++]=ch; Request_PROCESS=Array[0]; Request_COURCE=Array[1]; Request_COURCE_NEMBER=Array[2];infile.close();}
void Write_Allocation(void){ //修改资源分配列表(资源分配)ofstream outfile("Allocated_list.txt");if(!outfile){cout<<"不能打开资源分配列表:"<<'\n';exit(1);}for(int i=0;i<MAX_FACT_PROCESS;i++){for(int j=0;j<MAX_FACT_COURCE;j++)outfile<<Allocation[i][j]<<" ";outfile<<endl;} DWORD m_delay=3000;Sleep(m_delay);cout<<"修改资源分配列表成功!"<<endl;outfile.close();}
void Allocate_Source(void){ //开始分配(已通过扫描和安全性检测)cout<<'\n'<<"开始给第"<<Request_PROCESS<<"个进程分配第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;Write_Initiate();Write_Allocation();DWORD m_delay=3000;Sleep(m_delay);cout<<'\n'<<"祝贺您,资源分配已成功!"<<endl;}
void Test_Safty(){ //安全性检测cout<<'\n'<<"进入安全性检测!"<<endl; int Work[MAX_COURCE];for(int i=0;i<MAX_FACT_COURCE;i++){Work[i]=Available[i];} bool Finish[MAX_PROCESS][MAX_COURCE];for(i=0;i<MAX_FACT_PROCESS;i++)for(int j=0;j<MAX_FACT_COURCE;j++)Finish[i][j]=false;COMP Array[32];for(i=0;i<MAX_FACT_PROCESS;i++){Array[i].value=Need[i][Request_COURCE-1]; Array[i].num=i;}for(i=0;i<MAX_FACT_PROCESS;i++)for(int j=i+1;j<MAX_FACT_PROCESS;j++){if(Array[i].value>=Array[j].value){int t;t=Array[j].value; Array[j].value=Array[i].value;Array[i].value=t;t=Array[j].num; Array[j].num=Array[i].num; Array[i].num=t;}else continue;}DWORD m_delay=3000;Sleep(m_delay);/*for(i=0;i<MAX_FACT_PROCESS;i++){for(int j=0;j<MAX_FACT_COURCE;j++)cout<<Need[i][j]<<'\t';cout<<endl;}*/if(Finish[Request_PROCESS-1][Request_COURCE-1]==false&&Need[Request_PROCESS-1][Request_COURCE-1]<=Work[Request_COURCE-1]){Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Request_PROCESS-1][Request_COURCE-1]; Finish[Request_PROCESS-1][Request_COURCE-1]=true;}else{cout<<"未通过安全性测试,不与以分配"<<endl;exit(0);} for(i=0;i<MAX_FACT_PROCESS;i++){if(Array[i].num==Request_PROCESS-1)continue;if(Array[i].num!=Request_PROCESS-1&&Finish[Array[i].num][Request_COURCE-1]==false&&Need[Array[i].num][Request_COURCE-1]<=Work[Request_COURCE-1]){Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Array[i].num][Request_COURCE-1]; Finish[Array[i].num][Request_COURCE-1]=true;}} for(i=0;i<MAX_FACT_PROCESS;i++){if(Finish[i][Request_COURCE-1]==true)continue;else{cout<<"未通过安全性测试,不与以分配"<<endl; exit(0);}}cout<<'\n'<<"找到一个安全序列:"<<"P"<<Request_PROCESS<<"--->"; for(i=0;i<MAX_FACT_PROCESS;i++){if(Array[i].num==Request_PROCESS)continue;elsecout<<"P"<<Array[i].num<<"--->";}cout<<'\n'<<"已通过安全性测试!"<<endl;Allocate_Source();}
void RUN(void){ //执行银行家算法
cout<<"*************************************************"<<'\n'<<"点击1执行!"<<'\n'<<"点击2退出!"<<'\n'<<"*************************************************"<<endl;cin>>flag;if(flag==2)exit(0);if(flag==1){cout<<"开始扫描请求信息!"<<endl;DWORD m_delay=3000;Sleep(m_delay);if(Request_COURCE_NEMBER>Need[Request_PROCESS-1][Request_COURCE-1]){cout<<'\n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl; cout<<"可是已超出该进程尚需的该类资源的最大数量,所以不予以分配!!"<<endl;exit(0);}if(Request_COURCE_NEMBER>Available[Request_COURCE-1]){cout<<'\n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl; cout<<"可是系统中尚无足够的资源,所以进入等待队列!!"<<endl;exit(0);} else{Available[Request_COURCE-1]=Available[Request_COURCE-1]-Request_COURCE_NEMBER; Allocation[Request_PROCESS-1][Request_COURCE-1]=Allocation[Request_PROCESS-1][Request_COURCE-1]+Request_COURCE_NEMBER; Need[Request_PROCESS-1][Request_COURCE-1]=Need[Request_PROCESS-1][Request_COURCE-1]-Request_COURCE_NEMBER;cout<<"扫描通过"<<endl;Sleep(m_delay);Test_Safty();}}else {cout<<"输入错误,请重新输入!"<<'\n';RUN();}}
void main(void){ Read_Initiate();cout<<MAX_FACT_COURCE<<'\t';for(int i=0;i<MAX_FACT_COURCE;i++)cout<<Available[i]<<'\t';cout<<endl<<MAX_FACT_PROCESS<<endl;for(i=0;i<MAX_FACT_PROCESS;i++){for(int j=0;j<MAX_FACT_COURCE;j++)cout<<Max[i][j]<<'\t';cout<<endl;}DWORD m_delay=3000;Sleep(m_delay);cout<<"读入成功"<<'\n';
Allocated_list();for(i=0;i<MAX_FACT_PROCESS;i++){for(int j=0;j<MAX_FACT_COURCE;j++)cout<<Allocation[i][j]<<'\t';cout<<endl;}Sleep(m_delay);cout<<"读入成功"<<'\n';
Set_Need(); for(i=0;i<MAX_FACT_PROCESS;i++){for(int j=0;j<MAX_FACT_COURCE;j++)cout<<Need[i][j]<<'\t';cout<<endl;} Sleep(m_delay);cout<<"设置成功"<<'\n';
Read_Request();cout<<'\n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;cout<<'\n'<<"读入成功"<<'\n';
RUN();}
三.数据测试注:数组Array[I]表示第I+1个实际意义量 需要创建三个txt文本。1.Initiate.txt文本3 3 3 2 //共有3类资源,Available[0]=3; Available[1]=3; Available[2]=25 //当前系统中有个进程7 5 3 // Max[0][0]=73 2 2 //Max[1][1]=39 0 22 2 2 4 3 32.Allocated_list.txt文本0 1 0 //Allocation[0][1]=12 0 03 0 22 1 10 0 23.Request_list.txt文本2 1 1 //第2个进程请求第1类资源1个Request[1][0]=1四.程序说明:本程序假设当前时刻只有一个进程请求某一类资源n个.若要满足某个进程当前时刻同时请求不止一类资源,则需要为最大需求矩阵Max,分配矩阵Allocation和需求矩阵Need增加维数,当然代码量也将大大增加,但是算法逻辑本身并无变化.
|
阅读全文(2034) | 回复(0) | 编辑 | 精华 |
|