作 业 调 度 实 验
班级：网络081 姓名：甘春泉 学号：200800824126
实验三 作业调度实验
一、实验目的
加深作业概念的理解，深入了解多道程序设计系统中如何组织作业、管理作业和调度作业，加深对作业调度算法的理解。
二、实验主要内容
编写程序完成批处理系统中的作业调度，要求实现先来先服务、短作业优先、最高响应比优先三种作业调度算法（采用非剥夺方式调度），一组作业完成后要计算并打 印这组作业的平均周转时间、带权平均周转时间。实验具体内容包括：首先确定作业控制块的内容，祖业控制块的组成方式；然后完成作业调度；最后编写主函数对 所作的工作进行测试。
三、实验原理
操作系统根据允许并行工作的道数和一定的算法从系统中选取若干作业把它们装入主存储器，使它们有机会获得处理器运行，这项工作称为作业调度。在本实验中采用非剥夺方式调度，作业一旦投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。
1） 先来先服务算法（FCFS）
先来先服务调度算法即按作业提交的先后次序进行调度。总是首先调度在系统中等待时间最长的作业，让其进入主存储器以便占用处理器运行。
2）短作业优先算法 （SJF）
短作业优先算法总是提交要求运行时间最短的作业，让其进入主存储器以便占用处理器运行。
3） 最高响应比调度算法（HRN）
最高响应比调度算法总是在作业等待队列中选择响应比最高的作业，让其进入主存储器以便占用处理器运行。
响应比＝响应时间/要求服务时间＝（等待时间＋要求服务时间）/要求服务时间
四、实验方法与步骤
作业调度的实现主要考虑两个方面，第一，如何将系统中的作业组织起来；另一个是如何进行作业调度。
1）设计作业队列的数据结构
每个作业由一个作业控制块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执行。
每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。
2） 作业调度算法
作业调度算法的关键是在已有的作业后备队列上按照一定的规则选择一个作业，如何在已有的数据结构上进行操作的问题。
a) 先来先服务算法（FCFS）
每次提交作业总是选择后备队列的对首作业，实验中用head指向对首JCB。有作业进入系统，则挂入后备队列对尾。对首JCB进入内存后执行，在实验中由于没有真正的内存，我们用程序模拟作业执行，需修改该作业的JCB的相关信息即可，如状态为state置为“R”,开始执行时间tb赋值为当前时间time。（p->state=R;p->tb=time;）该作业执行完成后，需修改其状态位state为“F”，并计算该作业的相关信息：
计算周转时间： p->ti=(float)(p->tc-p->ts);
计算带权周转时间：p->wi=(float)(p->ti/p->ntime);
计算平均周转时间 ：eti+=p->ti;
计算带权平均周转时间：ewi+=p->wi;
并输出当前系统中各作业的信息 print(p,m);
b）短作业优先算法（SJF）
提交作业时，从后备队列对首开始向对尾扫描，查找状态为“W”且要求系统运行时间最短（p->ntime最小）的作业，选中将其调入内存。同FCFS算法，在实验中由于没有真正的内存，我们用程序模拟作业执行，需修改该作业的JCB的相关信息。该作业执行完成后，需修改其状态位state为“F”，计算该作业的相关信息和输出当前系统中各作业的信息。
c)最高响应比调度算法（HRN）
提交作业时，从后备队列对首开始向对尾扫描，查找状态为“W”且响应比最高（p->super最大）的作业，选中将其调入内存。同FCFS算法，在实验中由于没有真正的内存，我们用程序模拟作业执行，需修改该作业的JCB的相关信息。该作业执行完成后，需修改其状态位state为“F”，计算该作业的相关信息和输出当前系统中各作业的信息。
五、核心代码：
void inital(){
char na[10];
int ts1;
int ntime1;
char resoure1[10];
cout<<"Input jcb num: ";
cin>>n;
cin.ignore ();
cout<<"Input"<<endl;
cout<<"name ts ntime resource ";
for(int i=0;i<n;i++){
p=getjcb(JCB);
cin>>na>>ts1>>ntime1>>resoure1;
cin.ignore ();
strcpy(p->name,na);
p->ts=ts1;
p->ntime=ntime1;
strcpy(p->resource,resoure1);
p->state='W';
p->next=NULL;
if(head==NULL)
head=tail=p; //队列为空则将新结点作为队列的第一结点
else{//队列不空则将新结点插入到队列尾部
tail->next=p;
tail=p;}}}/*从文件中读取初始数据*/
void fileinput(){
int i;
ifstream ifile("os2.txt",ios::in|ios::out);//打开文件
if(!ifile)//读取文件失败
{ cout<<"open error! ";
return;}
ifile>>n; //读入PCB个数n
for(i=0;i<n;i++){
p=getjcb(JCB);
ifile>>p->name>>p->ts>>p->ntime>>p->resource; // 读文件
p->state='W';p->super=0;p->next=NULL;
if(head==NULL)
head=tail=p;
else
{tail->next=p;tail=p;}
} ifile.close(); //关闭文件
}/*输出作业队列中运行状态、等待状态、完成状态的作业的JCB信息*/
void print(JCB *pr,int m)
{JCB *p;
cout<<"time="<<time<<endl;/*输出运行状态的进程的信息*/
if(m==3)// m=3时候为最高响应比
{ cout<<setw(7)<<"name"<<setw(7)<<"state"<<setw(7)<<"ts"<<setw(7)<<"ntime"<<setw(7)<<"super"<<setw(10)<<"resoure"<<setw(7)
<<"tb"<<setw(7)<<"tc"<<setw(10)<<"ti"<<setw(10)<<"wi ";
cout<<setw(7)<<pr->name<<setw(7)<<pr->state
<<setw(7)<<pr->ts<<setw(7)<<pr->ntime
<<setw(7)<<setiosflags(ios::fixed)<<setprecision(2)<<pr->super <<setw(10)<<pr->resource<<setw(7)<<pr->tb<<setw(7)<<pr->tc
<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<pr->ti//设置固定浮点表示格式，小数点后精确两位
<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<pr->wi<<endl; }else{
cout<<setw(7)<<"name"<<setw(7)<<"state"<<setw(7)<<"ts"<<setw(7)<<"ntime" <<setw(10)<<"resoure"<<setw(7)<<"tb"
<<setw(7)<<"tc"<<setw(10)<<"ti"<<setw(10)<<"wi ";
cout<<setw(7)<<pr->name<<setw(7)<<pr->state
<<setw(7)<<pr->ts<<setw(7)<<pr->ntime
<<setw(10)<<pr->resource<<setw(7)<<pr->tb <<setw(7)<<pr->tc <<setw(10)<<setiosflags(ios::fixed)<< setprecision(2)<<pr->ti <<setw(10)<<setiosflags(ios::fixed)<<
setprecision(2)<<pr->wi<<endl;}
/*输出作业队列中等待状态的作业的JCB信息*/
p=head;
do{ if(p->state=='W')
if(m==3)
{ // m=3时候为最高响应比
cout<<setw(7)<<p->name<<setw(7)<<p->state<<setw(7)<<p->ts<<setw(7)
<<p->ntime<<setw(7)<<p->super<<setw(10)<<p->resource<<endl; }else{
cout<<setw(7)<<p->name<<setw(7)<<p->state<<setw(7)<<p->ts <<setw(7)<<p->ntime<<setw(10)<<p->resource<<endl;} p=p->next;
}while(p!=NULL);/*输出作业队列中完成状态的作业的JCB信息*/
p=head;
do{ if(p->state=='F')
if(m==3){
cout<<setw(7)<<p->name<<setw(7)<<p->state
<<setw(7)<<p->ts<<setw(7)<<p->ntime
<<setw(7)<<setiosflags(ios::fixed)<<setprecision(2)<<p->super <<setw(10)<<p->resource<<setw(7)<<p->tb<<setw(7)<<p->tc <<setw(10)<<setiosflags(ios::fixed)<<
setprecision(2)<<pr->ti
<<setw(10)<<setiosflags(ios::fixed)<<
setprecision(2)<<pr->wi<<endl;
}else{
cout<<setw(7)<<p->name<<setw(7)<<p->state
<<setw(7)<<p->ts<<setw(7)<<p->ntime
<<setw(10)<<p->resource <<setw(7)<<p->tb<<setw(7)<<p->tc <<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<pr->ti
<<setw(10)<<setiosflags(ios::fixed)<<setprecision(2)<<pr->wi<<endl; }p=p->next;
}while(p!=NULL);}
/*运行当前进程并输出当前作业队列中个作业JCB的信息*/
void running(JCB *p,int m){
p->tb=time; //作业开始运行时间为当前时间
p->state='R'; //作业状态修改为R
p->tc=p->tb+p->ntime; //计算作业完成时间
p->ti=(float)(p->tc-p->ts); //计算作业周转时间
p->wi=(float)(p->ti/p->ntime);//计算作业带权周转时间
eti+=p->ti; //计算平均周转时间
ewi+=p->wi; //计算带权平均周转时间
print(p,m); //输出当前系统中各作业的信息
time+=p->ntime; //修改当前时间
p->state='F'; //作业*P运行后修改其状态为F
cout<<p->name<<" has been finished! press any key to continue... "; cin.get();}
/*计算平均周转时间和带权平均周转时间*/
void last(){
eti/=n; // 平均周转时间
ewi/=n; //带权平均周转时间
cout<<"eti="<<eti<<endl
<<"ewi="<<ewi<<endl;}
/*计算作业队列当中等待状态的作业的响应比*/
void super(){
JCB *padv;
padv=head;
do{ if(padv->state=='W'&&padv->ts<=time)
padv->super=(float)(time-padv->ts+padv->ntime)/padv->ntime;//计算作业的响应比 padv=padv->next;
}while(padv!=NULL);}/*最高响应比调度算法*/
void hrn(int m){
JCB *min;
int i,iden;
for(i=0;i<n;i++)/*n个作业需要调度n次*/
{ p=min=head;
iden=1;
super(); /*计算当前作业队列中等待状态的作业的响应比*/
do{ /*do-while语句在每次调度时找等待作业中响应比最高的作业，用min指向*/ if(p->state=='W'&&p->ts<=time)
if(iden)
{min=p;iden=0; //用min指向第一个等待状态的作业
}else if(p->super>min->super) min=p;//用min指向响应比最高的结点 p=p->next;
}while(p!=NULL);
if(iden)
{ //iden=1时表示iden的值没有改变，队列中没有等待状态的作业 i--;
time++;
cout<<" time="<<time<<" no JCB submib...wait..."<<endl; if(time>1000){cout<<" runtime is too
long...error..."<<endl;cin.get();}
} else
{ //iden=0时表示队列中有等待状态的作业，min指向该作业并运行该作业 running(min,m);}}}/*最短作业优先调度算法*/
void sjf(int m){
JCB *min;
int i,iden;
for(i=0;i<n;i++){
p=min=head;iden=1;
do{ if(p->state=='W'&&p->ts<=time) //等待状态且到达时间小于当前时间 if(iden)
{min=p;iden=0;}
else if(p->ntime<min->ntime) min=p;
p=p->next;
}while(p!=NULL) ;
if(iden)
{ i--;
cout<<" time="<<time<<" no JCB submib...wait..."<<endl;
time++;
if(time>100){cout<<" runtime is too long...error"<<endl;cin.get();} }else
{running(min,m);}
}}/*先来先服务调度算法*/
void fcfs(int m){
int i,iden;
cout<<" the jcb is runing..."<<endl;
for(i=0;i<n;i++){
p=head;iden=1;
do{ if(p->state=='W'&&p->ts<=time)iden=0;
if(iden)p=p->next;
}while(p!=NULL&&iden);
if(iden) { i--;
cout<<" time="<<time<<" no JCB submib...wait..."<<endl;
time++;
if(time>100)
{cout<<" runtime is too long...error"<<endl;cin.get();}
} else
{running(p,m);}
}