共享资源分配与银行家算法.doc

中国计量学院现代科技学院计算机操作系统课程设计报告 课程设计报告课程设计名称 共享资源分配与银行家算法 系（部） 信息工程系 专业班级 姓 名 学 号 指导教师 2010 年 6 月 28 日目 录一、课程设计目的和意义 3二、方案设计及开发过程31.课题设计背景 32.算法描述 33.数据结构 44.主要函数说明 45.算法流程图 5三、调试记录与分析 四、运行结果及说明 61执行结果 62结果分析 7五、课程设计总结 8参考资料 8附录 8一、 课程设计目的和意义计算机科学与技术专业学生学习完计算机操作系统课程后，进行的一次全面的综合训练，其目的在于加深催操作系统基础理论和基本知识的理解，加强学生的动手能力. 银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法二、方案设计及开发过程1.课题设计背景银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待2.算法描述1）如果Requesti 是进程Pi的请求向量，如果Requesti，j=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果Requestij= Needi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。2）如果Requestij=Availablej,便转向步骤3，否则，表示尚无足够资源，进程Pi须等待。3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej:=Availablej-Requestij;Allocationi,j:=Allocationi,j+Requestij;Needi,j:=Needi,j-Requestij;4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程pi等待。3.数据结构1.可利用资源向量AVAILABLE。这是一个含有M个元素的数组，其中的每一个元素代表一类可利用的资源数目，其3初始值是系统中所配置的该类全部可哦那个资源的数目，其数值随该类资源的分配和回收而动态的改变。2.最大需求矩阵MAX。这是一个M*N的矩阵，它定义了系统中N个进程中的每一个进程对M类资源的最大需求。3.分配矩阵ALLOCATION。这也是一个M*N的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。4.需求矩阵NEED。这也是一个M*N的矩阵，用以表示每一个进程尚需的各类资源数。5.NEEDR,W=MAXR,W-ALLOCATIONR,W4.主要函数说明主要的常量变量#define W 10 /最大进程数W=10#define R 20 /最大资源总数R=20 int AVAILABLER; /可利用资源向量int MAXWR; /最大需求矩阵int ALLOCATIONWR; /分配矩阵int NEEDWR; /需求矩阵int RequestR; /进程请求向量 void changdata(int k);/进程请求资源数据改变int chksec(int s); /系统安全性的检测主要模块void inputdata()void showdata()void changdata(int k) void restoredata(int k) int chksec(int s) int chkmax(int s)5.算法流程图三、调试记录与分析调试通过,程序未出错四、运行结果及说明1. 执行结果2. 结果分析银行家算法就是当接收到一个系统资源的分配后找到一个安全序列，使得进程间不会发生死锁，若发生死锁则让进程等待。五、课程设计总结通过本次银行家算法实验，加深了我对银行家算法的了解，掌握了如何利用银行家算法避免死锁。实验中遇到点问题，通过查阅资料、询问老师顺利解决。通过这次的实践，使我的理论知识更加的牢固。参考资料1汤小丹、汤子瀛、哲凤屏等，计算机操作系统（第三版），西安电子科技大学出版社，2007.8附录程序源码:#include #include #define FALSE 0 #define TRUE 1 #define W 10 /最大进程数W=10#define R 20 /最大资源总数R=20int M ; int N ; int ALL_RESOURCEW; int AVAILABLER; /可利用资源向量int MAXWR; /最大需求矩阵int ALLOCATIONWR; /分配矩阵int NEEDWR; /需求矩阵int RequestR; /进程请求向量 void inputdata(); /数据输入 void showdata(); /数据显示 void changdata(int k);/进程请求资源数据改变void restoredata(int k); /数据恢复int chksec(int s); /系统安全性的检测int chkmax(int s); /检测最大需求 void bank(); /检测分配的资源是否合理void main() int i,j; inputdata(); for(i=0;i=M) cout错误提示：经安全性检查发现，系统的初始状态不安全！nendl; else cout提示：经安全性检查发现，系统的初始状态安全！endl; bank(); void inputdata()int i=0,j=0,p; cout请输入总进程数:M; if (MW) coutendl总进程数超过了程序允许的最大进程数，请重新输入:W); coutendl; cout请输入资源的种类数:N; if (NR)coutendl资源的种类数超过了程序允许的最大资源种类数，请重新输入:R); coutendl; cout请依次输入各类资源的总数量，即设置向量all_resource:endl; for(i=0;iALL_RESOURCEi; coutendl; cout请依次输入各进程所需要的最大资源数量，即设置矩阵max:endl; for (i=0;iM;i+) for (j=0;jMAXij; if (MAXijALL_RESOURCEj) coutendl该最大资源数量超过了声明的该资源总数,请重新输入:ALL_RESOURCEj); coutendl; cout请依次输入各进程已经占据的各类资源数量，即设置矩阵allocation:endl; for (i=0;iM;i+) for (j=0;jALLOCATIONij; if (ALLOCATIONijMAXij)coutendl已占有的资源数量超过了声明的最大资源数量,请重新输入:MAXij); coutendl; for (i=0;iM;i+) for(j=0;jN;j+) NEEDij=MAXij-ALLOCATIONij; for (j=0;jN;j+) p=ALL_RESOURCEj; for (i=0;iM;i+) p=p-ALLOCATIONij; AVAILABLEj=p; if(AVAILABLEj0) AVAILABLEj=0; void showdata() int i,j; cout各种资源的总数量，即向量all_resource为:endl; cout ; for (j=0;jN;j+) cout 资源j: ALL_RESOURCEj; coutendlendl; cout当前系统中各类资源的可用数量，即向量available为:endl; cout ; for (j=0;jN;j+) cout 资源j: AVAILABLEj; coutendlendl; cout各进程还需要的资源数量，即矩阵need为:endlendl; for (i=0;iM;i+) cout进程Pi: ; for (j=0;jN;j+) coutNEEDij ; coutendl; coutendl; cout各进程已经得到的资源量，即矩阵allocation为: endlendl; for (i=0;iM;i+) cout进程Pi: ; for (j=0;jN;j+) coutALLOCATIONij ; coutendl; coutendl; void changdata(int k) int j; for (j=0;jN;j+) AVAILABLEj=AVAILABLEj-Requestj; ALLOCATIONkj=ALLOCATIONkj+Requestj; NEEDkj=NEEDkj-Requestj;void restoredata(int k) int j; for (j=0;jN;j+) AVAILABLEj=AVAILABLEj+Requestj; ALLOCATIONkj=ALLOCATIONkj-Requestj; NEEDkj=NEEDkj+Requestj;int chksec(int s) int WORK,FINISHW; int i,j,k=0; for(i=0;iM;i+)FINISHi=FALSE; for(j=0;jN;j+) WORK=AVAILABLEj; i=s; doif(FINISHi=FALSE&NEEDij=WORK)WORK=WORK+ALLOCATIONij; FINISHi=TRUE; i=0; else i+; while(iM); for(i=0;iM;i+) if(FINISHi=FALSE) return 1; return 0; int chkmax(int s) int j,flag=0;for(j=0;jN;j+) if (MAXsj=ALLOCATIONsj) flag=1;AVAILABLEj=AVAILABLEj+MAXsj;MAXsj=0;return flag;c int i=0,j=0; char flag=Y; while(flag=Y|flag=y) i=-1; while(i=M) cout请输入需申请资源的进程号（从P0到PM-1，否则重新输入!）:; couti; if(i=M) cout输入的进程号不存在，重新输入!endl; cout请输入进程Pi申请的资源数:endl; for (j=0;jN;j+) cout 资源jRequestj; if(RequestjNEEDij) cout进程Pi申请的资源数大于进程Pi还需要j类资源的资源量!; cout申请不合理，出错!请重新选择!endlAVAILABLEj) cout进程Pi申请的资源数大于系统可用j类资源的资源量!; cout申请不合理，出错!请重新选择!endlendl; flag=N; break; if(flag=Y|flag=y) changdata(i); if(chksec(i) coutendl; cout该分配会导致系统不安全! 本次资源申请不成功，不予分配!endl; coutendl; restoredata(i); else coutendl; cout经安全性检查，系统安全，本次分配成功，且资源分配状况如下所示：endl; coutendl;showdata(); if(chkmax(i)cout在资源分配成功之后，由于该进程所需的某些资源的最大需求量已经满足，endl;cout因此在进程结束后系统将回收这些资源！endl; cout在资源收回之后，各进程的资源需求和分配情况如下所示：endl;showdata(); coutendl; coutflag; 附录A：指导教师评语及成绩指导教师评语：成绩评定： 指导教师： 年 月 日目 录1 总 论11.1 项目概况11.2 建设单位概况31.3 项目提出的理由与过程31.4 可行性研究报告编制依据41.5 可行性研究报告编制原则41.6 可行性研究范围51.7 结论与建议62 项目建设背景和必要性92.1 项目区基本状况92.2 项目背景112.3 项目建设的必要性113 市场分析143.1 物流园区的发展概况143.2 市场供求现状163.3 目标市场定位173.4 市场竞争力分析174 项目选址和建设条件194.1 选址原则194.2 项目选址194.3 场址所在位置现状194.4 建设条件205 主要功能和建设规模225.1 主要功能225.2 建设规模及内容266 工程建设方案276.1 设计依据276.2 物流空间布局的要求276.3 空间布局原则286.4 总体布局296.5 工程建设方案306.6 给水工程336.7 排水工程356.8 电力工程386.9 供热工程466.10 电讯工程477 工艺技术和设备方案517.1 物流技术方案517.2 制冷工艺技术方案678 节能方案分析738.1 节能依据738.2 能耗指标分析738.3 主要耗能指标计算748.4 节能措施和节能效果分析769环境影响评价839.1 设计依据839.2 环境影响评价应坚持的原则839.3项目位置环境现状849.4项目建设与运营对环境的影响849.5项目建设期环境保护措施849.6 项目运行期环境保护措施8610 安全与消防8710.1安全措施8710.2消防8811 组织机构和人力资源配置9211.1 施工组织机构9211.2 基建项目部的主要职责9211.3 运营管理9311.4 人员来源、要求及培训9412 工程进度安排9612.1 建设工期9612.2 工程实施进度安排9613 投资估算与资金筹措9813.1 投资估算98投资估算包括建设项目的全部工程，主要内容有：主体建筑工程、道路硬化工程、绿化工程、其他费用及基本预备费。9813.2 资金筹措9914 财务评价10214.1 评价依据及方法10214.2 基础数据与参数选取10214.3 营业收入及总成本费用估算10314.4 利润总额估算10514.5 盈亏平衡分析10514.6 财务评价10615 综合效益评价10716 招投标管理10816.1 编制依据10816.2 招标原则10816.3 招标方案10916.4 评标要点11017 结论及建议11117.1 结论11117.2 建议11221