第一篇:银行家算法实验报告
计算机操作系统实验报告
何美西109253030212
一、实验名称:银行家算法
二、实验目的:银行家算法是避免死锁的一种重要方法,通过编写一个简单的银行家算法程序,加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。
三、问题分析与设计:
1、算法思路:先对用户提出的请求进行合法性检查,即检查请求是否大于需要的,是否大于可利用的。若请求合法,则进行预分配,对分配后的状态调用安全性算法进行检查。若安全,则分配;若不安全,则拒绝申请,恢复到原来的状态,拒绝申请。
2、银行家算法步骤:(1)如果Requesti<or =Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过它所宣布的最大值。
(2)如果Request<or=Available,则转向步骤(3);否则,表示系统中尚无足够的资源,进程必须等待。
(3)系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值:
Available=Available-Request[i];Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。
3、安全性算法步骤:
(1)设置两个向量
①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目,执行安全算法开始时,Work=Allocation;②布尔向量Finish。它表示系统是否有足够的资源分配给进程,使之运行完成,开始时先做Finish[i]=false,当有足够资源分配给进程时,令Finish[i]=true。
(2)从进程集合中找到一个能满足下述条件的进程:
①Finish[i]=false ②Need (3)当进程P获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行: Work=Work+Allocation;Finish[i]=true;转向步骤(2)。(4)如果所有进程的Finish[i]=true,则表示系统处于安全状态;否则,系统处于不安全状态。 4、流程图: 系统主要过程流程图 银行家算法流程图 安全性算法流程图 四、实验代码: #include int Allocation[100][100]={0};//系统已分配资源 int Need[100][100]={0};//还需要资源 int Request[100]={0};//请求资源向量 int temp[100]={0};//存放安全序列 int Work[100]={0};//存放系统可提供资源 int p[100]={0};int q[100][100]={0};int z[100][100]={0};int M=100;//作业的最大数为100 int N=100;//资源的最大数为100 int gg=1;void showdata()//显示资源矩阵 { int i,j;cout< int changdata(int i)//进行资源分配 { int j;for(j=0;j for(i=0;i cout< }//变分配数 Finish[i]=True;temp[k]=i;cout<<“ ”;cout<<“true”<<“ ”;cout< for(i=0;i Allocation[i][j]=Allocation[i][j]-Request[j];; Need[i][j]=Need[i][j]+Request[j]; } cout< return 0;} } cout< cout<<“安全序列为:”;for(i=0;i cout< { cout< { //出错 cout< int main()//主函数 { int t=1,i,j,number,choice,m,n,flag;char ming;cout<<“*****************银行家算法的设计与实现*****************”< showdata();//显示各种资源 safe();//用银行家算法判定系统是否安全 while(1){ if(t==1){ cout< t=0;} else break;cout< } return 1;} 五、程序执行结果: cin>>t;cout< 六、实验总结 多个进程同时运行时,系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列,使得系统能快速且安全地运行进程,不至发生死锁。银行家算法是避免死锁的主要方法,其思路在很多方面都非常值得我们来学习借鉴。 09信管(2)班 何美西 109253030212 计算机操作系统实验报告 一、实验名称:银行家算法 二、实验目的:银行家算法是避免死锁的一种重要方法,通过编写一个简单的银行家算法程序,加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。 三、问题分析与设计: 1、算法思路:先对用户提出的请求进行合法性检查,即检查请求是否大于需要的,是否大于可利用的。若请求合法,则进行预分配,对分配后的状态调用安全性算法进行检查。若安全,则分配;若不安全,则拒绝申请,恢复到原来的状态,拒绝申请。 2、银行家算法步骤:(1)如果Requesti<or =Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过它所宣布的最大值。 (2)如果Request<or=Available,则转向步骤(3);否则,表示系统中尚无足够的资源,进程必须等待。 (3)系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值: Available=Available-Request[i];Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。 3、安全性算法步骤: (1)设置两个向量 ①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目,执行安全算法开始时,Work=Allocation;②布尔向量Finish。它表示系统是否有足够的资源分配给进程,使之运行完成,开始时先做Finish[i]=false,当有足够资源分配给进程时,令Finish[i]=true。 (2)从进程集合中找到一个能满足下述条件的进程: ①Finish[i]=false ②Need (3)当进程P获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行: Work=Work+Allocation;Finish[i]=true;转向步骤(2)。 (4)如果所有进程的Finish[i]=true,则表示系统处于安全状态;否则,系统处于不安全状态。 4、流程图: 系统主要过程流程图 银行家算法流程图 安全性算法流程图 四、实验代码: //#define M 5 //#define N 3 #include void line()//美化程序,使程序运行时更加明朗美观 { printf(“-----------------n”);} void start()//表示银行家算法开始 { line();printf(“ 银行家算法开始n”);printf(“--死锁避免方法 line();} void end()//表示银行家算法结束 { line();printf(” 银行家算法结束,谢谢使用n“);line();} void input()//输入银行家算法起始各项数据 { for(n=0;n<5;n++) { printf(”请输入进程P%d的相关信息:n“,n); printf(”Max:“); for(m=0;m<1;m++) scanf(”%d“,&max[n][m]); printf(”Allocation:“); for(m=0;m<1;m++) scanf(”%d“,&allocation[n][m]); n”); } for(m=0;m<1;m++) need[n][m]=max[n][m]-allocation[n][m];printf(“请输入系统可利用资源数Available:”);for(m=0;m<1;m++) } void output()//输出系统现有资源情况 { line();printf(“资源情况 Max Allocation Need Availablen”);printf(“进程 A A A A n”);line();for(n=0;n<5;n++){ printf(“P%d%3d%3d%3d”,n,max[n][0],allocation[n][0],need[n][0]); } line();} void change()//当Request[i,j]<=Available[j]时,系统把资源分配给进程P[i],Available[j]和Need[i,j]发生改变 { for(m=0;m<1;m++){ if(n==0)else printf(“n”); printf(“%3d%3dn”,available[0]);scanf(“%d”,&available[m]); } } available[m]-=request[i][m];allocation[i][m]+=request[i][m];need[i][m]-=request[i][m];void outputsafe()//输出安全序列的资源分配表 { printf(“该安全序列的资源分配图如下:n”);line();printf(“资源情况 Work Need Allocation Work+Allocation Finishn”);printf(“进程 A A A A n”);line();for(n=0;n<5;n++) printf(“P%d%9d%3d%3d%5d%12sn”,safe[n],works[safe[n]][0],need[safe[n]][0],allocation[safe[n]][0],works[safe[n]][0]+allocation[safe[n]][0],finish[n]);line();} int check()//安全性算法 { printf(“开始执行安全性算法……n”);for(m=0;m<1;m++)//数组work和finish初始化 work[m]=available[m];for(n=0;n<5;n++){ } finish[n]=“false”;safe[n]=0;k=0;for(m=0;m<5;m++)for(n=0;n<5;n++) if(strcmp(finish[n],“false”)==0 && need[n][0]<=work[0])//查找可以分配资源但尚未分配到资源的进程 { safe[k]=n;//以数组safe[k]记下各个进程得到 分配的资源的顺序 works[safe[k]][0]=work[0]; 放出分配给它的资源 work[0]+=allocation[n][0];//进程执行后释 finish[n]=“ture”;//finish[n]变为1以示该进 程完成本次分 } k++;for(m=0;m<5;m++)//判断是否所有进程分配资源完成{ 0 素都为ture } else if(m==4)//此处m=4表示所有数组finish的所有元if(strcmp(finish[m],“false”)==0){ printf(“找不到安全序列,系统处于不安全状态。n”);return 0;//找不到安全序列,结束check函数,返回 { printf(“找到安全序列P%d->P%d->P%d->P%d->P%d,系统是安全的n”,safe[0],safe[1],safe[2],safe[3],safe[4]); } return 1;} void main()//主程序开始 { start();for(;j==0;)//确认输入数据的正确性,若输入错误,重新输入 { 入:“); } printf(”数据确认无误,算法继续。n“);if(check()==0)//若check函数返回值为0,表示输入的初始数据找不到安全序列,无法进行下一步,程序结束 { } for(;j==1;)//当有多个进程请求资源时,循环开始 { printf(”请输入请求资源的进程i(0、1、2、3、4):“);//输入发出请求向量的进程及请求向量 end();exit(0);input();printf(”以下为进程资源情况,请确认其是否正确:n“);output();printf(”数据是否无误:n正确:输入1n错误:输入0n请输 } j=1; outputsafe();//输出安全序列的资源分配表 scanf(“%d”,&j); scanf(“%d”,&i);printf(“请输入进程P%d的请求向量Request%d:”,i,i);for(n=0;n<1;n++) scanf(“%d”,&request[i][n]); for(;request[i][0]>need[i][0];)//若请求向量大于需求资源,则认为是输入错误,要求重新输入 { printf(“数据输入有误,请重试!n请输入进程P%d的请求向量Request%d:”,i,i); 提供分配 n“,i); } if(request[i][0]<=available[0])//判断系统是否有足够资源 for(n=0;n<1;n++) scanf(”%d“,&request[i][n]);{ } else printf(”系统没有足够的资源,进程P%d需要等待。printf(“系统正在为进程P%d分配资源……n”,i);change();//分配资源 j=0;if(j==0)//j=0表示系统有足够资源分配的情况 { printf(“当前系统资源情况如下:n”);//输出分配资源后的系统资源分配情况 分配无效 output(); if(check()==0)//若找不到安全系列,则之前的资源 { printf(“本次资源分配作废,恢复原来的资源分配 状态。n”); 资源状态 输入:“); for(m=0;m<1;m++)//恢复分配资源前的系统 } } { } output();//输出系统资源状态 available[m]+=request[i][m];allocation[i][m]-=request[i][m];need[i][m]+=request[i][m];printf(”是否还有进程请求资源?n是:输入1n否:输入0n请 scanf(“%d”,&j);//若还有进程请求资源,j=1,之前的for循环条件满足 } end();} 五、程序执行结果: 六、实验总结 多个进程同时运行时,系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列,使得系统能快速且安全地运行进程,不至发生死锁。银行家算法是避免死锁的主要方法,其思路在很多方面都非常值得我们来学习借鉴。 课程设计报告 课程设计名称 共享资源分配与银行家算法 系(部) 专业班级 姓 名 学 号 指导教师 年 月 日 、目 录 一、课程设计目的和意义...................................................................................3 二、方案设计及开发过程..............................................................................................3 1.课题设计背景.................................................................................................................3 2.算法描述 ............................................................................................................................3 3.数据结构 ............................................................................................................................4 4.主要函数说明.................................................................................................................4 5.算法流程图......................................................................................................................5 三、调试记录与分析 四、运行结果及说明 ..............................................................................................6 1.执行结果.........................................................................................................................6 2.结果分析.........................................................................................................................7 五、课程设计总结...................................................................................................8 、一、程设计目的和意义 计算机科学与技术专业学生学习完《计算机操作系统》课程后,进行的一次全面的综合训练,其目的在于加深催操作系统基础理论和基本知识的理解,加强学生的动手能力.银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序,进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施方法 二、方案设计及开发过程 1.课题设计背景 银行家算法又称“资源分配拒绝”法,其基本思想是,系统中的所有进程放入进程集合,在安全状态下系统受到进程的请求后试探性的把资源分配给他,现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较,找出剩余资源能满足最大需求量的进程,从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤,最后检查进程的集合为空时就表明本次申请可行,系统处于安全状态,可以实施本次分配,否则,只要进程集合非空,系统便处于不安全状态,本次不能分配给他。请进程等待 2.算法描述 1)如果Request[i] 是进程Pi的请求向量,如果Request[i,j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查: 如果Requesti[j]<= Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。 2)如果Requesti[j]<=Available[j],便转向步骤3,否则,表示尚无足够资源,进程Pi须等待。 3)系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值: Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j]; 、4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程pi等待。 3.数据结构 1.可利用资源向量AVAILABLE。这是一个含有M个元素的数组,其中的每一个元素代表一类可利用的资源数目,其3初始值是系统中所配置的该类全部可哦那个资源的数目,其数值随该类资源的分配和回收而动态的改变。 2.最大需求矩阵MAX。这是一个M*N的矩阵,它定义了系统中N个进程中的每一个进程对M类资源的最大需求。 3.分配矩阵ALLOCATION。这也是一个M*N的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。 4.需求矩阵NEED。这也是一个M*N的矩阵,用以表示每一个进程尚需的各类资源数。5.NEED[R,W]=MAX[R,W]-ALLOCATION[R,W] 4.主要函数说明 主要的常量变量 #define W 10 //最大进程数W=10 #define R 20 //最大资源总数R=20 int AVAILABLE[R];//可利用资源向量 int MAX[W][R];//最大需求矩阵 int ALLOCATION[W][R];//分配矩阵 int NEED[W][R];//需求矩阵 int Request[R];//进程请求向量 void changdata(int k);//进程请求资源数据改变 int chksec(int s);//系统安全性的检测 主要模块 void inputdata()void showdata()void changdata(int k)void restoredata(int k)int chksec(int s)int chkmax(int s) 、5.算法流程图 三、调试记录与分析 调试通过,程序未出错 、四、运行结果及说明 1.执行结果 、2.结果分析 银行家算法就是当接收到一个系统资源的分配后找到一个安全序列,使得进程间不会发生死锁,若发生死锁则让进程等待。 、五、课程设计总结 通过本次银行家算法实验,加深了我对银行家算法的了解,掌握了如何利用银行家算法避免死锁。实验中遇到点问题,通过查阅资料、询问老师顺利解决。通过这次的实践,使我的理论知识更加的牢固。 附录 程序源码: #include void changdata(int k);//进程请求资源数据改变 void restoredata(int k);//数据恢复 int chksec(int s);//系统安全性的检测 int chkmax(int s);//检测最大需求 void bank();//检测分配的资源是否合理 int main(){ int i,j;inputdata();//安全性算法 for(i=0;i 、cout<<“错误提示:经安全性检查发现,系统的初始状态不安全!!n”< { int i=0,j=0,p;cout<<“请输入总进程数:”< 、for(j=0;j do{ cin>>ALLOCATION[i][j]; if(ALLOCATION[i][j]>MAX[i][j]) cout< }while(ALLOCATION[i][j]>MAX[i][j]);} } cout< NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];for(j=0;j AVAILABLE[j]=0;} } } void showdata()//银行家算法 { int i,j;cout<<“各种资源的总数量,即向量all_resource为:”< cout< 、cout< cout< void changdata(int k)//进程请求资源数据改变 { int j;for(j=0;j AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j];} } void restoredata(int k)//数据恢复 { int j;for(j=0;j ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j];} } int chksec(int s)//系统安全性的检测 { int WORK,FINISH[W];int i,j,k=0;for(i=0;i FINISH[i]=FALSE;for(j=0;j WORK=AVAILABLE[j]; 、i=s;do { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) { WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; i=0; }else { i++; } }while(i if(FINISH[i]==FALSE) { return 1; } } return 0;} int chkmax(int s)//检测最大需求 { int j,flag=0;for(j=0;j if(MAX[s][j]==ALLOCATION[s][j]) { flag=1; AVAILABLE[j]=AVAILABLE[j]+MAX[s][j]; MAX[s][j]=0; } } return flag;} void bank(){ int i=0,j=0;char flag='Y';while(flag=='Y'||flag=='y'){ i=-1;while(i<0||i>=M){ cout<<“请输入需申请资源的进程号(从P0到P”< cin>>i;if(i<0||i>=M) 、cout<<“输入的进程号不存在,重新输入!”< cin>>Request[j];if(Request[j]>NEED[i][j]) { cout<<“进程P”< cout<<“申请不合理,出错!请重新选择!”< flag='N'; break; } else { if(Request[j]>AVAILABLE[j]) { cout<<“进程P”< cout<<“申请不合理,出错!请重新选择!”< flag='N'; break; } } } if(flag=='Y'||flag=='y'){ changdata(i); if(chksec(i)) { cout< cout<<“该分配会导致系统不安全!!本次资源申请不成功,不予分配!!”< cout< restoredata(i); } else { cout< cout<<“经安全性检查,系统安全,本次分配成功,且资源分配状况如下所示:”< cout< showdata(); if(chkmax(i)) {cout<<“在资源分配成功之后,由于该进程所需的某些资源的最大需求量已经满足,”< cout<<“因此在进程结束后系统将回收这些资源!”< showdata(); 、} } } cout< 实验四 死锁 一、实验目的 当系统的总资源数m小于或等于所有进程对对资源的最大需求时,就可能产生 死锁。死锁会引起计算机系统的瘫痪。银行家算法是在实现资源分配时避免死锁的一个著名算法,该算法是在能确保系统处于安全状态时才把资源分配给申请者。通过本实验使学生能进一步理解死锁的概念,并能选择一个算法来避免死锁。 二、实验题目 系统中有m个同类资源被n个进程共享,每个进程对资源的最大需求数分别为S1, S2,…,Sn,且 Max(Si)<=m,(i=1,2,…n)。进程可以动态地申请资源和释放资源。编写一个程序,现银行家算法,当系统将资源分配给某一进程而不会死锁时,就分配之。否则,推迟分配,并显示适当的信息。 三、数据结构 主要数据结构: Struct aa { void Print();//用于打印输出表格的函数 void Input();//用于输入的函数 void tryfenpei(int i);//试分配函数 void refenpei(int i);//恢复数据函数 void checksafe(int s);//安全检测函数 }; 四、银行家算法的流程图 开始初始化资源类数c=3,进程数t=5初始化Available[c],Max[t][c],Allocation[t][c],Need[t][c],Request[c]输入进程数iInt f=0f 五、源代码 #include void Print();//用于打印输出表格的函数 void Input();//用于输入的函数 void tryfenpei(int i);//试分配函数 void refenpei(int i);//恢复数据函数 void checksafe(int s);//安全检测函数 //定义初始化数组 int Available[c], Max[t][c], Allocation[t][c], Need[t][c], Request[c]; int in;//用户选择的进程号 int main(int argc, char *argv[]){ int i;char ch='Y';cout<<“初始化数据如下:”< cout<<“试分配完成!”< cout<<“需要继续实验吗?(y-继续 n终止)”;} else if(ch=='N'||ch=='n'){ cout<<“感谢您的使用,祝您愉快!”< void Print(){ int i,j;cout<<“ 进程个数 : ”< void Input(){ for(int j=0;j { for(int m=0;m void tryfenpei(int i){ for(int f=0;f //安全检测函数 void checksafe(int s){ int Work, flag, temp[t], i,j,l=0,k=0;bool Finish[t];for(i=0;i } if(l==5)//一共有三类资源A B C,一条进程下面的安全性检测只检测了A类。如果A类通过了,那么还要判断B类,C类。否则不用 { for(i=0;i } i=s;//s传递进来赋给i,s是用户输入的进程号(有主函数里的in传递进来)while(i if(Finish[i]==false&&Need[i][j]<=Work){ Work=Work+Allocation[i][j];Finish[i]=true;temp[k]=i;//cout<<“temp=”< 六、执行结果: 七、实验总结 通过本次实验了解到用银行家算法来预防死锁是可靠的,但也是非常保守的,因为它限制了进程对资源的存取,从而降低了进程的并发运行程度。死锁检测并不限制进程对资源的申请,只要有,就分配,但这也可能造成死锁。但由于死锁并不是经常发生的,故大大提高了系统运行的效率。 总之,通过本实验,使我进一步加深理解和掌握银行家算法。 实验三 银行家算法 (1)死锁产生的原因和必要条件是什么? 原因: a)系统资源不足; b)进程运行推进的顺序不合适; c)资源分配不当。 如果系统资源充足,进程的资源请求都能够得到满足,死锁出现的可能性就很低,否则就会因争夺战、有限的资源而陷入死锁。其次,进程运行推进顺序与速度不同,也可能产生死锁。 必要条件: a)互斥条件:一个资源每次只能被一个进程使用; b)请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放; c)不剥夺条件:进程已获得的资源,在未使用完之前,不能强行剥夺; d)循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。 (2)银行家算法中的安全性检查时,Work[j]+Allocation[i,j]的含义是什么? work[j]表示当前系统可用的第j类资源,Allocation[i][j]表示当前已经分配给进程i使用的第j类资源数量。Work[j]= Work[j]+ Allocation[i,j]这句的意思是目前进程已经利用手上资源完成相关工作了,这些已分配的资源可以重新归还系统了,所以系统可用的第j类资源work[j]就增加了,增加量就是当前进程想要归还的资源量Allocation[i][j]。 (3)为什么银行家算法能有效避免死锁的发生?算法的主要思想是什么? 操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源,若能满足则按当前的申请量分配资源,否则也要推迟分配。 银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。 (4)补全Bank()和Safe()函数; void Bank()//银行家算法 { int q;bool flag = true;printf(“请输入请求的进程向量n”);scanf(“%d”,&q);printf(“请输入%d个资源的请求资源数n”,n);for(int i=0;i int Safe()//安全性算法 { //返回1表示安全,返回0表示不安全 int tp=1;int i;int Work[20];int tmp=0,t=0;for(i=0;i for(i=0;i for(i=0;i (5)给出程序运行截图。第二篇:银行家算法实验报告
第三篇:银行家算法_实验报告
第四篇:操作系统银行家算法实验报告
第五篇:银行家算法实验报告