银行家算法实验报告13551

./操作系统实验报告课题：银行家算法专业：班级：学号：姓名：年月日目录HYPERLINK一实验目的……………………3HYPERLINK二实验容………3HYPERLINK三问题描述……………………3HYPERLINK四设计思路………4HYPERLINK五详细设计……………………5HYPERLINK六运行结果…………………10HYPERLINK七心得体会……………………16HYPERLINK八参考文献………17HYPERLINK附源程序………17一、实验目的模拟实现银行家算法,用银行家算法实现资源分配。1．加深了解有关资源申请、避免死锁等概念。2．体会和了解死锁和避免死锁的具体实施方法。3、输入：1.系统中各类资源表2.每个进程需要各类资源总数系统分配给各个进程各类资源数4、输出：1.判断T0时刻的安全性2.如果系统是安全的,任意给出某个进程的一个资源请求方式并判断系统能否接受此请求,如果可以接受,其输出全部安全序列,反之,不予分配。二、实验容1．设计进程对各类资源最大申请表示及初值的确定。2．设定系统提供资源的初始状况。3．设定每次某个进程对各类资源的申请表示。4．编制程序,依据银行家算法,决定其资源申请是否得到满足。5．显示资源申请和分配时的变化情况。三、问题描述银行家算法.顾名思义是来源于银行的借贷业务,一定数量的本金要应多个客户的借贷周转,为了防止银行加资金无法周转而倒闭,对每一笔贷款,必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题,系统中有限的资源要供多个进程使用,必须保证得到的资源的进程能在有限的时间归还资源,以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源,则进程都无法继续执行下去的死锁现象。在死锁的避免中,银行家算法把系统状态分为安全状态和不安全状态,只要能使系统始终处于安全状态,便可以避免发生死锁。所谓安全状态,是指系统能按某种顺序为每个进程分配所需资源,直到最大需求,使每一个进程都可以顺利完成,即可找到一个安全资源分配序列。模拟实现这个工作过程。四、设计思路我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。银行家算法是一种最具代表性的避免死锁的算法。要解释银行家算法,必须先解释操作系统的安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1,…,Pn,则系统处于安全状态。安全状态一定没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。安全序列：一个进程序列{P1,…,Pn}是安全的,如果对于每个进程Pi〔0≤i≤n,它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj〔j＜i当前占有资源量之和。先对系统从源文件中读取的数据进行安全性判断,然后对用户提出的请求进行合法性检查,即检查请求的是不大于需要的,不大于系统可利用的资源。若请求合法,则进行试分配,最后对试分配状态调用安全性算法进行安全性检查。若安全,则分配,否则,不分配,恢复原来状态,拒绝申请。五、详细设计1、初始化由用户输入数据,分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。2、银行家算法在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。设进程cusneed提出请求REQUEST[i],则银行家算法按如下规则进行判断。<1>如果REQUEST[cusneed][i]<=NEED[cusneed][i],则转<2>；否则,出错。<2>如果REQUEST[cusneed][i]<=AVAILABLE[cusneed][i],则转<3>；否则,出错。<3>系统试探分配资源,修改相关数据：AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];<4>系统执行安全性检查,如安全,则分配成立；否则试探险性分配作废,系统恢复原状,进程等待。<5>对于某一进程i,若对所有的j,有NEED[i][j]=0,则表此进程资源分配完毕,应将占用资源释放。3、安全性检查算法<1>设置两个工作向量Work=AVAILABLE;FINISH<2>从进程集合中找到一个满足下述条件的进程,FINISH==false;NEED<=Work;如找到,执行<3>；否则,执行<4><3>设进程获得资源,可顺利执行,直至完成,从而释放资源。Work+=ALLOCATION;Finish=true;GOTO2<4>如所有的进程Finish=true,则表示安全；否则系统不安全。4、流程图1、整体流程图开始开始录入请求资源数REQUEST[i]>NEED[i]或者REQUEST[i]>AVAILABLE[i]报错,重新输入AVAILABLE[i]-=REQUEST[i];

ALLOCATION[i]+=REQUEST[i];

NEED[i]-=REQUEST[i];初始化安全性检查安全AVAILABLE[i]+=REQUEST[i];

ALLOCATION[i]-=REQUEST[i];

NEED[i]+=REQUEST[i];保持原分配进程执行完释放资源继续分配结束YESNOYESNOYESYESNONO2、判断系统的安全性Safe〔六、运行结果1、系统不安全的输入〔1、本程序按下图建立.txt源文件,作为程序的初始化输入〔2执行程序,读取源文件,并判断T0时刻所得结果:2.系统安全的输入〔1、本程序按下图建立.txt源文件,作为程序的初始化输入〔2执行程序,读取源文件,并判断T0时刻所得结果:〔3T0时刻的安全序列〔4不合理的分配输入P1进程Request〔221与输入P2进程Request〔222所得请求结果：〔5合理的分配1.存在安全序列：调用Request〔函数,测试该函数的可行性,如输入P1进程Request〔012,所得结果：2、不存在安全序列输入P0进程Request〔020,所得结果:七、心得体会本次实验让我对银行家算法和死锁都有了一定的理解。知道了在资源一定的条件下为了让多个进程都能使用资源完成任务,避免死锁的产生可以从一开始就对系统进行安全性检查来判断是否将资源分配给正在请求的进程。但是银行家算法会加大系统的开销。此外,存在以下疑问,在系统不分配进程所请求的资源的时候,是否会将此资源等待,直到拥有足够的资源的时候再来运行？进程会请求资源是指在执行的过程中只有拥有了足够数量的资源才可以执行下去,但是资源有限,进程数又有足够多,我们期望所有进程都可以在最短的时间执行完。也许可以这样理解。操作系统的基本特征就是并发和共享,系统允许多个进程并发执行,并且共享系统的软、硬件资源。为了最大限度的利用计算机资源,操作系统应采用动态分配的策略,但是这样就容易因资源不足、分配不当而引起"死锁"。本次课程设计就是用银行家算法来避免"死锁"。该算法就是一个资源分配过程,使分配序列不会产生死锁。此算法的中心思想就是,每次分配后总存在着一个进程,如果让它单独的运行下去,必然可以获得它所需要的全部资源,而它结束后可以归还这类资源以满足其他申请者的需要。另外,我知道了在程序进行编写之前,先对程序的要求进行分析,弄清楚程序所需要的功能,然后将每个功能分成一个功能模块即调用函数来实现,无需过多的画蛇添足。参考资料[1]《计算机操作系统》〔第三版汤小丹、梁红兵、汤子瀛、哲凤屏等电子科技大学2007-05[2]《C++Primer中文版》〔第4版〔美StanleyB.Lippman

等著师贤等译.人民邮电,2006-03-01[3]《C++Primer习题解答》〔第4版爱军,师贤,梅晓勇著人民邮电2007-02-01[4]《现代操作系统》〔原书第3版塔嫩鲍姆〔,向群,马洪兵著机械工业2009-07-01[5]《计算机操作系统教程》尧学,史美林,高清华大学2006-10-01[6]《数据结构〔STL框架》王晓东著清华大学2009-09-01[7]《计算机操作系统〔第三版》汤子瀛等电子科技大学2007-05[8]《操作系统实验教程——基于windows和Linux》明等清华大学2010-09-01附：源程序#include<fstream.h>#include<stdio.h>#include<stdlib.h>#defineM10//最大进程数#defineN3//系统所拥有的资源类型intMax[M][N];//进程对各类资源的最大需求intAllocation[M][N];//系统已为进程所分配的各类资源数intNeed[M][N];//运行进程尚需的各类资源数intWork[N];//运行进程时系统所拥有的资源数boolfinish[M];//表示系统是否有足够的资源分配给进程intAvailable[N];//系统可利用的资源数intn_pro=0;//进程的数目intflag[M]={-1};//用于标记安全序列intReadfile<>;//从磁盘读文件intSafe1<intflag[],intn,intt>;//输出所有安全状态voidshow<>;intSafe<>;//判断系统是否处于安全状态intRequest<>;//请求资源分配函数voidshow<>{ printf<"\t%-9s\t%-9s\t%-9s\n","MAX","Allocation","Need">;printf<"\tABC\tABC\tABC\n">;for<inti=0;i<n_pro;i++> { printf<"p%d\t%d%4d%4d\t",i,Max[i][0],Max[i][1],Max[i][2]>; printf<"%d%4d%4d\t",Allocation[i][0],Allocation[i][1],Allocation[i][2]>; printf<"%d%4d%4d\n",Need[i][0],Need[i][1],Need[i][2]>; } printf<"系统可利用资源数:\n">; printf<"\tA\tB\tC\n">; printf<"\t%d\t%d\t%d\n",Available[0],Available[1],Available[2]>;}intReadfile<>//从磁盘读文件{ inti=0,j=0;//i表进程,j表资源 ifstreaminFile;//文件 inFile.open<"test.txt">;//打开输入文件,按照规定的格式提取线程等信息 for<j=0;j<N;j++> inFile>>Available[j]; inFile.get<>; printf<"系统最大资源数:\n">; printf<"\tA\tB\tC\n">; printf<"\t%d\t%d\t%d\n",Available[0],Available[1],Available[2]>; inFile>>n_pro; inFile.get<>; printf<"当前进程的数目:%d\n",n_pro>; while<i<n_pro>//提取进程的相关资源信息 { for<j=0;j<N;j++> inFile>>Max[i][j]; for<j=0;j<N;j++> inFile>>Allocation[i][j]; for<j=0;j<N;j++> { Need[i][j]=Max[i][j]-Allocation[i][j]; Available[j]-=Allocation[i][j]; } i++; } for<j=0;j<N;j++> Work[j]=Available[j]; printf<"显示初始化资源分配表:\n">; show<>; printf<"\n">; return0;}intSafe<>//判断系统是否是安全的{ inttempn=n_pro; inti=0,j=0,t=0; for<i=0;i<n_pro;i++> finish[i]=false; while<tempn> { for<i=0;i<n_pro;i++> { if<!finish[i]> { inttp=0;//注释部分用于调试程序// printf<"%d\t%d%4d%4d\t",i,Work[0],Work[1],Work[2]>;// printf<"%d%4d%4d\n",Need[i][0],Need[i][1],Need[i][2]>; tp=<Work[0]>=Need[i][0]>&&<Work[1]>=Need[i][1]>&&<Work[2]>=Need[i][2]>; if<tp> { finish[i]=true; for<intj=0;j<N;j++> Work[j]+=Allocation[i][j]; flag[t]=i;// printf<"%d\tflag[%d]=%d",i,t,flag[t]>;system<"pause">;printf<"\n">;t++; break; } } } tempn--; } for<i=0;i<n_pro;i++> if<finish[i]==false>{printf<"系统不安全,不存在安全序列\n">;return-1;} printf<"系统是安全的,存在安全序列:\n">; for<j=0;j<N;j++> Work[j]=Available[j]; Safe1<flag,n_pro,0>; printf<"\n">; return0;}intSafe1<intflag[],intn,intt>{ intp,i,j,k;//p为标记 inttemp[N];//临时数组 for<i=0;i<n;i++> { inttp=0; tp=<Work[0]>=Need[i][0]>&&<Work[1]>=Need[i][1]>&&<Work[2]>=Need[i][2]>; if<tp> { for<j=0;j<N;j++> Work[j]+=Allocation[i][j]; flag[t]=i; p=1; } elsecontinue; for<intj=0;j<t;j++> if<flag[t]==flag[j]> { for<j=0;j<N;j++> Work[j]-=Allocation[i][j]; p=0;break; } if<p==1> { if<t==n-1> { for<k=0;k<n;k++> printf<"p%-5d",flag[k]>; printf<"\n">; } else { for<k=0;k<N;k++> temp[k]=Work[k]-Allocation[i][k]; Safe1<flag,n,t+1>; for<k=0;k<N;k++> Work[k]=temp[k]; } } } return0;}intRequest<>//进程提出请求后,判断系统能否将资源分配给它{ intrq;//下标 intRequest[N]; printf<"请输入需要请求的进程号<0~4>:">; scanf<"%d",&rq>; printf<"请输入需要请求的资源数<ABC>:">; scanf<"%d%d%d",&Request[0],&Request[1],&Request[2]>; if<Need[rq][0]<Request[0]||Need[rq][1]<Request[1]||Need[rq][2]<Request[2]> { printf<"进程p%d申请的资源大于它所需要的资源\n分配不合理,不予分配\n\n",rq>; return-1; } if<Available[0]<Request[0]||Available[1]<Request[1]||Available[2]<Request[2]> { printf<"进程p%d申请的资源大于系统现在可利用的资源\n分配不合理,不予分配\n\n",rq>; return-1; } fo