操作系统实习报告

操作系统原理实习报告实习一银行家算法实习二多级队列调度算法学院：姓名：学号：班级：指导教师：实习一银行家算法【问题描述】1、概念安全状态：系统按照某种序列为多个进程分配资源直到最大需求，如果能够保证所有进程全部顺利执行完毕，则称系统是安全的。2、采取的数据结构（1）可利用资源量Available（2）最大需求矩阵Max（3）分配矩阵Allocation[i]（4）需求矩阵Need[i]（5）请求矩阵Request[i]3、银行家算法设request：是Pi进程的请求向量，当Pi发了资源请求后，系统按下述步骤检查：（1）如果Request[i]=Need[i]，则转向步骤（2）；（2）若Request[i]=Available，则转向步骤（3）；（3）系统试探性地把要求的资源分配给进程Pi，并修改以下数据结构的值：Available=Available-Request[i]；Allocation[i]=Allocation[i]+Request[i]；Need[i]=Need[i]-Request[i]；（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给Pi进程，完成本次分配；否则，试探性分配作废，恢复原来的资源分配状态，Pi进程进入等待状态。4、安全性算法（1）设置两个向量：工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时，work初值=Available；finish表示系统是否有足够的资源分配给里程，使之运行完成，开始时，finish[i]=false；当有足够资源分配给进程时，令finish[i]=true；（2）从进程集合中找到满足下述条件的进程：finish[i]=false；Need[i]=work；若找到执行（3），否则执行（4）；（3）当进程Pi获得资源后，顺序执行直到完成，并释放它的资源，执行：work=work+Allocation[i]；finish[i]=true；gotostep(2);（4）若所有进程的finish[i]=true，则系统处于安全状态，否则，处于不安全状态。【测试数据】a.进程P2请求资源（0，3，4）b进程P4请求资源（1，0，1）c.进程P1请求资源（2，0，1）d.进程P3请求资源（0，0，2）【实现提示】(1)将各部分设计成子函数，然后调用，可以使结构清晰。(2)将向量和矩阵存储在一维数组和二维数组中。一、需求分析1.将向量和矩阵存储在一维数组和二维数组中。2.用户输入数据，并且可以决定测试的数据数量。3.安全性算法可以决定拟分配是否实行。4.要求测试四组数据。二、设计1.设计思想1.银行家算法（1）存储结构：用数组来存储向量和矩阵。（2）主要算法基本思想：设request：是Pi进程的请求向量，当Pi发了资源请求后，系统按下述步骤检查：（1）如果Request[i]=Need[i]，则转向步骤（2）；（2）若Request[i]=Available，则转向步骤（3）；（3）系统试探性地把要求的资源分配给进程Pi，并修改以下数据结构的值：Available=Available-Request[i]；Allocation[i]=Allocation[i]+Request[i]；Need[i]=Need[i]-Request[i]；（4）系统执行安全性算法，设置两个向量：工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时，work初值=Available；finish表示系统是否有足够的资源分配给里程，使之运行完成，开始时，finish[i]=false；当有足够资源分配给进程时，令finish[i]=true；从进程集合中找到满足下述条件的进程：finish[i]=false；Need[i]=work；若找到执行（5），否则执行（6）；（5）当进程Pi获得资源后，顺序执行直到完成，并释放它的资源，执行：work=work+Allocation[i]；finish[i]=true；gotostep(6);（6）若所有进程的finish[i]=true，则系统处于安全状态，否则，处于不安全状态。检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给Pi进程，完成本次分配；否则，试探性分配作废，恢复原来的资源分配状态，Pi进程进入等待状态。2、安全性算法（1）设置两个向量：工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时，work初值=Available；finish表示系统是否有足够的资源分配给里程，使之运行完成，开始时，finish[i]=false；当有足够资源分配给进程时，令finish[i]=true；（2）从进程集合中找到满足下述条件的进程：finish[i]=false；Need[i]=work；若找到执行（3），否则执行（4）；（3）当进程Pi获得资源后，顺序执行直到完成，并释放它的资源，执行：work=work+Allocation[i]；finish[i]=true；gotostep(2);（4）若所有进程的finish[i]=true，则系统处于安全状态，否则，处于不安全状态。2.设计表示（1）函数调用关系图main-Bijiaomain-safe（2）函数接口规格说明intBijiao(inti)/*比较请求与需求矩阵*/intsafe(inth)/*安全性算法*/3.实现注释（1）根据输入的进程号和所申请的资源数来对向量进行比较；（2）符合要求则进行拟分配，否则输出进程阻塞；（3）进行安全性算法检测，不安全则撤销分配，否则实行分配；4.详细设计#definen5//进程个数#definem3//资源种类intAvailable[m],Alloc[n][m],Need[n][m];main(){intrequest[m];input();while(1){read_req();if(请求结束)break;(1)if(!(requesti=Needi))表示非法请求；(2)if(!(requesti=Availablei))则Pi阻塞；(3)试探性分配Available=Available-Requesti;Alloci=Alloci+Requesti;Needi=Needi-Requesti;(4)若新状态安全，则实际分配资源给Pi,否则取消试探性分配。}}安全状态判别算法：(1)设置Finish=(false,...,false)work=Available(2)循环查找满足下列条件的进程pi//最多循环n次Finish[i]=false且Needi=work(3)若找到则Finish[i]=true;work=work+Alloci;转(2)(4)若Finish=(true,...,true)则安全，否则不安全。测试数据：m=3:种类型的资源（A,B,C,）；进程个数n=5；Available=(2,3,3);已分配资源数量资源需求量ABCABCP1212347P2402134P3305003P4204221P53141105.流程图开始输入需申请资源的进程号输入进程%d申请的资源数请求向量与需求矩阵比较是否是否是三、调试分析遇到的问题：在测试数据时，一直显示的是进程阻塞。解决办法：产生这一现象的原因是在安全性算法失败时，没有撤销拟分配的资源，只要加上撤销资源的步骤就可以解决这一问题。四、用户手册进程阻塞请求向量与可利用资源量比较=?=?拟分配执行安全性算法安全?撤销分配新状态稳定，资源实际分配点击运行程序会显示如下提示：根据提示依次输入进程号，会有如下显示：按照提示输入进程所申请的资源量：则第一个进程的处理就完成了：五、运行结果六、源程序清单#includestring.h#includestdio.h#definen5//总进程数#definem3//总资源数#defineFALSE0#defineTRUE1intMax[n][m];intAvailable[m]={2,2,3};//系统可用资源数intAllocation[n][m]={{2,1,2},{4,0,2},{3,0,5},{2,0,4},{3,1,4}};//n个进程已经得到N类资源的资源量intNeed[n][m]={{3,4,7},{1,3,4},{0,0,3},{2,2,1},{1,1,0}};//n个进程还需要m类资源的资源量intRequest[m];//请求矩阵intBijiao(inti);intsafe();voidmain(){inta,b,c,d;inti=0,j=0,k;while(1){printf(请输入需申请资源的进程号:);scanf(%d,&i);printf(请输入进程%d申请的资源数,i);scanf(%d%d%d,&Request[0],&Request[1],&Request[2]);a=Bijiao(i);if(a){for(k=0;km;k++){Available[k]=Available[k]-Request[k];Allocation[i-1][k]=Allocation[i-1][k]+Request[k];Need[i-1][k]=Need[i-1][k]-Request[k];}safe(i);}}}intBijiao(inti)//比较请求与需求矩阵{intj;intm=0,n=0;for(j=0;jm;j++){if((Request[j]=Need[i-1][j]))m++;if((Request[j]=Available[j]))n++;}if(m==3&&n==3)return1;elseprintf(该进程阻塞!\n);return0;}intsafe(inth){intwork[m],Finish[n];inti=0,j,k=0;for(i=0;in;i++)Finish[i]=FALSE;for(j=0;jm;j++)work[j]=Available[j];//i=s;while(in+120){k=0;for(j=0;jn;j++){if(Finish[j]==FALSE&&Need[j][0]=work[0]&&Need[j][1]=work[1]&&Need[j][2]=work[2]){Finish[j]=TRUE;work[0]=Allocation[j][0];work[1]=Allocation[j][1];work[2]=Allocation[j][2];}}for(j=0;jn;j++)if(Finish[j]=TRUE)k++;if(k==n)break;elsei++;}k=0;for(i=0;in;i++){if(Finish[i]==TRUE)k++;}if(k!=n){printf(该进程阻塞!\n);for(j=0;jm;j++){Available[j]=Available[j]+Request[j];Allocation[h-1][j]=Allocation[h-1][j]-Request[j];Need[h-1][j]=Need[h-1][j]+Request[j];}}else{printf(新状态稳定,资源实际分配!\n);}return0;}实习二多级队列调度算法【问题描述】设RQ分为RQ1和RQ2，RQ1采用轮转法，时间q=7.RQ1RQ2，RQ2采用短进程优先调度算法。RQ1:P1-P5,RQ2:P6-P10。【测试数据】测试数据如下：RQ1:P1-P5,RQ2:P6-P10进程P1P2P3P4P5P6P7P8P9P10运行时间1611141315211810714已等待时间6543212345一、需求分析1.将p1-p5、p6-p10做成链表，并把各个进程的运行时间和已等待时间保存到节点中；2.当RQ1中的进程没