2024年银行家算法实验报告完整版

操作系统试验报告课题：银行家算法专业：班级：学号：姓名：年月日目录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时刻所得成果:（3）T0时刻的安全序列（4）不合理的分派输入P1进程Request（221）与输入P2进程Request（222）所得祈求成果：（5）合理的分派1.存在安全序列：调用Request（）函数，测试该函数的可行性，如输入P1进程Request（012），所得成果：2、不存在安全序列输入P0进程Request（020），所得成果:七、心得体会本次试验让我对银行家算法和死锁都有了一定的了解。懂得了在资源一定的条件下为了让多个进程都能使用资源完成任务，防止死锁的产生能够从一开始就对系统进行安全性检查来判断是否将资源分派给正在祈求的进程。不过银行家算法会加大系统的开销。另外，存在如下疑问，在系统不分派进程所祈求的资源的时候，是否会将此资源等候，直到拥有足够的资源的时候再来运行？进程会祈求资源是指在执行的过程中只有拥有了足够数量的资源才能够执行下去，不过资源有限，进程数又有足够多，我们期望所有进程都能够在最短的时间内执行完。也许能够这么了解。操作系统的基本特性就是并发和共享，系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大程度的利用计算机资源，操作系统应采取动态分派的方略，不过这么就轻易因资源不足、分派不当而引起“死锁”。本次课程设计就是用银行家算法来防止“死锁”。该算法就是一个资源分派过程，使分派序列不会产生死锁。此算法的中心思想就是，每次分派后总存在着一个进程，假如让它单独的运行下去，必然能够取得它所需要的所有资源，而它结束后能够偿还此类资源以满足其他申请者的需要。另外，我懂得了在程序进行编写之前，先对程序的要求进行分析，搞清楚程序所需要的功效，然后将每个功效提成一个功效模块即调用函数来实现，无需过多的画蛇添足。参考资料【1】《计算机操作系统》（第三版）汤小丹、梁红兵、汤子瀛、哲凤屏等西安电子科技大学出版社-05

【2】《C++Primer中文版》（第4版）（美）StanleyB.Lippman

等著

李师贤等译.人民邮电出版社,-03-01【3】《C++Primer习题解答》（第4版）蒋爱军，李师贤，梅晓勇

著人民邮电出版社-02-01【4】《当代操作系统》（原书第3版）塔嫩鲍姆（Tanenbaum.A.S），陈向群，马洪兵

著机械工业出版社-07-01【5】《计算机操作系统教程》张尧学，史美林，张高清华大学出版社-10-01【6】《数据结构（STL框架）》王晓东

著清华大学出版社-09-01【7】《计算机操作系统（第三版）》汤子瀛等西安电子科技大学出版社-05【8】《操作系统试验教程——基于windows和Linux》秦明等\o"清华大学"清华大学出版社-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; } for(intj=0;j<N;j++) { Available[j]-=Request[j]; Allocation[rq][j]+=Request[j]; Need[rq][j]-=Request[