操作系统课程设计实验报告-用C++实现银行家算法

.../操作系统实验报告<2>学院：计算机科学与技术学院班级：计091学号：姓名：时间：2011/12/30目录实验名称……………………3实验目的……………………3实验内容……………………3实验要求……………………3实验原理……………………3实验环境……………………4实验设计……………………47.1数据结构设计……………………47.2算法设计…………67.3功能模块设计……………………7实验运行结果………………8实验心得……………………9附录：源代码〔部分…………………9一、实验名称：用C++实现银行家算法二、实验目的：通过自己编程来实现银行家算法,进一步理解银行家算法的概念及含义,提高对银行家算法的认识,同时提高自己的动手实践能力。各种死锁防止方法能够阻止发生死锁,但必然会降低系统的并发性并导致低效的资源利用率。死锁避免却与此相反,通过合适的资源分配算法确保不会出现进程循环等待链,从而避免死锁。本实验旨在了解死锁产生的条件和原因,并采用银行家算法有效地防止死锁的发生。三、实验内容：利用C++,实现银行家算法四、实验要求：1.完成银行家算法的设计2.设计有n个进程共享m个系统资源的系统,进程可动态的申请和释放资源,系统按各进程的申请动态的分配资源。五、实验原理：系统中的所有进程放入进程集合,在安全状态下系统收到进程的资源请求后,先把资源试探性的分配给它。之后,系统将剩下的可用资源和进程集合中的其他进程还需要的资源数作比较,找出剩余资源能够满足的最大需求量的进程,从而保证进程运行完毕并归还全部资源。这时,把这个进程从进程集合中删除,归还其所占用的所有资源,系统的剩余资源则更多,反复执行上述步骤。最后,检查进程集合,若为空则表明本次申请可行,系统处于安全状态,可以真正执行本次分配,否则,本次资源分配暂不实施,让申请资源的进程等待。银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现银行家算法,系统必须设置若干数据结构。要解释银行家算法,必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi<1≤i≤n,它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj<j<i>当前占有资源量之和。安全状态：如果存在一个由系统中所有进程构成的安全序列P1,…,Pn,则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全,银行家规定：<1>当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；<2>顾客可以分期贷款,但贷款的总数不能超过最大需求量；<3>当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款；<4>当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源,若能满足则按当前的申请量分配资源,否则也要推迟分配。六、实验环境：Win-7系统VisualC++6.0七、实验设计：1.数据结构设计定义结构体：structProcess//进程属性构成{ Sourceclaim; //进程最大需求量 Sourceallocation; //进程占有量 Sourceclaim_allocation;//进程需求量 SourcecurrentAvail;//进程可获得量};定义类对象：classSource//资源的基本构成以及功能{private:public: intR1;//定义三类类资源 intR2; intR3; Source<intr1=0,intr2=0,intr3=0>{ R1=r1;R2=r2;R3=r3; } Source<Source&s> { R1=s.R1;R2=s.R2;R3=s.R3; } voidsetSource<intr1=0,intr2=0,intr3=0>//设置各类资源 { R1=r1;R2=r2;R3=r3; } voidadd<Sources>//加法 { R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3; } voidsub<Sources>//减法 { R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3; } boollower<Sources>//比较 { if<R1>s.R1>returnfalse; if<R2>s.R2>returnfalse; if<R3>s.R3>returnfalse; returntrue; }};classData//封装所有数据{public: Process*p;//进程指针 Sourcesum;//总资源量 Sourceavailable; //可获得量 Sourceask;//请求量 intpLength; //进程个数 int*ruler; //逻辑尺 voidclearProcess<> //进程currentAvail清零 { for<inti=0;i<pLength;i++> { p[i].currentAvail.setSource<0,0,0>;} }};classDataInit//封装初始化数据函数类{private:public: DataInit<>//构造函数 { } voidinitLength<Data*db>//设置进程个数 { intn; cout<<"输入进程数:"; cin>>n; db->pLength=n; db->p=newProcess[n]; if<!db->p> {cout<<"error!noenoughmemoryspace！";return;} db->ruler=newint[n]; if<!db->ruler> {cout<<"error!noenoughmemoryspace！";return;} }2.算法设计classFindSafeList//寻找安全序列{private:public: FindSafeList<> //构造函数 {} boolcheckList<Data*db> //检查一个序列安全性 { inti=0; //i用于循环 db->p[db->ruler[i]].currentAvail.add<db->available>; //将当前系统可用资源量赋给该序列的第一个进程 if<!db->p[db->ruler[i]].claim_allocation.lower<db->p[db->ruler[i]].currentAvail>> //若当前进程currentAvail小于该进程需求量<claim-allocation>,返回false {returnfalse;} for<i=1;i<db->pLength;i++> { //当前进程的可获得资源量currentAvail获得前一个进程的未释放资源前可获得资源量currentAvail db->p[db->ruler[i]].currentAvail.add<db->p[db->ruler[i-1]].currentAvail>; //当前进程的可获得资源量currentAvail获得前一个进程的释放的资源量 db->p[db->ruler[i]].currentAvail.add<db->p[db->ruler[i-1]].allocation>; //若当前进程currentAvail小于该进程需求量<claim-allocation>,返回false if<!db->p[db->ruler[i]].claim_allocation.lower<db->p[db->ruler[i]].currentAvail>> { returnfalse; } //若当前进程currentAvail大于该进程总资源量,返回false if<!db->p[db->ruler[i]].currentAvail.lower<db->sum>> { returnfalse; } } returntrue; //该序列进程安全。返回true } boolexsitSafeList<Data*db> //判断是否存在安全序列 { inti=0; for<i=0;i<db->pLength;i++> //设置逻辑尺的刻度值 { db->ruler[i]=i; } while<1> //该循环将检测逻辑尺刻度值的全排列 { if<checkList<db>> //找到一个安全序列,返回true { returntrue; } db->clearProcess<>; //将所有进程的currentAvail清零 if<!next_permutation<db->ruler,db->ruler+db->pLength>> //所有排列完毕后退出生成排列库函数的调用 { returnfalse; } } returnfalse; } intfindSafeList<Data*db,inti=0> //寻找安全序列 { //请求值大于系统当前可用资源值,返回0 if<!db->ask.lower<db->available>> { return0; } //请求值大于当前进程需求资源值,返回1 if<!db->ask.lower<db->p[i].claim_allocation>> { return1; } Sources<db->p[i].allocation>; //根据请求,分配资源值 db->available.sub<db->ask>; db->p[i].allocation.add<db->ask>; db->p[i].claim_allocation.sub<db->ask>; if<!exsitSafeList<db>> //判断是否存在安全序列 { db->available.add<db->ask>; //不存在安全序列,回滚,恢复分配前状态,并返回2 db->p[i].allocation.sub<db->ask>; db->p[i].claim_allocation.add<db->ask>; return2; } db->ask.setSource<0,0,0>; //找到安全序列,将请求资源置零,返回3 return3; } };3.功能模块设计classData//封装所有数据classDataInit//封装初始化数据函数类classDisplay//封装显示方法classFindSafeList//寻找安全序列structProcess//进程属性构成voidmain<>//主函数实验运行结果：输入进程数,及相关资源数量分配选择算法完成的操作：1查看进程情况2请求分配2.1分配失败2.2分配成功2.3继续分配失败,退出九、实验心得：通过此次实验,我能够更加深入的理解银行家算法的执行过程,也懂得用银行家算法去防止发生死锁,有效地解决了资源利用率低的问题,保证了系统的安全性。当然在实验过程中,我也遇到了一些困难,但是我通过及时请教同学,查询相关资料,及时解决了问题,但仍有不足之处,我将会在今后学习中更加努力。附录：源代码〔部分#include<iostream>#include<algorithm>usingnamespacestd;classSource//资源的基本构成以及功能{private:public: intR1;//定义三类类资源 intR2; intR3; Source<intr1=0,intr2=0,intr3=0> { R1=r1;R2=r2;R3=r3; } Source<Source&s> { R1=s.R1;R2=s.R2;R3=s.R3; } voidsetSource<intr1=0,intr2=0,intr3=0>//设置各类资源 { R1=r1;R2=r2;R3=r3; } voidadd<Sources>//加法 { R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3; } voidsub<Sources>//减法 { R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3; } boollower<Sources>//比较 { if<R1>s.R1>returnfalse; if<R2>s.R2>returnfalse; if<R3>s.R3>returnfalse; returntrue; }};structProcess//进程属性构成{ Sourceclaim; //进程最大需求量 Sourceallocation; //进程占有量 Sourceclaim_allocation;//进程需求量 SourcecurrentAvail;//进程可获得量};classData//封装所有数据{public: Process*p;//进程指针 Sourcesum;//总资源量 Sourceavailable; //可获得量 Sourceask;//请求量 intpLength; //进程个数 int*ruler; //逻辑尺 voidclearProcess<> //进程currentAvail清零{ for<inti=0;i<pLength;i++> { p[i].currentAvail.setSource<0,0,0>;} }};classDataInit//封装初始化数据函数类{private:public: DataInit<>//构造函数 { } voidinitLength<Data*db>//设置进程个数 { intn; cout<<"输入进程数:"; cin>>n; db->pLength=n; db->p=newProcess[n]; if<!db->p> {cout<<"error!noenoughmemoryspace！";return;} db->ruler=newint[n]; if<!db->ruler> {cout<<"error!noenoughmemoryspace！";return;} } voidsetAsk<Data*db> //设置请求资源量 { intr1,r2,r3; r1=0; r2=0; r3=0; db->ask.setSource<r1,r2,r3>; } voidinitSum<Data*db> //设置总资源量 { intr1,r2,r3; cout<<"Available<R1,R2,R3>:"; cin>>r1>>r2>>r3; db->sum.setSource<r1,r2,r3>; } voidinitAvail<Data*db> //设置可获得量 { intr1,r2,r3; cout<<"输入初始分配Allocation:\n"; cout<<"available[R1,R2,R3]:\n"; cin>>r1>>r2>>r3; db->available.setSource<r1,r2,r3>; } voidinitProcess<Data*db> //设置各进程属性值 { intr1,r2,r3; cout<<"输入t0时分配Allocation:\n"; for<inti=0;i<db->pLength;i++>//设置进程p[i]的allocation { cout<<'p'<<i<<"allocation[R1,R2,R3]:"; cin>>r1>>r2>>r3; db->p[i].allocation.setSource<r1,r2,r3>; cout<<'p'<<i<<"maxallocation<claim[R1,R2,R3]>:";//设置进程p[i]的claim cin>>r1>>r2>>r3; db->p[i].claim.setSource<r1,r2,r3>; r1=db->p[i].claim.R1-db->p[i].claim.R1;//设置进程p[i]的claim_allocation r2=db->p[i].claim.R2-db->p[i].claim.R2; r3=db->p[i].claim.R3-db->p[i].claim.R3; db->p[i].claim_allocation.setSource<r1,r2,r3>; } }};classDisplay//封装显示方法{private:public: Display<> //构造函数 { } voiddisplaySource<Sources> //设置基本资源显示方式 {cout<<s.R1<<""<<s.R2<<""<<s.R3;} displayAvailable<Sources> //显示可获得资源量 {displaySource<s>;} voiddisplayProcess<Process*p,intlength> //显示进程基本信息 {for<inti=0;i<length;i++>{ cout<<"p"<<i<<"\t"; displaySource<p[i].claim>;cout<<"\t\t"; displaySource<p[i].allocation>; cout<<endl; } cout<<endl; } voiddisplaySafeList<Data*db> //显示安全序列 { for<inti=0;i<db->pLength;i++> { cout<<"p"<<db->ruler[i]<<"";displaySource<db->p[db->ruler[i]].currentAvail>; cout<<""; displaySource<db->p[db->ruler[i]].claim>; cout<<""; displaySource<db->p[db->ruler[i]].allocation>; cout<<""; displaySource<db->p[db->ruler[i]].claim_allocation>; cout<<"true"; cout<<endl; } } voiddisplayAskResult<Data*db,intn> //显示请求资源结果 { if<n==0> {cout<<"不分配,请求量大于当前可获得量!\n";return;} if<n==1> {cout<<"不分配,请求量大于当前可获得量!\n";return;} if<n==2> {cout<<"不分配,找不到安全序列!\n";return;} if<n==3> { cout<<"存在安全序列:";for<inti=0;i<db->pLength;i++> {cout<<db->ruler[i]<<"";} cout<<endl; charc='N'; cout<<"查看安全序列详情?<Y/N>"; cin>>c; if<c=='Y'||c=='y'> { cout<<"进程currentavailclaimallocationclaim-allocationpossible\n"; displaySafeList<db>; } return; } }};classFindSafeList//寻找安全序列{private:public: FindSafeList<> //构造函数 {} boolcheckList<Data*db> //检查一个序列安全性 { inti=0; //i用于循环 db->p[db->ruler[i]].currentAvail.add<db->available>; //将当前系统可用资源量赋给该序列的第一个进程 if<!db->p[db->ruler[i]].claim_allocation.lower<db->p[db->ruler[i]].currentAvail>> //若当前进程currentAvail小于该进程需求量<claim-allocation>,返回false {returnfalse;} for<i=1;i<db->pLength;i++> { //当前进程的可获得资源量currentAvail获得前一个进程的未释放资源前可获得资源量currentAvaildb->p[db->ruler[i]].currentAvail.add<db->p[db->ruler[i-1]].currentAvail>; //当前进程的可获得资源量currentAvail获得前一个进程的释放的资源量 db->p[db->ruler[i]].currentAvail.add<db->p[db->ruler[i-1]].allocation>; //若当前进程currentAvail小于该进程需求量<claim-allocation>,返回false if<!db->p[db->ruler[i]].claim_allocation.lower<db->p[db->ruler[i]].currentAvail>> { returnfalse; } //若当前进程currentAvail大于该进程总资源量,返回false if<!db->p[db->ruler[i]].currentAvail.lower<db->sum>> { returnfalse; } } returntrue; //该序列进程安全。返回true } boolexsitSafeList<Data*db> //判断是否存在安全序列 { inti=0; for<i=0;i<db->pLength;i++> //设置逻辑尺的刻度值 { db->ruler[i]=i; } while<1> //该循环将检测逻辑尺刻度值的全排列 { if<checkList<db>> //找到一个安全序列,返回true { returntrue; } db->clearProcess<>; //将所有进程的currentAvail清零 if<!next_permutation<db->ruler,db->ruler+db->pLength>> //所有排列完毕后退出生成排列库函数的调用 { returnfalse; } } returnfalse; } intfindSafeList<Data*db,inti=0> //寻找安全序列 { //请求值大于系统当前可用资源值,返回0 if<!db->ask.lower<db->available>> { return0; } //请求值大于当前进程需求资源值,返回1 if<!db->ask.lower<db->p[i].claim_allocation>> { return1; } Sources<db->p[i].allocation>; //根据请求,分配资源值 db->available.sub<db->ask>; db->p[i].allocation.add<db->ask>; db->p[i].claim_allocation.sub<db->ask>; if<!exsitSafeList<db>> //判断是否存在安全序列 { db->available.add<db->ask>; //不存在安全序列,回滚,恢复分配前状态,并返回2 db->p[i].allocation.sub<db->ask>; db->p[i].claim_allocation.add<db->ask>; return2; } db->ask.setSource<0,0,0>; //找到安全序列,将请求资源置零