进程调度算法设计报告.docx

1、进程调度算法设计报告操作系统课程设计报告题目： 进程调度算法 院 系： 信息学院 班 级： 信管11-2 姓 名： 王裕辰 学 号： 1101051024 指导教师： 赵 华 一、概述本次设计的程序主要功能是模拟CPU的进程调度过程，实现先来先服务调度算法、短作业优先调度算法、非抢占优先权调度算法、时间片轮转法四个进程调度算法，并根据输入的数据和相应的调度算法计算每个进程的调度结果，对四个算法的平均周转时间进行比较和评价。本程序主要解决的是CPU的四种进程调度算法的评价和比较问题，包括平均周转时间和平均等待时间。通过这四种调度算法的比较，有利于加深对四种算法的理解，使用户能够更好、更快的运用四

2、种调度算法。二、设计的基本概念和原理1、基本概念（1） 到达时间：指进程到达CPU的时间点。（2） 服务时间：指进程需要CPU执行的时间长度。（3） 完成时间：指进程执行完成的时间。（4） 周转时间：指进程从到达到执行完成所经过的时间。（5） 带权周转时间：进程的周转时间与服务时间的比值，用于反映长短进程的差别。（6） 平均周转时间：指一个调度算法中所有进程的周转时间的平均值。用于衡量不同调度算法对相同进程的调度性能。（7） 平均带权周转时间：指一个调度算法中所有进程的带权周转时间的平均值。用于比较调度算法对不同进程的调度性能。2、基本原理（1） FCFS调度算法按照进程的到达时间从小到大进行

3、排序，放入就绪队列中，每次调度都是从就绪队列中选择对头的进程进入内存，运行此程序至完成，然后继续从就绪队列中再次调入一个进程，运行，结束。重复上述过程直到就绪队列中所有进程全部运行完成。（2） SPF调度算法从就绪队列中选出一个服务时间最短的进程，将其调入内存，将CPU分配给它，使它立即执行并一直执行到完成，然后再从当前就绪队列中选出一个服务时间最短的进程，调入内存执行到完成。重复此过程直到所有进程全部执行完成。（3） 非抢占高优先权优先调度算法从就绪队列中选出一个优先权最高的进程，将其调入内存，并为其分配CPU，该进程一直执行直至完成。然后再次重复上述过程。（4） 基于时间片的轮转调度算法将

4、所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并执行一个时间片。当执行的时间片用完，调度进程便停止该进程的执行，并将它送往就绪队列的末尾，然后再把CPU分配给就绪队列中新的队首进程，同时也让它执行一个时间片。三、总体设计本程序才用了结构化程序设计方法，首先将进程抽象为一个类，用用户所输入的每个进程的信息来把每个对象来初始化。然后分块地调用不同的函数实现不同的调度算法。本程序包括以下三个模块：（1） 预定义及进程类定义模块定义程序所用到的头文件和常量。定义进程类的类成员，成员函数以及进程的构造函数和析构函数。（2） 主程序模块包括以下五个步骤选择进程调度算法输

5、入进程相关信息调用所选的进程调度算法计算每个进程的完成时间、周转时间、带权周转时间输出每个进程的时间参数，计算并输出所选算法的平均周转时间和平均带权周转时间（3） 其它函数模块定义了四种调度算法和程序中调用的其他函数。程序流程图： 四、详细设计每个模块的代码及分析如下：1、预定义及进程类定义模块#include stdafx.h#include #include #include #define MAX 100 /进程的最大数量class Process private: int arritime,sevtime,finitime,zhtime,sevtime1,priority;/arrit

6、ime-到达时间，sevtime、sevtime1-服务时间，finitime-完成时间,zhtime-周转时间,priority-优先权 double qtime;/ 带权周转时间 public: string pname;/ 进程名 Process()/无参构造函数，用于构造对象数组 arritime=0; sevtime=0; sevtime1=0; finitime=0; zhtime=0; qtime=0; priority=0; int getarritime()return arritime;/返回到达时间 int getsevtime()return sevtime;/返回服务

7、时间时间 int getsevtime1()return sevtime1;/返回服务时间1时间 int getfinitime()return finitime;/返回完成时间 int getzhtime()return zhtime;/返回周转时间 int getprior()return priority;/返回优先权 double getqtime()return qtime;/返回带权周转时间 void setpname(string n)pname=n;/设置进程名 void setarritime(int t)arritime=t;/设置到达时间 void setsevtime1

8、(int t)sevtime1=t;/设置服务时间1 void setsevtime(int t)sevtime=t;/设置服务时间 void setfinitime(int t)finitime=t;/设置完成时间 void setzhtime(int t)zhtime=t;/设置周转时间 void setqtime(double t)qtime=t;/设置带权周转时间 void setprior(int t)priority=t;/设置优先权 void show() const;/ 输出类成员（到达时间，服务时间，完成时间，周转时间,priority，带权周转时间）定义为常量函数，防止对成

9、员变量进行修改 void showQHP() const;/输出优先权;void Process:showQHP() const coutsetw(5)pnamesetw(10)arritimesetw(10)sevtimesetw(10)finitimesetw(10)zhtimesetw(13)qtimesetw(10)priorityendl;void Process:show() const coutsetw(5)pnamesetw(10)arritimesetw(10)sevtimesetw(10)finitimesetw(10)zhtimesetw(13)qtimesetw(10)

10、endl;2、主程序模块int main(int argc, char* argv)/主函数 int n,Arrive,Serve,i,q,choice,Priority; string Pname; Process proMAX;/ 定义对象数组用于存放进程 double averz,averq;/averz-平均周转时间，averq-平均带权周转时间 while(1) / 死循环，重复选择调度算法。根据选择调用相关的调度算法，若为0，退出程序。 cout 进程调度算法 endl; cout 1.先来先服务 2.短作业优先 endl; cout 3.高优先级 4.时间片轮转 endl; co

11、ut 0.退出 endl; cout 请选择进程调度算法： choice; if(choice=0) return 0; cout输入进程数目n:n; coutendl; cout输入每个进程的信息:endl; coutendl; for(i=0;in;i+) / 输入进程信息 cout输入第i+1个进程的信息:endl; coutPname; proi.setpname(Pname); coutArrive; proi.setarritime(Arrive); coutServe; proi.setsevtime(Serve); proi.setsevtime1(Serve); if(cho

12、ice=1) FCFS(pro,n); /按到达时间从小到大排序 coutendlFCFS算法调度各进程相关时间：endl; if(choice=2) SJF(pro,n); /调用短作业优先算法 coutendlSJF算法调度各进程相关时间：endl; if(choice=3) for(i=0;in;i+) / 输入进程的优先权 cout输入第i+1个进程的优先级:Priority; proi.setprior(Priority); QHP(pro,n);/调用高优先权算法 coutendlQHP算法调度各进程相关时间：endl; if(choice=4) cout输入时间片大小:q; RR

13、(pro,n,q); /调用时间片轮转算法 coutendlFCFS算法调度各进程相关时间：endl; averz=calaverzh(pro,n);/计算平均周转时间 averq=calaverqt(pro,n);/计算平均带权周转时间/输出进程的到达时间、服务时间、完成时间、周转时间、带权周转时间、优先级、平均周转时间、平均带权周转时间 if(choice=3) coutsetw(5)进程名setw(10)到达时间setw(10)服务时间setw(10)setw(10)完成时间setw(10)周转时间setw(13)带权周转时间setw(10)优先级endl; for(i=0;in;i+)

14、 proi.showQHP();/ 如果选择高优先权算法，输出每个进程的优先权 else coutsetw(5)进程名setw(10)到达时间setw(10)服务时间setw(10)完成时间setw(10)周转时间setw(13)带权周转时间endl; for(i=0;in;i+) proi.show(); coutendl平均周转时间： averzendl; cout平均带权周转时间：averqendlendl; 3、其它函数模块/先来先服务进程调度算法void FCFS(Process *P,int N) sort_arritime(P,N);/ 按照到达时间从小到大进行排序，即可模拟出进

15、程到达顺序 calculate(P,N);/ 计算完成时间、周转时间、带权周转时间/短作业优先调度算法void SJF(Process *P,int N) int i,j,count; Process mediaprocessMAX; sort_arritime(P,N);/按到达时间从小到大排序 for(i=0;iN;i=j) count=0; if(i=0) Pi.setfinitime(Pi.getarritime()+Pi.getsevtime();/完成时间=到达时间+服务时间 else Pi.setfinitime(Pi-1.getfinitime()+Pi.getsevtime(

16、);/完成时间=i-1的完成时间+i的服务时间 for(j=i+1;jN;j+)/将Pi执行过程中到达的进程放入mediaprocess中 if(Pj.getarritime()=Pi.getfinitime() mediaprocesscount+=Pj; else break; sort_sevtime(mediaprocess,count);/ 对mediaprocess中的进程按照服务时间进行排序 int d=0; for(int c=i+1;ci+count+1;c+)/将mediaprocess中的进程放入p中 Pc=mediaprocessd+; calculate(P,N);

17、/非抢占优先级调度算法void QHP(Process *P,int N) int i,j,count; Process mediaprocessMAX; sort_arritime(P,N);/按到达时间从小到大排序 for(i=0;iN;i=j) count=0; if(i=0) Pi.setfinitime(Pi.getarritime()+Pi.getsevtime();/完成时间=到达时间+服务时间 else Pi.setfinitime(Pi-1.getfinitime()+Pi.getsevtime();/完成时间=第i-1个进程的完成时间+第i个进程的服务时间 for(j=i+

18、1;jN;j+)/将Pi执行过程中到达的进程放入mediaprocess中 if(Pj.getarritime()=Pi.getfinitime() mediaprocesscount+=Pj; else break; sort_prior(mediaprocess,count);/ 对mediaprocess中的进程按照优先级进行排序 int d=0; for(int c=i+1;ci+count+1;c+)/将mediaprocess中的进程放入p中 Pc=mediaprocessd+; calculate(P,N);/计算相关时间 /时间片轮转调度算法void RR(Process *P

19、,int N,int R) int i,j,time;/time表示当前时间 int flagMAX;/用于标记进程是否执行完成 sort_arritime(P,N);/按到达时间从小到大排序 for(i=0;iN;i+)/ 初始值为零，表示没有进程执行完成 flagi=0; time=P0.getarritime();/把当前时间置为第一个到达的进程的到达时间 j=0; while(jN) for(i=0;iN;i+) if(flagi=1)/ 进程执行完成，继续下一次循环 continue; if(Pi.getarritime()=time)/ 如果第i个进程的到达时间小于等于当前时间，表

20、示此进程已经到达 Pi.setsevtime1(Pi.getsevtime1()-R);/ 执行一个时间片，将服务时间1减去一个时间片 time+=R;/当前时间需要加上一个时间片 if(Pi.getsevtime1()=0)/ 第i个进程的服务时间已经执行完成 Pi.setfinitime(time);/设置此时的时间为此进程的完成时间，并将其flag置为1 flagi=1; j+; for(i=0;iN;i+) / 计算周转时间和带权周转时间 Pi.setzhtime(Pi.getfinitime()-Pi.getarritime(); Pi.setqtime(double)Pi.getz

21、htime()/Pi.getsevtime(); void sort_arritime(Process *P,int N)/按照到达时间由小到大对进程进行排序 int i,j; Process temp; for(i=0;iN;i+) for(j=i;jPj.getarritime() temp=Pi; Pi=Pj; Pj=temp; void sort_sevtime(Process *P,int N)/按照服务时间由小到大对进程进行排序 int i,j; Process temp; for(i=0;iN;i+) for(j=i;jPj.getsevtime() temp=Pi; Pi=Pj

22、; Pj=temp; void sort_prior(Process *P,int N)/按照优先级由大到小对进程进行排序 int i,j; Process temp; for(i=0;iN;i+) for(j=i;jN;j+) if(Pi.getprior()Pj.getprior() temp=Pi; Pi=Pj; Pj=temp; void calculate(Process *P,int N)/计算相关时间参数 int i; for(i=0;iN;i+) if(i=0) Pi.setfinitime(Pi.getarritime()+Pi.getsevtime();/第一个执行的进程的

23、完成时间=开始执行时间+服务时间 else Pi.setfinitime(Pi-1.getfinitime()+Pi.getsevtime();/完成时间=上一个进程的完成时间+服务时间 Pi.setzhtime(Pi.getfinitime()-Pi.getarritime();/周转时间=完成时间-到达时间 Pi.setqtime(double)Pi.getzhtime()/Pi.getsevtime();/带权周转时间=周转时间/服务时间 double calaverzh(Process *P,int N)/计算平均周转时间 int i; double averzh; averzh=0;

24、 for(i=0;iN;i+) averzh+=Pi.getzhtime(); averzh=averzh/N; return averzh;double calaverqt(Process *P,int N)/计算平均带权周转时间 int i; double averqt; averqt=0; for(i=0;iN;i+) averqt+=Pi.getqtime(); averqt=averqt/N; return averqt;五、测试与数据分析选择FCFS进程调度算法，输入以下进程信息：进程名 到达时间 服务时间A 0 4B 1 3 C 2 5 D 3 3 E 4 4可以得到先来先服务调

25、度算法的平均周转时间和平均带权周转时间（应为9、2.8）。选择SPF进程调度算法，再次输入上述进程信息。可以得到短作业优调度算法的平均周转时间和平均带权周转时间（应为8、2.1）。选择高优先权调度算法，再次输入以上进程的信息，另外再输入每个进程的优先权进程名 优先权A 3B 1C 3D 4E 2则得到高优先权调度算法的的平均周转时间和平均带权周转时间（应为、）。选择基于时间片的轮转调度算法，输入时间片为1，再次输入上述进程信息，得到时间片轮转算法的的平均周转时间和平均带权周转时间。将上述四个进程调度算法得到的平均周转时间和平均带权周转时间进行比较，可以对这四种算法的性能进行分析，对这四个进程调

26、度算法有了更深入的理解。六、完成的情况、简要的使用说明本程序经过了调试，能够正常运行，并能够得到正确的结果。但使用时应注意以下几个问题：1、 选择调度算法的时候只能输入0、1、2、3、4这五个数字，若输入其它字符将造成程序进入死循环。2、 在输入进程信息之前，应确定进程的数目，并输入。3、 进程名不限于字符，可以是任意长度的字符串。4、 本程序需要逐个输入进程的信息，对于进程数目比较多的时候会花费较长的时间。故本程序最好用于进程数目较少的情况。5、 程序中的进程到达时间、服务时间、优先权和时间片只能是整数，没有考虑实数的情况。七、结果分析进入程序显示如下界面：选择不同的调度算法，分别将测试与数据分析中的数据输入到程序中得到如下结果八、总结本程序的最大特色为用户可以循环不断地选择调度算法，输入进程，得到每种算法的调度结果，以便用户可以对不同的进程调度算法进行比较和分析。本程序能够模拟四种进程调度算法，计算出每个进程的完成时间、周转时间、带权周转时和每种算法的平均周转时间、平均带权周转时间，便于加深对进程调度过程的理解，也能够更好地对四种算法的性能进行较为全面的分析。本次课程设计首先让我对课本上的知识掌握的更加牢固，通过自己编写算法，模拟了进程调度过程，不但提高了我的编程能