实验三-利用预约表编程计算非线性流水线任务调度方案.doc

实验三 利用预约表编程计算非线性流水线的任务调度方案
一、 实验目的
通过本实验帮助学生理解单功能非线性流水线基本任务调度方法。
二、 实验环境
开发工具使用windows平台下的vc++6.0。
三、 实验内容
给定某单功能非线性流水线的预约表，通过编程求出所有不冲突的任务调度方案并输出。流水线功能段数随机。
四、 实验结果
#include<stdio.h>
#include<iostream.h>
#include<iomanip.h>
#include<string.h>

const int MAXJOB=50;

//定义数据结构体
typedef struct node{
int number;
int reach_time;
int reach_hour;
int reach_minite;
int need_time;
int privilege;
float excellent;
int start_time;
int wait_time;
int visited;
}job;
job jobs[MAXJOB]; int quantity;
//初始化函数
void initial()
{ int i;
for(i=0;i<MAXJOB;i++){
jobs[i].number=0;
jobs[i].reach_time=0;
jobs[i].reach_hour=0;
jobs[i].reach_minite=0;
jobs[i].privilege=0;
jobs[i].excellent=0;
jobs[i].start_time=0;
jobs[i].wait_time=0;
jobs[i].visited=0;
}
quantity=0;
}
void reset() //重置作业数据函数
{ int i;
for(i=0;i<MAXJOB;i++){
jobs[i].start_time=0;
jobs[i].wait_time=0;
jobs[i].visited=0;
}
}

void readData() //读入作业数据函数
{
FILE *fp;
char fname[20];
int i;

cout<<"请输入作业数据文件名:";
strcpy(fname,"8job.txt");
cin>>fname;
if((fp=fopen(fname,"r"))==NULL){
cout<<"错误,文件打不开,请检查文件名:)"<<endl;
}
else{
while(!feof(fp)){
fscanf(fp,"%d %d %d %d",&jobs[quantity].number,&jobs[quantity].reach_time,&jobs[quantity].need_time,&jobs[quantity].privilege);
jobs[quantity].reach_hour=jobs[quantity].reach_time/100;
jobs[quantity].reach_minite=jobs[quantity].reach_time%100;
quantity++;
}
//输出初始作业数据
cout<<"输出初始作业数据"<<endl;
cout<<"---------------------------------------------------------------"<<endl;
cout.setf(2);
cout<<setw(10)<<"作业号"<<setw(12)<<"到达时间"<<setw(14)<<"所需时间(分)"<<setw(14)<<"优先级(0>1)"<<endl;
for(i=0;i<quantity;i++){
cout<<setw(10)<<jobs[i].number<<setw(12)<<jobs[i].reach_time<<setw(14)<<jobs[i].need_time<<setw(14)<<jobs[i].privilege<<endl;
}
}
}

//FIFO算法
void FIFO()
{
int i;
int current_hour;
int current_minute;
int total_time=0;
cout<<endl; //输出作业流
cout<<endl<<"FIFO算法作业流"<<endl;
cout<<"---------------------------------------------------------------"<<endl;
cout.setf(2);
cout<<setw(10)<<"作业号"<<setw(12)<<"到达时间"<<setw(12)<<"开始时间"<<setw(14)<<"周转时间(分)"<<endl;
current_hour=jobs[0].reach_hour;
current_minute=jobs[0].reach_minite;
for(i=0;i<quantity;i++){
jobs[i].start_time=current_hour*100+current_minute;
jobs[i].wait_time=(current_hour-jobs[i].reach_hour)*60+(current_minute-jobs[i].reach_minite)+jobs[i ].need_time; cout<<setw(10)<<jobs[i].number<<setw(12)<<jobs[i].reach_time<<setw(12)<<jobs[i].start_time<<setw(14)<<jobs[i].wait_time<<endl;
current_hour=current_hour+(jobs[i].need_time+current_minute)/60;
current_minute=(jobs[i].need_time+current_minute)%60;
total_time+=jobs[i].wait_time;
}
cout<<endl<<"总周转时间:"<<total_time<<" 平均周转时间:"<<total_time/quantity<<endl;
}
void shorter() //运算时间短的作业优先算法
{
int i,j,p;
int current_hour;
int current_minute;
int current_need_time;
int total_time=0; //输出作业流
cout<<endl;
cout<<endl<<"时间短作业优先算法作业流(开始调度时刻为最后一个作业到达系统的时间)"<<endl;
cout<<"------------------------------------------------------------------------"<<endl;
cout.setf(2);
cout<<setw(10)<<"作业号"<<setw(12)<<"到达时间"<<setw(14)<<"所需时间(分)"<<setw(12)<<"开始时间"<<setw(14)<<"周转时间(分)"<<endl;
current_hour=jobs[quantity-1].reach_hour;
current_minute=jobs[quantity-1].reach_minite;
for(i=0;i<quantity;i++){
current_need_time=30000;
for(j=0;j<quantity;j++){
if((jobs[j].visited==0)&&(jobs[j].need_time<current_need_time)){
p=j;
current_need_time=jobs[j].need_time;
}
}
jobs[p].start_time=current_hour*100+current_minute;
jobs[p].wait_time=(current_hour-jobs[p].reach_hour)*60+(current_minute-jobs[p].reach_minite)+jobs[p ].need_time;
cout<<setw(10)<<jobs[p].number<<setw(12)<<jobs[p].reach_time<<setw(14)<<jobs[p].need_time<<setw(12)<<jobs[p].start_time<<setw(14)<<jobs[p].wait_time<<endl;
current_hour=current_hour+(jobs[p].need_time+current_minute)/60;
current_minute=(jobs[p].need_time+current_minute)%60;
jobs[p].visited=1;
total_time+=jobs[p].wait_time;
}
cout<<endl<<"总周转时间:"<<total_time<<" 平均周转时间:"<<total_time/quantity<<endl;
}
void privilege() //优先数调度算法
{
int i,j,p;
int current_hour;
int current_minute;
int current_privilege;

int total_time=0;

//输出作业流

cout<<endl;
cout<<endl<<"优先数调度算法作业流(开始调度时刻为最后一个作业到达系统的时间)"<<endl;
cout<<"------------------------------------------------------------------------"<<endl;
cout.setf(2);
cout<<setw(10)<<"作业号"<<setw(12)<<"到达时间"<<setw(14)<<"优先级(0>1)"<<setw(12)<<"开始时间"<<setw(14)<<"周转时间(分)"<<endl;

current_hour=jobs[quantity-1].reach_hour;
current_minute=jobs[quantity-1].reach_minite;
for(i=0;i<quantity;i++){
current_privilege=30000;
for(j=0;j<quantity;j++){
if((jobs[j].visited==0)&&(jobs[j].privilege<current_privilege)){
p=j;
current_privilege=jobs[j].privilege;
}
}
jobs[p].start_time=current_hour*100+current_minute;
jobs[p].wait_time=(current_hour-jobs[p].reach_hour)*60+(current_minute-jobs[p].reach_minite)+jobs[p
].need_time;

cout<<setw(10)<<jobs[p].number<<setw(12)<<jobs[p].reach_time<<setw(14)<<jobs[p].privilege<<setw(12)<<jobs[p].start_time<<setw(14)<<jobs[p].wait_time<<endl;

current_hour=current_hour+(jobs[p].need_time+current_minute)/60;
current_minute=(jobs[p].need_time+current_minute)%60;

jobs[p].visited=1;

total_time+=jobs[p].wait_time;
}
cout<<endl<<"总周转时间:"<<total_time<<" 平均周转时间:"<<total_time/quantity<<endl;
}

//响应比最高者优先调度算法

void excellent()
{
int i,j,p;
int current_hour;
int current_minute;
float current_excellent;

int total_time=0;
//输出作业流

cout<<endl;
cout<<endl<<"响应比高者优先调度算法作业流(开始调度时刻为最后一个作业到达系统的时间)"<<endl;
cout<<"------------------------------------------------------------------------"<<endl;
cout.setf(2);
cout<<setw(10)<<"作业号"<<setw(12)<<"到达时间"<<setw(12)<<"开始时间"<<setw(14)<<"周转时间(分)"<<endl;

current_hour=jobs[quantity-1].reach_hour;
current_minute=jobs[quantity-1].reach_minite;
for(i=0;i<quantity;i++){
current_excellent=-1;
for(j=0;j<quantity;j++){
if(jobs[j].visited==0){
jobs[j].wait_time=(current_hour-jobs[j].reach_hour)*60+(current_minute-jobs[j].reach_minite);
jobs[j].excellent=(float)(jobs[j].wait_time/jobs[j].need_time);
}
}

for(j=0;j<quantity;j++){
if((jobs[j].visited==0)&&(jobs[j].excellent>current_excellent)){
p=j;
current_excellent=jobs[j].excellent;
}
}
jobs[p].start_time=current_hour*100+current_minute;
jobs[p].wait_time=(current_hour-jobs[p].reach_hour)*60+(current_minute-jobs[p].reach_minite)+jobs[p
].need_time;

cout<<setw(10)<<jobs[p].number<<setw(12)<<jobs[p].reach_time<<setw(12)<<jobs[p].start_time<<setw(14)<<jobs[p].wait_time<<endl;

current_hour=current_hour+(jobs[p].need_time+current_minute)/60;
current_minute=(jobs[p].need_time+current_minute)%60;
jobs[p].visited=1;
total_time+=jobs[p].wait_time;
}
cout<<endl<<"总周转时间:"<<total_time<<" 平均周转时间:"<<total_time/quantity<<endl;
}
Void main()
{
initial();
readData();
FIFO();
shorter();
reset();
privilege();
reset();
excellent();
}
五、 问题以及解决方案
1. 问题：什么是线性流水线和非线性流水线；
解决方案：线性流水线：流水线的各段串行连接，没有反馈回路。非线性流水线：非线性流水线不同于线性流水线，线性流水线是一段接一段地往后走，它的连接关系是唯一的。非线性流水线中某一段或某些段可能有反馈信号，这就是线性流水线和非线性流水线的区别。
2. 问题：什么是流水线冲突；
解决方案：采用非线性流水线会发生流水线冲突（也叫功能部件冲突），这主要是由于在非线性流水线中存在反馈回路。当一个任务在流水线流过时，在同一功能段可能要经过几次，这样，如果仍像线性流水线那样，每个时钟周期输入一个任务就会发生几个任务争用同一个功能段的情况。
六、 思考题
将单功能非线性流水线改为多功能非线性流水线，如何编程计算非冲突任务调度呢？
流水线输入两个任务间隔的时钟周期数叫做启动周期。非线性流水线调度的任务就是找出一个最小的启动循环周期，按照这个周期向流水线输入任务，流水线的各个功能段都不会发生冲突，也就是同一时间只有一个任务进入到这个流水线，在不发生冲突的情况下尽量提高流水线的效率和吞吐率。
下面以一条非线性流水线为例，说明非线性流水线的调度方法。
1、写出流水线的禁止向量和初始冲突向量。
2、画出调度流水线的状态图。
3、求流水线的最小启动循环和最小平均启动距离。
4、求平均启动距离最小的恒定循环。
七、 实验心得
在此次试验中更加熟练的应用C++进行编程，并对操作系统和体系结构课程中的任务调度和流水线技术进行了复习和印象的加深。运用流水线，处理冲突的任务调度，很好的理解了课本中基本调度算法的知识，加深了课本的理解。