银行家算法的模拟实现

银行家算法的模拟实现1 课设简介： 1.1 课程设计题目 银行家算法的模拟实现 1.2 课程设计目的 1.2.1了解进程产生死锁原因，了解为什么要进行死锁的避免。 1.2.2掌握银行家算法的数据结构，了解算法的执行过程，加深对银行家算法的理解。 1.3 课程设计内容 设计一个n 个并发进程共享m 个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法实现。2 实验原理分析：2.1 整个银行家算法的思路 先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。2.2 算法用到的主要数据结构和C语言说明。 2.2.1可利用资源向量 INT AVAILABLEM M为资源的类型。 2.2.2最大需求矩阵 INT MAXNM N为进程的数量。 2.2.3已分配矩阵 INT ALLOCATIONNM 2.2.4还需求矩阵 INT NEEDNN 2.2.5申请各类资源数量int Requestx; 2.2.6工作向量 int Workx; 2.2.7 int Finishy; /是否有足够的资源分配给进程，0为否，非0为是2.3 银行家算法主程序 2.3.1系统初始化。调用函数 chushihua()，输入进程数量，资源种类，各资源可用数量，各进程已分配、最大需求各资源数量等 2.3.2安全性算法调用函数safe()检查当前资源分配状态。 2.3.3调用bank()函数，输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。 2.3.4检查用户请求是否小于还需求量，条件是K=NEEDI,J。如果条件不符则提示重新输入，即不允许索取大于需求量 2.3.5检查用户的请求是否小于系统中的可利用资源数量，条件是K=AVALIABLEI,J。如果条件不符则申请失败，阻塞该进程，重新进行进程动态资源申请（使用goto语句跳转） 2.3.6进行资源的预分配，语句如下：AVALIBLEIJ= AVALIBLEIJ-K；ALLOCATIONIJ= ALLOCATIONIJ+K；NEEDIJ=NEEDIJ-K； 2.3.7系统调用安全性检查算法（safe()函数）进行检查，如果检查不安全，则进行回收，进程资源申请失败进入等待。否则不用回收，并检查该进程是否已获得所有需要资源，如是则进行其拥有资源释放，语句如下：Availablej=Availablej+Allocationkj;Allocationkj=0; 2.3.8 dowhile 循环输入字符Y/N判断是否继续进行资源申请。2.4 安全性检查算法（safe()函数） 2.4.1设置两个临时变量：FINISHN记录进程模拟执行的结束状态，初值为0，如果可以模拟执行结束，则可设为1。WORKM记录模拟执行中资源的回收情况，初值为AVAILABLEM的值。 2.4.2在进程中查找符合以下条件的进程。条件1：FINISHI=0条件2：NEEDIJ=WORKJ 2.4.3如果查找成功则存储安全序列并进行资源的模拟回收，语句如下： FINISHI=1 WORKJ=WORKJ+ALLOCATIONIJ； 2.4.4如查找不成功，则根据不同地方的调用情况进行相应判断处理。3 程序结构分析：3.1 程序流程图3.2 程序模块划分本程序共有以下六个模块： 3.2.1、字符判断模块：判断输入的字符是否为数字，如果不是则提示出错并重新输入，主要处理输入为非数字时程序出现运行错误现象。此模块功能由数字判断函数（ int shuzi(int sz); ）实现。 3.2.2、程序初始化模块：用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。此模块功能在系统初始化函数（void chushihua(); ）中实现。 3.2.3、当前安全性检查模块：用于判断当前状态安全性，根据不同地方的调用提示处理不同，在安全性算函数（void safe(); ）中实现。 3.2.4、银行家算法模块：进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程，在银行家算法函数（void bank();）中实现。 3.2.5、显示分配模块：显示当前资源分配详细情况，包括：各种资源的总数量(all)、系统目前各种资源可用的数量、各进程已经得到的资源数量、各进程还需要的资源量，在显示分配情况函数（void showdata(); ）中实现。 3.2.6、签名模块：用于程序结束时显示程序版权声明签名等，在签名函数（void sign(); ）中实现。4 数据结构分析本程序所使用的主体数据结构如下：4.1定义全局变量const int x=50,y=100; /定义常量，便于修改int Availablex; /各种资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量int Maxyy; /各进程对各类资源的最大需求数int Needyy; /还需求矩阵int Requestx; /申请各类资源的数量int Workx; /工作向量，表系统可提供给进程运行所需各类资源数量int Finishy; /表系统是否有足够的资源分配给进程，0为否，1为是int py; /存储安全序列int i,j; /全局变量，主要用于循环语句中int n,m; /n为进程的数量,m为资源种类数int l=0,counter=0;4.2函数声明int shuzi(int sz); /数字判断函数，还可使用 void shuzi(int& sz); 方式void chushihua(); /系统初始化函数void safe(); /安全性算法函数void bank(); /银行家算法函数void showdata(); /函数showdata,输出当前资源分配情况void sign(); /签名函数4.3主函数结构int main()system(color 06f); /设置当前窗口的背景色和前景色cout /显示程序开始提示信息chushihua(); /初始化函数调用coutendlendl;showdata(); /输出初始化后的状态/=判断当前状态的安全性=safe(); /安全性算法函数调用if (ln)coutn当前状态不安全，无法申请,程序退出!endl;coutendl; system(pause); sign(); /调用签名函数return 0; / break; else int i; /局部变量l=0;coutn安全的状态!endl;cout安全序列为: ;coutendl进程(p0); /输出安全序列，考虑显示格式，先输出第一个for (i=1; in; i+)cout进程(pi); for (i=0; in; i+) Finishi=0; /所有进程置为未分配状态coutendlendl;bank(); /银行家算法函数调用return 0; 5 程序代码见下=银行家算法的模拟实现=一、实验题目银行家算法的模拟实现二、目的：1、了解进程产生死锁的原因，了解为什么要进行死锁的避免。2、掌握银行家算法的数据结构，了解算法的执行过程，加深对银行家算法的理解。三、内容： 设计一个n 个并发进程共享m 个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。要求采用银行家算法实现。四、实验提示：1、整个银行家算法的思路。先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。2、算法用到的主要数据结构和C语言说明。（1）、可利用资源向量 INT AVAILABLEM M为资源的类型。（2）、最大需求矩阵 INT MAXNM N为进程的数量。（3）、已分配矩阵 INT ALLOCATIONNM （4）、还需求矩阵 INT NEEDNN（5）、申请各类资源数量int Requestx; /（6）、工作向量 int Workx;（7）、int Finishy; /表示系统是否有足够的资源分配给进程，0为否，非0为是3、银行家算法 （主程序）（1）、系统初始化。输入进程数量，资源种类，各进程已分配、还需求各资源数量，各资源可用数量等（2）、输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。（3）、检查用户的请求是否小于还需求的数量，条件是 K=NEEDI,J。如果条件不符则提示重新输入，即不允许索取大于需求量（4）、检查用户的请求是否小于系统中的可利用资源数量，条件是K=AVALIABLEI,J。如果条件不符则申请失败，阻塞该进程，重新进行进程动态资源申请（使用goto语句）（5）、进行资源的预分配，语句如下：AVALIBLEIJ= AVALIBLEIJ-K；ALLOCATIONIJ= ALLOCATIONIJ+K；NEEDIJ=NEEDIJ-K；（6）、系统调用安全性检查算法（safe()函数）进行检查，如果检查通过，则不用回收，否则进行回收，进程资源申请失败进入等待。4、安全性检查算法（safe()子函数）（1）、设置两个临时变量。FINISHN记录进程模拟执行的结束状态，初值为0，如果可以模拟执行结束，则可设为1，也可设为其它非零值以表示执行的先后次序。WORKM记录模拟执行中资源的回收情况，初值为AVAILABLEM的值。（2）、在进程中查找符合以下条件的进程。条件1：FINISHI=0条件2：NEEDIJ=WORKJ（3）、如果查找成功则进行资源的模拟回收，语句如下：WORKJ=WORKJ+ALLOCATIONIJ；FINISHI=1 或查找到的顺序号（4）、如果查找不成功，则检查所有进程的FINISH，如果有一个为0，则系统不为0，返回不成功标志。否则返回成功标志。*/#include #include #include #include #include /=定义全局变量=const int x=50,y=100; /定义常量，便于修改int Availablex; /各种资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量int Maxyy; /各进程对各类资源的最大需求数int Needyy; /还需求矩阵int Requestx; /申请各类资源的数量int Workx; /工作向量，表示系统可提供给进程继续运行所需的各类资源数量int Finishy; /表示系统是否有足够的资源分配给进程，0为否，非0为是int py; /存储安全序列int i,j;int n,m; /n为进程的数量,m为资源种类数int l=0,counter=0;/函数声明int shuzi(int sz); /数字判断函数 或者使用 void shuzi(int& sz); 方式void chushihua(); /系统初始化函数void safe(); /安全性算法函数void bank(); /银行家算法函数void showdata(); /函数showdata,输出当前资源分配情况void sign(); /签名函数 /=数字判断函数=int shuzi(int sz) /输入数据并判断是否为数字char *temp;temp=new char; /临时指针，存放输入字符int len; /存储取字符的长度sz=0 ; /清零char s; /do /输入赌注，只能输入数字 / gets(temp); /getline(cin,temp)cintemp;len=strlen(temp); /取字符长度for(int i=0;ilen;i+) s= *(temp+i);if(s9) cout 笨蛋，输错了! 你输入的是数字吗?! nn;cout请重新输入：;break; while(s9); for(int i=0;ilen;i+) /输入字符串转化为整形数字 int t=1; for(int j=1;jlen-i;j+) t*=10;sz+=(*(temp+i)-48)*t; return sz;/=系统初始化函数=void chushihua() /=系统初始化输入=cout% 程序开始，系统初始化输入 %endl; /endlcout=endlendl;cout请输入进程的数量: ;/从此开始输入有关数据n=shuzi(n);cout请输入资源种类数: ;m=shuzi(m);coutendlendl请输入各种资源可利用的数量( m 种): endl;coutendl; for (j=0; jm; j+)cout 输入资源 j 可利用的数量Availablej: ;Availablej=shuzi(Availablej);Workj=Availablej; /初始化Workj/ coutendl;/system(cls); /清屏coutendl;cout请输入各进程当前已分配的资源数量Allocationnm: endlendl;for (i=0; in; i+)for (j=0; jm; j+)cout 请输入进程 i 当前已分配的资源 j 数量: ;Allocationij=shuzi(Allocationij);/ coutendl;coutendl;Finishi=0;/初始化Finishi/break;coutendlendl;cout请输入各进程对各类资源的最大需求数Maxnm: endlendl;for (i=0; in; i+)for (j=0; jm; j+) cout 请输入进程 i 对资源 j=Allocationij) /Needij = Maxij-Allocationij; /计算还需求量elseNeedij=0;/最大需求量小于已分配量时还需求量为0,即此类资源已足够不需再申请coutendl;coutendl% 初始化完成! %endl;/=安全性算法函数=void safe() l=0; for (i=0; in;) /i+ if (Finishi=0) /寻找Finishi=0的进程 条件一counter=0; /记数器/* 算法一： for (j=0; j=Needij) /可用大于等于需求counter=counter+1;/记数if(counter=m)*/ /算法二：for (j=0; j=Needij); /可用大于等于需求elsecounter=1;break;if(counter!=1) /进程的每类资源量都符合条件Workj=Needij 条件二pl=i; /存储安全序列Finishi=1; /标志为可分配for (j=0; j=Needij i= -1; /从第一个进程开始继续寻找满足条件一二的进程i+; /for循环继续寻找/=显示分配情况函数 =void showdata() /函数showdata,输出当前资源分配情况 int i,j; /局部变量int Ally; /各种资源的总数量int l2; /局部变量 l1,cout=endlendl;cout% 系统当前状态如下：%endlendl;cout% 各种资源的总数量(all):endl; for (j=0;jm;j+) cout 资源j: ;Allj=Availablej; /初始化 先赋值加上可利用量for (i=0;in;i+)Allj+=Allocationij; /再加上每个进程已分配量计算J类资源总量coutAllj ;if (j+1)%5=0 ) coutendl; /每行显示五个 & j!=0coutendlendl; cout% 系统目前各种资源可用的数为(available):endl; for (j=0;jm;j+)cout 资源j: Availablej ;if(j+1)%5=0) coutendl; /每行最多显示五个 & j!=0coutendlendl; cout% 各进程已经得到的资源量(allocation): endl; / l1=0; /归零for(i=0;i=m/5;i+) /设计每行最多显示五种资源for (j=i*5;ji*5+5 & jm;j+)cout 资源j;coutendl;for(l2=0;l2n;l2+)cout进程l2:;for (j=i*5;ji*5+5 & jm;j+)coutAllocationl2j ;coutendl;coutendl;cout% 各进程还需要的资源量(need):endl; /endl/l1=0;for(i=0;i=m/5;i+) /设计每行显示五种资源for (j=i*5;ji*5+5 & jm;j+)cout 资源j;coutendl;for(l2=0;l2n;l2+)cout进程l2:;for (j=i*5;ji*5+5 & jm;j+)coutNeedl2j ;coutendl;coutendl;cout=endl;coutendl;system(pause); / 暂停/=签名函数 =void sign() system(cls); / 清屏coutendlendlendlendlendlendl;couttt =endl;couttt = =endl;couttt = 本程序由李志文制作 =endl;couttt = 谢谢你的使用 =endl;couttt = 版权没有，随便复制 =endl;couttt = =endl;couttt = 洛阳师院 08.5 =endl;couttt = =endl;couttt =endl;coutendlendlendlendlendlendlendlendlendl;/ getch(); /等待键盘输入，不返回任何值，用于设置程序运行界面 system(pause);/暂停 比较两种方式/* 经过在不同的编辑器中调试发现,不同的调试器对函数执行的顺序有差别如在此处使用 getch() 和 system(pause) 函数时,在visual c+6.0中先执行此函数再显示,而在dev-c+ 中则按顺序执行对此问题我在很多地方搜索查找均未找到满意的答案,本次换用调试器才发现理解-4.29本次调试格式时，将换行命令 n 改为 endl 时，发现 system(pause) 函数执行变为顺序执行，由此领悟到 n 命令和system(pause)调用了一样系统函数，在调用的顺序上system(pause)优先所以它就先执行了查找了一下相关帮助：在OSTREAM.H中有这样的一个inline函数：inline _CRTIMP ostream& _cdecl endl(ostream& _outs) return _outs n flush; 也就是说endl= return _outs n flush;endl除了写n进外，还调用flush函数，刷新缓冲区，把缓冲区里的数据写入文件或屏幕，如果考虑效率就用n*/ coutl; coutttt ;/=银行家算法函数=void bank()cout=endlendl;cout% 以下开始为进程进行资源分配申请 %endlendl;/=申请资源=int k=0;/用于输入进程编号bool r=false; / 初值为假，输入Y继续申请则置为真do/输入请求cout请输入申请资源的进程编号(输入0-n-1之间): ;k=shuzi(k);coutn-1) /输入异常处理coutendl您输入了错误的进程号，请重新输入!endl;coutendl请输入申请资源的进程编号(输入0-n-1之间): ;k=shuzi(k);coutendl;coutendl请输入该进程申请各类资源的数量: endl;for (j=0; jm; j+)do /dowhile 循环判断申请输入的情况cout进程 k 申请资源j的数量:;Requestj=shuzi(Requestj); coutNeedkj) /申请大于需求量时出错，提示重新输入（贷款数目不允许超过需求数目）cout申请大于需要量!endl;cout您申请资源j的数量为Requestj,大于进程k对该资源需求量Needkj。endl;cout请重新输入!Availablej) /申请大于可利用量， 应该阻塞等待？ ？coutn没有那么多资源，目前可利用资源j数量为Availablej,本次申请不成功，进程等待!Needkj); /RequestjAvailablej|/改变Avilable、Allocation、Need的值for (j=0; jm; j+) Availablej = Availablej-Requestj;Allocationkj = Allocationkj+Requestj;Needkj = Needkj-Requestj;Workj = Availablej;/判断当前状态的安全性safe(); /调用安全性算法函数if (ln) l=0; coutn当前状态不安全,不予分配!endl;/恢复数据 for (j=0; jm; j+) Availablej = Availablej+Requestj;Allocationkj = Allocationkj-Requestj;Needkj = Needkj+Requestj;Workj = Availablej;for (i=0; in; i+)Finishi=0; /进程置为未分配状态else/ system(cls);l=0; coutn申请资源成功!endl;/=/* /如果该进程所有需要的资源都已申请到，即NEEDkj均为零，则进程可以执行，执行完后需释放其所有拥有的资源/算法一：for(j=0;jm;j+) if(Needkj=0) l=l+1; if(l=m) /此处借用 l 做下计数器for (j=0;jm;j+) /释放该进程的所有资源Availablej=Availablej+Maxkj;Allocationkj=0; l=0; /归零*/算法二： （相对第一种算法节省时间）for(j=0;jm;j+) if(Needkj=0);else /有一种资源还没全部申请到，则该进程不可执行，不能释放拥有的资源l=1; /置l为1，作为判断标志break; if(l!=1) /进程可以执行，则释放该进程的所有资源for (j=0;jm;j+) Availablej=Availablej+Allocationkj;Allocationkj=0;cout该进程已得到所有需求资源，执行后将释放其所有拥有资源！endl;l=0; /归零/=coutn安全的状态!endl;cout安全序列为: ;coutendl进程(p0); /输出安全序列，考虑显示格式，先输出第一个Finish0=0;for (i=1; in; i+)cout进程(pi);Finishi=0; /所有进程置为未分配状态coutendlendl;showdata(); /显示当前状态 ppp: /申请大于可利用量， 应该阻塞等待,结束本次资源申请，GOTO 语句跳转至此coutendl是否继续申请资源(y/n) ?;char* b=new char; /输入y/n，判断是否继续申请 b;coutendl;cout=endlendl;coutendl;if(*b=y|*b=Y)r=true;elser=false; /输入非 Y 则令 R =false / system(cls); /在sign() 里调用 sign(); /调用签名函数 while (r=true);/=主函数=int main() / void main()system(color 06f); /设置当前窗口的背景色和前景色 0 = 黑色 8 = 灰色 coutendlendl;couttt=endl;couttt| |endl;couttt| 模拟银行家算法 |endl; couttt| |endl;couttt| 作者：lzw |endl;couttt| |endl;couttt=endlendlendlendl;chushihua(); /初始化函数调用coutendlendl;showdata(); /输出初始化后的状态/=判断当前状态的安全性=safe(); /安全性算法函数调用if (ln)coutn当前状态不安全，无法申请,程序退出!endl;coutl;sign(); /调用签名函数 return 0; / break; else int i; /局部变量l=0;coutn安全的状态!endl;cout安全序列为: ;coutendl进程(p0); /输出安全序列，考虑显示格式，先输出第一个for (i=1; in; i+)cout进程(pi); for (i=0; in; i+) Finishi=0; /所有进程置为未分配状态coutendlendl;bank(); /银行家算法函数调用return 0; / break; 6 程序运行结果分析6.1 示例数据进程数量：2 资源种类：2 资源0可利用数：2 资源1可利用数：2进程0已分配： 0 1 进程1已分配： 0 2进程0最大需求：2 4 进程1最大需求：2 26.2 运行结果6.2.1程序运行开始显示提示界面：6.2.1程序初始化输入（进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数）：6.2.2初始化完成后，输出系统当前各进程及各类资源的分配状态：6.2.3按任意键后判断状态为安全则输出提示及安全序列，然后进行进程资源申请（输入为非数字则提示出错要求重新输入；输入申请大于需求则提示要求重新输入；如果输入申请量小于需求量并且大于可利用量则提示不能分配，进程阻塞等待，提示是否继续进行申请）：6.2.4申请成功输出成功提示和安全序列，并显示当前系统分配状态：6.2.5按任意键后本次申请结束，提示是否继续进行资源申请，如果输入 Y 则转到步骤6.2.3：6.2.6如果输入非 Y 则程序结束，输出签名提示，然后退出：6.2.7在初始化输入后，如果系统状态不安全，说明无法进行资源分配，则程序退出：6.2.8如果资源申请后该进程所需资源已全部得到，则该进程可完成，故该释放其所有资源：6.3 出现问题及解决方案本程序考虑了程序功能实现、格式显示合理化、输入错误异常处理等各个方面的设计，尽可能使程序设计的更加完美。在长期的设计调试过程中遇到过许多问题，通过网上搜索、查询资料、调试试验等方法一一解决。下面大致罗列一些主要问题：6.3.1关于输入错误的异常处理：数字判断在调试程序过程中我们都知道在要求输入整型数据时，如不小心键入字母符号等，则程序立即出错；还有如在要求输入一个字符时，如果不小心输入为了字符串，则也会出错（此时多键入的字符被保留在缓冲区内，当下次要求屏幕输入时先从缓冲区取出导致出错）。因此设计了一个判断函数int shuzi(int n); 进行处理此类输入异常错误。此函数主要设计思路为：定义一个动态字符串指针，输入后判断每个输入的字符是否在09 之间来判断是否输入的为数字字符，然后按照字符ASCII码值与数字值的关系将输入的字符转换为整数。而对于字符输入的问题，可以定义为一个动态字符串指针然后只取输入的第一个字符内容。6.3.2关于某些判断算法优劣问题：在程序中很多地方都会用到循环判断是否符合条件的算法，在设计这些算法时有很多方法，而有的算法可以更节省时间。如下安全性算法中寻找寻找符合Finishi=0条件的进程的例子：/* 算法一： for (j=0; j=Needij) counter=counter+1;/记数if(counter=m)*/ /算法二：for (j=0; j=Needij); /可用大于等于需求elsecounter=1;break;if(counter!=1)显然算法二要优于算法一。本程序中还有很多类似的地方。这里主要考虑的是一个程序的优化设计问题。6.3.3关于显示格式问题：在输出如当前各进程已经得到的各类资源量及当前各进程已经还需要的各类资源量时，考虑多个进程及多类资源的不确定性，设计格式为：行显示每个进程信息，列显示每类资源信息，每行最多显示五中资源。于是设计如下：for(i=0;i=m/5;i+) /设计每行最多显示五种资源for (j=i*5;ji*5+5 & jm;j+)cout 资源j;coutendl;for(l2=0;l2n;l2+)cout进程l2:;for(j=i*5;ji*5+5 & jm;j+)coutAllocationl2j ;coutendl;6.3.4关于某些系统函数调用时的执行顺序：在调用一些系统函数如getch() 、system(pause)等时发现其执行顺序的一些问题。如类似：cout =endl;cout nnnendl;system(pause);/暂停调试时发现此时：在Microsoft Visual