操作系统课程设计银行家算法模拟实现

1、操作系统课程设计 操作系统原理 课程设计 课设名称： 银行家算法模拟实现 姓 名： 郝碧涛 班 级： 13软件3班 学 号： 1310321308 指导教师： 万方 一设计题目 银行家算法模拟实现二主要内容设计目的1、 了解多道程序系统中，多个进程并发执行的资源分配。2、 掌握思索的产生原因、产生死锁的必要条件和处理死锁的基本方法。3、 掌握预防死锁的方法，系统安全状态的基本概念。4、 掌握银行家算法，了解资源在进程并发执行中的资源分配策略。5、 理解死锁避免在当前计算机系统不常使用的原因。3 银行家算法的概念 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源

2、，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 安全序列是指一个进程序列P1，Pn是安全的，即对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。4 银行家算法原理及思想 在银行家算法中，为了决定是否对挡墙申请资源的进程进行资源分配，将系统状态划分为安全状态与不安全状态。若为当前申请资源的进程分配资源后系统进入安全状态，则接受进程请求为其分配资源，否则

3、拒绝进程请求，不为其分配资源。（安全状态：从当前时刻起，若系统能按某种进程顺序（p1,p2.pn)逐个分配所需全部剩余资源，使各个进程依次运行完毕，则称此时刻系统处于安全状态，上述进程序列称为安全序列。否则系统处于不安全状态） 注：前提是假设从当前时刻起，进程一次性申请全部剩余资源，而且一直保持当时已经占有的资源直至运行完毕。5 解决的问题 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但银行家算法在系统在进行资源分配之前(并不是真的不分配，这样就没法做了，只不过是试探性分配，不满足的话再恢复)，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状

4、态，则分配，否则等待。六、程序设计1.需求分析1、始化这组进程的最大资源请求和一次申请的资源序列。把各进程已占用和需求资源情况记录在进程控制块中。假定进程控制块的内容包括：进程名，状态，当前申请量，资源需求总量，已占资源量，能执行完标志。其中，进程的状态有：就绪，等待和完成。当系统不能满足进程的资源请求时，进程出于等待状态。资源需求总量表示进程运行过程中对资源的总的需求量。已占资源量表示进程目前已经得到但还为归还的资源量。因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。陷入每个进程的资源需求总量不应超过系统拥有的资源总量。2、银行家算法分配资源的原则是：当某个进程提出资源请求

5、时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。A) 查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程，如果能，则转B）。B）将资源分配给所选的进程，这样，该进程已获得资源最大请求，最终能运行完成。标记这个进程为终止进程，并将其占有的全部资源归还给系统。重复第A)步和B)步，直到所有进程都标记为终止进程，或知道一个死锁发生。若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。2.概要设计2.1设

6、计思想当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。若能，则让进程等待，否则，让进程的假分配变为真分配。2.2数据结构假设有m个进程，则有如下数据结构:#define w 50 /宏定义#define r 50 /宏定义int m; /总进程数 int allw;/各种资源的数目总和int maxwr; /m个进程最大资源需求量int availabler; /系统可用资源数int allocationwr; /m个进程已经得到资源的资源量int needwr; /m个进程还需要资源的资源量int requestr

7、; /请求资源个数开始输入进程数m，各资源总数，初始化Available向量i=1i<=m输入进程i的最大需求向量max。max<=资源总数i+YNNY错误初始化need任选一个进程作为当前进程（0到m-1）该进程的Need向量为0输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或并给出提示NY该进程已运行结束Need矩阵为0Y结束3.详细设计3.1算法思想银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。否则拒绝分配。3.2银行家算法设Requestn，是进程的请求向量，如果Requestn=m，则表示该进程需要m个资源。当该进

8、程发出资源请求后，系统按下述步骤进行检查：(1)如果Requestn=Needi，n，便转向步骤（2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。 (2)如果Requestn>Available，则进程i进入等待资源状态，返回。 (3)假设进程i的申请已获批准，于是修改下面数据结构中的数值： Available=Available-Request Allocation=Allocation+RequestNeed=Need-Request (4)系统执行安全性检查，如安全，则分配成立；否则恢复原来的资源分配状态，系统恢复原状，进程等待。 程序void bank() /银

9、行家算法 int i=0,j=0; char flag='Y' while(flag='Y'|flag='y') i=-1; while(i<0|i>=m) cout<<" 请输入需申请资源的进程号（从0到"<<m-1<<"）:" cin>>i; if(i<0|i>=m)cout<<" 该进程号不存在，请重新输入!"<<endl; cout<<" 请输入进程"&

10、lt;<i<<"申请的资源数:" for (j=0;j<1;j+) cout<<" " cin>>requestj; if(requestj>needij) /若请求的资源数大于进程还需要i类资源的资源量j cout<<" 进程"<<i<<"申请的资源数大于进程"<<i<<"还需要资源的资源量!" cout<<"申请不合理，请重新选择!"<<

11、;endl<<endl; flag='1' break; else if(requestj>availablej) /若请求的资源数大于可用资源数 cout<<" 进程"<<i<<"申请的资源数大于系统可用资源的资源量!" cout<<"申请不合理!请重新选择!"<<endl<<endl; flag='1' break; if(flag='Y'|flag='y') change(i)

12、; /调用change(i)函数，改变资源数 if(chkerr(i) /若系统安全 rstore(i); /调用rstore(i)函数，恢复资源数 show(); /输出资源分配情况 else /若系统不安全 show(); /输出资源分配情况 else /若flag=N|flag=n show(); cout<<endl; cout<<" 是否继续(Y/N): " cin>>flag; 3.3安全性检查算法(1)设置两个工作向量Work=Available；FinishM=False(2)从进程集合中找到一个满足下述条件的进程， Fi

13、nish i=False Need<=Work 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work=Work+Allocation Finish=True GO TO 2 (4)如所有的进程FinishM=true，则表示安全；否则系统不安全。程序int chkerr(int s) /检查安全性 int work,FInISHw; int i,j,k=0; for(i=0;i<m;i+)FInISHi=false; for(j=0;j<1;j+) work=availablej; i=s; do if(FInISHi=f

14、alse&&needij<=work)work=work+allocationij; FInISHi=true; i=0; else i+; while(i<m); for(i=0;i<m;i+) if(FInISHi=false) cout<<endl; cout<<" 系统不安全! 本次资源申请不成功!"<<endl; cout<<endl; return 1; cout<<endl; cout<<" 系统安全，分配成功。"<<end

15、l; cout<<endl; return 0; 3.4 修改数据结构中的数值改变可用资源和已经拿到资源和还需要的资源的值void change(int k) int j; for (j=0;j<1;j+) availablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj; 3.5 如果分配失败，则恢复原来的资源分配状态恢复可用资源和已经拿到资源和还需要的资源的值void rstore(int k) int j; availablej=availablej+re

16、questj; allocationkj=allocationkj-requestj; needkj=needkj+requestj; 3.6 输出显示实现人机交互的各类资源输出显示情况。void show() /输出资源分配情况 int i,j; cout<<"资源总量:"<<" " for (j=0;j<1;j+)cout<<" "<<allj; cout<<endl<<endl; cout<<"系统目前资源可用数:"&l

17、t;<" " for (j=0;j<1;j+)cout<<" "<<availablej; cout<<endl<<endl; cout<<"进程名 各进程还需要的资源量"<<endl; for (i=0;i<m;i+) for (i=0;i<m;i+) cout<<"进程"<<i<<": " for (j=0;j<1;j+)cout<<needi

18、j<<" " cout<<endl; cout<<endl; cout<<"进程名 各进程已经得到的资源量"<<endl; for (i=0;i<m;i+) cout<<"进程"<<i<<": " for (j=0;j<1;j+)cout<<allocationij<<" " cout<<endl; cout<<endl; void chan

19、ge(int k) /改变可用资源和已经拿到资源和还需要的资源的值 int j; for (j=0;j<1;j+) availablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj; 3.7 主函数void main() /主函数 int i=0,j=0,p; cout<<"-银行家算法模拟-"<<endl; cout<<"请输入总进程数:" cin>>m; cout<<&q

20、uot;请输入总资源数:" for(i=0;i<1;i+) cin>>alli; cout<<"依次输入各进程所需要的最大资源数量:"<<endl; for (i=0;i<m;i+) for (j=0;j<1;j+) do cin>>maxij; if (maxij>allj) cout<<endl<<"占有资源超过了声明的该资源总数,请重新输入"<<endl; while (maxij>allj); cout<<&qu

21、ot;依次输入各进程已经占据的资源数量:"<<endl;for (i=0;i<m;i+) for (j=0;j<1;j+) do cin>>allocationij; if (allocationij>maxij) cout<<endl<<"占有资源超过了声明的最大资源,请重新输入"<<endl; while (allocationij>maxij); /初始化资源数量 for (j=0;j<1;j+) p=allj; for (i=0;i<m;i+) p=p-allocationij;/减去已经被占据的资源 availablej=p; if(availablej<0) availablej=0; for (i=0;i<m;i+) for(j=0;j<1;j+) needij=maxij-allocationij; show(); bank();3.8 定义全局变量#include "string.h" #include "iostream"using namespace std;#define