«August 2025»
12
3456789
10111213141516
17181920212223
24252627282930
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.

我的分类(专题)

首页(78)
others(4)
HTML+CSS+JS(2)
汇编(1)
music(0)
art(0)
linux(29)
php(1)
math(0)
network security(1)
idea(0)
企业管理与营销(4)
life(10)
link(0)
软件工程理论(2)
C/C++(14)
algorithm(1)


最新日志
何谓数据结构
陈老师的BLOG
iptables 规则的保存
compatible , enhance
重装windows后,修复Fedora的
著名的SQL注入攻击法 (转)
PE病毒技术剖析[转载]
auto register stat
调节WINDOWS为保护眼睛的颜色!
类似深构造函数的运算符‘=’重载用法

最新回复
直接给他这个时间做什么就行
回复:三国典故集锦
回复:《如何控制自己的时间和生活 》精彩
回复:扫描方法详细
回复:心态决定一切
回复:心态决定一切
回复:男人100
回复:信息熵(定义,性质,热力学熵)
回复:《如何控制自己的时间和生活 》精彩
回复:编写类string的构造函数、拷贝

留言板
签写新留言


统计
blog名称:我的IT人生
日志总数:78
评论数量:185
留言数量:-1
访问次数:523978
建立时间:2006年4月5日

链接




本站首页    管理页面    写新日志    退出

[C/C++]银行家算法
zc9706 发表于 2008/4/5 9:55:43

转自: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) | 编辑 | 精华


发表评论:
昵称:
密码:
主页:
标题:
验证码:  (不区分大小写,请仔细填写,输错需重写评论内容!)
站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.031 second(s), page refreshed 144770422 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号