操作系统课程设计实验报告-用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 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;iplength;i+)pi.currentavail.setsource(0, 0, 0);class datainit/封装初始化数据函数类private:public:datainit()/构造函数void initlength(data *db)/设置进程个数int n;coutn;db-plength = n;db-p = new processn;if(!db-p)coutruler = new intn;if(!db-ruler)coutpdb-ruleri.currentavail.add(db-available);/将当前系统可用资源量赋给该序列的第一个进程if(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentavail)/若当前进程currentavail小于该进程需求量(claim-allocation)，返回falsereturn false;for(i=1; iplength; 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 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() /主函数8、 实验运行结果：输入进程数，及相关资源数量分配选择算法完成的操作：1 查看进程情况2 请求分配 2.1分配失败2.2 分配成功2.3 继续分配失败，退出九、实验心得：通过此次实验，我能够更加深入的理解银行家算法的执行过程，也懂得用银行家算法去防止发生死锁，有效地解决了资源利用率低的问题，保证了系统的安全性。当然在实验过程中，我也遇到了一些困难，但是我通过及时请教同学，查询相关资料，及时解决了问题，但仍有不足之处，我将会在今后学习中更加努力。附录：源代码（部分）#include#include 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;iplength;i+)pi.currentavail.setsource(0, 0, 0);class datainit/封装初始化数据函数类private:public:datainit()/构造函数void initlength(data *db)/设置进程个数int n;coutn;db-plength = n;db-p = new processn;if(!db-p)coutruler = new intn;if(!db-ruler)coutask.setsource(r1,r2,r3);void initsum(data *db)/设置总资源量int r1,r2,r3;coutr1r2r3;db-sum.setsource(r1,r2,r3);void initavail(data *db)/设置可获得量int r1,r2,r3;cout输入初始分配 allocation:n;coutr1r2r3;db-available.setsource(r1,r2,r3);void initprocess(data *db)/设置各进程属性值int r1,r2,r3;cout输入t0时分配 allocation:n;for(int i=0;iplength;i+)/设置进程pi 的 allocationcoutpir1r2r3;db-pi.allocation.setsource(r1,r2,r3); coutpir1r2r3;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)/设置基本资源显示方式couts.r1 s.r2 s.r3;displayavailable(source s)/显示可获得资源量displaysource(s);void displayprocess(process *p,int length)/显示进程基本信息for(int i=0; ilength; i+)cout pit;displaysource(pi.claim);couttt;displaysource(pi.allocation);coutendl;coutendl;void displaysafelist(data *db)/显示安全序列for(int i=0; iplength; i+)cout pruleripdb-ruleri.currentavail);coutpdb-ruleri.claim);coutpdb-ruleri.allocation);coutpdb-ruleri.claim_allocation);cout true;coutendl;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;iplength;i+)coutruleri ;coutendl;char c=n;coutc;if(c=y|c=y)coutpdb-ruleri.currentavail.add(db-available);/将当前系统可用资源量赋给该序列的第一个进程if(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentavail)/若当前进程currentavail小于该进程需求量(claim-allocation)，返回falsereturn false;for(i=1; iplength; 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 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