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

实验三 利用预约表编程计算非线性流水线的任务调度方案一、 实验目的通过本实验帮助学生理解单功能非线性流水线基本任务调度方法。二、 实验环境开发工具使用windows平台下的vc+6.0。三、 实验内容给定某单功能非线性流水线的预约表，通过编程求出所有不冲突的任务调度方案并输出。流水线功能段数随机。四、 实验结果#include #include #include #include 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 jobsMAXJOB; int quantity; /初始化函数 void initial() int i; for(i=0;iMAXJOB;i+) jobsi.number=0; jobsi.reach_time=0; jobsi.reach_hour=0; jobsi.reach_minite=0; jobsi.privilege=0; jobsi.excellent=0; jobsi.start_time=0; jobsi.wait_time=0; jobsi.visited=0; quantity=0; void reset() /重置作业数据函数 int i; for(i=0;iMAXJOB;i+) jobsi.start_time=0; jobsi.wait_time=0; jobsi.visited=0; void readData() /读入作业数据函数 FILE *fp; char fname20; int i; coutfname; if(fp=fopen(fname,r)=NULL) cout错误,文件打不开,请检查文件名:)endl; else while(!feof(fp) fscanf(fp,%d %d %d %d,&jobsquantity.number,&jobsquantity.reach_time,&jobsquantity.need_time,&jobsquantity.privilege); jobsquantity.reach_hour=jobsquantity.reach_time/100; jobsquantity.reach_minite=jobsquantity.reach_time%100; quantity+; /输出初始作业数据 cout输出初始作业数据endl; cout-endl; cout.setf(2); coutsetw(10)作业号setw(12)到达时间setw(14)所需时间(分)setw(14)1)endl; for(i=0;iquantity;i+) coutsetw(10)jobsi.numbersetw(12)jobsi.reach_timesetw(14)jobsi.need_timesetw(14)jobsi.privilegeendl; /FIFO算法 void FIFO() int i; int current_hour; int current_minute; int total_time=0; coutendl; /输出作业流coutendlFIFO算法作业流endl; cout-endl; cout.setf(2); coutsetw(10)作业号setw(12)到达时间setw(12)开始时间setw(14)周转时间(分)endl; current_hour=jobs0.reach_hour; current_minute=jobs0.reach_minite; for(i=0;iquantity;i+) jobsi.start_time=current_hour*100+current_minute; jobsi.wait_time=(current_hour-jobsi.reach_hour)*60+(current_minute-jobsi.reach_minite)+jobsi .need_time; coutsetw(10)jobsi.numbersetw(12)jobsi.reach_timesetw(12)jobsi.start_timesetw(14)jobsi.wait_timeendl; current_hour=current_hour+(jobsi.need_time+current_minute)/60; current_minute=(jobsi.need_time+current_minute)%60; total_time+=jobsi.wait_time; coutendl总周转时间:total_time 平均周转时间:total_time/quantityendl; void shorter() /运算时间短的作业优先算法 int i,j,p; int current_hour; int current_minute; int current_need_time; int total_time=0; /输出作业流 coutendl; coutendl时间短作业优先算法作业流(开始调度时刻为最后一个作业到达系统的时间)endl; cout-endl; cout.setf(2); coutsetw(10)作业号setw(12)到达时间setw(14)所需时间(分)setw(12)开始时间setw(14)周转时间(分)endl; current_hour=jobsquantity-1.reach_hour; current_minute=jobsquantity-1.reach_minite; for(i=0;iquantity;i+) current_need_time=30000; for(j=0;jquantity;j+) if(jobsj.visited=0)&(jobsj.need_timecurrent_need_time) p=j; current_need_time=jobsj.need_time; jobsp.start_time=current_hour*100+current_minute; jobsp.wait_time=(current_hour-jobsp.reach_hour)*60+(current_minute-jobsp.reach_minite)+jobsp .need_time; coutsetw(10)jobsp.numbersetw(12)jobsp.reach_timesetw(14)jobsp.need_timesetw(12)jobsp.start_timesetw(14)jobsp.wait_timeendl; current_hour=current_hour+(jobsp.need_time+current_minute)/60; current_minute=(jobsp.need_time+current_minute)%60; jobsp.visited=1; total_time+=jobsp.wait_time; coutendl总周转时间:total_time 平均周转时间:total_time/quantityendl; void privilege() /优先数调度算法 int i,j,p; int current_hour; int current_minute; int current_privilege; int total_time=0; /输出作业流 coutendl; coutendl优先数调度算法作业流(开始调度时刻为最后一个作业到达系统的时间)endl; cout-endl; cout.setf(2); coutsetw(10)作业号setw(12)到达时间setw(14)1)setw(12)开始时间setw(14)周转时间(分)endl; current_hour=jobsquantity-1.reach_hour; current_minute=jobsquantity-1.reach_minite; for(i=0;iquantity;i+) current_privilege=30000; for(j=0;jquantity;j+) if(jobsj.visited=0)&(jobsj.privilegecurrent_privilege) p=j; current_privilege=jobsj.privilege; jobsp.start_time=current_hour*100+current_minute; jobsp.wait_time=(current_hour-jobsp.reach_hour)*60+(current_minute-jobsp.reach_minite)+jobsp .need_time; coutsetw(10)jobsp.numbersetw(12)jobsp.reach_timesetw(14)jobsp.privilegesetw(12)jobsp.start_timesetw(14)jobsp.wait_timeendl; current_hour=current_hour+(jobsp.need_time+current_minute)/60; current_minute=(jobsp.need_time+current_minute)%60; jobsp.visited=1; total_time+=jobsp.wait_time; coutendl总周转时间:total_time 平均周转时间:total_time/quantityendl; /响应比最高者优先调度算法 void excellent() int i,j,p; int current_hour; int current_minute; float current_excellent; int total_time=0; /输出作业流 coutendl; coutendl响应比高者优先调度算法作业流(开始调度时刻为最后一个作业到达系统的时间)endl; cout-endl; cout.setf(2); coutsetw(10)作业号setw(12)到达时间setw(12)开始时间setw(14)周转时间(分)endl; current_hour=jobsquantity-1.reach_hour; current_minute=jobsquantity-1.reach_minite; for(i=0;iquantity;i+) current_excellent=-1; for(j=0;jquantity;j+) if(jobsj.visited=0) jobsj.wait_time=(current_hour-jobsj.reach_hour)*60+(current_minute-jobsj.reach_minite); jobsj.excellent=(float)(jobsj.wait_time/jobsj.need_time); for(j=0;jcurrent_excellent) p=j; current_excellent=jobsj.excellent; jobsp.start_time=current_hour*100+current_minute; jobsp.wait_time=(current_hour-jobsp.reach_hour)*60+(current_minute-jobsp.reach_minite)+jobsp .need_time; coutsetw(10)jobsp.numbersetw(12)jobsp.reach_timesetw(12)jobsp.start_timesetw(14)jobsp.wait_timeendl; current_hour=current_hour+(jobsp.need_time+current_minute)/60; current_minute=(jobsp.need_time+current_minute)%60; jobsp.visited=1; total_time+=jobsp.wait_time; coutendl总周转时间:total_time 平均周转时间:total_time/quantityendl; Void main() initial(); readData(); FIFO(); shorter(); reset(); privilege(); reset(); excellent(); 五、 问题以及解决方案1. 问题：什么是线性流水线和非线性流水线；解决方案：线性流水线：流水线的各段串行连接，没有反馈回路。非线性流水线：