操作系统课程设计报告实验报告-用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); //