操操 作作 系系 统统 实 验 报 告 (2) 学院：学院：计算机科学与技术学院计算机科学与技术学院 班级：班级：计计 091091 学号：姓名：学号：姓名： 时间：时间：2011/12/302011/12/30 2 目目录录 1.1.实验名称实验名称3 3 2.2.实验目的实验目的3 3 3.3.实验内容实验内容3 3 4.4.实验要求实验要求3 3 5.5.实验原理实验原理3 3 6.6.实验环境实验环境4 4 7.7.实验设计实验设计4 4 7.17.1数据结构设计数据结构设计4 4 7.27.2算法设计算法设计6 6 7.37.3功能模块设计功能模块设计7 7 8.8.实验运行结果实验运行结果8 8 9.9.实验心得实验心得9 9 附录：附录：源代码（部分）源代码（部分）9 3 一、实验名称：一、实验名称： 用 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;in; 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)，返回 false return false; for(i=1; ipLength; i+) /当前进程的可获得资源量 currentAvail 获得前一个进程的未释放资源前可获 得资源量 currentAvail db-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.currentAvail); /当前进程的可获得资源量 currentAvail 获得前一个进程的释放的资源量 db-pdb-ruleri.currentAvail.add(db-pdb-ruleri-1.allocation); /若当前进程 currentAvail 小于该进程需求量(claim-allocation)，返回 false if(!db-pdb-ruleri.claim_allocation.lower(db-pdb-ruleri.currentAvail) return false; /若当前进程 currentAvail 大于该进程总资源量，返回 false if(!db-pdb-ruleri.currentAvail.lower(db-sum) return false; return true;/该序列进程安全。返回 true 7 bool exsitSafeList(Data *db) /判断是否存在安全序列 int i = 0; for(i = 0; i pLength; i+)/设置逻辑尺的刻度值 db-ruleri = i; while(1)/该循环将检测逻辑尺刻度值的全排列 if(checkList(db)/找到一个安全序列，返回 true return true; db-clearProcess();/将所有进程的 currentAvail 清零 if(!next_permutation(db-ruler,db-ruler+db-pLength)/ 所 有 排 列 完毕后退出生成排列库函数的调用 return false; return false; int findSafeList(Data *db, int i=0) /寻找安全序列 /请求值大于系统当前可用资源值，返回 0 if(!db-ask.lower(db-available) return 0; /请求值大于当前进程需求资源值，返回 1 if(!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);/不存在安全序列，回滚，恢复分配前状 态，并返回 2 db-pi.allocation.sub(db-ask); db-pi.claim_allocation.add(db-ask); return 2; db-ask.setSource(0,0,0);/找到安全序列，将请求资源置零，返回 3 return 3; ; 3.3.功能模块设计功能模块设计 8 class Data/封装所有数据 class DataInit/封装初始化数据函数类 class Display/封装显示方法 class FindSafeList/寻找安全序列 struct Process/进程属性构成 void main()/主函数 八、八、实验运行结果：实验运行结果： 输入进程数，及相关资源数量分配 选择算法完成的操作：1 查看进程情况 2 请求分配 2.1 分配失败 9 2.2 分配成功 2.3 继续分配失败，退出 10 九、实验心得：九、实验心得： 通过此次实验，我能够更加深入的理解银行家算法的执行过程，也懂得用银行家算法 去防止发生死锁，有效地解决了资源利用率低的问题，保证了系统的安全性。 当然在实验过程中，我也遇到了一些困难，但是我通过及时请教同学，查询相关资料， 及时解决了问题，但仍有不足之处，我将会在今后学习中更加努力。 附录：附录：源代码（部分） #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(SourceR2=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; 11 ; struct Process/进程属性构成 Source claim; /进程最大需求量 Source allocation; /进程占有量 Source claim_allocation;/进程需求量 Source currentAvail;/进程可获得量 ; class Data/封装所有数据 public: Process *p;/进程指针 Source sum;/总资源量 Source available