一种改进的wRR独立任务调度算法研究

刘林东

(广东第二师范学院 计算机科学系， 广东 广州 510303)

0 引言

分布式异构处理机环境中，按任务之间的依赖关系，可以将任务调度分为独立任务调度[1-3]和相关任务调度[4-5]两种，独立任务调度的任务之间没有相关性，任务调度没有先后顺序限制，也不存在数据通信；相关任务调度的任务存在先后关系，一般DAG图对任务进行描述，且任务间存在数据通信. 常用的独立任务调度算法包括RR[6]、wRR、LC、Min-Min、Min-Max、Sufferage以及遗传算法[7]等，wRR调度算法[8]通过队列优先级来区别对待不同QoS需求的任务调度，没有考虑异构处理器的计算性能对不同优先级队列的公平性的影响.

1 问题描述

1.1 任务描述

分布式异构环境中任务集T包括n个独立任务，分别为t0,t1,…,tn-1，处理机集P包括m个性能异构的处理机，分别为P0,P1,…,Pm-1，表1描述了7个任务在4个处理机上执行开销. 设任务ti被调度的处理机不受限制，每个处理机同时只能调度1个任务，1个任务不能在多个处理机上调度. 如何将n个独立任务调度到m个处理机，且满足任务集T在处理机集P上的执行跨度、平均等待时间优于同类算法是文中需要主要研究的问题.

表1 任务在处理机上的执行开销

ms任务P0P1P2P3t0200211180223t110212291130t281928895t355595761t432332936t5155160149173t6135142122160

1.2 wRR任务调度算法

w0w1w2w3P0P1P2P3t0t1t2t3t4t5t6Q0Q1Q2Q3a.队列调度b.处理机调度t4t0t1t2t3t5t6P0P1P2P3

图1 wRR算法任务调度

2 任务调度模型及算法

为解决wRR算法在独立任务调度过程中出现的问题，提出一种改进的任务调度模型及iwRR任务调度算法.

2.1 任务调度模型

带阈值的加权轮转任务调度模型包括处理机池初始化和任务调度两个阶段，如图2所示. 处理机池中的处理机均被调度之后，根据队列中的任务调度请求，处理机调度模块根据当前处理机的调度情况，将任务调度结束时间最晚的处理机Pj从处理机池中删除，其余处理机均加入处理机池中；在任务调度阶段，更新处理机池中的每个处理机的权值，然后按照wRR调度队列中的所有任务.

t0t4t1t3t2t5t6处理机集P处理机池P1wRR算法任务调度模块任务集T

图2 改进的加权轮转调度模型

2.2 任务调度算法

改进的加权轮转调度算法iwRR算法如下：

输入：任务集T,处理机集P,任务在处理机上的执行开销T[n][m],权值w[m];

输出：任务调度关系表S[n][m],任务调度跨度makespan,任务平均等待时间AWT;

初始化处理机池P;

while任务集T非空{

for(i=0;i

计算处理机Pi的结束时间E[i];

}

找出最小的E[j]对应的处理机Pj;

从处理机池P中删除处理机Pj;

for(i=0;i

计算每个处理机上分配的任务数ai;

}

对于当前任务ti{

ifcj

调度任务到处理机Pj;

elsej=(j+1)mod(m-1);

}

计算输出makespan和AWT;

}

3 实验分析

为验证iwRR算法的性能，将iwRR算法与wRR算法在相同的实验条件下进行性能比较，主要对任务调度跨度Makespan值进行比较. 利用SimGrid[9-11]环境下的集群环境仿真分布式异构环境，分布式异构计算环境中的处理机对应SimGrid中的处理机，对SimGrid模拟器进行设置：处理机之间通过高速网络互连；每个任务只能在1个处理机上执行，且任务被调度后不能中止；每个处理机同时只能调度1个任务；处理机的任务调度性能异构.

仿真实验中的软硬件环境为：Intel Core(TM) i5-8265U 1.6 1.8GHzCPU、4GB内存硬件环境、操作系统为Ubuntu12.

3.1 测试数据集

iwRR算法输入有两个，分别是任务执行时间矩阵和被调度任务. 有两种不同的任务集执行时间矩阵，任务数均为10个任务，处理机数为4和6两种情况；任务在处理机上的执行开销通过随机程序生成；被调度任务集的任务数为50，100，…，1 000；任务编号通过程序随机产生；任务到达时间为0.

3.2 实验结果分析

1)4个处理机

4个处理机情况下两种算法任务调度跨度对比情况如图3所示，iwRR算法在不同任务数情况下，任务调度跨度要比wRR算法长，wRR算法的性能总体上要优于iwRR算法，wRR算法任务调度跨度要比iwRR算法少0.177%. 由于iwRR算法在调度过程中会从处理机池中放弃一个调度结束时间最晚的处理机，在处理机数量较少的情况下，处理机池中的处理机数量变得更少，iwRR算法的优势不能体现出来，因此导致wRR算法性能总体上要优于iwRR算法.

50000400003000020000100000iwRRwRR调度跨度/ms1000200400600800任务数/个iwRRwRR100020040060080035000300002500020000150001000050000任务数/个调度跨度/ms

图3 任务调度跨度对比 图4 任务调度跨度对比

2)6个处理机

6个处理机情况下两种算法任务调度跨度对比情况如图4所示，iwRR算法在不同任务数情况下，任务调度跨度要比wRR算法短，iwRR算法的性能总体上要优于wRR算法，iwRR算法任务调度跨度要比wRR算法最小少0.98%，最高少9.98%，iwRR算法的优势在处理机数量较多的情况较好地体现了出来.

4 结束语

通过对wRR算法的改进，提出了一种改进的iwRR独立任务调度算法，在相同的实验环境下，利用测试数据集对任务集进行调度，得出两种算法的任务调度跨度，得出在处理机数量较少的情况下，wRR算法要优于iwRR算法，但优势并不明显；而当处理机数量较大时，iwRR算法明显优于wRR算法.

对iwRR算法进一步完善，将iwRR算法应用于在线任务调度问题以及相关任务调度问题. 另外，在真实异构环境中对独立任务进行调度是后续需要进一步研究的问题.