多级队列调度算法

实用标准文案精彩文档操作系统原理上机报告院系：计算机学院班级：191094—16姓名：熊金莲学号：20091003768二O一一年六月实用标准文案精彩文档一：银行家算法实验目的：1、了解并掌握银行家算法的思想；2、通过编程实现银行家算法；实验步骤：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，则系统处于安全状态，否则，处于不安全状态。5、具体代码实现如下#definea5#defineb3实用标准文案精彩文档#includeiostream.hintDistribution_of_test(int*Available1,intNeed1[5][3],intAlloc[5][3]){intfinish[a]={0,0,0,0,0};intpro[b];for(inti=0;i3;i++)pro[i]=Available1[i];for(inth=0;h5;h++)for(inti=0;i5;i++){if(finish[i]==0){for(intj=0;j3;j++)Need1[i][j]=pro[j];if(j3){for(intt=0;t3;t++)pro[t]=pro[t]+Alloc[i][t];finish[i]=1;}}}for(i=0;i5;i++)if(finish[i]);if(i5)return(0);elsereturn(1);}voidmain(){intAvailable[b]={2,3,3};intAlloc[a][b]={{2,1,2},{4,0,2},{3,0,5},{2,0,4},{3,1,4}};intNeed[a][b]={{3,4,7},{1,3,4},{0,0,3},{2,2,1},{1,1,0}};intrequest[3]={0,0,0};intfinish[a]={0,0,0,0,0};intnum;while(1){cout请输入进程序列号:;cinnum;num--;cout请输入需要请示的资源序列:;cinrequest[0]request[1]request[2];for(inti=0;i3;i++){if(request[i]=Need[num][i]&&request[i]=Available[i])实用标准文案精彩文档continue;elsebreak;}if(i3){cout该进程阻塞!endl;continue;}else{for(intj=0;j3;j++){Available[j]=Available[j]-request[j];Alloc[num][j]=Alloc[num][j]+request[j];Need[num][j]=Need[num][j]-request[j];}}if(!Distribution_of_test(Available,Need,Alloc)){for(intj=0;j3;j++){Available[j]=Available[j]+request[j];Alloc[num][j]=Alloc[num][j]-request[j];Need[num][j]=Need[num][j]+request[j];}cout新状态不稳定,资源回收endl;}elsecout新状态稳定,资源实际分配!endl;}}请求序列如下：a.进程P2请求资源（0，3，4）b．进程P4请求资源（1，0，1）c.进程P1请求资源（2，0，1）d.进程P3请求资源（0，0，2）预期实验结果如下：请输入进程序号:2请输入需要请求的资源序列:034该进程阻塞!请输入进程序号:4请输入需要请求的资源序列:101新状态稳定,资源实际分配!实用标准文案精彩文档请输入进程序号:1请输入需要请求的资源序列:201该进程阻塞!请输入进程序号:3请输入需要请求的资源序列:002新状态稳定,资源实际分配!该运行结果与实验预期结果相符,即实现了银行家算法！！！！二：多级队列调度算法实验目的：1.了解进程高度算法的原理及物理变换；2.掌握简单轮转调度算法和短程优先调度算法，并对两种算法的效率进行简单分析实验步骤：1.设置好各种队列，两种算法均以链表作为调度队列，因为两种算法均只需要一个队列就能满足调度。2.第一种算法的思想是采用的轮转调试，第二种采用的是短进程优先算法，确定好算法步骤，进行输入测试。3设RQ分为RQ1和RQ2，RQ1采用轮转法，时间q=7.实用标准文案精彩文档RQ1RQ2，RQ2采用短进程优先调度4、采取的数据结构typedefstructtag_pcb{charname[8];intneed;intturn;structtag_pcb*next;}PCB;5,大体设计思路（1）/Test_of_Rotation_cycle循环轮转法轮转法将CPU时间划分成若干个短的时间片断（通常小于100ms），将这些时间片断轮流分配给各个就绪进程使用。如果时间片结束时，进程还没有运行完，则CPU将被剥夺并分配给另一个就绪进程使用；如果进程在时间片结束前阻塞或结束，则CPU理解发生切换。//RQ1采用轮转法p=RQ1;intflag=0;while(p!=NULL){while(p!=NULL&&p-need0){q=p;while(q-next!=NULL)q=q-next;if(p-needpiece_time){clock+=piece_time;p-need-=piece_time;if(s!=NULL)s-next=p-next;q-next=p;p=p-next;q-next-next=NULL;}else{flag++;clock+=p-need;p-need=0;p-turn+=clock;if(flag==1)RQ1=p;s=p;p=p-next;}实用标准文案精彩文档}while(p!=NULL&&p-need==0)p=p-next;}（2）//Test_of_Priority短进程优先调度调度思想：每个进程按进程执行时间长短被赋予一个优先级，进程越短优先级越高，进程越长优先级越低，优先级最高的就绪进程率先被运行。为了防止高优先级的进程无休止的运行下去，调度程序可以在每一个时钟中断适当降低当前进程的优先级。如果这时运行进程优先级低于次高优先级进程，则将进行进程切换。//RQ2采用短进程优先调度算法。for(i=0;i5;i++){q=RQ2;p=(PCB*)malloc(sizeof(PCB));p-need=max;p-next=NULL;while(q!=NULL){if(q-need!=0&&q-needp-need)p=q;q=q-next;}clock+=p-need;p-turn+=clock;p-need=0;}//输出各进程的周转时间printf(输出各进程的周转时间如下:\n);p=RQ1;printf(\nRQ1各进程运行时间如下);while(p!=NULL){printf(\n%s:%d,p-name,p-turn);p=p-next;}p=RQ2;printf(\nRQ2各进程运行时间如下);while(p!=NULL){printf(\n%s:%d,p-name,p-turn);实用标准文案精彩文档p=p-next;}printf(\n\n\n);}6测试数据如下设RQ分为RQ1和RQ2，RQ1采用轮转法，时间q=7.RQ1RQ2，RQ2采用短进程优先调度算法。测试数据如下：RQ1:P1-P5,RQ2:P6-P10进程P1P2P3P4P5P6P7P8P9P10运行时间1611141315211810714已等待时间65432123457、具体代码实现如下#definemax10000#includestdio.h#includestring.h#includemalloc.htypedefstructtag_pcb{charname[8];intneed;intturn;structtag_pcb*next;}PCB;PCB*RQ1,*RQ2;voidmain(){//各进程运行时间及等待时间PCB*p,*q,*s=NULL;inti,clock=0,piece_time=7;charname1[5][8]={p1,p2,p3,p4,p5};charname2[5][8]={p6,p7,p8,p9,p10};intneed1[5]={16,11,14,13,15},wait1[5]={6,5,4,3,2};intneed2[5]={21,18,10,7,14},wait2[5]={1,2,3,4,5};//RQ1链表的创建RQ1=(PCB*)malloc(sizeof(PCB));strcpy(RQ1-name,name1[0]);RQ1-need=need1[0];RQ1-turn=wait1[0];RQ1-next=NULL;p=RQ1;for(i=1;i5;i++){实用标准文案精彩文档q=(PCB*)malloc(sizeof(PCB));strcpy(q-name,name1[i]);q-need=need1[i];q-turn=wait1[i];p-next=q;q-next=NULL;p=p-next;}//RQ2链表的创建RQ2=(PCB*)malloc(sizeof(PCB));strcpy(RQ2-name,name2[0]);RQ2-need=need2[0];RQ2-turn=wait2[0];RQ2-next=NULL;p=RQ2;for(i=1;i5;i++){q=(PCB*)malloc(sizeof(PCB));strcpy(q-name,name2[i]);q-need=need2[i];q-turn=wait2[i];p-next=q;q-next=NULL;p=p-next;}//R