【分析解答题】
设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案是的完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个1务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
[C代码]
下面是算法的C语言实现。
(1)常量和变量说明
m:机器数。
n:任务数。
t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始。
s[][]:二维数组,长度为m*n,下标从0开始,其中元素s[i][j]表示机器i运行的任务j的编号。
D[]:数组,长度为m其中元素D[i]表示机器i的运行时间,下标从0开始。
Count[]:数组,长度为m,下标从0开始,其中元素Count[i]表示机器i运行的任务数。
i:循环变量。
j:循环变量。
k:临时变量。
mAx:完成所有任务的时间。
min:临时变量。
(2)函数sChEDulE
voiD sChEDulE()
int i,j,k mAx=0;
For(i=0;i<m;i++)
D[i]=0;
For(j=0;j<n;j++)
s[i][j]=0;
For(i=0;i<m;i++)//分配前m个任务
s[i][0]=i;
______;
Count[i]=1;
For(______;i<n;i++)//分配后n-m个任务
int min=D[0];
k=0;
For(j=1;j<n;j++)//确定空闲机器
iF(rAin>D[j])
min=D[j];
k=j;//机器k空闲
______;
Count[k]=Count[k]+1;
D[k]=D[k]+t[i];
For(i=0;i<m;i++)//确定完成所有任务所需要的时间
iF(______)
mAx=D[i];
考虑实例m=3(编号0~2),n=7(编号0~6),各任务的运行时间为{16,14,6,5,4,3,2}。则在机器0、1和2上运行的任务分别为______、______和______(给出任务编号)。从任务开始运行到完成所需要的时间为______。
查看答案解析
参考答案:
正在加载...
答案解析
正在加载...
根据网考网移动考试中心的统计,该试题:
0%的考友选择了A选项
0%的考友选择了B选项
0%的考友选择了C选项
0%的考友选择了D选项