「银行家算法实验报告总结」.doc

操作系统原理课程设计银行家算法指导老师： 周敏 唐洪英 杨宏雨 杨承玉 傅由甲 黄贤英 院 系： 计算机学院计算机科学与技术系 班 级： 0237-6 学 号： 2002370608 姓 名： 朱 应 瑜 同 组 者： 陈 源 时 间： 2005/12/22-2005/12/28 目录一、设计目的3二、设计内容3三、银行家算法的基本思想3（一）死锁3（二）系统安全状态4（三）银行家算法避免死锁41、银行家算法中的数据结构42、银行家算法43、安全性算法5四、系统模块间关系图6五、系统子模块结构图7六、输入、输出数据9七、源程序及系统文件使用说明12（一）源程序12（二）系统文件使用说明25八、心得体会26九、参考文献26银行家算法一、 设计目的本课程设计是学习完计算机操作系统课程后，进行的一次全面的综合训练。通过这次课程设计，让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。二、 设计内容编制银行家算法通用程序，并检测所给状态的系统安全性。三、银行家算法的基本思想（一）死锁在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。产生死锁的原因可归结为如下两点：（1）竞争资源。（2）进程间推进顺序非法。死锁的发生必须具备下列四个必要条件：（1）互斥条件。（2）请求和保持条件。（3）不剥夺条件。（4）环路等待条件。（二）系统安全状态避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。所谓安全状态，是指系统能按某种进程顺序（P1，P2，Pn）（称序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利的完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。（三）银行家算法避免死锁为实现银行家算法，系统中必须设置若干数据结构。1、银行家算法中的数据结构（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Availablej=K，则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，j=K，则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi，j=K，则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi，j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵存在如下关系： Needi,j= Maxi，j- Allocationi，j2、银行家算法设Requesti 是进程Pi的请求向量，如果Requesti，j=K,表示进程需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：（1）如果Requesti，j= Needi，j，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requesti，j= Availablej，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej= Availablej- Requesti，j； Allocationi，j= Allocationi，j+ Requesti，j； Needi，j= Needi，j- Requesti，j；（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。3、安全性算法系统所执行的安全性算法可描述如下：（1）设置两个向量：工作向量Work：它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，在执行安全算发开始时，Work=Available；Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false；当有足够资源分配给进程时，再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=false；Needi，j = Workj；若找到，执行步骤（3），否则，执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj= Worki+ Allocationi，j； Finishi=true； go to step 2；（4）如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。四、系统模块间关系图五、系统子模块结构图六、输入、输出数据执行程序，输入数据之前：现在请分别输入对应的进程号、资源号和个数：现在请选择1或2：选择了1后：因为未通过安全性测试，不予以分配，所以一切数据均无变化。点击了1后：现在又请分别输入其它需要测试的进程号、资源号和个数：现在请选择1或2：选择了1后：因为通过了安全性测试，并找到了一个安全序列，所以分配成功，有关数据均要发生变化。（请对照前后数据及所输入的数据进行比较）l 资源类型1的可利用资源由4变成3；l 进程2的资源类型1的已分配资源由2变成3；l 进程2的资源类型1的已需求资源由1变成0；点击了1后：七、源程序及系统文件使用说明（一）源程序#include stdafx.h#include#include#include#include#define MAX_PROCESS 32 /最大进程数#define MAX_COURCE 64 /最大资源类别int MAX_FACT_PROCESS; /实际总进程数int MAX_FACT_COURCE; /实际资源类别数int AvailableMAX_COURCE; /可利用资源向量int MaxMAX_PROCESSMAX_COURCE; /最大需求矩阵int AllocationMAX_PROCESSMAX_COURCE; /分配矩阵int NeedMAX_PROCESSMAX_COURCE; /需求矩阵int Request_PROCESS; /发出请求的进程int Request_COURCE; /被请求资源类别int Request_COURCE_NEMBER; /请求资源数bool loop = true;struct COMPint value;int num;int next;int flag=0;void Read_Initiate(void)/读入初始化文档 ifstream infile(Initiate.txt);if(!infile)cout不能打开输入文件:Initiate.txtendl;exit(1);cout开始读入初始化文档ch) /初始化文档的第一个数字为长度Arraynum+=ch;num=0;MAX_FACT_COURCE=Arraynum+;for(int j=0;jMAX_FACT_COURCE;j+)Availablej=Arraynum+;MAX_FACT_PROCESS=Arraynum+;for(int i=0;iMAX_FACT_PROCESS;i+)for(int j=0;jMAX_FACT_COURCE;j+)Maxij=Arraynum+;infile.close();void Write_Initiate(void)/写入初始化文档(分配资源) ofstream outfile(Initiate.txt);if(!outfile)cout不能打开初始化文档：endl;exit(1);int ArrayMAX_PROCESS*MAX_COURCE*2;int num=0;Arraynum+=MAX_FACT_COURCE;for(int i=0;iMAX_FACT_COURCE;i+)Arraynum+=Availablei;Arraynum+=MAX_FACT_PROCESS;for(i=0;iMAX_FACT_PROCESS;i+)for(int j=0;jMAX_FACT_COURCE;j+)Arraynum+=Maxij;num=0;outfileArraynum+ ;for(i=0;iMAX_FACT_COURCE;i+)outfileArraynum+ ;outfileendlArraynum+endl;for(i=0;iMAX_FACT_PROCESS;i+)for(int j=0;jMAX_FACT_COURCE;j+)outfileArraynum+ ;outfileendl;int m_delay=3000;Sleep(m_delay);outfile.close();cout修改初始化文档成功!endl;void Allocated_list(void)/读入已分配资源列表 ifstream infile(Allocated_list.txt);if(!infile)cout不能打开输入文件:Allocated_list.txtendl;exit(1);cout开始读入已分配资源列表ch)Arraynum+=ch;num=0;for(int i=0;iMAX_FACT_PROCESS;i+)for(int j=0;jMAX_FACT_COURCE;j+)Allocationij=Arraynum+;infile.close();void Set_Need(void)/设置需求矩阵 cout设置需求矩阵endl;for(int i=0;iMAX_FACT_PROCESS;i+)for(int j=0;jMAX_FACT_COURCE;j+)Needij=Maxij-Allocationij;void Write_Allocation(void)/修改资源分配列表(资源分配) ofstream outfile(Allocated_list.txt);if(!outfile)cout不能打开资源分配列表：endl;exit(1);for(int i=0;iMAX_FACT_PROCESS;i+)for(int j=0;jMAX_FACT_COURCE;j+)outfileAllocationij ;outfileendl;int m_delay=3000;Sleep(m_delay);cout修改资源分配列表成功!endl;outfile.close();void Allocate_Source(void)/开始分配(已通过扫描和安全性检测) coutendl开始给第Request_PROCESS个进程分配第Request_COURCE类资源Request_COURCE_NEMBER个endl;Write_Initiate();Write_Allocation();int m_delay=3000;Sleep(m_delay);coutendl祝贺您，资源分配已成功!endl;bool Test_Safty()/安全性检测 coutendl进入安全性检测!endl;int WorkMAX_COURCE;for(int i=0;iMAX_FACT_COURCE;i+)Worki=Availablei;bool FinishMAX_PROCESSMAX_COURCE;for(i=0;iMAX_FACT_PROCESS;i+)for(int j=0;jMAX_FACT_COURCE;j+)Finishij=false;COMP Array32;for(i=0;iMAX_FACT_PROCESS;i+)Arrayi.value=NeediRequest_COURCE-1; Arrayi.num=i;for(i=0;iMAX_FACT_PROCESS;i+)for(int j=i+1;j=Arrayj.value)int t;t=Arrayj.value;Arrayj.value=Arrayi.value;Arrayi.value=t;t=Arrayj.num;Arrayj.num=Arrayi.num;Arrayi.num=t;else continue;int m_delay=3000;Sleep(m_delay);if(FinishRequest_PROCESS-1Request_COURCE-1=false&NeedRequest_PROCESS-1Request_COURCE-1=WorkRequest_COURCE-1)WorkRequest_COURCE-1=WorkRequest_COURCE-1+AllocationRequest_PROCESS-1Request_COURCE-1;FinishRequest_PROCESS-1Request_COURCE-1=true;elsecout未通过安全性测试，不与以分配endl;return false; for(i=0;iMAX_FACT_PROCESS;i+) if(Arrayi.num=Request_PROCESS-1)continue;if(Arrayi.num!=Request_PROCESS-1&FinishArrayi.numRequest_COURCE-1=false&NeedArrayi.numRequest_COURCE-1=WorkRequest_COURCE-1)WorkRequest_COURCE-1=WorkRequest_COURCE-1+AllocationArrayi.numRequest_COURCE-1; FinishArrayi.numRequest_COURCE-1=true;for(i=0;iMAX_FACT_PROCESS;i+)if(FinishiRequest_COURCE-1=true)continue;elsecout未通过安全性测试，不与以分配endl;return false;coutendl找到一个安全序列:PRequest_PROCESS;for(i=0;iMAX_FACT_PROCESS;i+)if(Arrayi.num=Request_PROCESS)continue;elsecoutPArrayi.num;coutendl已通过安全性测试!endl;Allocate_Source();return true;bool RUN(void) /执行银行家算法 cout*endl点击1执行!endl点击2退出!endl*flag;if(flag=2)loop = false;exit(0);if(flag=1)cout开始扫描请求信息!NeedRequest_PROCESS-1Request_COURCE-1)coutendl第Request_PROCESS个进程请求第Request_COURCE类资源Request_COURCE_NEMBER个endl;cout可是已超出该进程尚需的该类资源的最大数量,所以不予以分配!AvailableRequest_COURCE-1)coutendl第Request_PROCESS个进程请求第Request_COURCE类资源Request_COURCE_NEMBER个endl;cout可是系统中尚无足够的资源,所以进入等待队列!endl;return false;elseAvailableRequest_COURCE-1=AvailableRequest_COURCE-1-Request_COURCE_NEMBER;AllocationRequest_PROCESS-1Request_COURCE-1=AllocationRequest_PROCESS-1Request_COURCE-1+Request_COURCE_NEMBER;NeedRequest_PROCESS-1Request_COURCE-1=NeedRequest_PROCESS-1Request_COURCE-1-Request_COURCE_NEMBER;cout扫描通过endl;Sleep(m_delay);Test_Safty();else cout输入错误,请重新输入!endl;RUN();return true; void main(void)int tflag;int i;int j;char tch;while(loop)Read_Initiate();coutendl资源个数：MAX_FACT_COURCEendl;cout可利用资源endl;cout资源类型 ;for(i=0;iMAX_FACT_COURCE;i+)couti+1 ;coutendl;cout ;for(i=0;iMAX_FACT_COURCE;i+)coutAvailablei ;coutendl进程个数：MAX_FACT_PROCESSendl;cout资源类型 ;for(i=0;iMAX_FACT_COURCE;i+)couti+1 ;coutendl;for(i=0;iMAX_FACT_PROCESS;i+)coutPi+1: ;for(j=0;jMAX_FACT_COURCE;j+)coutMaxij ;coutendl;int m_delay=3000;Sleep(m_delay);cout读入成功endlendl;Allocated_list();cout资源类型 ;for(i=0;iMAX_FACT_COURCE;i+)couti+1 ;coutendl;for(i=0;iMAX_FACT_PROCESS;i+)coutPi+1: ;for(j=0;jMAX_FACT_COURCE;j+)coutAllocationij ;coutendl;Sleep(m_delay);cout读入成功endlendl;Set_Need();cout资源类型 ;for(i=0;iMAX_FACT_COURCE;i+)couti+1 ;coutendl;for(i=0;iMAX_FACT_PROCESS;i+)coutPi+1: ;for(j=0;jMAX_FACT_COURCE;j+)coutNeedij ;coutendl;Sleep(m_delay);cout设置成功endl;coutendl请输入进程号(1MAX_FACT_PROCESSRequest_PROCESS;coutendl请输入资源号(1MAX_FACT_COURCERequest_COURCE;coutendlRequest_COURCE_NEMBER;coutendl第Request_PROCESS个进程请求第Request_COURCE类资源Request_COURCE_NEMBER个endl;coutendl读入成功endl;RUN();cout*endl点击1继续!endl其它则退出!en