基于多维度资源需求的改进遗传调度算法*

高 原顾文杰彭 晖陈 鹏

（1.南瑞集团有限公司（国网电力科学研究院） 南京 211106）（2.国电南瑞科技股份有限公司 南京 211106）（3.智能电网保护和运行控制国家重点实验室 南京 211106）

1 引言

随着网络和云计算［1～2］技术的飞速发展，网络数据正以几何级数的方式迅速增长，为了解决对海量数据的存储与处理，云计算海量数据处理平台（如Hadoop［3］、Dryad［4］等）应运而生。同时IT基础设施发展也呈现CPU、内存速度得到快速提升，而存储设备的速度提升相对缓慢的状态。如何在这些云平台上利用有效的资源管理与调度策略提高处理效率成为一个非常重要的问题。

国内外已有学者或者技术领先的IT公司研究任务调度技术。如Google的Borg［5］任务调度系统、Yahoo公司开发的新一代MapReduce框架YARN［6］和诞生于加州大学伯克利分校的Mesos系统［7］。它们的特点是只针对CPU、内存资源进行调度，容易造成其他类型的资源如磁盘IO在各个节点的不均衡使用。因为IO速度相对于CPU和内存有数量级差异，它的不均衡会造成整个系统的效率低下。

任务调度问题是经典的NP-Hard问题［8］，许多学者提出了多种启发式算法来进行解决。文献［9～10］提出使用遗传算法解决网格任务调度问题，但是寻找最优解时只考虑了任务的执行时间这一个目标。文献［11］虽然提出了两个适应度函数，但本质上还都是执行时间这一种属性。文献［12］提出的多目标遗传算法以执行时间最短和执行费用最低为目标，但是与文献［9～11］一样，算法的输入参数只有任务的执行时间，没有考虑到分布式任务调度中多种资源的负载均衡问题，比如CPU、内存（下简称MEM）、磁盘IO（下简称IO）等。文献［13］的蚁群算法以任务延迟时间最短为目标。但是算法中的参数是在大量实验基础上的经验值，不具备通用性。文献［14］中的粒子群算法仍然仅以任务的总完成时间最短作为调度目标，而且由于没有进行局部最优处理，算法很快便收敛到局部最优。综上所述，在求解分布式任务调度问题时，多数启发式算法的研究文献存在以下不足：1）大多选择执行时间作为适应度函数，但是实际工程中任务的执行时间是一个预先很难确定，也容易受到环境影响而变化的量，导致算法的实用性不高。并且执行时间参数不适合调度常驻进程；2）算法初始解和参数的优化力度不足，算法随机性较大；3）由于启发式算法固有的特点，求解容易陷入局部最优，往往不能得到问题最优的解决方案；4）没有考虑资源使用的负载均衡，特别是没有考虑使用更容易造成任务延迟的IO资源作为调度参数。

考虑到上述调度系统和调度算法的不足，本文提出一种基于CPU、MEM、IO三种资源维度的遗传算法用于任务调度，并对初始种群提出三种优化方法，对遗传变异过程也进行了改进。考虑到硬件资源的争抢会拖慢任务的执行速度，本文采用在实际系统中较为实用的各类资源占用均方差作为多目标的适应度函数，目的在于使任务调度后的整个系统的资源使用更加负载均衡，减少任务之间的资源冲突，提高任务的执行速度。最后用测试数据说明了本算法在收敛性和优化目标方面都有良好的表现。

2 支持多资源维度的分布式任务调度模型

2.1 任务调度的软件框架

基于本文调度算法实现的软件框架由资源管理器、节点管理器、任务管理器等模块组成，如图1所示。

图1 任务调度的软件框架

首先是由用户定义需要被调度的任务的属性，如各类资源的需求等。然后资源管理器中含有的调度器会根据本文的算法将任务调度到具体的节点，由节点管理器将任务实例启动。

2.2 任务调度的数学模型

本文任务调度算法中的各个参数的数学描述如下：

1）N个任务的集合T=｛T1，T2，T3，…，TN｝；

2）资源类型的集合R=｛CPU，MEM，IO｝；

3）M个节点第i种资源总量的集合Rti=｛Rti1，Rti2，Rti3，…，RtiM｝，i∈R；

4）M个节点第i种资源已使用量的集合Rui=｛Rui1，Rui2，Rui3，…，RuiM｝，i∈R；

5）负载均衡值：

式（1）中的负载均衡值σi是第i种资源已使用量的均方差，用来衡量该资源的使用分布情况。其中Ruij是第j个节点的第i种资源的使用量，Riavg是所有节点上第i种资源使用量的平均值。均方差越小，资源使用分布越平均，任务之间的资源竞争越少，系统的整体运行效率越高。

3 基于多维度资源需求的遗传调度算法

本文对遗传算法做了多个方面的优化，首先任务的参数使用实际可测得的CPU、MEM和IO属性，没有使用不确定的执行时间，这样常驻类型的任务也可进行调度；然后对初始种群使用三种方法进行了优化；并对算法的遗传操作进行了改进；算法的适应度函数也采用多目标进行了优化。改进后的遗传算法流程图如图2所示。

图2 改进遗传算法的流程图

3.1 染色体编码

在任务调度的遗传算法中，一个染色体代表一种任务调度方案。如图3所示，染色体的长度是任务总数的2倍，虚线左侧是任务调度的序列，左侧基因的值为任务的序号。虚线右侧是资源节点的选择序列，右侧基因的值是节点的序号。图中整个染色体表示8个任务被分别调度到4个可用的资源上去执行，其中任务T1被调度到R3即第三个节点上，任务T3被调度到R4，依次类推。

图3 染色体示例

也可用｛1，3，4，8，6，5，2，7；3，4，1，2，4，2，1，3｝的形式表示，染色体的长度由待调度任务的数量确定。

3.2 初始种群优化

对初始种群的优化思想是染色体表示的任务调度方案能够使得各维度的资源均方差尽量小，即各个节点的资源使用更加均衡。本文首先使用改进的主资源公平算法（详见3.2.1）得到1个精英染色体；然后使用单资源维度的贪心算法（详见3.2.2）得到3个精英染色体；最后采用让初始种群在可能取值的范围内尽可能均匀分布的方法（详见3.2.3）产生多个随机均匀分布的染色体。这些染色体组成初始种群，作为遗传算法的初始解集。

3.2.1 CMI-DRF算法

本文将IO与CPU、MEM资源统一考虑，设计了一种支持三维度的主资源公平算法，下称为CMI-DRF（CPU，Memory，IO based-Dominant Resource Fairness）算法，此算法用于遗传算法的初始种群优化。并通过Linux操作系统的/proc文件系统采集CPU、MEM和IO资源的状态。包括系统总资源容量和每个进程资源使用的状态。本文使用每个任务的IO需求占整个系统总IO容量的比值进行调度。

以下举例说明多资源维度DRF算法的执行过程。假设系统中有4台服务器，每台服务器有24个CPU核心、16G的内存，单机IO能力设定为10个单位。假设有三种类型的任务，每个任务需要在调控系统中启动4个实例，每个实例需要的资源量为

A：<2CPU，2GB，4IO>

B：<3CPU，4GB，2IO>

C：<4CPU，1GB，1IO>

对于A任务，每个实例要消耗系统总体CPU的1/48、内存的1/32和IO的1/10，所以A的主消耗资源（以下简称为主资源）为IO；同理可得B的主资源为内存，C的主资源为CPU。

算法的调度过程如下：

初始化状态下所有任务的主资源比例都为0，先选取A任务进行调度，部署在node1上；然后是B和C分布在node2和node3上部署一个实例。此时三种任务的主资源使用量分别是1/10、1/16、1/24，因此下一个部署的实例应该是任务C，部署在node4。此时C的主资源变为1/12，B的主资源份额变为最小，因此应该部署一个B的实例，B的主资源是内存，考虑到负载均衡，选择一个内存消耗最小的node3进行部署。因此直到全部12个任务实例部署完成，可得到调度序列如表1。

任务在4节点的集群中的调度结果如图4所示，图中圆括号中的数字代表调度序列中的步骤编号。

图4 多资源维度DRF算法的调度结果

将图4的调度结果转换为染色体的的表达方式则为：｛1，2，3，3，2，3，1，2，3，2，1，1；1，2，3，4，3，1，4，1，2，4，2，3｝。

表1 CMI-DRF算法的调度序列

3.2.2 贪心算法

本文使用贪心算法产生初始种群中的精英染色体，目的是使得初始种群中部分个体适应度大，因而能更好地指导种群的寻优过程。但是与DRF不同，贪心算法每次只能处理一类资源，所以需要执行三次得到三个精英染色体加入到初始种群中，算法的流程如下：

1）如果待调度任务集合不为空，选取本次算法指定资源需求最大的任务i，否则调度完成；

2）选取该项资源已使用量最小的节点j，如果任务i的各项资源需求均小于节点j的资源空闲量，将任务调度到该节点，否则算法结束；

3）Di←任务i的资源需求；

4）Ruj←Ruj+Di（更新节点j的资源使用量）；

5）返回1）。

理论上，通过贪心算法得到的3个染色体并非最优解，但是都是比较优秀的可行解，它们都将被加入到本文遗传算法的初始种群中。

3.2.3 均匀分布算法

初始种群的数量越大，遗传算法越容易找到最优解，但是算法的执行时间也越长。随着待调度的任务数量增加，排列组合形成的全体染色体的数量呈指数级增长。在保证算法的执行时间可接受的同时，如何保证初始种群的多样性是影响遗传算法性能的一个关键问题，本文采用的是一种让初始种群尽量均匀分布在全局解空间范围内的方法，尽最大可能保证算法能够搜索到最优解。

因为初始种群规模太大会让遗传算法执行时间过长，但是随机生成初始种群染色体的时间是较快的。本优化方法的思想就是尽可能多地在全局解空间内产生染色体，然后在其中根据均匀分布的原则选取一个染色体子集参与遗传算法运算，即在全局解空间内进行均匀的采样。假设有8个任务要部署在8个节点上，所有的部署方法组成的集合就是这个问题的全局解空间，染色体后半段的随机值介于｛0，0，0，0，0，0，0，0｝和｛7，7，7，7，7，7，7，7｝之间（节点号在实际编程时采用从0开始）。图5是一个全局解空间大体形状的示意图，是32个任务部署在8个节点上的8196个染色体的分布图。横坐标是染色体个数，纵坐标是染色体在解空间中的位置。图中可以看出在纵轴方向分为较明显的8段，是因为节点数为8，染色体中8和9的数值不可能存在。

图5 染色体全局解空间示意图

从中按照均匀分布原则抽取128个染色体加入到初始种群中，这128个染色体的分布图如图6所示。

图6 优化后的初始种群示意图

在128个均匀分布染色体的基础上，用CMI-DRF算法和贪心算法产生的4个精英个体替换掉其中的4个染色体，组成新的既有精英个体，分布又较为均匀的初始种群。

3.3 适应度函数设计

为了将问题的目标函数转换为指导遗传算法寻优的适应度函数，本文的适应度函数由三个部分组成，分别是σCPU、σMEM以及σIO，如下所示：

式（2）、（3）、（4）分别衡量CPU、MEM、IO的负载均衡状态。在处理多目标规划问题时，一般需要将多目标规划问题转化为单目标问题，类似地，遗传算法的适应度函数的设计也遵循这个原则。

假设LoadBalance（i）为第i条染色体的整体资源负载均衡值，那么它可以表示为

其中，σCPU(i)、σMEM(i)和*σIO(i)是第i条染色体的CPU、MEM和IO部分的负载均衡值。w1+w2+w3=1，且w1≥0，w2≥0，w3≥0。这里，w1、w2、w3分别为CPU、MEM和IO负载均衡部分的权重。

如果集群整体资源的负载均衡值越小，那么该任务调度方案越好。因此，本文的适应度函数为

其中，Fitness（i）为第i条染色体的适应值。

3.4 遗传操作改进

选择：选择操作是为了有效地选出优秀个体进行交叉，将其优秀基因遗传到下一代，本文根据每个个体适应度在整个种群总适应度中所占的比例，采用轮盘赌选择机制；

交叉：交叉操作的作用是使得算法能遍历更大的解空间，本文采用了基于交叉点的多点交叉的方式，即对一对染色体交叉点的后半部分基因进行交叉；

变异：变异操作是一种预防算法陷入局部最优的手段，本文采用的变异方式是，基于变异点的单点随机变异；

局部最优处理：在一般启发式算法中，在迭代过程中，算法容易陷入局部最优，导致最优个体的搜寻陷入停滞状态，如果没有干预，算法得到的解质量并不会很高。遗传算法也有同样的问题，虽然变异操作也可以预防局部最优，但是由于变异概率较小，而且变异点多为单点变异，跳出局部最优也需要较长的时间开销。为了处理该问题：本文提出了一种基于适应度大小的大变异。

Step1：比较当代最优个体适应值与上代最优个体适应值大小，如果相等，更新计数器：SAME_GEN，SAME_GEN←SAME_GEN+1；否则，继续下一轮迭代；

Step2：比较SAME_GEN与MAX_SAME_GEN大小，如果相等，则进入Step3；否则，继续下一轮迭代；

Step3：将当代所有个体按照适应值从大到小进行排序，找到排在后面的REPLACE_NUM个个体，替换其所有基因，替换方式为随机替换，形成新一代种群；

Step4：将Step3中形成的新一代种群替换当前种群，继续参与迭代计算。

由于新的种群既保留了前面迭代后遗传下来的优秀个体基因，又加入了新的个体，因此，能更好地跳出局部最优。

4 实验结果与分析

本文的算法实现采用C++编程语言，分别实现了基本遗传算法以及改进后的遗传算法，在任务数量固定和不固定场景下共进行了数百次实验，对两种算法的性能进行对比，验证了改进算法的有效性和在任务调度方面的性能提高情况。

4.1 任务数固定情况下的实验

在任务数固定的情况下，进行100次实验，比较基本遗传算法和改进遗传算法得到的最终可行解的适应值。

考虑到磁盘IO对性能影响较大，在实验中，我们给予了IO较高的权重，具体的实验参数设置如下。

任务数量：32，每次实验迭代次数：100，处理机数量：8，种群规模：128，遗传选择：轮盘赌选择，交叉概率：0.75，变异概率：0.05，CPU权重系数：0.1，内存权重系数：0.1，IO权重系数：0.8。

图7是100次实验后，基本遗传算法（BGA）和改进遗传算法（IGA）的适应值大小对比图。

图7 任务数固定情况下，多次实验的最终适应值对比图

由图7可以看出，在任务数量固定的场景中，改进后的遗传算法在100次实验中，最终的适应值绝大部分都大于基本遗传算法（下称BGA）得出的值，改进遗传算法（下称IGA）的平均适应值大约是基本算法的2.5倍。说明精英个体的加入以及局部最优处理确实可以起到指导种群向更好方向进化的作用，因而得到的可行解的质量也更好。

4.2 任务数变化情况下的实验

本次实验测试在不同任务数量的场景中，基本遗传算法和改进遗传算法的性能。考虑到遗传算法的随机性，本实验每组数据是连续10次实验结果的平均值。

实验参数设置如下：

每次实验迭代次数：100，处理机数量：8，种群规模：128，遗传选择：轮盘赌选择，交叉概率：0.75，变异概率：0.05，CPU权重系数：0.1，内存权重系数：0.1，IO权重系数：0.8。

实验中被调度的任务类型有8种，每种任务对CPU、MEM和IO的需求如表2所示，其中CPU单位是核心、内存是G字节、IO是一个比值。

表2 每种任务的资源需求

每轮实验通过增加任务的实例个数达到任务数量递增的效果，如每种任务部署5个实例则共有40个任务。每轮测试的结果如图8所示。

图8 不同任务数量下，两种算法最终适应值对比图

由图8可以看出：随着调度任务数量的增加，基本遗传算法的适应值有下降的趋势，BGA得到的最终可行解的质量并不高；但是与BGA不同的是，IGA在待调度任务数量增加时，依然可以得到较优的可行解，在0-120个任务的范围内，改进遗传调度算法的平均适应值大约是基本算法的2.6倍，表现出了更好的负载均衡性能。这是因为不论任务调度的规模如何，IGA算法的初始种群要优于BGA，而且IGA在迭代过程中会根据适应值的变化情况，适时地进行局部最优处理，保证了后代种群向着全局最优解的方向不断进化。与BGA相比，IGA不会因为调度任务规模的增大而出现适应值降低的情况，因此使用IGA算法进行任务调度时，能够获得更好的系统级负载均衡的效果。

5 结语

本文提出的基于多维度资源需求的改进遗传调度算法能够支持使用CPU、内存、磁盘IO三个维度的资源进行调度，使得任务对系统中各个节点资源的使用更加负载均衡，并能同时支持调度常驻和非常驻任务。算法通过初始种群的优化和局部最优处理，引导种群向更好的方向发展。实验结果表明，本文的改进遗传算法相对于传统的遗传算法取得了更好的效果。