银行家算法实验报告.doc

实验报告实验名称银行家算法班级学号姓名一、 实验目的和要求理解死锁概念、银行家算法及安全性检测算法掌握用程序设计语言实现银行家算法的基本过程验证银行家算法对于避免死锁的作用二、实验环境硬件平台个人计算机软件平台操作系统：XP 运行环境：VC 6.0三、实验内容定义并初始化进程及其资源数据结构提供一个用户界面，用户利用它可动态输入进程和资源种类等相关参数设计实现安全状态检测和银行家死锁避免算法的功能函数四、实验方案（含程序、数据记录等）1银行家算法的思路先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。2银行家算法中用到的主要数据结构可利用资源向量 int Availablej / j为资源的种类。最大需求矩阵 int Maxij /i为进程的数量。分配矩阵 int Allocationij /i进程当前已分配j资源的数量 需求矩阵 int needij= Maxij- Allocationij申请各类资源数量 int Request ij i进程申请j资源的数量工作向量 int Workx int Finishy 3银行家算法bank()进程i发出请求申请k个j资源，Request ij=k (1)检查申请量是否不大于需求量：Request ij=needi,j,若条件不符重新输入，不允许申请大于需求量。(2)检查申请量是否小于系统中的可利用资源数量：Request ij=availablei,j，若条件不符就申请失败，阻塞该进程，用goto语句跳转到重新申请资源。(3)若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值： Availablei,j= Availablei,j- Request ij； Allocationij= Allocationij+ Request ij； needij= needij- Request ij；(4)试分配后，执行安全性检查，调用safe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。(5)用dowhile 循环语句实现输入字符y/n判断是否继续进行资源申请。4安全性检查算法（safe()函数）(1)设置两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work= Available。Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=0；当有足够的资源分配给进程时，再令Finishi=1。(2)在进程中查找符合以下条件的进程：条件1：Finishi=0；条件2：needij=Workj若找到，则执行步骤(3)否则，执行步骤(4)(3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj= Workj+ Allocationij；Finishi=1；goto step 2；(4)如果所有的Finishi=1都满足，则表示系统处于安全状态，否则，处于不安全状态。程序源代码#include #include #include #include /定义全局变量const int x=10,y=10; /常量，便于修改int Availablex; /各资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量int Maxyy; /各进程对各类资源的最大需求数int Needyy; /尚需多少资源int Requestx; /申请多少资源int Workx; /工作向量，表示系统可提供给进程继续运行所需的各类资源数量int Finishy; /表示系统是否有足够的资源分配给进程，1为是int py; /存储安全序列int i,j; /i表示进程，j表示资源int n,m; /n为进程i的数量,m为资源j种类数int l=0; /l用来记录有几个进程是Finishi=1的，当l=n是说明系统状态是安全的int counter=0;/函数声明void initialization (); /初始化函数void safe(); /安全性算法void show(); /函数show,输出当前状态void bank(); /银行家算法void End(); /结束函数/以上函数的实现void initialization () /初始化函数的实现 coutn; coutm; coutendl输入各种资源当前可用的数量( m 种): endl; for (j=0; jm; j+) cout输入资源 j 可利用的数量AvailablejAvailablej; /输入数字的过程. Workj=Availablej; /初始化Workj，它的初始值就是当前可用的资源数 coutendl输入各进程当前已分配的资源数量Allocationnm: endl; for (i=0; in; i+) for (j=0; jm; j+) cout 输入进程 i 当前已分配的资源 jAllocationij; coutendl; Finishi=0;/初始化Finishi coutendl输入各进程对各类资源的最大需求Maxnm: endl; for (i=0; in; i+) for (j=0; jm; j+) cout 输入进程 i 对资源 jMaxij; if(Maxij=Allocationij) /若最大需求大于已分配，则计算需求量 Needij = Maxij-Allocationij; else Needij=0;/Max小于已分配的时候，此类资源已足够不需再申请 coutendl; coutendl初始化完成endl;/安全性算法函数的实现void safe() l=0; for (i=0; in;i+) /i+ if (Finishi=0) /逐个查找Finishi=0的进程 条件一 counter=0; /记数器 for (j=0; j=Needij) counter=counter+1;/可用大于需求，记数 if(counter=m) /i进程的每类资源都符合Workj=Needij 条件二 pl=i; /存储安全序列 Finishi=1; /i进程标志为可分配 for (j=0; jm;j+) Workj=Workj+Allocationij; /释放资源 l=l+1; /记数,现在有L个进程是安全的，当L=N时说明满足安全序列 i= -1; /从第一个进程开始继续寻找满足条件一二的进程 /显示当前状态函数void show() /函数show,输出当前资源分配情况 int i,j; /局部变量 int Ally; /各种资源的总数量 int L1; /局部变量L1 cout当前的状态为：endl; cout各种资源的总数量:endl; for (j=0;jm;j+) cout 资源j: ; Allj=Availablej; /总数量=可用的+已分配的 for (i=0;in;i+) Allj+=Allocationij; coutAllj ; coutendl当前各种资源可用的量为(available):endl; for (j=0;jm;j+) cout 资源j: Availablej ; coutendl各进程已经得到的资源量(allocation): endl; for(i=0;i=m;i+) for (j=i;jm;j+) cout 资源j; coutendl; for(L1=0;L1n;L1+) cout进程L1:; for (j=i;jm;j+) coutAllocationL1j ; coutendl; coutendl各进程还需要的资源量(need):endl; for(i=0;i=m;i+) for (j=i;jm;j+) cout 资源j; coutendl; for(L1=0;L1n;L1+) cout进程L1:; for (j=i;jm;j+) coutNeedL1j ; coutendl; /银行家算法函数void bank() coutendl进程申请分配资源：endl; int k=0; /用于输入进程编号 bool r=false; / 初值为假，输入Y继续申请则置为真 do/输入请求 cout输入申请资源的进程(0-n-1k; coutn-1) /输入错误处理 coutendl输入错误，重新输入：endl; coutendl输入申请资源的进程(0-n-1k; coutendl; coutendl输入该进程申请各类资源的数量: endl; for (j=0; jm; j+) do /dowhile 循环判断申请输入的情况 cout进程 k 申请资源jRequestj; 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 l=0; coutn申请资源成功!endl; 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; show(); /显示当前状态ppp: /申请大于可利用量， 应该阻塞等待,结束本次资源申请，GOTO 语句跳转至此 coutendl是否继续申请资源(y/n) ?; char* b=new char; /输入y/n，判断是否继续申请 b; coutendl; cout-endlendl; coutendl; if(*b=y|*b=Y) r=true; else r=false; /输入非 Y 则令 R =false End(); /调用结束函数 while (r=true);/结束函数void End() coutendlendl; couttt 演示计算完毕endl; coutendlendl;/主函数int main() coutendlendltttt模拟银行家算法endlendl;initialization (); /初始化函数调用 coutendl; show(); /输出当前状态 safe(); /判断当前状态的安全性 if (ln) /l在safe中是用来记录安全的