学步园

//任何转载源代码的请保留出处作者等相关信息

//作者:chlaws

//运行环境:visual studio 2008

//描述:银行家算法及演示结果

//说明:这里不给出原创的思路，在阅读过程中有不懂得可以询问

#include <iostream><br /> #include <cstdlib><br /> #include <string><br /> #include <iterator><br /> #include <algorithm><br /> #include <vector><br /> #include <cstdlib><br /> using namespace std;<br /> const int MAX=5;<br /> class Banker;<br /> class ProcessInfo{<br /> public:<br /> ProcessInfo()<br /> {<br /> _processname="";</p> <p> memset(_allocation,0,MAX);<br /> memset(_need,0,MAX);<br /> memset(_work,0,MAX);<br /> memset(_tmpalloc,0,MAX);<br /> memset(_tmpneed,0,MAX);</p> <p> _finish=false;<br /> //_insafe=false;<br /> }<br /> static void Prompt();</p> <p> void InitProInfo();<br /> ProcessInfo(const ProcessInfo& rhs);<br /> ProcessInfo& operator=(const ProcessInfo& rhs);</p> <p> ~ProcessInfo(){}<br /> friend ostream& operator<<(ostream& out,const ProcessInfo& rhs);<br /> friend istream& operator>>(istream& in, const ProcessInfo& rhs);<br /> friend class Banker;</p> <p>private:</p> <p> static string _sourcename[MAX];<br /> static int _srctype;//资源种类数<br /> static int _sourcenum[MAX];//各种资源的数量<br /> static int _avaliable[MAX];</p> <p> string _processname;<br /> int _allocation[MAX];<br /> int _need[MAX];<br /> static bool _insafe;//判断是否已进入安全检查,通过该标志来确定是否输出work和max<br /> //false 没进入过,不输出work,可输出max<br /> //true 已进入过,输出work,不输出max<br /> int _tmpalloc[MAX];<br /> int _tmpneed[MAX];<br /> int _work[MAX];<br /> bool _finish;<br /> };</p> <p>//静态变量定义<br /> bool ProcessInfo::_insafe = false;<br /> string ProcessInfo::_sourcename[MAX]={"a","b","c"};<br /> int ProcessInfo::_srctype=3;<br /> int ProcessInfo::_sourcenum[MAX]={10,5,7};<br /> int ProcessInfo::_avaliable[MAX]={-1};//第一个数-1用来标识可用资源avariable没有经过计算<br /> //静态函数定义<br /> void ProcessInfo::Prompt()<br /> {<br /> int tmplen=ProcessInfo::_srctype;<br /> int ix;<br /> cout << "初始时有" << tmplen << "种资源(";<br /> for(ix=0; ix<tmplen-1; ix++)<br /> {<br /> cout << "[资源名:" << ProcessInfo::_sourcename[ix] <<",数量为:"<br /> << ProcessInfo::_sourcenum[ix] << "],";<br /> }<br /> cout << "[资源名:" <<ProcessInfo::_sourcename[ix] <<"数量为:"<br /> << ProcessInfo::_sourcenum[ix] << "]" << ")" ;</p> <p> //若avariable已经计算过了,则输出<br /> if(ProcessInfo::_avaliable[0] != -1)<br /> {<br /> cout << ",可用资源分别为(";<br /> for(ix=0; ix<tmplen-1; ix++)<br /> {<br /> cout << ProcessInfo::_avaliable[ix] <<",";<br /> }<br /> cout << ProcessInfo::_avaliable[ix] << ")";<br /> }<br /> cout << endl;</p> <p>}<br /> //重载输出操作符<br /> ostream& operator<<(ostream& out,const ProcessInfo& rhs)<br /> {<br /> out << rhs._processname << "/t";</p> <p> int tmplen=ProcessInfo::_srctype;<br /> int max[MAX];<br /> int wkalloc[MAX];//work+allocation<br /> ostream_iterator<int> itout(out," ");</p> <p> //通过是否进入安全检查来判断是输出work还是max<br /> if(ProcessInfo::_insafe)<br /> {<br /> for(int ix=0; ix<tmplen; ix++)<br /> {<br /> wkalloc[ix]=rhs._work[ix]+rhs._allocation[ix];<br /> }<br /> copy(rhs._work,rhs._work+tmplen,itout);<br /> }<br /> else<br /> {<br /> for(int ix=0; ix<tmplen; ix++)<br /> {<br /> max[ix]=rhs._allocation[ix]+rhs._need[ix];<br /> }<br /> copy(max,max+tmplen,itout);<br /> }</p> <p> out << " ";<br /> copy(rhs._allocation,rhs._allocation+tmplen,itout);<br /> out << " ";<br /> copy(rhs._need,rhs._need+tmplen,itout);<br /> out << " ";<br /> if(ProcessInfo::_insafe)<br /> {<br /> copy(wkalloc,wkalloc+tmplen,itout);<br /> out << "/t";<br /> rhs._finish ? out << "true" : out <<"false";<br /> }<br /> return out;<br /> }<br /> //重载输入操作符<br /> istream& operator>>(istream& in, ProcessInfo& rhs)<br /> {<br /> rhs.InitProInfo();<br /> return in;<br /> }<br /> ProcessInfo& ProcessInfo::operator=(const ProcessInfo& rhs)<br /> {<br /> _processname=rhs._processname;</p> <p> int tmplen=ProcessInfo::_srctype;<br /> for(int ix=0; ix<tmplen; ix++)<br /> {<br /> _allocation[ix]=rhs._allocation[ix];<br /> _need[ix]=rhs._need[ix];</p> <p> _tmpalloc[ix]=rhs._tmpalloc[ix];<br /> _tmpneed[ix]=rhs._tmpneed[ix];<br /> _work[ix]=rhs._work[ix];<br /> }</p> <p> _finish=rhs._finish;<br /> _insafe=rhs._insafe;</p> <p> return *this;<br /> }<br /> ProcessInfo::ProcessInfo(const ProcessInfo& rhs)<br /> {<br /> _processname=rhs._processname;</p> <p> int tmplen=ProcessInfo::_srctype;<br /> for(int ix=0; ix<tmplen; ix++)<br /> {<br /> _allocation[ix]=rhs._allocation[ix];<br /> _need[ix]=rhs._need[ix];</p> <p> _tmpalloc[ix]=rhs._tmpalloc[ix];<br /> _tmpneed[ix]=rhs._tmpneed[ix];<br /> _work[ix]=rhs._work[ix];<br /> }</p> <p> _finish=rhs._finish;<br /> //_insafe=rhs._insafe;<br /> }<br /> void ProcessInfo::InitProInfo()<br /> {<br /> cout << "输入进程名称:";<br /> cin >> _processname;<br /> int tmplen=ProcessInfo::_srctype;<br /> int ix;<br /> cout << "输入对每类资源的已分配[allocation](用空格隔开):" ;<br /> for(ix=0; ix<tmplen; ix++)<br /> {<br /> cin >> _allocation[ix];<br /> }<br /> cout << "输入对每类资源的需求[need](用空格隔开):";<br /> for(ix=0; ix<tmplen; ix++)<br /> {<br /> cin >> _need[ix];<br /> }<br /> cout << endl;<br /> }</p> <p>class Banker{<br /> public:<br /> Banker()<br /> {<br /> _ismodify=false;<br /> }<br /> Banker(const Banker& rhs)<br /> {<br /> copy(rhs._val.begin(),rhs._val.end(),_val.begin());<br /> }<br /> void InitBanker();<br /> bool SafeCheck();</p> <p> int Request(int* request);</p> <p> bool BankerCheck(int rindex,int* request);</p> <p> friend ostream& operator << (ostream& out,const Banker& rhs);<br /> private:<br /> //用来重置finish和work变量<br /> void reset();<br /> bool calavariable();<br /> bool modify();</p> <p> bool _ismodify;//用来确定是否对初始化信息做了修改false没修改,true已修改<br /> vector<ProcessInfo> _val;<br /> };<br /> //Private function define<br /> bool Banker::modify()<br /> {<br /> int tmplen;<br /> cout << "输入资源种类数量:" ;<br /> cin >> tmplen;<br /> ProcessInfo::_srctype=tmplen;</p> <p> cout << "输入各类资源名称(用空格隔开):" ;<br /> for(int ix=0; ix<tmplen; ix++)<br /> {<br /> cin >> ProcessInfo::_sourcename[ix];<br /> }<br /> cout << "输入各类资源的数量(用空格隔开):";<br /> for(int ix=0; ix<tmplen; ix++)<br /> {<br /> cin >> ProcessInfo::_sourcenum[ix];<br /> }<br /> return true;<br /> }<br /> bool Banker::calavariable()//计算每类可用资源数量<br /> {<br /> int srctypenum=ProcessInfo::_srctype;<br /> int processnum=_val.size();<br /> int usetotal;<br /> for(int id=0; id<srctypenum; id++)<br /> {<br /> usetotal=0;<br /> for(int ix=0; ix<processnum; ix++)<br /> {<br /> //ProcessInfo::_avaliable[id]+=_val[ix]._allocation[id];<br /> usetotal+=_val[ix]._allocation[id];<br /> }<br /> //ProcessInfo::_avaliable[id] =<br /> // ProcessInfo::_sourcenum[id] - ProcessInfo::_avaliable[id];<br /> ProcessInfo::_avaliable[id] = ProcessInfo::_sourcenum[id] - usetotal;<br /> if(ProcessInfo::_avaliable[id]<0)<br /> {<br /> //cout << "可用资源数为负";<br /> return false;<br /> }<br /> }<br /> return true;<br /> }<br /> void Banker::reset()<br /> {<br /> int tmplen=ProcessInfo::_srctype;<br /> int processnum=_val.size();<br /> for(int ix=0; ix<processnum; ix++)<br /> {<br /> _val[ix]._finish=false;<br /> for(int id=0; id<tmplen; id++)<br /> {<br /> _val[ix]._work[id]=0;<br /> }<br /> }<br /> }<br /> //End private function define</p> <p>bool Banker::BankerCheck(int rindex,int* request)<br /> {<br /> //进入预分配<br /> //使用tmpalloc保存未修改的allocation<br /> //使用tmpneed保存未修改的need<br /> //使用临时变量tmpavaliable保存未修改的avaliable<br /> //修改avaliable,allocation,need<br /> int tmplen=ProcessInfo::_srctype;<br /> int tmpavaliable[MAX];<br /> int ix;<br /> for(ix=0; ix<tmplen; ix++)<br /> {<br /> _val[rindex]._tmpalloc[ix] = _val[rindex]._allocation[ix];<br /> _val[rindex]._tmpneed[ix] = _val[rindex]._need[ix];<br /> tmpavaliable[ix] = ProcessInfo::_avaliable[ix];<br /> ProcessInfo::_avaliable[ix] -= request[ix];<br /> _val[rindex]._allocation[ix] += request[ix];<br /> _val[rindex]._need[ix] -= request[ix];<br /> }<br /> //由于初始时调用过安全性检查,所以要重置finish和work<br /> reset();<br /> //不存在安全序列,重置avaliable,allocation,need<br /> if(!SafeCheck())<br /> {<br /> for(ix=0; ix<tmplen; ix++)<br /> {<br /> _val[rindex]._allocation[ix] = _val[rindex]._tmpalloc[ix] ;<br /> _val[rindex]._need[ix] = _val[rindex]._tmpneed[ix] ;<br /> ProcessInfo::_avaliable[ix] = tmpavaliable[ix] ;<br /> }<br /> return false;<br /> }<br /> return true;<br /> }<br /> void Banker::InitBanker()<br /> {<br /> char c;<br /> ProcessInfo::Prompt();<br /> cout << "是否需要修改进程默认的初始相关信息(y/n):";<br /> cin >> c;<br /> if (c == 'y' || c == 'Y')<br /> {<br /> _ismodify=true;<br /> if(!modify()){<br /> cout << "operator error!";<br /> exit(1);<br /> }<br /> }<br /> if(_ismodify)<br /> {<br /> ProcessInfo::Prompt();<br /> }<br /> do{<br /> ProcessInfo tmpObj;<br /> cin >> tmpObj;<br /> _val.push_back(tmpObj);<br /> //system("cls"); //如果觉得需要刷新屏幕就把这句加上<br /> cout << "是否完成输入,并进入安全检查(y/n):";<br /> cout.flush();</p> <p> cin >> c;<br /> }while(c!='y' && c!='Y');</p> <p> if(!calavariable())<br /> {<br /> cout << "calculator avariable error,avariable have negative value!" << endl;<br /> exit(1);<br /> }<br /> }<br /> bool Banker::SafeCheck()<br /> {<br /> int processnum=_val.size();<br /> int tmplen=ProcessInfo::_srctype;<br /> int tmpwork[MAX]={0};</p> <p> copy(ProcessInfo::_avaliable,ProcessInfo::_avaliable+tmplen,tmpwork);<br /> bool isnlessw=true;//标识need是否小于work;<br /> int safenum=0;//保存finish为true的次数</p> <p> vector<ProcessInfo> safelist;<br /> //考虑最坏查找情况使用processnum次大循环进行查找<br /> for(int i=0; i<processnum; i++)<br /> { //每次大循环中小循环,循环processnum次<br /> for(int ix=0; ix<processnum; ix++)<br /> {</p> <p> if(_val[ix]._finish == false)<br /> {<br /> isnlessw=true;<br /> //判断 need <= work;<br /> for(int id=0; id<tmplen; id++)<br /> {<br /> if(_val[ix]._need[id] > tmpwork[id])<br /> {<br /> isnlessw=false;<br /> break;<br /> }<br /> }<br /> if(!isnlessw)//need !<= work,则跳过对finish,work的修改.表示没有找到符合条件的<br /> {<br /> continue;<br /> }<br /> else<br /> {<br /> _val[ix]._finish=true;<br /> safenum += 1;<br /> //修改work<br /> copy(tmpwork,tmpwork+tmplen,_val[ix]._work);<br /> //修改tmpwork<br /> for(int id=0; id <tmplen; id++)<br /> {<br /> //work=work+allocation<br /> tmpwork[id]=tmpwork[id]+_val[ix]._allocation[id];<br /> }<br /> //将符合的要求的进程项插入安全序列中<br /> safelist.push_back(_val[ix]);<br /> }<br /> }<br /> }<br /> }</p> <p> if(safenum != processnum)<br /> {<br /> cout << "不存在安全序列" << endl;<br /> return false;<br /> }<br /> else<br /> {<br /> ProcessInfo::_insafe=true;//修改insafe标志,表示进入了安全检查.<br /> //用于在输出时输出work,而不输出max等<br /> cout << "存在安全序列!" <<endl;<br /> //ProcessInfo::Prompt();<br /> cout << "进程/tWork/tAllocation/tNeed/tWork+Allocation/tFinish/n";<br /> ostream_iterator<ProcessInfo> itout(cout,"/n");<br /> copy(safelist.begin(),safelist.end(),itout);<br /> }<br /> return true;<br /> }<br /> int Banker::Request(int* request)<br /> {<br /> int tmplen=ProcessInfo::_srctype;<br /> //int request[MAX];<br /> cout << "输入请求资源的进程名称(";<br /> int processnum=_val.size();<br /> int ix;//用于循环中的下标索引变量<br /> int rindex=-1;//用来保存request所对应进程在进程序列中的索引值<br /> for(ix=0; ix < processnum-1; ix++)<br /> {<br /> cout << _val[ix]._processname <<",";<br /> }<br /> cout << _val[processnum-1]._processname<< "):";<br /> string rprocessname;<br /> cin >> rprocessname;<br /> bool isnametrue=false; //标识输入的进程名称是否正确.<br /> //int isnametrue=0; //标识输入的进程名称是否正确.<br /> //判断进程名是否在进程序列中<br /> for(ix=0; ix < processnum; ix++)<br /> {<br /> if(rprocessname.compare(_val[ix]._processname) == 0)<br /> {<br /> isnametrue=true;<br /> //isnametrue=1;<br /> rindex=ix;<br /> break;<br /> }<br /> }<br /> if(!isnametrue)<br /> {<br /> cout<< "输入的进程名不在进程序列中,出错退出!" << endl;<br /> exit(1);<br /> }</p> <p> cout << "输入对各类资源的请求数量(用空格隔开):";<br /> for(ix=0; ix<tmplen; ix++)<br /> {<br /> cin >> request[ix];<br /> }</p> <p> bool isrlessn=true;//用来标识request是否小于need;<br /> //request <= need<br /> for(ix=0; ix<tmplen; ix++)<br /> {<br /> if(request[ix] > _val[rindex]._need[ix])<br /> {<br /> isrlessn=false;<br /> break;<br /> }<br /> }<br /> if(!isrlessn)<br /> {<br /> cout << "error:request !<= need" << endl;<br /> return -1;<br /> }</p> <p> bool isrlessa=true;//用来标识request是否小于avaliable;<br /> //request <= avaliable<br /> for(ix=0; ix<tmplen; ix++)<br /> {<br /> if(request[ix] > ProcessInfo::_avaliable[ix])<br /> {<br /> isrlessa=false;<br /> break;<br /> }<br /> }<br /> if(!isrlessa)<br /> {<br /> cout << "error:request !<= avaliable" << endl;<br /> return -1;<br /> }<br /> return rindex;<br /> }<br /> ostream& operator << (ostream& out,const Banker& rhs)<br /> {<br /> cout << endl;<br /> ProcessInfo::Prompt();<br /> cout << "进程/tMax/tAllocation/tNeed/n";<br /> ostream_iterator<ProcessInfo> itout(out,"/n");<br /> copy(rhs._val.begin(),rhs._val.end(),itout);<br /> return out;<br /> }<br /> int main()<br /> {<br /> Banker b;<br /> b.InitBanker();</p> <p> cout << b;<br /> if(!b.SafeCheck())<br /> {<br /> cout << "在t0时刻不存在安全序列,结束退出" << endl;<br /> exit(1);<br /> }<br /> else<br /> {<br /> cout << "所以在t0时刻存在安全序列" << endl;<br /> }</p> <p> int request[MAX];<br /> int rindex;<br /> while(1)<br /> {<br /> rindex=b.Request(request);<br /> if(rindex ==-1 )<br /> {<br /> cout << "请求request 不符合条件" << endl;<br /> continue;<br /> }<br /> if(!b.BankerCheck(rindex,request))<br /> {<br /> cout << "BankerCheck error:no exist safe queue!" << endl;<br /> }<br /> }<br /> return 0;<br /> }  

运行结果如下：

初始时有3种资源([资源名:a,数量为:10],[资源名:b,数量为:5],[资源名:c数量为:7])<br /> 是否需要修改进程默认的初始相关信息(y/n):n<br /> 输入进程名称:p0<br /> 输入对每类资源的已分配[allocation](用空格隔开):0 1 0<br /> 输入对每类资源的需求[need](用空格隔开):7 4 3<br /> 是否完成输入,并进入安全检查(y/n):n<br /> 输入进程名称:p1<br /> 输入对每类资源的已分配[allocation](用空格隔开):2 0 0<br /> 输入对每类资源的需求[need](用空格隔开):1 2 2<br /> 是否完成输入,并进入安全检查(y/n):n<br /> 输入进程名称:p2<br /> 输入对每类资源的已分配[allocation](用空格隔开):3 0 2<br /> 输入对每类资源的需求[need](用空格隔开):6 0 0<br /> 是否完成输入,并进入安全检查(y/n):n<br /> 输入进程名称:p3<br /> 输入对每类资源的已分配[allocation](用空格隔开):2 1 1<br /> 输入对每类资源的需求[need](用空格隔开):0 1 1<br /> 是否完成输入,并进入安全检查(y/n):n<br /> 输入进程名称:p4<br /> 输入对每类资源的已分配[allocation](用空格隔开):0 0 2<br /> 输入对每类资源的需求[need](用空格隔开):4 3 1<br /> 是否完成输入,并进入安全检查(y/n):y<br /> 初始时有3种资源([资源名:a,数量为:10],[资源名:b,数量为:5],[资源名:c数量为:7]),可<br /> 用资源分别为(3,3,2)<br /> 进程 Max Allocation Need<br /> p0 7 5 3 0 1 0 7 4 3<br /> p1 3 2 2 2 0 0 1 2 2<br /> p2 9 0 2 3 0 2 6 0 0<br /> p3 2 2 2 2 1 1 0 1 1<br /> p4 4 3 3 0 0 2 4 3 1<br /> 存在安全序列!<br /> 进程 Work Allocation Need Work+Allocation Finish<br /> p1 3 3 2 2 0 0 1 2 2 5 3 2 true<br /> p3 5 3 2 2 1 1 0 1 1 7 4 3 true<br /> p4 7 4 3 0 0 2 4 3 1 7 4 5 true<br /> p0 7 4 5 0 1 0 7 4 3 7 5 5 true<br /> p2 7 5 5 3 0 2 6 0 0 10 5 7 true<br /> 所以在t0时刻存在安全序列<br /> 输入请求资源的进程名称(p0,p1,p2,p3,p4):p1<br /> 输入对各类资源的请求数量(用空格隔开):1 0 2<br /> 存在安全序列!<br /> 进程 Work Allocation Need Work+Allocation Finish<br /> p1 2 3 0 3 0 2 0 2 0 5 3 2 true<br /> p3 5 3 2 2 1 1 0 1 1 7 4 3 true<br /> p4 7 4 3 0 0 2 4 3 1 7 4 5 true<br /> p0 7 4 5 0 1 0 7 4 3 7 5 5 true<br /> p2 7 5 5 3 0 2 6 0 0 10 5 7 true<br /> 输入请求资源的进程名称(p0,p1,p2,p3,p4):p4<br /> 输入对各类资源的请求数量(用空格隔开):3 3 0<br /> error:request !<= avaliable<br /> 请求request 不符合条件<br /> 输入请求资源的进程名称(p0,p1,p2,p3,p4):p0<br /> 输入对各类资源的请求数量(用空格隔开):0 2 0<br /> 不存在安全序列<br /> BankerCheck error:no exist safe queue!<br /> 输入请求资源的进程名称(p0,p1,p2,p3,p4):p0<br /> 输入对各类资源的请求数量(用空格隔开):0 1 0<br /> 存在安全序列!<br /> 进程 Work Allocation Need Work+Allocation Finish<br /> p1 2 2 0 3 0 2 0 2 0 5 2 2 true<br /> p3 5 2 2 2 1 1 0 1 1 7 3 3 true<br /> p4 7 3 3 0 0 2 4 3 1 7 3 5 true<br /> p0 7 3 5 0 2 0 7 3 3 7 5 5 true<br /> p2 7 5 5 3 0 2 6 0 0 10 5 7 true<br /> 输入请求资源的进程名称(p0,p1,p2,p3,p4):22<br /> 输入的进程名不在进程序列中,出错退出!<br /> 请按任意键继续. . .