进程调度算法模拟
专业:计算机科学与技术
学号:121404126
姓名:朱永润
实验日期:2015年1月7日
一、实验目的
通过对进程调度算法的模拟加深对进程概念和进程调度算法的理解。
二、实验要求
编写程序实现对5个进程的调度模拟,要求至少采用两种不同的调度算法分别进行模拟调度。
三、实验方法内容
1.算法设计思路
将每个进程抽象成一个控制块PCB,PCB用一个结构体描述。
构建一个进程调度类。将进程调度的各种算法分装在一个类中。类中存在三个容器,一个保存正在或未进入就绪队列的进程,一个保存就绪的进程,另一个保存已完成的进程。还有一个PCB实例。主要保存正在运行的进程。类中其他方法都是围绕这三个容器可以这个运行中的PCB展开。
主要用到的技术是STL中的vector以维护和保存进程容器、就绪容器、完成容器。
当程序启动时,用户可以选择不同的调度算法。然后用户从控制台输入各个进程的信息,这些信息保存到进程容器中。进程信息输入完毕后,就开始了进程调度,每调度一次判断就绪队列是否为空,若为空则系统时间加一个时间片。判断进程容器中是否有新的进程可以加入就绪队列。
2.算法流程图
主程序的框架:
开始
选择调度算法void FCFS();//先来先服务
void SJF();//最短进程优先调度void RR();//简单时间片轮转void PD();//最高优先数优先
输入进程信息
将输入容器中以满足进入条件的进程调入就绪队列
判断就绪容器和输入容器是否为空!processScheduler.m_WaitQueue.empty()|| !processScheduler.m_ProcessQueue.empt() void ProcessQueueProcess();
//查看当前时间下,有无进程加
入。若有则把该进程调入就绪队列
void PCBInput();//输入进程信息
Y
打印各进程信息
进行统计计算周转
时间等
结束void PCBDisplay();
//打印当前状况下。就绪队列、完成队列、运行中的进程信息
void SchedulerStatistics();
//调度统计,计算周转时间等
按照选择的算法开
始选择就绪队列的
进程开始执行
void ProcessSelect();
//若当前就绪队列不为空则根
据选择的调度算法开始调度,否则,系统时间加一个时间片.以等待新的进程到
进程调度过程:
开始
判断就绪队列是否为空
非空
为空
根据设定的调度算法从就绪队列中调入一个进程并执行(此时进程从就绪队列中删除,赋值到表示运行中的成员变量中)
void FCFS ();//先来先服务
void SJF ();//最短进程优先调度void RR ();//简单时间片轮转void PD ();//最高优先数优先
if (m_WaitQueue .empty ())
选入的进程状态是否为“完成”
Y
设置进程完成时间,将该进程放入
完成队列
进程未完成,将进程优先数减一,并放回到就绪队列中让系统等待一个时
间片
是否达到该进程停止运行的条件
如进程已完成,或者分得的时间片个数已到
N
进程运行一个时间片Y
结束
ProcessRun ()
TimePast ()
vector
vector
3. 算法中用到的数据结构
struct fcfs{ //先来先服务算法从这里开始 char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime;
}; //定义一个结构体,里面包含的有一个进程相关的信息
4. 主要的常量变量
vector
PCB m_runProcess ;//运行中的进程
int m_ProcessCount;//进程数
float m_RunTime;//运行时间
int m_tagIsRun;//是否在运行标志。表示正在运行,表示没有
float m_TimeSlice;//时间片大小
int m_TimeSliceCount;//指时间片轮转中一次分到的时间片个数
char m_SchedulerAlgorithm;//调度算法
5.主要模块
void PCBInput();//输入进程信息
void PCBSort();//对进程控制块按照优先级排序(采用冒泡排序)
void ProcessSelect();//若当前就绪队列不为空则根据选择的调度算法开始调度。否则,系统时间加.以等待新的进程到来
void PCBDisplay();//打印当前状况下。就绪队列、完成队列、运行中的进程信息
void ProcessRun();//进程运行一次。运行时间加个时间片。并判断进程是否达到完成条件。若是则ProcessStatus='f'.否则为'w';
void ProcessQueueProcess();//查看当前时间下,有无进程加入。若有则把该进程调入就绪队列void ProcessDispatch();//进程分派,进程执行完成后决定进程该进入哪个队列(就绪、完成) void TimePast(){ m_RunTime +=m_TimeSlice; ProcessQueueProcess();}//当前系统时间加个时间片,并检查是否有新的进程加入
void SchedulerStatistics();//调度统计,计算周转时间等
void FCFS();//先来先服务
void SJF();//最短进程优先调度
void RR();//简单时间片轮转
void PD();//最高优先数优先
四、实验代码
#include
#include
#include
using namespace std;
struct fcfs{ //先来先服务算法从这里开始
char name[10];
float arrivetime;
float servicetime;
float starttime;
float finishtime;
float zztime;
float dqzztime;
}; //定义一个结构体,里面包含的有一个进程相关的信息
fcfs a[100];
void input(fcfs *p,int N)
{
int i;
cout< printf(" 请您输入进程的名字到达时间服务时间: (例如: a 0 100)\n\n"); for(i=0;i<=N-1;i++) { printf(" 请您输入进程%d的信息:\t",i+1); scanf("\t\t\t%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime); } } void Print(fcfs *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N) { int k; printf("\n\n调用先来先服务算法以后进程运行的顺序是: "); printf("%s",p[0].name); for(k=1;k { printf("-->%s",p[k].name); } cout< printf("\n 具体进程调度信息:\n"); printf("\t进程名到达时间服务时间开始时间结束时间周转时间带权周转时间\n"); for(k=0;k<=N-1;k++) { printf("\t%s\t%-.2f\t %-.2f\t %-.2f\t %-.2f\t %-.2f\t %-.2f\n",p[k].n ame,p[k].arrivetime, p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } getchar(); //此处必须要有这个函数,否则就看不到显示器上面的输出,可以看到的结果只是一闪而过的一个框剪 } void sort(fcfs *p,int N) //排序 { for(int i=0;i<=N-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { fcfs temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(fcfs *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N) //运行阶段 { int k; for(k=0;k<=N-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} } for(k=0;k<=N-1;k++) { p[k].zztime=p[k].finishtime-p[k].arrivetime; p[k].dqzztime=p[k].zztime/p[k].servicetime; } } void FCFS(fcfs *p,int N) { float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N); deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); getchar(); } //先来先服务算法到此结束 struct sjf{//最短进程优先调度算法从这里开始 char name[10]; float arrivetime; //到达时间 float servicetime; //运行时间 float starttime; //开始时间 float finishtime; //完成时间 }; sjf a1[100]; void input(sjf *p,int N1)//进程信息输入 { int i; cout< printf(" 请您输入进程的名字到达时间服务时间: (例如: a 0 100)\n"); for(i=0;i<=N1-1;i++) { printf(" 请您输入进程%d的信息:\t",i+1); scanf("\t\t\t%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime); } } void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,int N1)//最终结果输出 { int k; printf("\n\t调用最短进程优先调度算法以后进程的调度顺序为:"); printf("%s",p[0].name); for(k=1;k {printf("-->%s",p[k].name);} cout< printf("\n给个进程具体调度信息如下:\n"); printf("\n\t进程名\t到达时间\t运行时间\t开始时间\t完成时间\n"); for(k=0;k<=N1-1;k++) { printf(" \t%s\t %-.2f\t\t %-.2f\t\t %-.2f\t\t %-.2f\t\n",p[k].name,p[k].arrivetime, p[k].servicetime,p[k].starttime,p[k].finishtime); } getchar(); } void sort(sjf *p,int N1)//排序 { for(int i=0;i<=N1-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { sjf temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,int N1)//运行阶段 { int k; for(k=0;k<=N1-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+float(p[k].servicetime)/60;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+float(p[k].servicetime)/60;} } } void sjff(sjf *p,int N1) { float arrivetime=0,servicetime=0,starttime=0,finishtime=0; sort(p,N1); for(int m=0;m {if(m==0) p[m].finishtime=p[m].arrivetime+float(p[m].servicetime)/60; else p[m].finishtime=p[m-1].finishtime+float(p[m].servicetime)/60; int i=0; for(int n=m+1;n<=N1-1;n++) { if(p[n].arrivetime<=p[m].finishtime) i++; } float min=p[m+1].servicetime; int next=m+1; for(int k=m+1;k { if(p[k+1].servicetime {min=p[k+1].servicetime; next=k+1;} } sjf temp; temp=p[m+1]; p[m+1]=p[next]; p[next]=temp; } deal(p,arrivetime,servicetime,starttime,finishtime,N1); Print(p,arrivetime,servicetime,starttime,finishtime,N1); getchar(); }//最短进程优先调度算法到这里结束 char menu()//用来输出相关信息的函数 { char cse1; while(1) { system("cls"); fflush(stdin); cout< cout< cout<<"\t"<<"|| <<<<<<<<<<<<欢<<<<<<<<<<< >>>>>>>>>>>>迎>>>>>>>>>>> ||"< cout<<"\t"<<"|| ||"< cout<<"\t"<<"||"<<"\t 进程调度算法模拟"<<"\t\t"<<"||"< cout<<"\t"<<"|| ||"< cout<<"\t"<<"||"<<"\t\t 1.先来先服务调度算法 "<<"\t\t"<<"||"< cout<<"\t"<<"|| ||"< cout<<"\t"<<"||"<<"\t\t 2.最短进程优先调度算法"<<"\t\t"<<"||"< cout<<"\t"<<"|| ||"< cout<<"\t"<<"|| <<<<<<<<<<<<<<<<<<<<<<<<<您>>>>>>>>>>>>>>>>>>>>>>>>> ||"< cout< cout< cout<<"\t\t 请输入您的选择(1/2):"; cse1=getchar(); if(cse1<'1'||cse1>'2') cout<<"你的输入有错!"< else break; } return cse1; } int main(int argc, char *argv[]) { while(1) { switch(menu()) { case '1': int N; cout< cout< printf("\t\t<<---!!!@@@先来先服务调度算法@@@!!!--->>\n"); cout< printf("输入进程数目:"); scanf("%d",&N); input(a,N); FCFS(a,N); case '2': int N1; cout< cout< printf("\t\t<<---!!!@@@最短进程优先调 度算法@@@!!!--->>\n"); cout< printf("输入进程数目: "); scanf("%d",&N1); input(a1,N1); sjf *b=a1; sjf *c=a1; sjff(b,N1); getchar(); } } system("PAUSE"); return EXIT_SUCCESS; } 五、实验结果 1.执行结果 2.结果分析 先来先服务调度算法就是根据进程达到的时间为依据,哪一个进程先来那么该进程就会先执行;最短进程优先调度算法则是以每个进程执行所需时间长短为依据,某一个进程执行所需花的时间要短些那么该进程就先执行。 以上就是本次进程调度实验的依据。 六、实验总结 通过本次实验了解到算法很重要,又更加明白算法本身可以节约时间,而且不同的函数之间在调用的时候要注意很多的问题。