FCFS和SJF进程调度算法实验报告
【实验题目】:编写程序,实现FCFS和SJF算法,模拟作
业调度过程,加深对作业调度的理解。
【实验内容】
实现FCFS和SJF调度算法。
– 数据结构设计(JCB,后备作业队列)
– 算法实现与模拟(排序、调度)
– 输出调度结果,展示调度过程并解释
【实验要求】
1. 设计作业控制块(JCB)的数据结构
– 应包含实验必须的数据项,如作业ID、需要的服务时间、进入系
统时间、完成时间,以及实验者认为有必要的其他数据项。
2. 实现排序算法(将作业排队)
– 策略1:按“进入系统时间”对作业队列排序(FCFS)
– 策略2:按“需要的服务时间”对作业队列排序(SJF)
3. 实现调度过程模拟
(1) 每个作业用一个JCB表示,如果模拟FCFS,按策略1将作业排队,如果模拟SJF,按策略2将作业排队
(2)选择队首的作业,将其从后备队列移出
(3) (作业运行过程,在本实验中,无需实现,可认为后备队列的
作业一但被调度程序选出,就顺利运行完毕,可以进入第4步)
(4) 计算选中作业的周转时间
(5) 进行下一次调度(去往第2步)
4.实现结果输出
– 输出作业状态表,展示调度过程
? 初始作业状态(未调度时)
? 每次调度后的作业状态
设计作业控制块(JCB)的数据结构
每个作业由一个作业控制块JCB表示,JCB可以包含如下信息:作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下: typedef struct jcb{
char name[10]; /* 作业名 */
char state; /* 作业状态 */
int ts; /* 提交时间 */
float super; /* 优先权 */
int tb; /* 开始运行时间 */
int tc; /* 完成时间 */
float ti; /* 周转时间 */
float wi; /* 带权周转时间 */
int ntime; /* 作业所需运行时间 */
char resource[10]; /* 所需资源 */
struct jcb *next; /* 结构体指针 */
} JCB;
JCB *p,*tail=NULL,*head=NULL;
作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。,组成一个后备队列等待,总是首先调度等待队列中队首的作业。
本实验采用链表的形式存放各后备队列当中的作业控制块,各个等待的作业按照提交时刻的先后次序排队。当一个作业进入系统时,就为其动态建立一作业控制块(JCB),挂入后备队列尾部。当作业调度时,从后备队列中按某种调度算法选择一作业,让其进入主存以便占用CPU执行。
每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间,这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。
程序代码:
#include<iostream.h>
#include<iomanip.h>
#define Number 5
void main()
{
int n;
int daoda[Number],fuwu[Number],i;
cout<<"请依次输入各个进程的到达时间并以空格间隔:";
for(i=0;i<Number;i++)
{
cin>>daoda[i];
}
cout<<"请依次输入各个进程的服务时间,并以空格间隔:";
for(i=0;i<Number;i++)
{
cin>>fuwu[i];
}
cout<<"请输入n=1选择FCFS或者n=2选择SJF或者n=3同时调用FCFS和SJF,n=";
cin>>n;
while(n<1||n>3){
cout<<"输入的n有误,请重新输入n,n=";
cin>>n;
}
struct statedd //声明结构
{
bool doneF,doneS;
int daoda,fuwu;
float wancheng,zhouzhuan,daiquan,wan,zhou,dai;
};
statedd process[Number];//声明结构变量,这里为数组
int timeflyF=0,timeflyS=0;//定义两个类似于秒表的变量
int j,k,l,nextproF,nextproS;
// 获取数据
for(i=0;i<Number;i++)
{
process[i].doneF = false;
process[i].doneS = false;
process[i].wancheng = 0;
process[i].zhouzhuan = 0;
process[i].daiquan = 0;
process[i].wan = 0;
process[i].zhou = 0;
process[i].dai =0;
process[i].daoda = daoda[i];
process[i].fuwu = fuwu[i];
}
// 获取最先到达的进程下标first
int first=0;
l=first;
for(i=1;i<Number;i++)
{
if(daoda[first]>daoda[i])
first=i;
}
process[first].doneF=true;
process[first].doneS=true;
process[first].wancheng = process[first].fuwu + process[first].daoda;
process[first].wan = process[first].fuwu + process[first].daoda;
timeflyF += process[first].daoda+process[first].fuwu;
timeflyS += process[first].daoda+process[first].fuwu;
// 接下去到达的进程
//*************************************************************
// fcfs ********************************************************
for(j=1;j<Number;j++)
{
nextproF = Number+1;
for(k =0 ; k<Number; k++ )
{
if( !process[k].doneF )
{
if( process[k].daoda <= timeflyF ) // 到达
{
if( nextproF ==Number+1)
nextproF = k;
else
{
if( process[nextproF].daoda > process[k].daoda )
nextproF = k; //获取到达时刻最先的进程
}//else
}//if2
}//if1
}//for
// 处理
process[nextproF].wancheng = process[nextproF].fuwu + timeflyF;
timeflyF += process[nextproF].fuwu;
process[nextproF].doneF=true;
} // circle2
// SJF **********************************************
for(j=1;j<Number;j++)
{
nextproS = Number+1;
for(k=0 ; k<Number; k++ )
{
if(!process[k].doneS)
{
if( process[k].daoda <= timeflyS ) // 到达
{
if( nextproS ==Number+1 )
nextproS = k;
else
{
if( process[nextproS].fuwu > process[k].fuwu )
nextproS = k; //获取服务时间最小的进程
}//else
}//if2
}//if1
}//for
// 处理
process[nextproS].wan = process[nextproS].fuwu + timeflyS;
timeflyS += process[nextproS].fuwu;
process[nextproS].doneS=true;
} // circle2
//****************************************************************
float Fz=0,Fdq=0,Sz=0,Sdq=0;//
for(i=0;i<Number;i++)
{ //----------------------------------------------------
process[i].zhouzhuan=process[i].wancheng-process[i].daoda;
Fz += process[i].zhouzhuan;
process[i].daiquan=process[i].zhouzhuan/process[i].fuwu;
Fdq += process[i].daiquan;
//----------------------------------------------------
process[i].zhou=process[i].wan-process[i].daoda;
Sz += process[i].zhou;
process[i].dai=process[i].zhou/process[i].fuwu;
Sdq += process[i].dai;
}
//=========================输出==================================
//-------------------------------------------------------------------
if(n==1||n==3){
cout<<"\t"<<endl;
cout<<"FCFS:"<<endl;
for(i=0;i<Number;i++)
{
if(i<1)
{
cout<<"时刻"<<l<<":进程"<<i+1<<"在运行"<<endl;
}
else
{
cout<<"时刻"<<process[i-1].wancheng<<":进程"<<i+1<<"在运行"<<endl;
}
}
cout<<setw(10)<<"进程ID"<<" ";
cout<<setw(10)<<"完成时间"<<" ";
cout<<setw(10)<<"周转时间"<<" ";
cout<<setw(10)<<"带权周转时间"<<" "<<endl;
for(i=0;i<Number;i++)
{
cout<<setw(10)<<i+1<<" ";
cout<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<process[i].wancheng<<" ";
cout<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<process[i].zhouzhuan<<" ";
cout<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<process[i].daiquan<<" "<<endl;
}
cout<<"平均周转时间为: "<<setiosflags(ios::fixed)<<setprecision(2)<<Fz/Number<<endl;
cout<<"平均带权周转时间为:"<<setiosflags(ios::fixed)<<setprecision(2)<<Fdq/Number<<endl;
}
//-------------------------------------------------------------------
if(n==2||n==3){
cout<<"\t"<<endl;
cout<<"SJF:"<<endl;
for(i=0;i<Number;i++)
{
if(i<1)
{
cout<<"时刻"<<l<<":进程"<<i+1<<"在运行"<<endl;
}
else
{
cout<<"时刻"<<process[i-1].wan<<":进程"<<i+1<<"在运行"<<endl;
}
}
cout<<setw(10)<<"进程ID"<<" ";
cout<<setw(10)<<"完成时间"<<" ";
cout<<setw(10)<<"周转时间"<<" ";
cout<<setw(10)<<"带权周转时间"<<" "<<endl;
for(i=0;i<Number;i++)
{
cout<<setw(10)<<i+1<<" ";
cout<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<process[i].wan<<" ";
cout<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<process[i].zhou<<" ";
cout<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<process[i].dai<<" "<<endl;
}
cout<<"平均周转时间为: "<<setiosflags(ios::fixed)<<setprecision(2)<<Sz/Number<<endl;
cout<<"平均带权周转时间为:"<<setiosflags(ios::fixed)<<setprecision(2)<<Sdq/Number<<endl;
cout<<"\t"<<endl;
}
}
实例截图:
五个进程,到达时间分别为8,21,9,18,6
服务时间分别为10,4,16,22,9
设置选择量n,
当n=1时,选择FCFS
当n=2时,选择SJF
当n=3时,同时分别调用FCFS和SJF
n不为1或2或3时提示错误,重新输入n;
1-FCFS 算法
2-SJF算法
3同时调用FCFS和SJF