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

操 作 系 统实验报告(2)学院：计算机科学与技术学院班级：计091学号：姓名：时间：2011/12/30目 录1. 实验名称32. 实验目的33. 实验内容34. 实验要求35. 实验原理36. 实验环境47. 实验设计47.1数据结构设计47.2算法设计67.3功能模块设计78. 实验运行结果89. 实验心得9附录：源代码（部分）9一、实验名称：用C+实现银行家算法二、实验目的：通过自己编程来实现银行家算法，进一步理解银行家算法的概念及含义，提高对银行家算法的认识，同时提高自己的动手实践能力。各种死锁防止方法能够阻止发生死锁，但必然会降低系统的并发性并导致低效的资源利用率。死锁避免却与此相反，通过合适的资源分配算法确保不会出现进程循环等待链，从而避免死锁。本实验旨在了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生。三、实验内容：利用C+,实现银行家算法四、实验要求：1.完成银行家算法的设计2.设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。五、实验原理：系统中的所有进程放入进程集合，在安全状态下系统收到进程的资源请求后，先把资源试探性的分配给它。之后，系统将剩下的可用资源和进程集合中的其他进程还需要的资源数作比较，找出剩余资源能够满足的最大需求量的进程，从而保证进程运行完毕并归还全部资源。这时，把这个进程从进程集合中删除，归还其所占用的所有资源，系统的剩余资源则更多，反复执行上述步骤。最后，检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可以真正执行本次分配，否则，本次资源分配暂不实施，让申请资源的进程等待。银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全，银行家规定： (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客； (2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量； (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款； (4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。六、实验环境：Win-7系统Visual C+ 6.0七、实验设计：1.数据结构设计定义结构体：struct Process/进程属性构成Source claim;/进程最大需求量Source allocation;/进程占有量Source claim_allocation;/进程需求量Source currentAvail;/进程可获得量;定义类对象：class Source /资源的基本构成以及功能 private:public:int R1;/定义三类类资源int R2;int R3;Source(int r1 = 0,int r2 = 0,int r3 = 0)R1=r1;R2=r2;R3=r3;Source(Source& s)R1=s.R1;R2=s.R2;R3=s.R3;void setSource(int r1 = 0,int r2 = 0,int r3 = 0)/设置各类资源R1=r1;R2=r2;R3=r3;void add(Source s)/加法R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;void sub(Source s)/减法R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;bool lower(Source s)/比较if(R1 > s.R1) return false;if(R2 > s.R2) return false;if(R3 > s.R3) return false;return true;class Data/封装所有数据public:Process *p;/进程指针Source sum;/总资源量Source available;/可获得量Source ask;/请求量int pLength;/进程个数int * ruler;/逻辑尺void clearProcess()/进程currentAvail清零for(int i=0;i<pLength;i+)pi.currentAvail.setSource(0, 0, 0);class DataInit/封装初始化数据函数类private:public:DataInit()/构造函数void initLength(Data *db)/设置进程个数int n;cout<<"输入进程数: "cin>>n;db->pLength = n;db->p = new Processn;if(!db->p)cout<<"error!no enough memory space！"return;db->ruler = new intn;if(!db->ruler)cout<<"error!no enough memory space！"return;2.算法设计class FindSafeList/寻找安全序列private:public:FindSafeList()/构造函数bool checkList(Data *db)/检查一个序列安全性int i=0;/i用于循环db->pdb->ruleri.currentAvail.add(db->available);/将当前系统可用资源量赋给该序列的第一个进程if(!db->pdb->ruleri.claim_allocation.lower(db->pdb->ruleri.currentAvail)/若当前进程currentAvail小于该进程需求量(claim-allocation)，返回falsereturn false;for(i=1; i< db->pLength; i+)/当前进程的可获得资源量currentAvail获得前一个进程的未释放资源前可获得资源量currentAvaildb->pdb->ruleri.currentAvail.add(db->pdb->ruleri-1.currentAvail);/当前进程的可获得资源量currentAvail获得前一个进程的释放的资源量db->pdb->ruleri.currentAvail.add(db->pdb->ruleri-1.allocation);/若当前进程currentAvail小于该进程需求量(claim-allocation)，返回falseif(!db->pdb->ruleri.claim_allocation.lower(db->pdb->ruleri.currentAvail)return false;/若当前进程currentAvail大于该进程总资源量，返回falseif(!db->pdb->ruleri.currentAvail.lower(db->sum)return false;return true;/该序列进程安全。返回truebool exsitSafeList(Data *db)/判断是否存在安全序列int i = 0;for(i = 0; i < db->pLength; i+)/设置逻辑尺的刻度值db->ruleri = i;while(1) /该循环将检测逻辑尺刻度值的全排列 if(checkList(db)/找到一个安全序列，返回truereturn true;db->clearProcess();/将所有进程的currentAvail清零if(!next_permutation(db->ruler,db->ruler+db->pLength)/所有排列完毕后退出生成排列库函数的调用return false;return false;int findSafeList(Data *db, int i=0)/寻找安全序列/请求值大于系统当前可用资源值，返回0if(!db->ask.lower(db->available)return 0;/请求值大于当前进程需求资源值，返回1if(!db->ask.lower(db->pi.claim_allocation)return 1;Source s(db->pi.allocation);/根据请求，分配资源值db->available.sub(db->ask);db->pi.allocation.add(db->ask);db->pi.claim_allocation.sub(db->ask);if(!exsitSafeList(db)/判断是否存在安全序列db->available.add(db->ask);/不存在安全序列，回滚，恢复分配前状态，并返回2db->pi.allocation.sub(db->ask);db->pi.claim_allocation.add(db->ask);return 2;db->ask.setSource(0,0,0);/找到安全序列，将请求资源置零，返回3return 3;3.功能模块设计class Data/封装所有数据class DataInit/封装初始化数据函数类class Display/封装显示方法class FindSafeList/寻找安全序列struct Process/进程属性构成void main() /主函数八、 实验运行结果：输入进程数，及相关资源数量分配选择算法完成的操作：1 查看进程情况2 请求分配 2.1分配失败2.2 分配成功2.3 继续分配失败，退出九、实验心得：通过此次实验，我能够更加深入的理解银行家算法的执行过程，也懂得用银行家算法去防止发生死锁，有效地解决了资源利用率低的问题，保证了系统的安全性。当然在实验过程中，我也遇到了一些困难，但是我通过及时请教同学，查询相关资料，及时解决了问题，但仍有不足之处，我将会在今后学习中更加努力。附录：源代码（部分）#include<iostream>#include<algorithm> using namespace std;class Source /资源的基本构成以及功能 private:public:int R1;/定义三类类资源int R2;int R3;Source(int r1 = 0,int r2 = 0,int r3 = 0)R1=r1;R2=r2;R3=r3;Source(Source& s)R1=s.R1;R2=s.R2;R3=s.R3;void setSource(int r1 = 0,int r2 = 0,int r3 = 0)/设置各类资源R1=r1;R2=r2;R3=r3;void add(Source s)/加法R1=R1+s.R1;R2=R2+s.R2;R3=R3+s.R3;void sub(Source s)/减法R1=R1-s.R1;R2=R2-s.R2;R3=R3-s.R3;bool lower(Source s)/比较if(R1 > s.R1) return false;if(R2 > s.R2) return false;if(R3 > s.R3) return false;return true;struct Process/进程属性构成Source claim;/进程最大需求量Source allocation;/进程占有量Source claim_allocation;/进程需求量Source currentAvail;/进程可获得量;class Data/封装所有数据public:Process *p;/进程指针Source sum;/总资源量Source available;/可获得量Source ask;/请求量int pLength;/进程个数int * ruler;/逻辑尺void clearProcess()/进程currentAvail清零for(int i=0;i<pLength;i+)pi.currentAvail.setSource(0, 0, 0);class DataInit/封装初始化数据函数类private:public:DataInit()/构造函数void initLength(Data *db)/设置进程个数int n;cout<<"输入进程数: "cin>>n;db->pLength = n;db->p = new Processn;if(!db->p)cout<<"error!no enough memory space！"return;db->ruler = new intn;if(!db->ruler)cout<<"error!no enough memory space！"return;void setAsk(Data *db)/设置请求资源量int r1,r2,r3;r1=0;r2=0;r3=0;db->ask.setSource(r1,r2,r3);void initSum(Data *db)/设置总资源量int r1,r2,r3;cout<<"Available (R1,R2,R3): "cin>>r1>>r2>>r3;db->sum.setSource(r1,r2,r3);void initAvail(Data *db)/设置可获得量int r1,r2,r3;cout<<"输入初始分配 Allocation:n"cout<<"availableR1,R2,R3:n "cin>>r1>>r2>>r3;db->available.setSource(r1,r2,r3);void initProcess(Data *db)/设置各进程属性值int r1,r2,r3;cout<<"输入t0时分配 Allocation:n"for(int i=0;i<db->pLength;i+)/设置进程pi 的 allocationcout<<'p'<<i<<" allocationR1,R2,R3: "cin>>r1>>r2>>r3;db->pi.allocation.setSource(r1,r2,r3); cout<<'p'<<i<<" max allocation(claimR1,R2,R3): "/设置进程pi 的 claimcin>>r1>>r2>>r3;db->pi.claim.setSource(r1,r2,r3);r1=db->pi.claim.R1-db->pi.claim.R1;/设置进程pi 的 claim_allocationr2=db->pi.claim.R2-db->pi.claim.R2;r3=db->pi.claim.R3-db->pi.claim.R3;db->pi.claim_allocation.setSource(r1, r2, r3);class Display/封装显示方法private:public:Display()/构造函数void displaySource(Source s)/设置基本资源显示方式cout<<s.R1<<" "<<s.R2<<" "<<s.R3;displayAvailable(Source s)/显示可获得资源量displaySource(s);void displayProcess(Process *p,int length)/显示进程基本信息for(int i=0; i<length; i+)cout<<" p"<<i<<"t"displaySource(pi.claim);cout<<"tt"displaySource(pi.allocation);cout<<endl;cout<<endl;void displaySafeList(Data *db)/显示安全序列for(int i=0; i<db->pLength; i+)cout<<" p"<<db->ruleri<<" "displaySource(db->pdb->ruleri.currentAvail);cout<<" "displaySource(db->pdb->ruleri.claim);cout<<" "displaySource(db->pdb->ruleri.allocation);cout<<" "displaySource(db->pdb->ruleri.claim_allocation);cout<<" true"cout<<endl;void displayAskResult(Data *db,int n)/显示请求资源结果if(n=0)cout<<"不分配，请求量大于当前可获得量! n"return;if(n=1)cout<<"不分配，请求量大于当前可获得量!n"return;if(n=2)cout<<"不分配，找不到安全序列! n"return;if(n=3)cout<<"存在安全序列:"for(int i=0;i<db->pLength;i+)cout<<db->ruleri<<" "cout<<endl;char c='N'cout<<"查看安全序列详情?(Y/N) "cin>>c;if(c='Y'|c='y')cout<<" 进程 currentavail claim allocation claim-allocation possiblen"displaySafeList(db);return;class FindSafeList/寻找安全序列private:public:FindSafeList()/构造函数bool checkList(Data *db)/检查一个序列安全性int i=0;/i用于循环db->pdb->ruleri.currentAvail.add(db->available);/将当前系统可用资源量赋给该序列的第一个进程if(!db->pdb->ruleri.claim_allocation.lower(db->pdb->ruleri.currentAvail)/若当前进程currentAvail小于该进程需求量(claim-allocation)，返回falsereturn false;for(i=1; i< db->pLength; i+)/当前进程的可获得资源量currentAvail获得前一个进程的未释放资源前可获得资源量currentAvaildb->pdb->ruleri.currentAvail.add(db->pdb->ruleri-1.currentAvail);/当前进程的可获得资源量currentAvail获得前一个进程的释放的资源量db->pdb->ruleri.currentAvail.add(db->pdb->ruleri-1.allocation);/若当前进程currentAvail小于该进程需求量(claim-allocation)，返回falseif(!db->pdb->ruleri.claim_allocation.lower(db->pdb->ruleri.currentAvail)return false;/若当前进程currentAvail大于该进程总资源量，返回falseif(!db->pdb->ruleri.currentAvail.lower(db->sum)return false;return true;/该序列进程安全。返回truebool exsitSafeList(Data *db)/判断是否存在安全序列int i = 0;for(i = 0; i < db->pLength; i+)/设置逻辑尺的刻度值db->ruleri = i;while(1) /该循环将检测逻辑尺刻度值的全排列 if(checkList(db)/找到一个安全序列，返回truereturn true;db->clearProcess();/将所有进程的currentAvail清零if(!next_permutation(db->ruler,db->ruler+db->pLength)/所有排列完毕后退出生成排列库函数的调用return false;return false;int findSafeList(Data *db, int i=0)/寻找安全序列/请求值大于系统当前可用资源值，返回0if(!db->ask.lower(db->available)return 0;/请求值大于当前进程需求资源值，返回1if(!db->ask.lower(db->pi.claim_allocation)return 1;Source s(db->pi.allocation);/根据请求，分配资源值db->available.sub(db->ask);db->pi.allocation.add(db->ask);db->pi.claim_allocation.sub(db->ask);if(!exsitSafeList(db)/判断是否存在安全序列db->available.add(db->ask);/不存在安全序列，回滚，恢复分配前状态，并返回2db->pi.allocation.sub(db->ask);db->pi.claim_allocation.add(db->ask);return 2;db->ask.setSource(0,0,0);/找到安全序列，将请求资源置零，返回3return 3;void main()Data *db;db=new Data;if(!db)cout<<"error!no enough memory space！"return;DataInit dataInit;dataInit.initLength(db);/设置进程个数dataInit.initSum(db);/设置系统总资源量dataInit.initAvail(db);/设置当前系统可获得资源量dataInit.initProcess(db);/设置t0时刻进程基本状态Display display;FindSafeList findSafeList;int r1=0,r2=0,r3=0;int c;db->ask.setSource(r1,r2,r3);/设置请求资源为0，即无请求c=findSafeList.findSafeList(db,0);/寻找安全序列，返回结果if(c!=3)cout<<"t0时刻的进程组不存在安全序列!n"return;int choice=1;int pi;while(choice)cout<<"n 选择操作:n 1 查看进程情况n 2 请求分配资源n 0 退出n "cin>>choice;switch(choice)case 1:cout<<"当前资源量availableR1,R2,R3:n "display.displayAvailable(db->available);cout<<endl;cout<<"n当前进程资源分配情况piR1,R2,R3: n"cout<<" 进程tclaimttallocationn"display.displayProcess(db->p,db->pLength);break;case 2:cout<<"输入请求资源进程序号:"cin>>pi;cout<<"输入请求资源(R1,R2,R3): (0,0,0)表示当前进程组无请求 n"cin>>r1>>r2>>r3;db->ask.setSource(r1,r2,r3);c=findSafeList.findSafeList(db,pi);display.displayAskResult(db,c);cout<<endl;break;case 0:break;default:cout<<"input error!try again！n"break;