实验八多级调度问题.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:";
cin>>m;
Header *head=new Header [m]; //动态构建数组结构体，用于记录机器的作业时间；
cout<<"请输入作业个数n:";
cin>>n;
Job *job=new Job [n]; //动态构建作业的数组结构体；
cout<<"\n请按序号输入每个作业调度所需时间time：";
for(int i=0;i<n;i++)
{
cin>>job[i].time;
job[i].ID=i;
}
QuickSort(job,0,n-1); //作业排序
outSort(job,n); //输出排序
solve(head,job,n,m); //作业分配
display(head,m); //输出分配
cout<<endl<<endl;
return 0;
}

int SelectMin(Header* M,int m) //选择s最小的机器序号k;
{
int k=0;
for(int i=1;i<m;i++)
{
if(M[i].s<M[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].time>middle)&&(i<right))
i++;
while((job[j].time<middle)&&(j>left))
j--;
if(i<=j)
{
itemp=job[j];
job[j]=job[i];
job[i]=itemp;
i++;
j--;
}
}while(i<=j);
if(left<j)
QuickSort(job,left,j);
if(right>i)
QuickSort(job,i,right);
}

void display(Header *M,int m) //作业分配输出函数；
{
JobNode *p;
for(int i=0;i<m;i++)
{
cout<<"\n第"<<i<<"台机器上处理的工作序号：";
if(M[i].next==0)
continue;
p=M[i].next;
do{
cout<<p->ID<<' ';
p=p->next;
}while(p!=0);
}
}

void outSort(Job *job,int n) //作业时间由大到小排序后输出函数；
{
cout<<"\n按工作时间由大到小为:\n时间：\t";
for(int i=0;i<n;i++)
cout<<setw(4)<<job[i].time;
cout<<"\n序号：\t";
for( i=0;i<n;i++)
cout<<setw(4)<<job[i].ID;
}
void solve(Header *head,Job*job,int n,int m) //作业分配函数；
{
int k;
for(int i=0;i<m&&i<n;i++)
{
JobNode *jobnode=new JobNode;
jobnode->time=job[i].time;
jobnode->ID=job[i].ID;
jobnode->next=0;
head[i].s=jobnode->time;
head[i].next=jobnode;
}
if(i<=m) //n<m的情况续处理；
{
for(i;i<m;i++)
{
head[i].s=0;
head[i].next=0;
}
}
if(n>m)
{
for(i;i<n;i++)
{
JobNode *p;
JobNode *jobnode=new JobNode;
jobnode->time=job[i].time;
jobnode->ID=job[i].ID;
jobnode->next=0;
k=SelectMin(head,m);
p=head[k].next;
head[k].s+=jobnode->time;
while(p->next!=0)
p=p->next;
p->next=jobnode;
}
}
}