实验八多级调度问题

算法设计与分析实验报告姓名：杨勇涛班级：计科 102 班一、实验名称：多级调度问题时间：2012 年4月11日，星期三，第四节地点：12#311二、实验目的及要求多级调度问题要求给出一种作业调度方案，时所给的 n 个作业在尽可能短 的时间内由 m 台及其加工处理完成。三、实验环境Vc+四、实验内容设有n个独立的作业1,2, ,n，由m台相同的机器进行加工处理。 作业i所须的处理时间为Ti。现约定，任何作业可以在任何一台机器上加工处理, 单位完工前不许中断处理。任何作业不能处理成更小的子作业。五、算法描述及实验步骤当nWm时，只要机器i的O,Ti时间区间分配给作业i即可。当nm时，首先将n个作业一起所需的处理时间从大到小排列。然后依 此顺序将作业分配给空闲的处理机。六、调试过程及实验结果请按序号输入每个作业调度所需时间钏1441643226Q:3:1 6：4 5 2 0为 6 rB_6_LL- 1 番OR第第Press any key to continue七、总结通过本次模拟实验，我加深了解调度工作的模式和原理。八、附录（源程序清单）# include # include 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;/将 job 时间排序 /输出排序 /输出每个每台机器处/分配作业时选取机器/作业分配函数；/动态构建数组结构体，用于记int main() void QuickSort(Job *job,int left,int right); 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;coutvvtt多机调度问题n; coutvv请输入机器台数m:; cinm;Header *head=new Header m; 录机器的作业时间；/动态构建作业的数组结构体；coutvv请输入作业个数n:; cinn;Job *job=new Job n;coutn 请按序号输入每个作业调度所需时间 time：;for(int i=0;ijobi.time; jobi.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(Mi.smiddle)&(iright) i+;while(jobj.timeleft)j-;if(i=j)itemp=jobj; jobj=jobi; jobi=itemp; i+;j-;while(i=j);if(lefti) QuickSort(job,i,right);void display(Header *M,int m)/作业分配输出函数；JobNode *p;for(int i=0;im;i+)coutvvn第vvivv台机器上处理的工作序号：；if(Mi.next=0)continue；p=Mi.next；do coutIDnext；while(p!=0)；void outSort(Job *job,int n)/作业时间由大到小排序后输出函数coutvvn按工作时间由大到小为:n时间：t;for(int i=0；in；i+)coutsetw(4)jobi.time; coutvvn 序号：t; for( i=0;in;i+)coutsetw(4)jobi.ID;void solve(Header *head,Job*job,int n,int m)/作业分配函数；int k;for(int i=0;im&itime=jobi.time; jobnode-ID=jobi.ID; jobnode-next=0; headi.s=jobnode-time; headi.next=jobnode;if(i=m) /nm 的情况续处理； for(i;im)for(i;itime=jobi.time; jobnode-ID=jobi.ID; jobnode-next=0; k=SelectMin(head,m); p=headk.next; headk.s+=jobnode-time; while(p-next!=0) p=p-next;p-next=jobnode;