多级队列调度算法和银行家算法

PAGEPAGE5操作系统原理上机报告院系：计算机学院班级：191094—16姓名：熊金莲学号：20091003768 二O一一年六月一：银行家算法实验目的：1、了解并掌握银行家算法的思想；2、通过编程实现银行家算法；实验步骤：安全状态：系统按照某种序列为多个进程分配资源直到最大需求，如果能够保证所有进程全部顺利执行完毕，则称系统是安全的。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#include<iostream.h>{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->need>0) { q=p; while(q->next!=NULL)q=q->next; if(p->need>piece_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;i<5;i++){ q=RQ2; p=(PCB*)malloc(sizeof(PCB)); p->need=max; p->next=NULL;while(q!=NULL){if(q->need!=0&&q->need<p->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.RQ1>RQ2，RQ2采用短进程优先调度算法。测试数据如下：RQ1:P1-P5,RQ2:P6-P10进程P1P2P3P4P5P6P7P8P9P10运行时间1611141315211810714已等待时间65432123457、具体代码实现如下#definemax10000#include<stdio.h>#include<string.h>#include<malloc.h>typedefstructtag_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;i<5;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;i<5;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; }//RQ1采用轮转法p=RQ1;intflag=0;while(p!=NULL) { while(p!=NULL&&p->need>0) { q=p; while(q->next!=NULL)q=q->next; if(p->need>piece_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; }//RQ2采用短进程优先调度算法。for(i=0;i<5;i++){ q=RQ2; p=(PCB*)malloc(sizeof(PCB)); p->need=max; p->next=NULL;while(q!=NULL){if(q->need!=0&&q->need<p->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");}8运行情况如下程序运行结果与所期待的理论值一致！！！9实验分析及心得体会如下：通过该程序的设计、编译、实现，我更好地了解银行家算法，循环轮转法，短进程优先调度算法的设计与实现，实验过程中通过调试分析，自己的编程能力有所提高。一．通过实现银行家算法，我明白了进程之间的关系及资源分配的实质，对于死锁问题的检查，银行家算法简便易行。在安全性算法中，当安全性算法检测为不安全时,要将资源返还。安全性算法设置两个向量：工作向量pro，它表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时，pro初值=Available；finish表示系统是否有足够的资源分配给里程，使之运行完成，开始时，finish[i]=0；当有足够资源分配给进程时，令finish[i]=1；（2）从进程集合中找到满足下述条件的进程：finish[i]=0；Need[i]<=pro；若找到执行（3），否则执行（4）；（3）当进程Pi获得资源后，顺序执行直到完成，并释放它的资源，执行：Pro=pro+Allocation[i]；finish[i]=1；gotostep(2);（4）若所有进程的finish[i]=1，则系统处于安全状态，否则，处于不安全状态。二．循环轮转和短程优先算法是一种操作系统的基础模拟，实现原理以及实现过程都不复杂，基本思想如下：(1)循环轮转法：轮转法将CPU时间划分成若干个短的时间片断（通常小于100ms），将这些时间片断轮流分配给各个就绪进