(2)设计调度算法,为每个作业分配一台可用机器; (3)给出分配方案。 3.设计思想
假设有7个作业,所需时间分别为{2,14,4,16,6,5,3},有三台机器,编号分别为ml ,m2和m3。这7个作业在三台机器上进行调度的情形如图所示,阴影区代表作业的运行区间。作业4在0到16时间被调度到机器1上运行,在这16个时间单位中,机器1完成了对作业4的处理;作业2在0到14时间被调度到机器2上处理,之后机器2在14到17时间处理作业7;在机器3上,作业5在0~6时间完成,作业6在6~11时间完成,作业3在11~15时间完成,作业1在15~17时间完成。注意到作业i只能在一台机器上从si时刻到si+ti时间完成且任何机器在同一时刻仅能处理一个作业,因此最短调度长度为17。
图 三台机器的调度示例
在上述处理中,采用了最长时间优先(LPT)的简单调度策略。在LPT算法中,作业按其所需时间的速减顺序排列,在分配一个作业时,将其分配给最先变为空闲的祝器。
下面设计宪成LPT算法的存储结构。 ·为每个机器设计数据类型: strnct harhineNode {
int ID。 //机器号 int avail; //机器可用时刻 };
·为每个作业设计数据类型: struct JobNode {
int ID ; //作盛号 int time; //处理时间 };
36
LPT算法用伪代码描述如下: 1.如果作业数n<=机器数m,则 1.1将作业i分配到机器i上;
1.2最短调度长度等于n个作业中处理时间最大值; 2.否则,重复执行以下操作,直到n个作业都被分配: 2.1将n个作业按处理时间建成一个大根堆H1; 2.2将m个机器按可用时刻建立一个小根堆H2; 2.3将堆H1的堆顶作业分配给堆H2的堆顶机器;
2.4将H2的堆顶机器加上H1的堆顶作业的处理时间重新插入H2中; 2.5将堆HI的堆顶元素删除; 3.堆H2的堆顶元素就是最短调度时间。
思考题:关于机器的调度问题还有很多解法,请上网查找相关资料。
37