操作系统课程设计实验报告

1、.操作系统课程设计实验报告书科 目： 操作系统 设计题目： 银行家算法 指导教师： 孙浩 班 级： 1020603 学 号： 06250317 姓 名： 孟祥可 2009 年 1 月 6 日实验题目：银行家算法实验目的： 1.掌握多道程序系统中多个进程并发执行的资源分配； 2.掌握死锁产生的原因，产生死锁的必要条件和处理死锁的基本方法； 3.掌握预防死锁的方法，系统安全状态的基本概念； 4.掌握银行家算法，了解资源在进程并发执行中的资源分配策略； 5.理解死锁避免在当前计算机系统中不常用的原因实验要求：银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。

2、加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。设计内容（1）设计及进程对各类资源的最大申请及初值确定；（2）设定系统提供资源初始状况；（3）设定每次某个进程对各资源的申请表示情况；（4）编写程序，依据银行家算法，决定其申请是否得到满足。实验步骤：（阐述清楚实验的具体步骤）算法核心银行家可以把一定数量的资金供多个用户周转使用，为保证资金的安全银行家规定：（1）当一个用户对资金的最大需求量不超过银行家现有的资金就要接纳该用户；（2）用户可以分期贷款,但贷的总数不能超过最大需求量；（3）当银行家现有的资金不能满足用户的沿需贷数时,对用户的贷款可推迟支付,但总能使用户

3、在有限的时间里得到贷款；（4） 当用户得到所需的全部资金后,一定能在有限的时间里归还所有的资金。数据结构设计3.2.3.数据结构假设有M个进程N类资源，则有如下数据结构:#define W 10#define R 20int A ; /总进程数int B ; /资源种类int ALL_RESOURCEW; /各种资源的数目总和int MAXWR; /M个进程对N类资源最大资源需求量int AVAILABLER; /系统可用资源数int ALLOCATIONWR; /M个进程已经得到N类资源的资源量int NEEDWR; /M个进程还需要N类资源的资源量int RequestR; /请求资源个数

4、主要函数说明void showdata(); /主要用来输出资源分配情况void changdata(int); /主要用来输出资源分配后后的情况void rstordata(int); /用来恢复资源分配情况,如:银行家算法时,由于分配不安全则要恢复资源分配情况int chkerr(int); /银行家分配算法的安全检查void bank() ; /银行家算法算法的实现（1）初始化由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED 赋值。（2） 银行家算法 进程向操作系统请求分配资源,操作系统按照银行家制定的规则为进

5、程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配

6、资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程 cusneed提出请求REQUEST i，则银行家算法按如下规则进行判断。 如果 REQUEST cusneed i<= NEEDcusneedi，则转；否则，出错。 如果 REQUEST cusneed i<= AVAILABLEcusneedi，则转；否则，出错。 系统试探分配资源，修改相关数据：AVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi; 系统执行

7、安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。（3）安全性检查算法 设置两个工作向量Work=AVAILABLE;FINISH 从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED<=Work;如找到，执行；否则，执行 设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO 如所有的进程Finish= true，则表示安全；否则系统不安全。 说明 引入了两个向量：Resourse（资源总量）、Available（剩余资源量） 以及两个矩阵：Claim（每个进程的最大需求量

8、）、Allocation（已为每个进程分配的数量）。它们共同构成了任一时刻系统对资源的分配状态。 向量模型： R1 R2 R3 矩阵模型： R1 R2 P1 P2 P3 设置另外一个矩阵：各个进程尚需资源量（Need）,可以看出 Need = Claim Allocation 因此，银行家算法描述如下： 设Requesti是进程Pi的请求向量。如果Requesti , j=k，表示Pi需k个Rj类资源。当Pi发出资源请求后，系统按下述步骤进行检查: (1) if (Requesti<=Needi) goto (2); else error(“over request”); (2) if

9、(Requesti<=Availablei) goto (3); else wait(); (3) 系统试探性把要求资源分给Pi（类似回溯算法）。并根据分配修改下面数据结构中的值。 Availablei = Availablei Requesti ； Allocationi = Allocationi + Requesti； Needi = Needi-Requesti; (4) 系统执行安全性检查，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程以完成此次分配；若不安全，试探方案作废，恢复原资源分配表，让进程Pi等待。 系统所执行的安全性检查算法可描述如下： 设

10、置两个向量：Free、Finish 工作向量Free是一个横向量，表示系统可提供给进程继续运行所需要的各类资源数目，它含有的元素个数等于资源数。执行安全算法开始时， Free = Available. 标记向量Finish是一个纵向量，表示进程在此次检查中中是否被满足，使之运行完成，开始时对当前未满足的进程做Finishi = false；当有足够资源分配给进程(Needi<=Free)时，Finishi=true，Pi完成，并释放资源。 (1)从进程集中找一个能满足下述条件的进程Pi Finishi = false(未定) Needi <= Free (资源够分) (2)当Pi获

11、得资源后，认为它完成，回收资源: Free = Free + Allocationi ; Finishi = true ; Go to step(1); 实验结果： （实验结果的数据以及图、表等）结果分析：（利用你所掌握的基础理论知识对实验的结果进行相应的分析）结果分析：我是采用逐个输入的方法来获得各个进程数据的，这样输入可以让人直观得知道现在输入的是第几个进程的第几类资源的数据，但由于不能修改所以只要输错一个就要重新来过。附录：代码#include <iostream>using namespace std;#define MAXPROCESS 50 /*最大进程数*/#defi

12、ne MAXRESOURCE 100 /*最大资源数*/int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程需要资源数*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int

13、 m,n; /*m个进程,n个资源*/void Init();bool Safe();void Bank();int main() Init(); Safe(); Bank();void Init() /*初始化算法*/ int i,j; cout<<"请输入进程的数目:" cin>>m; cout<<"请输入资源的种类:" cin>>n; cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n&l

14、t;<"矩阵输入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>MAXij; cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>ALLOCATIONij; NEEDij=MAXij-ALLOCATIONij

15、; if(NEEDij<0) cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数错误,请重新输入:"<<endl; j-; continue; cout<<"请输入各个资源现有的数目:"<<endl; for(i=0;i<n;i+) cin>>AVAILABLEi; void Bank() /*银行家算法*/ int i,cusneed; char again;

16、while(1) cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl; cin>>cusneed; cout<<"请输入进程所请求的各资源的数量"<<endl; for(i=0;i<n;i+) cin>>REQUESTcusneedi; for(i=0;i<n;i+) if(REQUESTcusneedi>NEEDcusneedi) cout<<"您输入的请求数超过进程的需求量!请重新输入!"<

17、;<endl; continue; if(REQUESTcusneedi>AVAILABLEi) cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl; continue; for(i=0;i<n;i+) AVAILABLEi-=REQUESTcusneedi; /*申请的资源小于等于可用资源*/ ALLOCATIONcusneedi+=REQUESTcusneedi; /*测试该进程已占用的资源数是否超过了该进程对资源的最大需求量*/ NEEDcusneedi-=REQUESTcusneedi; /*测试系统

18、现存的资源能否满足该进程尚需的最大资源量*/ if(Safe() /*如果小于，则分配，反之，被拒绝*/ cout<<"同意分配请求!"<<endl; else cout<<"您的请求被拒绝!"<<endl; for(i=0;i<n;i+) AVAILABLEi+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;i<m;i+) FINISHi=false; c

19、out<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl; cin>>again; if(again='y'|again='Y') continue; break; bool Safe() /*安全性算法*/ int i,j,k,l=0; int WorkMAXRESOURCE; /*工作数组*/ for(i=0;i<n;i+) Worki=AVAILABLEi; /*系统中剩余资源量的变化. */ for(i=0;i<m;i+) FINISHi=false; /*各进程是否假设"已完成*/ for(i=0;i<m;i+) if(FINISHi=true) continue; else for(j=0;j<n;j+) if(NEEDij>Workj) break; if(j=n) FINISHi=true; for(k=0;k<n;k+) Workk+=ALLOCATIONik; pl+=i; i=-1; else continue; /*(分配过后)系统是安全的,否