操作系统实验三-银行家算法

1、广东海洋大学学生实验报告书（学生用表）实验名称实验三 死锁的避免(银行家算法)课程名称计算机操作系统课程号学院(系)专业班级学生姓名学号实验地点实验日期实验三 死锁的避免银行家算法一、 实验目的1 掌握死锁产生的原因。2 掌握银行家算法。3 能使用高级语言模拟实现银行家算法。二、 相关知识介绍参与死锁的进程最少是两个。参与死锁的进程至少有两个已经占有资源。参与死锁的所有进程都在等待资源。参与死锁的进程是当前系统中所有进程的子集。三、 相关数据结构1 可利用资源向量Available ，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资

2、源数目。其数值随该类资源的分配和回收而动态地改变。如果Availablej=k，标是系统中现有j类资源k个。2 最大需求矩阵Max，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxij=k，表示进程i需要j类资源的最大数目为k。3 分配矩阵Allocation，这是一个n×m的矩阵，它定义了系统中的每类资源当前分配到每一个进程的资源数。如果Allocationij=k，表示进程i当前已经分到j类资源的数目为k个。Allocationi表示进程i的分配向量。4 需求矩阵Need，这是一个n×m的矩阵，用以表示每个进程还需要的

3、各类资源的数目。如果Needij=k，表示进程i还需要j类资源k个，才能完成其任务。Needi表示进程i的需求向量。 上述三个矩阵间存在关系：Needij=Maxij-Allocationij；四、 银行家算法Request是进程i的请求向量。Requestj=k表示进程i请求分配j类资源k个。当进程i发出资源请求后，系统按下述步骤进行检查：1 如果Request Needi，则转向步骤2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。2 如果Request Available，则转向步骤3；否则，表示系统中尚无足够的资源满足进程i的申请，进程i必须等待。3 系统试探性地把资源

4、分配给进程i，并修改下面数据结构中的数值：Available = Available - Request Allocationi= Allocationi+ RequestNeedi= Needi - Request 4 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程i，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程i等待。五、 安全性算法1 设置两个向量。Work：它表示系统可提供给进程继续运行的各类资源数目，它包含m个元素，开始执行安全性算法时，Work = Available。Finish：它表示系统是否有足够的资源分配

5、给进程，使之运行完成，开始Finishi=false；当有足够资源分配给进程i时，令Finishi=true；2 从进程集合中找到一个能满足下述条件的进程。Finishi= = false；Neediwork；如找到则执行步骤3；否则，执行步骤4；3 当进程i获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行Work = work + AllocationiFinishi=true；转向步骤2；4 若所有进程的Finishi都为true，则表示系统处于安全状态；否则，系统处于不安全状态。六、 实验内容设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的

6、申请动态的分配资源。系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于用户观察和分析。程序框架已经给出，要求将安全性算法补充完整。/*/* 实验三 死锁的避免银行家算法 */* */*本程序需要预先设置三个文件：Available_list.txt，Max_list.txt，Allocation_list.txt */* 各文件格式如下： */* Available_list.txt */* 3 /表示共有3类资源 */* 10 5 7 /表示各类资源的初始可用个数，即Available0=10, Available1=5 */* */* */* Max_list.txt */

7、* 5 /表示共有5个进程 */* 7 5 3 /表示各个进程需要各类资源的最大数目，即Max00=7, Max01=5*/* 3 2 2 */* 9 0 2 */* 2 2 2 */* 4 3 3 */* */* */* Allocation_list.txt */* 0 1 0 /表示各个进程已分配各类资源的数目 */* 2 0 0 */* 3 0 2 */* 2 1 1 */* 0 0 2 */* */* */*/#include <iostream.h>#include <stdio.h>#include <windows.h>#define MAX

8、_PROCESS 32 /最大进程数#define MAX_RESOURCE 64 /最大资源类别int PROCESS_NUM; /实际总进程数int RESOURCE_NUM; /实际资源类别数int AvailableMAX_RESOURCE; /可利用资源向量int MaxMAX_PROCESSMAX_RESOURCE; /最大需求矩阵int AllocationMAX_PROCESSMAX_RESOURCE; /分配矩阵int NeedMAX_PROCESSMAX_RESOURCE; /需求矩阵int Request_PROCESS; /发出请求的进程int Request_RESO

9、URCE_NEMBERMAX_RESOURCE; /请求资源数void Read_Available_list(); /读入可用资源Availablevoid Read_Max_list(); /读入最大需求矩阵Maxvoid Read_Allocation_list(); /读入已分配矩阵Allocationvoid PrintInfo(); /打印各数据结构信息void Read_Request();/输入请求向量void Allocate_Source(); /开始正式分配资源（修改Allocation_list.txt）void Recover_TryAllocate(); /恢复试分

10、配前状态int Test_Safty(); /安全性检测void RunBanker(); /执行银行家算法/读入可用资源Availablevoid Read_Available_list() FILE *fp;if(fp=fopen("Available_list.txt","r")=NULL) cout<<"错误,文件打不开,请检查文件名"<<endl; exit(0);fscanf(fp,"%d",&RESOURCE_NUM);int i=0;while(!feof(fp)fs

11、canf(fp,"%d",&Availablei);i+;fclose(fp);/读入最大需求矩阵Maxvoid Read_Max_list() FILE *fp;if(fp=fopen("Max_list.txt","r")=NULL) cout<<"错误,文件打不开,请检查文件名"<<endl; exit(0);fscanf(fp,"%d",&PROCESS_NUM);for(int i=0;i<PROCESS_NUM;i+)for(int j=

12、0;j<RESOURCE_NUM;j+)fscanf(fp,"%d",&Maxij);fclose(fp);/读入已分配矩阵Allocationvoid Read_Allocation_list() FILE *fp;if(fp=fopen("Allocation_list.txt","r")=NULL) cout<<"错误,文件打不开,请检查文件名"<<endl; exit(0);for(int i=0;i<PROCESS_NUM;i+)for(int j=0;j<

13、;RESOURCE_NUM;j+)fscanf(fp,"%d",&Allocationij);fclose(fp);/设置需求矩阵Needvoid Set_Need_Available() for(int i=0;i<PROCESS_NUM;i+)for(int j=0;j<RESOURCE_NUM;j+)Needij=Maxij-Allocationij;Availablej=Availablej-Allocationij;/打印各数据结构信息void PrintInfo()cout<<"进程个数： "<<P

14、ROCESS_NUM<<"t"<<"资源个数： "<<RESOURCE_NUM<<endl;cout<<"可用资源向量Available："<<endl;int i,j;for(i=0;i<RESOURCE_NUM;i+)cout<<Availablei<<"t"cout<<endl;cout<<"最大需求矩阵Max："<<endl;for(i=0;i<

15、PROCESS_NUM;i+)for(j=0;j<RESOURCE_NUM;j+)cout<<Maxij<<"t"cout<<endl;cout<<"已分配矩阵Allocation："<<endl;for(i=0;i<PROCESS_NUM;i+)for(j=0;j<RESOURCE_NUM;j+)cout<<Allocationij<<"t"cout<<endl;cout<<"需求矩阵Need：&q

16、uot;<<endl;for(i=0;i<PROCESS_NUM;i+)for(j=0;j<RESOURCE_NUM;j+)cout<<Needij<<"t"cout<<endl;/输入请求向量void Read_Request() cout<<"输入发起请求的进程（0"<<PROCESS_NUM-1<<")："cin>>Request_PROCESS;cout<<"输入请求资源的数目：按照这样的格式输入

17、x x x："for(int i=0; i<RESOURCE_NUM; i+)cin>>Request_RESOURCE_NEMBERi;/开始正式分配资源（修改Allocation_list.txt）void Allocate_Source() cout<<'n'<<"开始给第"<<Request_PROCESS<<"个进程分配资源."<<endl;FILE *fp;if(fp=fopen("Allocation_list.txt"

18、;,"w")=NULL) cout<<"错误,文件打不开,请检查文件名"<<endl; exit(0);for(int i=0;i<PROCESS_NUM;i+)for(int j=0;j<RESOURCE_NUM;j+)fprintf(fp,"%d ",Allocationij);fprintf(fp,"n");cout<<"分配完成，已更新Allocation_list.txt"<<endl;fclose(fp);/恢复试分配前状态

19、void Recover_TryAllocate()for(int i=0;i<RESOURCE_NUM;i+)Availablei=Availablei+Request_RESOURCE_NEMBERi;AllocationRequest_PROCESSi=AllocationRequest_PROCESSi-Request_RESOURCE_NEMBERi; NeedRequest_PROCESSi=NeedRequest_PROCESSi+Request_RESOURCE_NEMBERi;/安全性检测/返回值：0：未通过安全性测试； 1：通过安全性测试int Test_Safty(

20、) /请完成安全性检测算法的编程void RunBanker() /执行银行家算法cout<<endl;cout<<"开始执行银行家算法."<<endl;for(int i=0;i<RESOURCE_NUM;i+) /检查是否满足条件Request<=Needif(Request_RESOURCE_NEMBERi>NeedRequest_PROCESSi)cout<<"n第"<<Request_PROCESS<<"个进程请求资源不成功"<&

21、lt;endl;cout<<"原因：超出该进程尚需的资源的最大数量!"<<endl;return;for(i=0;i<RESOURCE_NUM;i+) /检查是否满足条件Request<=Availableif(Request_RESOURCE_NEMBERi>Availablei)cout<<"n第"<<Request_PROCESS<<"个进程请求资源不成功"<<endl;cout<<"原因：系统中无足够的资源!&quo

22、t;<<endl;return;else/试分配，更新各相关数据结构Availablei=Availablei-Request_RESOURCE_NEMBERi; AllocationRequest_PROCESSi=AllocationRequest_PROCESSi+Request_RESOURCE_NEMBERi; NeedRequest_PROCESSi=NeedRequest_PROCESSi-Request_RESOURCE_NEMBERi;cout<<endl<<"试分配完成."<<endl;if(Test_Sa

23、fty() /使用安全性算法检查，若满足，则正式分配Allocate_Source();else /否则恢复试分配前状态Recover_TryAllocate(); void main()char c;Read_Available_list();Read_Max_list();Read_Allocation_list();Set_Need_Available();PrintInfo();while(1)Read_Request();RunBanker();cout<<"nn需要继续吗？（y-继续；n-终止）"cin>>c;if(c='n

24、9;)break;cout<<endl<<endl;PrintInfo();实验的时候题目给出的资源介绍：MaxAllocationNeedAvailableABCABCABCA 3B 3C 2P0753010743P1322200122P2902302600P3222211011P4433002431实验进行中：以后就是我给实验代码缺失的部分补充的代码：（参考了很多文献书籍，看懂了也算是收获。）Work=Available；所有Finishi=false；while（还有未放入安全序列的进程）if （找到满足Finishi=false&&Needi&l

25、t;=Work的进程i）Work=Work+Allocationi;Finshi=true;If（遍历一遍，找不到满足条件的进程）break；if（所有Finishi=true）返回“安全”；else返回“不安全”；实验过程：网络上的其它参考答案：（看懂了也算是收获吧）#include<iostream.h>#include<fstream.h>#include<stdlib.h>#include "windows.h"#define MAX_PROCESS 32 /最大进程数#define MAX_COURCE 64 /最大资源类别in

26、t 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; /请求资源数struct

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

28、S*MAX_COURCE*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+)Maxj=Arraynum+;infile.close();void Write_Initi

29、ate(void) /写入初始化文档(分配资源ofstream outfile("Initiate.txt");if(!outfile)cout<<"不能打开初始化文档："<<'n'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+=Available;Arraynum+=MAX_FACT_PROCESS;for(i=0

30、;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Arraynum+=Maxj;num=0;outfile<<Arraynum+<<" "for(i=0;i<MAX_FACT_COURCE;i+)outfile<<Arraynum+<<" "outfile<<'n'<<Arraynum+<<endl;for(i=0;i<MAX_FACT_PROCESS;i+)for(in

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

32、"不能打开输入文件:"<<"Allocated_list.txt"<<'n'exit(1);cout<<"开始读入已分配资源列表"<<'n'int ch,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+)

33、Allocationj=Arraynum+;infile.close(); void Set_Need(void) /设置需求矩阵cout<<"设置需求矩阵"<<'n'for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Needj=Maxj-Allocationj;void Read_Request(void) /读入请求向量ifstream infile("Request_list.txt"); if(!infile)c

34、out<<"不能打开输入文件:"<<"Request_list.txt"<<'n'exit(1); cout<<"开始读入请求向量"<<'n'int Array3;int num=0,ch;while(infile>>ch) Arraynum+=ch; Request_PROCESS=Array0; Request_COURCE=Array1; Request_COURCE_NEMBER=Array2;infile.close();

35、void Write_Allocation(void) /修改资源分配列表(资源分配)ofstream outfile("Allocated_list.txt");if(!outfile)cout<<"不能打开资源分配列表："<<'n'exit(1);for(int i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)outfile<<Allocationj<<" "outfile<<

36、;endl; DWORD m_delay=3000;Sleep(m_delay);cout<<"修改资源分配列表成功!"<<endl;outfile.close();void Allocate_Source(void) /开始分配(已通过扫描和安全性检测)cout<<'n'<<"开始给第"<<Request_PROCESS<<"个进程分配第"<<Request_COURCE<<"类资源"<<R

37、equest_COURCE_NEMBER<<"个"<<endl;Write_Initiate();Write_Allocation();DWORD m_delay=3000;Sleep(m_delay);cout<<'n'<<"祝贺您，资源分配已成功!"<<endl; void Test_Safty() /安全性检测cout<<'n'<<"进入安全性检测!"<<endl; int WorkMAX_COURCE

38、;for(int i=0;i<MAX_FACT_COURCE;i+)Work=Available; bool FinishMAX_PROCESSMAX_COURCE;for(i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)Finishj=false;COMP Array32;for(i=0;i<MAX_FACT_PROCESS;i+)Array.value=NeedRequest_COURCE-1; Array.num=i;for(i=0;i<MAX_FACT_PROCESS;i+)for(in

39、t j=i+1;j<MAX_FACT_PROCESS;j+)if(Array.value>=Arrayj.value)int t;t=Arrayj.value; Arrayj.value=Array.value;Array.value=t;t=Arrayj.num; Arrayj.num=Array.num; Array.num=t;else continue;DWORD m_delay=3000;Sleep(m_delay);/*for(i=0;i<MAX_FACT_PROCESS;i+)for(int j=0;j<MAX_FACT_COURCE;j+)cout<

40、;<Needj<<'t'cout<<endl;*/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

41、;elsecout<<"未通过安全性测试，不与以分配"<<endl;exit(0); for(i=0;i<MAX_FACT_PROCESS;i+)if(Array.num=Request_PROCESS-1)continue;if(Array.num!=Request_PROCESS-1&&FinishArray.numRequest_COURCE-1=false&&NeedArray.numRequest_COURCE-1<=WorkRequest_COURCE-1)WorkRequest_COURCE-

42、1=WorkRequest_COURCE-1+AllocationArray.numRequest_COURCE-1; FinishArray.numRequest_COURCE-1=true; for(i=0;i<MAX_FACT_PROCESS;i+)if(FinishRequest_COURCE-1=true)continue;elsecout<<"未通过安全性测试，不与以分配"<<endl; exit(0);cout<<'n'<<"找到一个安全序列:"<<"

43、;P"<<Request_PROCESS<<"->" for(i=0;i<MAX_FACT_PROCESS;i+)if(Array.num=Request_PROCESS)continue;elsecout<<"P"<<Array.num<<"->"cout<<'n'<<"已通过安全性测试!"<<endl;Allocate_Source(); void RUN(void) /执

44、行银行家算法 cout<<"*"<<'n'<<"点击1执行!"<<'n'<<"点击2退出!"<<'n'<<"*"<<endl;cin>>flag;if(flag=2)exit(0);if(flag=1)cout<<"开始扫描请求信息!"<<endl;DWORD m_delay=3000;Sleep(m_delay);i

45、f(Request_COURCE_NEMBER>NeedRequest_PROCESS-1Request_COURCE-1)cout<<'n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl; cout<<"可是已超出该进程尚需的该类资源

46、的最大数量,所以不予以分配!"<<endl;exit(0);if(Request_COURCE_NEMBER>AvailableRequest_COURCE-1)cout<<'n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl; cout<<"可是系统中尚无足够的资源,所以进入等待队列!"<<endl;exit