操作系统实验报告—银行家算法模拟

1、银行家算法模拟【开发语言及实现平台或实验环境】C+/C#Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003【实验目的】(1) 进一步理解利用银行家算法避免死锁的问题；(2) 在了解和掌握银行家算法。(3) 理解和掌握安全序列、安全性算法【实验内容】(1) 编写安全性算法；(2) 编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机 屏幕上，再检测和笔算的一致性。【实验原理】一、安全状态指系统能按照某种顺序如(称为序列为安全序 列),为每个进程分配所需的资源，直至最大需求，使得每个进程都能顺利完成。二、银行家算

2、法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k 。系统按下述步骤进行安全检查：(1) 如果Requesti Need则继续以下检查，否则显示需求申请超出最大需求值 的错误。(2) 如果Requesti Available 则继续以下检查，否则显示系统无足够资源， Pi阻塞等待。(3) 系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值：Availablej ： =Available j -Request ij ;Allocation i,j : =Allocation i,j +Requesti j ;Need i,j : =Need i,j -Re

3、questi j ;(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。三、安全性算法(1) 设置两个向量： 工作向量 Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work： =Available; Fini sh:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish i ： =false;当有足够资源分配给进程时，再令Finish i ：=true。(2) 从进程集合中找到一个能

4、满足下述条件的进程：Finish i =false; Need i,j Workj；若找到，执行步骤，否则，执行步骤(4)。(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源， 故应执行：? Work j ： = Work i +Allocation i,j ;?Finish i : = true;? go to step 2;(4) 如果所有进程的Finish i =true都满足，则表示系统处于安全状态； 否则，系统处于不安全状态。【实验步骤】图1-1安全性算法流程图(2) 编写统一的输出格式。每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前 后的各

5、种数据，并且输出安全序列。(3) 参考图1-2所示流程图编写银行家算法。图1-2银行家算法流程图(4) 编写主函数来循环调用银行家算法。【实验思考】(1)在编程中遇到了哪些问题？你是如何解决的？答：编程的过程中， 在实现安全性算法和银行家算法的问题上遇到了困难， 比 如进程使用字母表示， 如何识别进程和进程与程序联系在一起的问题， 一直阻碍 着我，后来结合将所学知识我通过 for 循环语句将输入的字母先进行判断再与整 型数据对应，然后再将进程与程序联系在一起，从而解决了问题。( 2)在安全性算法中，为什么不用变量Available ，而又定义一个临时变量work？答：定义一个临时变量 work

6、 是为了防止在不安全的情况下破坏数据原值，这 样就能使程序更加安全。【源代码】#include #include #define M 3 /资源的种类数#define N 5 /进程的个数void output(int iMaxNM,int iAllocationNM,int iNeedNM,int iAvailableM,char cNameN); / 统一的输出格式 bool safety(int iAllocationNM,int iNeedNM,int iAvailableM,char cNameN);bool banker(int iAllocationNM,int iNeedNM,

7、intiAvailableM,char cNameN);void main()int i,j;/ 当前可用每类资源的资源数int iAvailableM=3,3,2;/系统中Nt进程中的每一个进程对M类资源的最大需求int iMaxNM=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/iNeedNM 每一个进程尚需的各类资源数/iAllocationNM 为系统中每一类资源当前已分配给每一进程的资源数 intiNeedNM,iAllocationNM=0,1,1,2,0,0,3,0,2,2,1,1,0,0,2;/ 进程名char cNameN=a,b,c,d,e;bool bEx

8、itFlag=true; / 退出标记char ch; / 接收选择是否继续提出申请时传进来的值bool bSafe; / 存放安全与否的标志/ 计算 iNeedNM 的值for(i=0;iN;i+)for(j=0;jM;j+) iNeedij=iMaxij-iAllocationij;/ 输出初始值 output(iMax,iAllocation,iNeed,iAvailable,cName);/ 判断当前状态是否安全 bSafe=safety(iAllocation,iNeed,iAvailable,cName);/ 是否继续提出申请while(bExitFlag)coutch;switc

9、h(ch)case y:/cout调用银行家算法 ;bSafe=banker(iAllocation,iNeed,iAvailable,cName); if (bSafe) / 安全，则输出变化后的数据 output(iMax,iAllocation,iNeed,iAvailable,cName);break;case n:cout 退出。 n;bExitFlag=false;break;default:cout 输入有误，请重新输入： n;/ 输出void output(int iMaxNM,int iAllocationNM,int iNeedNM,int iAvailableM,char

10、 cNameN)int i,j;coutnt Max tAllocationt Need t Availableendl; couttA B CtA B CtA B Ct A B Cendl; for(i=0;iN;i+)coutcNameit;for(j=0;jM;j+)coutiMaxij ;coutt;for(j=0;jM;j+)coutiAllocationij ; coutt;for(j=0;jM;j+)coutiNeedij ;coutt;cout ;/Available 只需要输出一次if (i=0)for(j=0;jM;j+) coutiAvailablej ;coutendl

11、;/ 安全性算法，进行安全性检查；安全返回 true ，并且输出安全序列，不安全返 回 false ，并输出不安全的提示；bool safety(int iAllocationNM,int iNeedNM,int iAvailableM,char cNameN)int i,j,flag,x=0;char NameN;int WorkM;bool FinishN;for(j=0;jM;j+)Workj=iAvailablej;for(i=0;iN;i+)Finishi=false;while(true)flag=0;for(i=0;i=iNeedi0 &Work1=iNeedi1 & Work2

12、=iNeedi2)for(j=0;jM;j+)Workj+= iAllocationij ;Finishi=true;flag+;Namex+=cNamei;for(i=0;iN;i+)if(Finishi=false)i=i;break;if(i=5)coutn;cout 安全序列为： for(x=0;xN;x+)coutNamex ;coutn;return true;if(flag=0)cout 无安全序列 ;return false;return true;/ 安全返回 true ，不安全返回 falsebool banker(int iAllocationNM,int iNeedNM

13、,intiAvailableM,char cNameN)int iMaxNM=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;int i,j,RequestM,checkM;bool f=true;char x;while(f)coutx;for(i=0;iN;i+)if (cNamei=x)i=i;break;if (i=5)coutn 您输入的进程名有误！请重新输入elsef=false;cout 请输入各资源数量： ;for(j=0;jRequestj;for(j=0;jM;j+) checkj=Requestj+iAllocationij;for(j=0;jM;j+)if(

14、iMaxij-checkj)0)coutn 资源申请超过最大需求量！ ！ n; return false;for(j=0;jM;j+)if(iAvailablej-Requestj)0)coutn 不能满足进程！ n;return false;for(j=0;jM;j+)iAvailablej-=Requestj;iAllocationij+=Requestj; iNeedij-=Requestj; safety(iAllocation,iNeed,iAvailable,cName); return true;实验结果与分析】C .,a aaaaaa amm aa.De cu gaaaaac

15、a a 日 a mm. exz1202A73B安全.序列为：debtMatKBC2HlJocatlon ABC 0112 U 3 22110U 222011Aua Liable DBG 332请重新输入请谕入进程名：1 1rl0Meedc 1 fi o 1 1B 3 2 0 1 3fi t 1 6 B 4xlaJbleFl2b aAllocationB CNeed D 4264ft 7 1 M 4艮全序列为:b 1 匡簪出申谙Q青啬入各资源数量=4冠崔満足进稈! ! !Atiaileihle ABC22eii=E !aaaaaaa aaa aaDe bug白白国自白左 aa a aai.exeAl Incation2Fllia LI able D D C1LjbmTJ2011? 0 请A 岀n 一一匹;d量.教 程餡 进卸 入入 辛冃生冃资源申请担过最大需求量！ ！【实验思考及总结】操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享 系统的软、硬件资源。为了最大限度的利用计算机系统的资源， 操作系统应采用