实验一、作业调度模拟程序实验
13物联网工程 刘烨 201306104146
一、 实验目的
（1）加深对作业调度算法的理解；
（2）进行程序设计的训练。
二、 实验内容和要求
用高级语言编写一个或多个作业调度的模拟程序。
单道批处理系统的作业调度程序。作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所运行的时间等因素。
作业调度算法：
1) 采用先来先服务（FCFS）调度算法，即按作业到达的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。
2) 短作业优先 (SJF) 调度算法，优先调度要求运行时间最短的作业。
3) 响应比高者优先(HRRN)调度算法，为每个作业设置一个优先权(响应比)，调度之前先计算各作业的优先权，优先数高者优先调度。RP (响应比)＝ 作业周转时间 / 作业运行时间=1+作业等待时间/作业运行时间
每个作业由一个作业控制块JCB表示，JCB可以包含以下信息：作业名、提交（到达）时间、所需的运行时间、所需的资源、作业状态、链指针等等。
三、 实验方法、步骤及结果测试
- 源程序名：实验二 修改版.c
可执行程序名：修改版.exe
- 原理分析及流程图
本次实验主要用了结构体数组来实现。首先定义一个JCB模块用于存放作业信息，如到达时间，运行时间等。后来各个函数分别实现相应的作业调度。其中用到冒泡排序将作业按到达时间或者运行时间排序。
- 主要程序段及其解释：
#include<stdio.h>
#include <stdlib.h>
int i,k,num,m,n;
#define N 24
struct JCB{
char name[10]; //作业名
float arrive; //作业提交时间
float run; //作业运行时间
float start; //开始时间
float finish; //完成时刻
float zhouzhuan; //周转时间
float weight; //带权周转时间
}jcb[N],temp;
void input() //用户输入模块
{
int i;
do{
printf(" 请输入作业数(2-24):");
scanf("%d",&num);
printf(" ");
if(num<2||num>24)
{
printf(" 请重新输入! ");
}
}
while(num<2||num>24);
for(i=0;i<num;i++){
printf(" 第%d个作业名:",i+1);
scanf("%s",&jcb[i].name);
printf(" 请输入作业提交时间:");
scanf("%f",&jcb[i].arrive);
printf(" 请输入作业运行时间:");
scanf("%f",&jcb[i].run);
printf(" ");
}
}
void output() //输出模块
{
float numT=0;
float numW=0;
float avgT=0; //平均周转时间
float avgW=0; //平均带权作业周转时间
printf("----------------------------------------------------------------------- ");
printf(" 作业名 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 ");
for(i=0;i<num;i++)
{
printf(" %-8s%-10.2f%-10.2f%-10.2f%-10.2f%-10.2f%-10.2f",jcb[i].name,jcb[i].arrive,jcb[i].run,jcb
[i].start,jcb[i].finish,jcb[i].zhouzhuan,jcb[i].weight);
printf(" ");
numT=numT+jcb[i].zhouzhuan;
numW=numW+jcb[i].weight;
}
printf("----------------------------------------------------------------------- ");
avgT=numT/num;
avgW=numW/num;
printf("平均作业周转时间：%.2f ",avgT);
printf(" ");
printf("平均带权作业周转时间：%.2f ",avgW);
printf(" ");
}
float addallruntime()//得到所有作业运行时间
{
int i;
float allruntime=0.0;
for(i=0;i<num;i++)
{
allruntime=allruntime+jcb[i].run;
}
return allruntime;
}
void fcfsrunning()
{
for(k=0;k<num;k++)
{
if(k==0)/*运行第一个作业*/
{
jcb[k].start=jcb[k].arrive;
jcb[k].finish=jcb[k].arrive+jcb[k].run;
}
else
{
if(jcb[k].arrive>=jcb[k-1].finish)/*当前作业运行完，但后面作业没到达*/
{
jcb[k].start=jcb[k].arrive;
jcb[k].finish=jcb[k].arrive+jcb[k].run;
}
else/*当前作业没运行完，后面作业已到达*/
{
jcb[k].start=jcb[k-1].finish;
jcb[k].finish=jcb[k-1].finish+jcb[k].run;
}
}
}
for(k=0;k<num;k++)
{
jcb[k].zhouzhuan=jcb[k].finish-jcb[k].arrive;
jcb[k].weight=jcb[k].zhouzhuan/jcb[k].run;
}
}
void FCFS() //先来先服务
{
int i,j;
for(j=0;j<num;j++) //冒泡排序，按到达时间排序
{
for(i=0;i<num-j-1;i++)
{
if(jcb[i].arrive>jcb[i+1].arrive)
{
temp=jcb[i];
jcb[i]=jcb[i+1];
jcb[i+1]=temp;
}
}
}
fcfsrunning();
output();
void SJF(float allruntime) //非抢占
{
float mintime=0; struct JCB jtemp={0};
int min=0;
int startwork=0;
float i;
int k;
for (i=0;i<allruntime;)
{
mintime=jcb[startwork].run;//假设一个剩余时间的最小值
for(k=startwork;k<num;k++)
{
if(jcb[k].run<=mintime&&jcb[k].arrive<=i)
{
mintime=jcb[k].run;
min=k;
}
}
jcb[min].start=i;
jcb[min].finish=jcb[min].start+jcb[min].run;
jcb[min].zhouzhuan=jcb[min].finish-jcb[min].arrive;
jcb[min].weight=jcb[min].zhouzhuan/jcb[min].run;
jtemp=jcb[startwork];
jcb[startwork]=jcb[min];
jcb[min]=jtemp;
startwork++;
i=i+mintime;
}
output();
}
void HRRF(float allruntime)
{
float maxrb=0;
struct JCB jtemp={0};
int z=0;
float time=0;
int startwork=0;
float i;
int k;
for(i=0;i<allruntime;)
{
maxrb=(i-jcb[startwork].arrive)/jcb[startwork].run+1;//假设是最高响应比
for(k=startwork;k<num;k++)
{
if(jcb[k].arrive<=i&&(i-jcb[k].arrive)/jcb[k].run+1>=maxrb)//若此作业的最高响应比更高，则将其记为更高
{
time=jcb[k].run;
z=k;
}
}
jcb[z].start=i;
jcb[z].finish=jcb[z].start+jcb[z].run;
jcb[z].zhouzhuan=jcb[z].finish-jcb[z].arrive;
jcb[z].weight=jcb[z].zhouzhuan/jcb[z].run;
jtemp=jcb[startwork];
jcb[startwork]=jcb[z];
jcb[z]=jtemp;
startwork++;
i=i+time;
}
output();
}
main()
{
int n;
float allruntime=0.0;
input();
allruntime=addallruntime();
do{
printf(" 作业调度模拟程序 ");
printf("---------------------------------------------------------------- ");
printf(" 请选择调度算法(1~3)： ");
printf(" 1:FCFS(先来先服务) 2:SJF(短作业优先) 3:HRRF(最高响应比优先) 0:exit(退出) ");
scanf("%d",&n);
if(n!=0&&n!=1&&n!=2&&n!=3)
{
printf(" 请重新输入!! ");
}
switch(n)
{
case 1:FCFS(); break;
case 2:SJF(allruntime); break;
case 3:HRRF(allruntime); break;
case 0: break;
}
}
while(n!=0);
}
- 运行结果及分析
一般必须配运行结果截图，结果是否符合预期及其分析。
（截图需根据实际，截取有代表性的测试例子）
先来先服务（FCFS）：
短作业优先（SJF）：
四、实验总结：
一开始毫无头绪，因为并不清楚怎样算出调度结果。后来看多几次例子，做了练习，然后老师讲解几次后，开始了解算法的过程。但是用程序表达出来还是困难的。然而想参考网上的，但由于大多是用链表写的，看得不太懂。后来发现用数组的形式也是可以的。而且比较直观，没那么难理解。但是写了先来先服务后，短作业优先就没那么容易实现了。因为要比较作业的运行时间，后来用了冒泡排序算法先进行一番排序，再慢慢实现相应的要求。至于最高相应比优先，虽然知道了怎样算出调度结果，但程序实现不了.