进程调度算法模拟
专业： XXXXX
学号： XXXXX
姓名： XXX
实验日期： 20XX 年 XX 月 XX 日
一、实验目的
通过对进程调度算法的模拟加深对进程概念和进程调度算法的理解。
二、实验要求
编写程序实现对 5 个进程的调度模拟， 要求至少采用两种不同的调度算 法分别进行模拟调度。
三、实验方法内容
1. 算法设计思路 将每个进程抽象成一个控制块 PCB， PCB 用一个结构体描述。
构建一个进程调度类。将进程调度的各种算法分装在一个类中。类中存 在三个容器， 一个保存正在或未进入就绪队列的进程， 一个保存就绪的进程， 另 一个保存已完成的进程。还有一个 PCB 实例。主要保存正在运行的进程。类中 其他方法都是围绕这三个容器可以这个运行中的 PCB 展开。
主要用到的技术是 STL 中的 vector 以维护和保存进程容器、就绪容器、 完成容器。
当程序启动时，用户可以选择不同的调度算法。然后用户从控制台输入 各个进程的信息， 这些信息保存到进程容器中。
进程信息输入完毕后， 就开始了 进程调度，每调度一次判断就绪队列是否为空， 若为空则系统时间加一个时间片。
判断进程容器中是否有新的进程可以加入就绪队列。
2. 算法流程图
主程序的框架：
进程调度过程：
开始
开始
3. 算法中用到的数据结构
struct fcfs{ //先来先服务算法从这里开始
char name[10];
float arrivetime;
float servicetime;
float starttime;
float finishtime;
float zztime;
float dqzztime;
}; //定义一个结构体，里面包含的有一个进程相关的信息
4. 主要的常量变量
vector <
PCB>m_ProcessQueue; // 进程输入队列
vector
<PCB>m_WaitQueue; // 进程就绪队列
vector
vector
<PCB>m_FinishQueue ; // 完成队列 <PCB>:: iterator m_iter ; // 迭代器
PCBm
_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 <cstdlib>
#include <iostream>
#include<iomanip>
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<<endl; 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<N;k++)
{
printf("-->%s",p[k].name);
}
cout<<endl;
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<p[j].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<<endl; 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<N1;k++) {printf("-->%s",p[k].name);} cout<<endl;
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<p[j].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<N1-1;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<m+i;k++)
{
if(p[k+1].servicetime<min) {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<<endl; cout<<endl;
cout<<"\t"<<"|| <<<<<<<<<<<< 欢 <<<<<<<<<<< >>>>>>>>>>>> 迎 >>>>>>>>>>> ||"<<endl ;
cout<<"\t"<<"||
||"<<endl ;
cout<<"\t"<<"||"<<"\t 进 程 调 度 算 法 模 拟 "<<"\t\t"<<"||"<<endl;
cout<<"\t"<<"||
||"<<endl ;
cout<<"\t"<<"||"<<"\t\t 1. 先 来 先 服 务 调 度 算 法
"<<"\t\t"<<"||"<<endl;
cout<<"\t"<<"||
||"<<endl ;
cout<<"\t"<<"||"<<"\t\t 2.最 短进 程优 先调度 算法
"<<"\t\t"<<"||"<<endl;
cout<<"\t"<<"||
||"<<endl ;
cout<<"\t"<<"|| <<<<<<<<<<<<<<<<<<<<<<<<< 您 >>>>>>>>>>>>>>>>>>>>>>>>> ||"<<endl ;
cout<<endl;
cout<<endl;
cout<<"\t\t 请输入您的选择( 1/2)："; cse1=getchar();
if(cse1<'1'||cse1>'2') cout<<"你的输入有错！ "<<endl;
else
break;
}
return cse1;
}
int main(int argc, char *argv[])
{
while(1)
{
switch(menu())
{
case '1':
int N;
cout<<endl;
cout<<endl;
printf("\t\t<<---!!!@@@ 先来先服务调度 算法@@@!!!--->>\n");
cout<<endl;
printf(" 输入进程数目 :");
scanf("%d",&N);
input(a,N);
FCFS(a,N);
case '2': int N1; cout<<endl; cout<<endl; printf("\t\t<<---!!!@@@ 最短进程优先调
度算法 @@@!!!--->>\n");
cout<<endl; printf(" 输入进程数目 : "); scanf("%d",&N1); input(a1,N1);
sjf *b=a1; sjf *c=a1; sjff(b,N1); getchar();
}
} system("PAUSE"); return EXIT_SUCCESS;
}
五、实验结果
1. 执行结果
1. 执行结果
2. 结果分析 先来先服务调度算法就是根据进程达到的时间为依据，哪一个进程先来 那么该进程就会先执行； 最短进程优先调度算法则是以每个进程执行所需时 间长短为依据，某一个进程执行所需花的时间要短些那么该进程就先执行。
以上就是本次进程调度实验的依据。
六、实验总结
通过本次实验了解到算法很重要， 又更加明白算法本身可以节约时间， 而且不同的 函数之间在调用的时候要注意很多的问题。