实验八多级调度问题.doc

算法设计与分析实验报告 姓名：杨勇涛 班级：计科102 班  一、实验名称：多级调度问题 时间：2012年4月11日，星期三，第四节 地点：12#311 二、实验目的及要求 多级调度问题要求给出一种作业调度方案，时所给的n个作业在尽可能短的时间内由m台及其加工处理完成。 三、实验环境 Vc++ 四、实验内容 设有n个独立的作业{1,2，……，n}，由m台相同的机器进行加工处理。作业i所须的处理时间为Ti。现约定，任何作业可以在任何一台机器上加工处理，单位完工前不许中断处理。任何作业不能处理成更小的子作业。 五、算法描述及实验步骤 当n≤m时，只要机器i的[0,Ti]时间区间分配给作业i即可。 当n＞m时，首先将n个作业一起所需的处理时间从大到小排列。然后依此顺序将作业分配给空闲的处理机。 六、调试过程及实验结果 七、总结 通过本次模拟实验，我加深了解调度工作的模式和原理。 八、附录（源程序清单） # include iostream # include iomanip using namespace std; typedef struct Job //作业 { int ID; int time; }Job; typedef struct JobNode //作业链表的节点 { int ID; int time; JobNode *next; }JobNode,*pJobNode; typedef struct Header //链表的表头 { int s; //处理机上的时间； JobNode *next; }Header,pHeader; int main() { void QuickSort(Job *job,int left,int right); //将job时间排序 void outSort(Job *job,int n); //输出排序 void display(Header *M,int m); //输出每个每台机器处理的工作序号数 int SelectMin(Header *M,int m); //分配作业时选取机器函数； void solve(Header *head,Job*job,int n,int m); //作业分配函数； int m,n; cout\t\t《多机调度问题》\n; cout请输入机器台数m:; cinm; Header *head=new Header [m]; //动态构建数组结构体，用于记录机器的作业时间； cout请输入作业个数n:; cinn; Job *job=new Job [n]; //动态构建作业的数组结构体； cout\n请按序号输入每个作业调度所需时间time：; for(int i=0;in;i++) { cinjob[i].time; job[i].ID=i; } QuickSort(job,0,n-1); //作业排序 outSort(job,n); //输出排序 solve(head,job,n,m); //作业分配 display(head,m); //输出分配 coutendlendl; return 0; } int SelectMin(Header* M,int m) //选择s最小的机器序号k; { int k=0; for(int i=1;im;i++) { if(M[i].sM[k].s) k=i; //k记录S最小的序号； } return k; } void QuickSort(Job *job,int left,int right) //小到大，排序 { int middle=0,i=left,j=right; Job itemp; middle=job[(left+right)/2].time; do { while((job[i].timemiddle)(iright)) i++; while((job[j].timemiddle)(jleft)) j--; if(i=j) { itemp=job[j]; job[j]=job[i]; job[i]