2. 计算机
  3. (2013年上半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为tI，要求确定一个调度方案，使得完成所有任务所需要的时间最短。

(2013年上半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为tI，要求确定一个调度方案，使得完成所有任务所需要的时间最短。

admin2018-07-27  68
问题 (2013年上半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
    【说明】
    设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为tI，要求确定一个调度方案，使得完成所有任务所需要的时间最短。
    假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m：机器数
n：任务数
t[]：输入数组，长度为n，其中每个元素表示任务的运行时间，下标从0开始
S[][]：二维数组，长度为m~n，下标从0开始，其中元素sD]表示机器i运行的任务
j的编号
d[]：数组，长度为m，其中元素d表示机器i的运行时间，下标从0开始
count[]：数组，长度为m，下标从0开始，其中元素count表示机器i运行的任务数
i：循环变量
j：循环变量
k：临时变量
max：完成所有任务的时间
min：临时变量
(2)函数schedule
void  Schedule(){
    int i,j，k，max=0；
    for(i=0;i＜m;i++){
    d=0；
    for(j=0；j＜n；j++){
    s[j]=0；
    }
}
    for(i=0；i＜m;i++){    ／／分配前m个任务
    s[0]=i；
    ______(1)
    count=1;
    }
    for(______(2)；i＜n；i++){    ／／分配后n-m个任务
    int min=d[0]；
    k=0；
    for(j=1；j＜m；j++){    ／／确定空闲机器
    if(min＞d[j]){
    min=d[j]；
    k=j；    ／／机器k空闲
    }
    }
    ______(3);
    count[k]=count[k]+1；
    d[k]=d[k]+t;
    for(i=0；i＜m；i++){    ／／确定完成所有任务所需要的时间
    if(____(4){
    max=d;
    }
         }
        }
    }
考虑实例m=3(编号0～2)，n=7(编号0～6)，各任务的运行时间为{16，14，6，5，4，3，2}。则在机器0、1和2上运行的任务分别为______(7)、______(8)和______(9)(给出任务编号)。从任务开始运行到完成所需要的时间为______(10)。
选项
答案(7)0 (8)1、 5 (9)2、 3、4、 6 (10)17
解析 根据题中算法的思想，将前i个任务分给三个机器，再将接下来的任务分给最先空闲的机器，故可知机器0运行任务0，机器1运行任务1、5，机器3运行任务2、3、4、6，且运行的最长时间为17。
转载请注明原文地址:https://kaotiyun.com/show/Y7DZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)