进程调度算法设计报告.docx
《进程调度算法设计报告.docx》由会员分享，可在线阅读，更多相关《进程调度算法设计报告.docx（22页珍藏版）》请在冰点文库上搜索。
进程调度算法设计报告
操作系统课程设计报告
题目：
进程调度算法
院系：
信息学院
班级：
信管11-2
姓名：
王裕辰
学号：
1101051024
指导教师：
赵华
一、概述
本次设计的程序主要功能是模拟CPU的进程调度过程，实现先来先服务调度算法、短作业优先调度算法、非抢占优先权调度算法、时间片轮转法四个进程调度算法，并根据输入的数据和相应的调度算法计算每个进程的调度结果，对四个算法的平均周转时间进行比较和评价。
本程序主要解决的是CPU的四种进程调度算法的评价和比较问题，包括平均周转时间和平均等待时间。
通过这四种调度算法的比较，有利于加深对四种算法的理解，使用户能够更好、更快的运用四种调度算法。
二、设计的基本概念和原理
1、基本概念
（1）到达时间：
指进程到达CPU的时间点。
（2）服务时间：
指进程需要CPU执行的时间长度。
（3）完成时间：
指进程执行完成的时间。
（4）周转时间：
指进程从到达到执行完成所经过的时间。
（5）带权周转时间：
进程的周转时间与服务时间的比值，用于反映长短进程的差别。
（6）平均周转时间：
指一个调度算法中所有进程的周转时间的平均值。
用于衡量不同调度算法对相同进程的调度性能。
（7）平均带权周转时间：
指一个调度算法中所有进程的带权周转时间的平均值。
用于比较调度算法对不同进程的调度性能。
2、基本原理
（1）FCFS调度算法
按照进程的到达时间从小到大进行排序，放入就绪队列中，每次调度都是从就绪队列中选择对头的进程进入内存，运行此程序至完成，然后继续从就绪队列中再次调入一个进程，运行，结束。
重复上述过程直到就绪队列中所有进程全部运行完成。
（2）SPF调度算法
从就绪队列中选出一个服务时间最短的进程，将其调入内存，将CPU分配给它，使它立即执行并一直执行到完成，然后再从当前就绪队列中选出一个服务时间最短的进程，调入内存执行到完成。
重复此过程直到所有进程全部执行完成。
（3）非抢占高优先权优先调度算法
从就绪队列中选出一个优先权最高的进程，将其调入内存，并为其分配CPU，该进程一直执行直至完成。
然后再次重复上述过程。
（4）基于时间片的轮转调度算法
将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并执行一个时间片。
当执行的时间片用完，调度进程便停止该进程的执行，并将它送往就绪队列的末尾，然后再把CPU分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
三、总体设计
本程序才用了结构化程序设计方法，首先将进程抽象为一个类，用用户所输入的每个进程的信息来把每个对象来初始化。
然后分块地调用不同的函数实现不同的调度算法。
本程序包括以下三个模块：
（1）预定义及进程类定义模块
定义程序所用到的头文件和常量。
定义进程类的类成员，成员函数以及进程的构造函数和析构函数。
（2）主程序模块
包括以下五个步骤
选择进程调度算法
输入进程相关信息
调用所选的进程调度算法
计算每个进程的完成时间、周转时间、带权周转时间
输出每个进程的时间参数，计算并输出所选算法的平均周转时间和平均带权周转时间
（3）其它函数模块
定义了四种调度算法和程序中调用的其他函数。
程序流程图：
四、详细设计
每个模块的代码及分析如下：
1、预定义及进程类定义模块
#include"stdafx.h"
#include
#include
#include
#defineMAX100//进程的最大数量
classProcess{
private:
intarritime,sevtime,finitime,zhtime,sevtime1,priority;//arritime---到达时间，sevtime、sevtime1--服务时间，finitime---完成时间,zhtime---周转时间,priority---优先权
doubleqtime;//带权周转时间
public:
stringpname;//进程名
Process（）//无参构造函数，用于构造对象数组
{
arritime=0;
sevtime=0;
sevtime1=0;
finitime=0;
zhtime=0;
qtime=0;
priority=0;
}
intgetarritime（）{returnarritime;}//返回到达时间
intgetsevtime（）{returnsevtime;}//返回服务时间时间
intgetsevtime1（）{returnsevtime1;}//返回服务时间1时间
intgetfinitime（）{returnfinitime;}//返回完成时间
intgetzhtime（）{returnzhtime;}//返回周转时间
intgetprior（）{returnpriority;}//返回优先权
doublegetqtime（）{returnqtime;}//返回带权周转时间
voidsetpname（stringn）{pname=n;}//设置进程名
voidsetarritime（intt）{arritime=t;}//设置到达时间
voidsetsevtime1（intt）{sevtime1=t;}//设置服务时间1
voidsetsevtime（intt）{sevtime=t;}//设置服务时间
voidsetfinitime（intt）{finitime=t;}//设置完成时间
voidsetzhtime（intt）{zhtime=t;}//设置周转时间
voidsetqtime（doublet）{qtime=t;}//设置带权周转时间
voidsetprior（intt）{priority=t;}//设置优先权
voidshow（）const;//输出类成员（到达时间，服务时间，完成时间，周转时间,priority，带权周转时间）定义为常量函数，防止对成员变量进行修改
voidshowQHP（）const;//输出优先权
};
voidProcess:
:
showQHP（）const{
cout<}
voidProcess:
:
show（）const{
cout<}
2、主程序模块
intmain（intargc,char*argv[]）
{//主函数
intn,Arrive,Serve,i,q,choice,Priority;
stringPname;
Processpro[MAX];//定义对象数组用于存放进程
doubleaverz,averq;//averz---平均周转时间，averq---平均带权周转时间
while
（1）
{//死循环，重复选择调度算法。
根据选择调用相关的调度算法，若为0，退出程序。
cout<<"进程调度算法"<cout<<"1.先来先服务2.短作业优先"<cout<<"3.高优先级4.时间片轮转"<cout<<"0.退出"<cout<<"请选择进程调度算法：
"<cin>>choice;
if（choice==0）
return0;
cout<<"输入进程数目n:
"<cin>>n;
cout<cout<<"输入每个进程的信息:
"<cout<for（i=0;i{
cout<<"输入"<<"第"<"<cout<<"进程名";
cin>>Pname;
pro[i].setpname（Pname）;
cout<<"到达时间";
cin>>Arrive;
pro[i].setarritime（Arrive）;
cout<<"服务时间";
cin>>Serve;
pro[i].setsevtime（Serve）;
pro[i].setsevtime1（Serve）;
}
if（choice==1）
{
FCFS（pro,n）;//按到达时间从小到大排序
cout<"<}
if（choice==2）
{
SJF（pro,n）;//调用短作业优先算法
cout<"<}
if（choice==3）
{
for（i=0;i{
cout<<"输入"<<"第"<"<cin>>Priority;
pro[i].setprior（Priority）;
}
QHP（pro,n）;//调用高优先权算法
cout<"<}
if（choice==4）
{
cout<<"输入时间片大小:
"<cin>>q;
RR（pro,n,q）;//调用时间片轮转算法
cout<"<}
averz=calaverzh（pro,n）;//计算平均周转时间
averq=calaverqt（pro,n）;//计算平均带权周转时间
//输出进程的到达时间、服务时间、完成时间、周转时间、带权周转时间、优先级、平均周转时间、平均带权周转时间
if（choice==3）
{
cout<for（i=0;ipro[i].showQHP（）;//如果选择高优先权算法，输出每个进程的优先权
}
else
{
cout<for（i=0;ipro[i].show（）;
}
cout<"<cout<<"平均带权周转时间：
"<}
}
3、其它函数模块
//先来先服务进程调度算法
voidFCFS（Process*P,intN）
{
sort_arritime（P,N）;//按照到达时间从小到大进行排序，即可模拟出进程到达顺序
calculate（P,N）;//计算完成时间、周转时间、带权周转时间
}
//短作业优先调度算法
voidSJF（Process*P,intN）
{
inti,j,count;
Processmediaprocess[MAX];
sort_arritime（P,N）;//按到达时间从小到大排序
for（i=0;i{
count=0;
if（i==0）
P[i].setfinitime（P[i].getarritime（）+P[i].getsevtime（））;//完成时间=到达时间+服务时间
else
P[i].setfinitime（P[i-1].getfinitime（）+P[i].getsevtime（））;//完成时间=i-1的完成时间+i的服务时间
for（j=i+1;j{
if（P[j].getarritime（）<=P[i].getfinitime（））
mediaprocess[count++]=P[j];
else
break;
}
sort_sevtime（mediaprocess,count）;//对mediaprocess中的进程按照服务时间进行排序
intd=0;
for（intc=i+1;c{
P[c]=mediaprocess[d++];
}
calculate（P,N）;
}
}
//非抢占优先级调度算法
voidQHP（Process*P,intN）{
inti,j,count;
Processmediaprocess[MAX];
sort_arritime（P,N）;//按到达时间从小到大排序
for（i=0;i{
count=0;
if（i==0）
P[i].setfinitime（P[i].getarritime（）+P[i].getsevtime（））;//完成时间=到达时间+服务时间
else
P[i].setfinitime（P[i-1].getfinitime（）+P[i].getsevtime（））;//完成时间=第i-1个进程的完成时间+第i个进程的服务时间
for（j=i+1;j{
if（P[j].getarritime（）<=P[i].getfinitime（））
mediaprocess[count++]=P[j];
else
break;
}
sort_prior（mediaprocess,count）;//对mediaprocess中的进程按照优先级进行排序
intd=0;
for（intc=i+1;cP[c]=mediaprocess[d++];
calculate（P,N）;//计算相关时间
}
}
//时间片轮转调度算法
voidRR（Process*P,intN,intR）{
inti,j,time;//time表示当前时间
intflag[MAX];//用于标记进程是否执行完成
sort_arritime（P,N）;//按到达时间从小到大排序
for（i=0;iflag[i]=0;
time=P[0].getarritime（）;//把当前时间置为第一个到达的进程的到达时间
j=0;
while（j{
for（i=0;i{
if（flag[i]==1）//进程执行完成，继续下一次循环
continue;
if（P[i].getarritime（）<=time）//如果第i个进程的到达时间小于等于当前时间，表示此进程已经到达
{
P[i].setsevtime1（P[i].getsevtime1（）-R）;//执行一个时间片，将服务时间1减去一个时间片
time+=R;//当前时间需要加上一个时间片
if（P[i].getsevtime1（）<=0）//第i个进程的服务时间已经执行完成
{
P[i].setfinitime（time）;//设置此时的时间为此进程的完成时间，并将其flag置为1
flag[i]=1;
j++;
}
}
}
}
for（i=0;i{//计算周转时间和带权周转时间
P[i].setzhtime（P[i].getfinitime（）-P[i].getarritime（））;
P[i].setqtime（（double）P[i].getzhtime（）/P[i].getsevtime（））;
}
}
voidsort_arritime（Process*P,intN）//按照到达时间由小到大对进程进行排序
{
inti,j;
Processtemp;
for（i=0;i{
for（j=i;j{
if（P[i].getarritime（）>P[j].getarritime（））
{
temp=P[i];
P[i]=P[j];
P[j]=temp;
}
}
}
}
voidsort_sevtime（Process*P,intN）//按照服务时间由小到大对进程进行排序
{
inti,j;
Processtemp;
for（i=0;i{
for（j=i;j{
if（P[i].getsevtime（）>P[j].getsevtime（））
{
temp=P[i];
P[i]=P[j];
P[j]=temp;
}
}
}
}
voidsort_prior（Process*P,intN）//按照优先级由大到小对进程进行排序
{
inti,j;
Processtemp;
for（i=0;i{
for（j=i;j{
if（P[i].getprior（）{
temp=P[i];
P[i]=P[j];
P[j]=temp;
}
}
}
}
voidcalculate（Process*P,intN）{//计算相关时间参数
inti;
for（i=0;i{
if（i==0）
P[i].setfinitime（P[i].getarritime（）+P[i].getsevtime（））;//第一个执行的进程的完成时间=开始执行时间+服务时间
else
P[i].setfinitime（P[i-1].getfinitime（）+P[i].getsevtime（））;//完成时间=上一个进程的完成时间+服务时间
P[i].setzhtime（P[i].getfinitime（）-P[i].getarritime（））;//周转时间=完成时间-到达时间
P[i].setqtime（（double）P[i].getzhtime（）/P[i].getsevtime（））;//带权周转时间=周转时间/服务时间
}
}doublecalaverzh（Process*P,intN）//计算平均周转时间
{
inti;
doubleaverzh;
averzh=0;
for（i=0;iaverzh+=P[i].getzhtime（）;
averzh=averzh/N;
returnaverzh;
}
doublecalaverqt（Process*P,intN）//计算平均带权周转时间
{
inti;
doubleaverqt;
averqt=0;
for（i=0;iaverqt+=P[i].getqtime（）;
averqt=averqt/N;
returnaverqt;
}
五、测试与数据分析
选择FCFS进程调度算法，输入以下进程信息：
进程名到达时间服务时间
A04
B13
C25
D33
E44
可以得到先来先服务调度算法的平均周转时间和平均带权周转时间（应为9、2.8）。
选择SPF进程调度算法，再次输入上述进程信息。
可以得到短作业优调度算法的平均周转时间和平均带权周转时间（应为8、2.1）。
选择高优先权调度算法，再次输入以上进程的信息，另外再输入每个进程的优先权
进程名优先权
A3
B1
C3
D4
E2
则得到高优先权调度算法的的平均周转时间和平均带权周转时间（应为、）。
选择基于时间片的轮转调度算法，输入时间片为1，再次输入上述进程信息，得到时间片轮转算法的的平均周转时间和平均带权周转时间。
将上述四个进程调度算法得到的平均周转时间和平均带权周转时间进行比较，可以对这四种算法的性能进行分析，对这四个进程调度算法有了更深入的理解。
六、完成的情况、简要的使用说明
本程序经过了调试，能够正常运行，并能够得到正确的结果。
但使用时应注意以下几个问题：
1、选择调度算法的时候只能输入0、1、2、3、4这五个数字，若输入其它字符将造成程序进入死循环。
2、在输入进程信息之前，应确定进程的数目，并输入。
3、进程名不限于字符，可以是任意长度的字符串。
4、本程序需要逐个输入进程的信息，对于进程数目比较多的时候会花费较长的时间。
故本程序最好用于进程数目较少的情况。
5、程序中的进程到达时间、服务时间、优先权和时间片只能是整数，没有考虑实数的情况。
七、结果分析
进入程序显示如下界面：
选择不同的调度算法，分别将测试与数据分析中的数据输入到程序中得到如下结果
八、总结
本程序的最大特色为用户可以循环不断地选择调度算法，输入进程，得到每种算法的调度结果，以便用户可以对不同的进程调度算法进行比较和分析。
本程序能够模拟四种进程调度算法，计算出每个进程的完成时间、周转时间、带权周转时和每种算法的平均周转时间、平均带权周转时间，便于加深对进程调度过程的理解，也能够更好地对四种算法的性能进行较为全面的分析。
本次课程设计首先让我对课本上的知识掌握的更加牢固，通过自己编写算法，模拟了进程调度过程，不但提高了我的编程能
升级会员 