银行家算法课设

1、操作系统实验报告 （理工类）课程名称： 银行家算法 专业班级:计算机科学与技术统2 学生学号：1305103040 学生姓名： 林荣 所属院部：计算机工程学院 指导教师： 李莉 20 15 20 16 学年 第 1 学期 金陵科技学院教务处制银行家算法一、        背景知识在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。在分配资源时判断是否会出现死锁，如不会死锁，则分配资源。死锁检测算法保存资源的请求和分配信息，

2、利用某种算法对这些信息加以检查，以判断是否存在死锁。主要是检查是否有循环等待.1 系统安全状态1）安全状态所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列 P1 ，P2 Pn就是安全序列。如果存在这样一个安全序列，则系统是安全的。2）安全状态之例进程最大需求已分配可用P1P2P310495223安全序列：P2 àP1à P3不安全序列：P1à P3à P2àP3àP1 3）由安全状态向不安全状态的转换2 利用银行家算法避免死锁1）银行家算法中的数据结构 可利用资源向量Available

3、。 最大需求矩阵Max。 分配矩阵Allocation 需求矩阵Need2）银行家算法 一个银行家拥有一定数量的资金，有若干个客户要贷款，每个客户须在一开始就声明他所需贷款的总额，若该客户贷款总额不超过银行家的资金总额，银行家可以接受客户的要求。客户贷款是以每次一个资金单位（如1万RMB等）的方式进行的，客户在借满所需的全部单位款额之前可能会等待，但银行家须保证这种等待是有限的，可完成的。 安全性算法利用安全性算法进行检查，如果分配是安全的，则执行分配；否则，分配不安全，不予分配。具体地，1）  当进程pi提出资源申请时，按照银行家算法分配资源，系统执行下列步骤：（1）若Reques

4、tNeed,转（2）；否则错误返回（2）若RequestAvailable,转（3）；否则进程等待（3）假设系统分配了资源，则有： Available:=Available-Request; Allocation:=Allocation+Request; Need:=Need-Request2）若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待为进行安全性检查，定义数据结构： Work:ARRAY1.m of integer; Finish:ARRAY1.n of Boolean;安全性检查的步骤：（1） Work:=Available; Finish:=fals

5、e;（2） 寻找满足条件的i： a.Finish=false; b.NeedWork; 如果不存在，则转(4)(3) Work:=Work+Allocation; Finish:=true;转(2)(4) 若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态。二、 实验目的通过模拟实现银行家算法，深入理解死锁避免的意义。 三、 实验要求1 充分理解死锁避免的意义。2 理解银行家算法和安全性检查算法的实质3 编写银行家算法模拟程序，实现银行家算法原理。开始输入资源数m及各类资源总数，初始化输入进程数ni<=n输入进程i的最大需求向量Max<=资源总数提示错误i加

6、1初始化needNeed矩阵为0所有进程运行结束任选一个进程作为当前进程Need向量为0该进程已运行输入该进程的资源请求量调用银行家算法，及安全性算法，完成分配并给出提示YNNYYYNN 四、 实验步骤1. 主要函数清单void showdata()/显示资源矩阵 int changdata(int i)/进行资源分配int safe()/安全性算法void share()/利用银行家算法对申请资源对进行判定void addprocess()/添加作业2.算法描述 设Requesti 是进程Pi的请求向量，如果Requestij=K,表示进程Pi需要K个Rj类型的资源，当Pi发出资源请求后，系

7、统按下面步骤进行检查：（1）如果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）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才

8、正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。3.数据结构银行家算法中的数据结构：（1） 可利用资源向量Available。这是一个含有n个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K,则表示系统中现有Rj类资源K个。（2）最大需求矩阵Max。这是一个m*n的矩阵，它定义了系统中n个进程中每一个进程对m类资源的最大需求。如果Maxi,j=K,则表示进程i需要Rj类资源的最大数目为K。（3）分配矩阵Allo

9、cation。这也是一个m*n的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K,则表示进程i当前已分得Rj类资源的数目为K。（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K,则表示进程i还需要Rj类资源K个，方能完成其任务。(5) 工作数组Work.。这是一个含有n个元素的数组，它代表可以提供分配的资源数，初始值是Available中的数值，随着资源的回收，它的值也会改变，公式是Worki=Worki+Allocationi。五、程序代码#include<iostream>us

10、ing namespace std;#include<string.h>#include<stdio.h>#define False 0#define True 1 int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/系统可用资源char name100=0;/资源的名称int Allocation100100=0;/系统已分配资源int Need100100=0;/还需要资源 int Request100=0;/请求资源向量 int temp100=0;/存放安全序列 int Work100=0;/存放系统可提供资源

11、int M=100;/作业的最大数为100 int N=100;/资源的最大数为100 void showdata()/显示资源矩阵 int i,j; cout<<"系统目前可用的资源Avaliable:"<<endl; for(i=0;i<N;i+)cout<<namei<<" " cout<<endl; for (j=0;j<N;j+)cout<<Avaliablej<<" "/输出分配资源cout<<endl; cout&

12、lt;<" Max Allocation Need"<<endl; cout<<"进程名 " for(j=0;j<3;j+)for(i=0;i<N;i+)cout<<namei<<" "cout<<" "cout<<endl;for(i=0;i<M;i+)cout<<" "<<i<<" "for(j=0;j<N;j+)cout<<

13、;Maxij<<" "cout<<" "for(j=0;j<N;j+)cout<<Allocationij<<" "cout<<" "for(j=0;j<N;j+)cout<<Needij<<" "cout<<endl; int changdata(int i)/进行资源分配int j;for (j=0;j<M;j+) Avaliablej=Avaliablej-Requestj;

14、Allocationij=Allocationij+Requestj; Needij=Needij-Requestj; return 1;int safe()/安全性算法int i,k=0,m,apply,Finish100=0; int j; int flag=0; Work0=Avaliable0; Work1=Avaliable1; Work2=Avaliable2; for(i=0;i<M;i+)apply=0; for(j=0;j<N;j+)if (Finishi=False&&Needij<=Workj)apply+;if(apply=N) for

15、(m=0;m<N;m+)Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;i=-1; k+;flag+;for(i=0;i<M;i+)if(Finishi=False)cout<<"系统不安全"<<endl;/不成功系统不安全return -1;cout<<"系统是安全的!"<<endl;/如果安全，输出成功cout<<"分配的序列:"for(i=0;i<M;i+)/输出运行进程数组cout<<

16、tempi;if(i<M-1)cout<<"->"cout<<endl;return 0;void share()/利用银行家算法对申请资源对进行判定char ch;int i=0,j=0;ch='y'cout<<"请输入要求分配的资源进程号(0-"<<M-1<<"):"cin>>i;/输入须申请的资源号cout<<"请输入进程 "<<i<<" 申请的资源:"&

17、lt;<endl;for(j=0;j<N;j+)cout<<namej<<":"cin>>Requestj;/输入需要申请的资源 for (j=0;j<N;j+)if(Requestj>Needij)/判断申请是否大于需求，若大于则出错cout<<"进程 "<<i<<"申请的资源大于它需要的资源"cout<<" 分配不合理，不予分配！"<<endl; ch='n' break; e

18、lseif(Requestj>Avaliablej)/判断申请是否大于当前资源，若大于则/出错cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源"cout<<" 分配出错，不予分配!"<<endl;ch='n'break; if(ch='y')changdata(i);/根据进程需求量变换资源showdata();/根据进程需求量显示变换后的资源 safe();/根据进程需求量进行银行家算法判断 void addproce

19、ss()/添加作业int flag=M;M=M+1; cout<<"请输入该作业的最打需求量Max"<<endl; for(int i=0;i<N;i+)cout<<namei<<":"cin>>Maxflagi;Needflagi=Maxflagi-Allocationflagi; showdata(); safe(); int main()/主函数int i,j,number,choice,m,n,flag;char ming;cout<<"*资源管理系统的设计与

20、实现*"<<endl;cout<<"请首先输入系统可供资源种类的数量:" cin>>n; N=n; for(i=0;i<n;i+)cout<<"资源"<<i+1<<"的名称:"cin>>ming;namei=ming;cout<<"资源的数量:" cin>>number; Avaliablei=number; cout<<endl; cout<<"请输入作业的

21、数量:"cin>>m; M=m;cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)Max:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Maxij;doflag=0;cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<n<<"矩阵)

22、Allocation:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Allocationij;if(Allocationij>Maxij)flag=1; Needij=Maxij-Allocationij; if(flag)cout<<"申请的资源大于最大需求量，请重新输入!n"while(flag);showdata();/显示各种资源safe();/用银行家算法判定系统是否安全while(true)cout<<"*银行家算法演示*"&l

23、t;<endl;cout<<" 1:增加资源 "<<endlcout<<" 2:分配资源 "<<endlcout<<"*"<<endl;cout<<"请选择功能号："cin>>choice;switch(choice)case 1: addresources();break;case 2: share();break;default: cout<<"请正确选择功能号(0-3)!"&l

24、t;<endl;break; return 1;五运行结果6、 遇到的问题与解决办法1. 纠结在Linux系统下运行，最后还是没有搞出来，只能在Windows下运行了。2. 代码的问题，运行时老出现错误，通过上网查询资料解决了。七、设计体会经过几天的自己动手练习，对操作系统的掌握又进了一步，收获了很多课堂上和书上未出现过的或老师未讲到的一些知识。在完成实验的过程中，进行了反复的修改和调试，这次实验，让我基本上明白了银行家算法的基本原理，加深了对课堂上知识的理解，也懂得了如何让银行家算法实现，但编程功底的原因使程序很是繁琐。这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，先用银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求量，才和系统所能给的资源相比较.让进程形成一个安全队列,看系统是否安全.再利用安全性算法检查此时系统是否安全。要做