银行家算法实验报告

1、操作系统原理课程设计银行家算法指导老师： 周敏 唐洪英 杨宏雨 杨承玉 傅由甲 黄贤英 院 系： 计算机学院计算机科学与技术系 班 级： 0237-6 学 号： 2002370608 姓 名： 朱 应 瑜 同 组 者： 陈 源 时 间： 2005/12/22-2005/12/28 目录一、设计目的3二、设计内容3三、银行家算法的基本思想3（一）死锁3（二）系统安全状态4（三）银行家算法避免死锁41、银行家算法中的数据结构42、银行家算法43、安全性算法5四、系统模块间关系图6五、系统子模块结构图7六、输入、输出数据9七、源程序及系统文件使用说明12（一）源程序12（二）系统文件使用说明25八、

2、心得体会26九、参考文献26银行家算法一、 设计目的本课程设计是学习完计算机操作系统课程后，进行的一次全面的综合训练。通过这次课程设计，让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。二、 设计内容编制银行家算法通用程序，并检测所给状态的系统安全性。三、银行家算法的基本思想（一）死锁在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。产生死锁的原因可归结为如下两

3、点：（1）竞争资源。（2）进程间推进顺序非法。死锁的发生必须具备下列四个必要条件：（1）互斥条件。（2）请求和保持条件。（3）不剥夺条件。（4）环路等待条件。（二）系统安全状态避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。所谓安全状态，是指系统能按某种进程顺序（P1，P2，Pn）（称<P1，P2，Pn>序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利的完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。（三）银行家算法避免死锁为实现银行家算法，系统中必须设置若干数据结构。1、银行家算法中的数据

4、结构（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当前已

5、分得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

6、<= 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、安全性算法系统所执行的安全性算法可描述

7、如下：（1）设置两个向量：工作向量Work：它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，在执行安全算发开始时，Work=Available；Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false；当有足够资源分配给进程时，再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=false；Needi，j <= Workj；若找到，执行步骤（3），否则，执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj= Worki+

8、Allocationi，j； Finishi=true； go to step 2；（4）如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。四、系统模块间关系图五、系统子模块结构图六、输入、输出数据执行程序，输入数据之前：现在请分别输入对应的进程号、资源号和个数：现在请选择1或2：选择了1后：因为未通过安全性测试，不予以分配，所以一切数据均无变化。点击了1后：现在又请分别输入其它需要测试的进程号、资源号和个数：现在请选择1或2：选择了1后：因为通过了安全性测试，并找到了一个安全序列，所以分配成功，有关数据均要发生变化。（请对照前后数据及所输入的数据

9、进行比较）l 资源类型1的可利用资源由4变成3；l 进程2的资源类型1的已分配资源由2变成3；l 进程2的资源类型1的已需求资源由1变成0；点击了1后：七、源程序及系统文件使用说明（一）源程序#include "stdafx.h"#include<iostream.h>#include<fstream.h>#include<windows.h>#include<stdlib.h>#define MAX_PROCESS 32 /最大进程数#define MAX_COURCE 64 /最大资源类别int MAX_FACT_PROC

10、ESS; /实际总进程数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;stru

11、ct COMPint value;int num;int next;int flag=0;void Read_Initiate(void)/读入初始化文档 ifstream infile("Initiate.txt");if(!infile)cout<<"不能打开输入文件:"<<"Initiate.txt"<<endl;exit(1);cout<<"开始读入初始化文档"<<endl;int ch;int ArrayMAX_PROCESS*MAX_COURC

12、E*2;int num=0;while(infile>>ch) /初始化文档的第一个数字为长度Arraynum+=ch;num=0;MAX_FACT_COURCE=Arraynum+;for(int j=0;j<MAX_FACT_COURCE;j+)Availablej=Arraynum+;MAX_FACT_PROCESS=Arraynum+;for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Maxij=Arraynum+;infile.close();void Write_Ini

13、tiate(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;i<MAX_FACT_COURCE;i+)Arraynum+=Availablei;Arraynum+=MAX_FACT_PROCESS;for(i=0;i&

14、lt;MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Arraynum+=Maxij;num=0;outfile<<Arraynum+<<" "for(i=0;i<MAX_FACT_COURCE;i+)outfile<<Arraynum+<<" "outfile<<endl<<Arraynum+<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j&l

15、t;MAX_FACT_COURCE;j+)outfile<<Arraynum+<<" "outfile<<endl;int m_delay=3000;Sleep(m_delay);outfile.close();cout<<"修改初始化文档成功!"<<endl;void Allocated_list(void)/读入已分配资源列表 ifstream infile("Allocated_list.txt");if(!infile)cout<<"不能打开输入

16、文件:"<<"Allocated_list.txt"<<endl;exit(1);cout<<"开始读入已分配资源列表"<<endl;int ch;int num=0;int ArrayMAX_PROCESS*MAX_COURCE;while(infile>>ch)Arraynum+=ch;num=0;for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Allocationij=Arraynu

17、m+;infile.close();void Set_Need(void)/设置需求矩阵 cout<<"设置需求矩阵"<<endl;for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Needij=Maxij-Allocationij;void Write_Allocation(void)/修改资源分配列表(资源分配) ofstream outfile("Allocated_list.txt");if(!outfile)cout<&

18、lt;"不能打开资源分配列表："<<endl;exit(1);for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)outfile<<Allocationij<<" "outfile<<endl;int m_delay=3000;Sleep(m_delay);cout<<"修改资源分配列表成功!"<<endl;outfile.close();void Allocate_So

19、urce(void)/开始分配(已通过扫描和安全性检测) cout<<endl<<"开始给第"<<Request_PROCESS<<"个进程分配第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;Write_Initiate();Write_Allocation();int m_delay=3000;Sleep(m_delay);cout&l

20、t;<endl<<"祝贺您，资源分配已成功!"<<endl;bool Test_Safty()/安全性检测 cout<<endl<<"进入安全性检测!"<<endl;int WorkMAX_COURCE;for(int i=0;i<MAX_FACT_COURCE;i+)Worki=Availablei;bool FinishMAX_PROCESSMAX_COURCE;for(i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_

21、COURCE;j+)Finishij=false;COMP Array32;for(i=0;i<MAX_FACT_PROCESS;i+)Arrayi.value=NeediRequest_COURCE-1; Arrayi.num=i;for(i=0;i<MAX_FACT_PROCESS;i+)for(int j=i+1;j<MAX_FACT_PROCESS;j+)if(Arrayi.value>=Arrayj.value)int t;t=Arrayj.value;Arrayj.value=Arrayi.value;Arrayi.value=t;t=Arrayj.num;

22、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;FinishReques

23、t_PROCESS-1Request_COURCE-1=true;elsecout<<"未通过安全性测试，不与以分配"<<endl;return false; for(i=0;i<MAX_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<

24、;=WorkRequest_COURCE-1)WorkRequest_COURCE-1=WorkRequest_COURCE-1+AllocationArrayi.numRequest_COURCE-1; FinishArrayi.numRequest_COURCE-1=true;for(i=0;i<MAX_FACT_PROCESS;i+)if(FinishiRequest_COURCE-1=true)continue;elsecout<<"未通过安全性测试，不与以分配"<<endl;return false;cout<<endl&

25、lt;<"找到一个安全序列:"<<"P"<<Request_PROCESS<<"->"for(i=0;i<MAX_FACT_PROCESS;i+)if(Arrayi.num=Request_PROCESS)continue;elsecout<<"P"<<Arrayi.num<<"->"cout<<endl<<"已通过安全性测试!"<<endl;A

26、llocate_Source();return true;bool RUN(void) /执行银行家算法 cout<<"*"<<endl<<"点击1执行!"<<endl<<"点击2退出!"<<endl<<"*"<<endl;cin>>flag;if(flag=2)loop = false;exit(0);if(flag=1)cout<<"开始扫描请求信息!"<<en

27、dl;int m_delay=3000;Sleep(m_delay);if(Request_COURCE_NEMBER>NeedRequest_PROCESS-1Request_COURCE-1)cout<<endl<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;cout&

28、lt;<"可是已超出该进程尚需的该类资源的最大数量,所以不予以分配!"<<endl;return false;if(Request_COURCE_NEMBER>AvailableRequest_COURCE-1)cout<<endl<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<&quo

29、t;个"<<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_PROCES

30、S-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();cout&l

31、t;<endl<<"资源个数："<<MAX_FACT_COURCE<<endl;cout<<"可利用资源"<<endl;cout<<"资源类型 "for(i=0;i<MAX_FACT_COURCE;i+)cout<<i+1<<" "cout<<endl;cout<<" "for(i=0;i<MAX_FACT_COURCE;i+)cout<<Avai

32、lablei<<" "cout<<endl<<"进程个数："<<MAX_FACT_PROCESS<<endl;cout<<"资源类型 "for(i=0;i<MAX_FACT_COURCE;i+)cout<<i+1<<" "cout<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)cout<<"P"<<i+1<<&quo

33、t;: "for(j=0;j<MAX_FACT_COURCE;j+)cout<<Maxij<<" "cout<<endl;int m_delay=3000;Sleep(m_delay);cout<<"读入成功"<<endl<<endl;Allocated_list();cout<<"资源类型 "for(i=0;i<MAX_FACT_COURCE;i+)cout<<i+1<<" "cout

34、<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)cout<<"P"<<i+1<<": "for(j=0;j<MAX_FACT_COURCE;j+)cout<<Allocationij<<" "cout<<endl;Sleep(m_delay);cout<<"读入成功"<<endl<<endl;Set_Need();cout<<"资源类型

35、"for(i=0;i<MAX_FACT_COURCE;i+)cout<<i+1<<" "cout<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)cout<<"P"<<i+1<<": "for(j=0;j<MAX_FACT_COURCE;j+)cout<<Needij<<" "cout<<endl;Sleep(m_delay);cout<<&qu

36、ot;设置成功"<<endl;cout<<endl<<"请输入进程号("<<"1"<<MAX_FACT_PROCESS<<"):"cin>>Request_PROCESS;cout<<endl<<"请输入资源号("<<"1"<<MAX_FACT_COURCE<<"):"cin>>Request_COURCE;cout<<endl<<"请输入个数:"cin>>Request_COURCE_NEMBER;cout<<endl<<"第"<<Request_PROCESS<<"个进程请求第"<&