阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间

admin2013-07-09  20

问题 阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。
    【说明】
    设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。
    假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
    【C代码】
    下面是算法的C语言实现。
    (1)常量和变量说明
    m:机器数。
    n:任务数。
    t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始。
    s[][]:二维数组,长度为m*n,下标从0开始,其中元素s[j]表示机器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

解析 根据题中算法的思想将任务将前三个任务分给三个机器,再将接下来的任务分给最先空闲的机器,故可知机器0运行任务0,机器1运行任务1、5,机器3运行任务2、3、4、6;且运行的最长时间为17。
转载请注明原文地址:https://kaotiyun.com/show/7YDZ777K
0

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