实验三进程调度.doc

实验三进程调度一实验目的加深理解并模拟实现进程（作业）调度算法。1）熟悉常用的进程调度算法，如FCFS、SPF、FPF、高响应比优先、时间片轮转；2）结合所学的数据结构及编程知识，选择三种进程调度算法予以实现。二实验属性该实验为设计性实验。三实验仪器设备及器材普通PC386以上微机四实验要求1） 编程实现单处理机系统中的进程调度，要求从FCFS、SPF、FPF、高响应比优先、时间片轮转算法中至少选择三个；2） 最后编写主函数对所做工作进行测试。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。五、需求分析1、1) 输入的形式和输入值的范围输入值：进程个数Num 范围：0Num=100 依次输入Num个进程的到达时间 范围： 依次输入Num个进程的服务时间 范围： 输入要使用的算法（A-FCFS，B-SJF） 2) 程序所能达到的功能输入进程个数Num，每个进程到达时间ArrivalTimei，服务时间ServiceTimei。采用先来先服务FCFS或者短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计Num个进程的平均周转时间和平均带权周转时间。2、高优先权优先调度算法1)输入进程数和进程的优先权要求服务时间后初始化队列。2)W为等待状态；R为运行状态。按照高优先权优先原则进行进程的调度和执行。一步步完成进程的调度和执行。六、经验和体会最高优先权优先（FPF）调度算法 此算法常被用在批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度，还可以用于实时系统中。当其用于作业调度， 将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，可以进一步把该算法分成以下两种：非抢占式优先权算法、抢占式优先权调度算法。非抢占式优先权算法是指一旦把处理机分配给就绪队列中优先权最高的进城后，该进程变一直执行下去直到完成。这种调度算法主要用于批处理系统中，也可以用于某些对实时性要求不高的实时系统中；而抢占式优先权算法系统将处理机分配给优先权最高点的进程，并执行但当在执行期间遇到另外一个优先权更高的程序的时候就会将处理机的使用权给这个优先权比较高的进程，这种调度算法能够更好的满足紧迫作业的要求，常用在要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统找中。通过本次实验我们深入理解了先来先服务和短进程优先进程调度算法的思想,学会高优先权调度算法的原理和调度过程、还要能够熟练运用。七、源程序 1、FCFS、SPF#include#includeusing namespace std;static const int Max=100;int ArrivalTimeMax;/到达时间int ServiceTimeMax;/服务时间int FinishTimeMax;/完成时间int WholeTimeMax;/周转时间double WeightWholeTimeMax;/帯权周庄时间double AverageWT_FCFS,AverageWT_SJF; /平均周转时间double AverageWWT_FCFS,AverageWWT_SJF;/平均帯权周转时间int ServiceTime_SJFMax;/在SJF算法中使用到int Num=0;int NowTime=0;/记录当前时间double SumWT=0,SumWWT=0;/SumWT用来计算总的周转时间，SumWWT用来计算总的帯权周转时间int i;int choice;/记录选择 / 先到先服务算法void FCFS()/找最早到达的。cout-FCFS-endl;for(i=0;iNowTime)/假如进程到达的时间比现在已经运行的时间NowTime大，说明在NowTime时刻进程未到达 NowTime=ArrivalTimei;/把进程的到达时间赋给NowTimeNowTime+=ServiceTimei;/把进程的服务时间加到NowTime上FinishTimei=NowTime;/计算完成时间WholeTimei=FinishTimei-ArrivalTimei;/计算周转时间=完成时间-到达时间WeightWholeTimei=(double)WholeTimei/ServiceTimei;/计算带权周转时间=周转时间/服务时间SumWT+=WholeTimei;/计算总的周转时间SumWWT+=WeightWholeTimei;/计算总的帯权周转时间AverageWT_FCFS=SumWT/Num;/平均周转时间AverageWWT_FCFS=SumWWT/Num;/平均帯权周转时间for(i=0;iNum;i+)/依次输出结果cout时刻FinishTimei-ServiceTimei: 进程i+1开始运行。 其完成时间：FinishTimei 周转时间：WholeTimeisetprecision(3) 帯权周转时间：WeightWholeTimeisetprecision(3)endl;cout平均周转时间：AverageWT_FCFSendl;cout平均帯权周转时间：AverageWWT_FCFSendl; / 短进程优先算法void SJF()/找已经到达的且服务时间最短的进程（假定输入的进程是按照到达时间先后输入的）cout-SJF-endl;int min=0;NowTime=ArrivalTime0+ServiceTime0;/计算第一次的NowTImeFinishTime0=NowTime;/计算第一个进程的完成时间ServiceTime_SJF0=1000;/赋初值。cout时刻FinishTime0-ServiceTime0: 进程1开始运行。;int allin=0,j,k;for(i=1;iNum;i+)/进入循环，从第二个到达的进程开始k=1;min=0;if(allin=0)/找到已经到达的进程个数j=0;while(ArrivalTimej=NowTime & j=Num)allin=1;else j=Num;j=j-1;/j是已经到达的进程数while(kServiceTime_SJFk)/比较，找到服务时间最短的进程min=k;k+;ServiceTime_SJFmin=0;/找完后置零，便于下一次循环时使用NowTime+=ServiceTimemin;/累加当前时间FinishTimemin=NowTime;/完成时间for(i=0;iNum;i+)/计算周转时间，带权周转时间，总的周转时间和总的带权周转时间WholeTimei=FinishTimei-ArrivalTimei;WeightWholeTimei=(double)WholeTimei/ServiceTimei;SumWT+=WholeTimei;SumWWT+=WeightWholeTimei;AverageWT_SJF=SumWT/Num;/平均周转时间AverageWWT_SJF=SumWWT/Num;/平均带权周转时间cout 其完成时间：FinishTime0 周转时间：WholeTime0setprecision(3) 帯权周转时间：WeightWholeTime0setprecision(3)endl;for(i=1;iNum;i+)/输出结果cout时刻FinishTimei-ServiceTimei: 进程i+1开始运行。 其完成时间：FinishTimei 周转时间：WholeTimeisetprecision(3) 帯权周转时间：WeightWholeTimeisetprecision(3)endl;cout平均周转时间：AverageWT_SJFendl;cout平均帯权周转时间：AverageWWT_SJFendl;void input() / 输入函数coutNum;while(Num100|Num=0)coutNum;for(i=0;iNum;i+)cout第i+1ArrivalTimei;for(i=0;iNum;i+)int data=0;cout第i+1data;ServiceTimei=data;ServiceTime_SJFi=data;cout-endl;coutchoice;void main()char flag=y;Loop:NowTime=0;SumWT=0;SumWWT=0;/参数初始化 input();/输入if(choice=1)FCFS();/调用FCFS算法else if(choice=2)SJF();/调用SJF算法else/输入有误，则重新选择while(1) cout您的选择有误!请重新选择!endl;coutchoice;if(choice=1)FCFS();break;else if(choice=2)SJF();break;coutendlflag;if(flag=y | flag=Y)goto Loop;2、高优先权优先调度算法#include stdio.h #include stdlib.h #define getpch(type) new typestruct pcb /* 定义进程控制块PCB */ char name10; /进程名 char state; /状态 int super; /优先级 int ntime; /要求服务时间 int rtime; /已运行时间 struct pcb* next; *ready=NULL,*p;typedef struct pcb PCB;void sort(PCB *a) /* 建立对进程进行优先级排列函数*/ PCB *first, *second; int insert=0; if(ready=NULL)|(a-super)(ready-super) /*优先级最大者,插入队首*/ a-next=ready; ready=a; else /* 进程比较优先级,插入适当的位置中*/ first=ready; second=first-next; while(second!=NULL) if(a-super)(second-super) /*若插入进程比当前进程优先数大,插入到当前进程前面*/a-next=second; first-next=a; second=NULL; insert=1; else /*指针后移，寻找插入点*/ first=first-next; second=second-next; if(insert=0) first-next=a;/* 插入进程优先数最低,则插入到队尾*/ void createpcb() /* 建立进程控制块函数*/ int i,num; printf(ttt最高优先权优先调度算法模拟tn); printf(n 请输入进程数目:); scanf(%d,&num); for(i=0;iname,&p-super,&p-ntime); p-rtime=0; p-state=w; p-next=NULL; sort(p); void display1() /*建立进程显示函数,用于显示当前进程*/ printf(n进程名 状态 优先数 要求服务的时间 已运行时间 n); void display2(PCB * pr) printf(%3.5s %7c %6d %12d %10d,pr-name,pr-state,pr-super,pr-ntime,pr-rtime); printf(n); void check() /* 建立进程查看函数 */ PCB *pr; printf(n); printf(n);printf(n * 当前正在运行的进程是%s的状态如下:n,p-name); display1(); display2(p); pr=ready; printf(n *当前就绪队列中进程的状态如下:n); if(pr=NULL) printf( *就绪队列为空!);else display1(); while(pr!=NULL) display2(pr); pr=pr-next; void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/ printf(n 进程 %s 已完成.n,p-name); free(p); void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态)*/ (p-rtime)+; /*运行时间加一*/ if(p-rtime=p-ntime) /*已运行时间与要求服务时间相等时，撤销进程*/destroy(); /* 调用destroy函数*/ else (p-su