一种基于节能树的大规模计算集群任务调度方法

摘要

本发明公开了一种基于节能树的大规模计算集群任务调度方法。本发明在面向大规模云数据中心的任务调度中，引入节能树作为模型，将数据节点作为节能树的叶结点，基于低能耗的目的，两两比较并选出最终的节能者。与此同时，本发明充分的考虑了大规模云数据中心的复杂情况，定义了任务比较系数，以此将不同的任务赋予不同的优先级，使得云数据中心在同时处理多个任务时的调度策略更为合理。相比现有的技术，本发明方法可以有效提高云数据中心的节点利用率，从而降低云数据中心的整体能耗。

权利要求

1.一种基于节能树的大规模计算集群任务调度方法，所述大规模计算集群包括一个管理节点和多个数据节点，管理节点将用户提交的任务分割为多个大小相同的子任务，并为每一个子任务分配相应的数据节点；其特征在于，管理节点为子任务分配相应的数据节点，其分配策略具体按照以下方法得到：步骤A、构建一颗完全二叉树，以所有具有额外计算能力的活跃态数据节点作为该二叉树的叶结点；

步骤B、对所有叶结点进行两两比较，分别选出其中的较节能者作为二叉树的上一层非叶结点；

步骤C、对所述上一层非叶结点再进行两两比较，分别选出其中的较节能者作为二叉树的再上一层非叶结点；依此类推，直到选出二叉树的根结点为止，管理节点将该根结点所对应的数据节点作为当前子任务拟分配的数据节点；

步骤D、更新数据节点的数据；

步骤E、对于剩余的未分配的子任务，依次重复执行步骤B-步骤D，直至为所有子任务找到拟分配的数据节点，从而得到最终的分配策略；

从两个节点DNA、DNB中选出其中的较节能者，具体按照以下方法：

假设使所述大规模计算集群达到最优资源配置时的单个数据节点的CPU利用率、磁盘传输速率分别为ORORU.CPU和ORORU.DIO，节点DNA当前的CPU利用率、磁盘传输速率分别为DNA.CPU、DNA.DIO，节点DNB当前的CPU利用率、磁盘传输速率分别为DNB.CPU、DNB.DIO，执行当前子任务所需的CPU利用率、磁盘传输速率分别为Task.CPU、Task.DIO；分别计算数组（（DNA.CPU+Task.CPU），（DNA.DIO+ Task.DIO））、（（DNB.CPU+Task.CPU），（DNB.DIO+ Task.DIO））、（DNA.CPU，DNA.DIO）、（DNB.CPU，DNB.DIO）与数组（ORORU.CPU，ORORU.DIO）之间的欧氏距离ED1、ED2、ED3、ED4；如ED1与ED4之和大于ED2与ED3之和，则节点DNA为较节能者；

否则，节点DNB为较节能者。

2.如权利要求1所述基于节能树的大规模计算集群任务调度方法，其特征在于，在步骤E中，如具有额外计算能力的活跃态数据节点数量不足时，则执行以下步骤：步骤1、假设存在L个子任务未找到拟分配的数据节点，选择L个休眠态数据节点，作为一颗完全二叉树的叶结点；

步骤2、对所有叶结点进行两两比较，分别选出其中的较节能者作为二叉树的上一层非叶结点；

步骤3、对所述上一层非叶结点再进行两两比较，分别选出其中的较节能者作为二叉树的再上一层非叶结点；依此类推，直到选出二叉树的根结点为止，管理节点将该根结点所对应的数据节点作为当前子任务拟分配的数据节点；

步骤4、更新数据节点的数据；

步骤5、对于剩余未分配的子任务，依次重复执行步骤2-步骤4，直至为所有L个子任务找到拟分配的数据节点；

步骤6、设L个子任务完成分配后，所述L个休眠态数据节点中有K个未部署任务，则激活L-K个休眠态数据节点后转至步骤A。

3.如权利要求1或2所述基于节能树的大规模计算集群任务调度方法，其特征在于，如同时存在多个任务需要调度，则管理节点首先按照各任务的任务比较系数从大到小的顺序对多个任务进行排序，然后依次进行子任务分割及子任务分配；所述任务的任务比较系数按照下式得到：式中， 表示第i个任务的任务比较系数， 分别为执行

第i 个任务所需的CPU利用率、磁盘传输速率，ORORU.CPU、ORORU.DIO分别为使所述大规模计算集群达到最优资源配置时的单个数据节点的CPU利用率、磁盘传输速率。

4.如权利要求3所述基于节能树的大规模计算集群任务调度方法，其特征在于，按照以下方法对多个任务进行排序：步骤a、构建一颗完全二叉树，以待排序的所有任务作为一颗完全二叉树的叶结点；

步骤b、对所有叶结点进行两两比较，分别选出其中的任务比较系数较大者作为二叉树的上一层非叶结点；

步骤c、对所述上一层非叶结点再进行两两比较，分别选出其中的任务比较系数较大者作为二叉树的再上一层非叶结点；依此类推，直到选出二叉树的根结点为止；记录该根结点所对应的任务；

步骤d、将选出的根结点从二叉树中删除；

步骤e、重复执行步骤b-步骤d，直至所有任务均完成选择；按照被选作为根结点的从前到后的次序对所有任务进行排序。

说明书

一种基于节能树的大规模计算集群任务调度方法

技术领域

[0001] 本发明涉及一种大规模计算集群任务调度方法，尤其涉及一种利用节能树降低能耗的大规模计算集群任务调度方法，属于计算机网络技术领域。

背景技术

[0002] 随着以云计算（Cloud Computing）为代表的大规模计算集群技术的兴起和发展，大规模云数据中心（Cloud Data Center）作为云计算技术的基础设施，也进入了高速发展的阶段。云数据中心的高能耗对自然环境产生的污染问题日渐突出，成为了世界各国普遍关心的热点问题。在数据中心的生命周期中，能耗成本已经超过硬件成本，成为继人力资源成本之后的第二大成本支出。如何降低并有效的控制能耗，已经成亟待解决的关键问题。

[0003] 为了保障服务的质量，目前数据中心大多按最高负载可能来进行构建和配置服务器集群，这使得服务器的利用率一般不足30%。数据中心的基础设施没有得到充分的利用是造成能源浪费的主要原因之一。

[0004] 从能耗的角度而言，运行在低利用率和高利用率的服务器所产生的热量和消耗的电力十分接近，单个服务器节点在CPU利用率低的情况下所产生的能耗与得到充分利用的情况下所产生的能耗相差无几。当磁盘利用率一定时，CPU利用率在10%和80%的情况下所产生的能耗差别很小，这为我们进一步的研究提供了很大的空间。

发明内容

[0005] 本发明所要解决的技术问题在于克服现有大规模云数据中心存在的高能耗问题，提供一种基于节能树的大规模计算集群任务调度方法，利用节能树模型，将数据节点作为节能树的叶结点，基于低能耗的目的两两比较并选出最终的节能者，有效降低了大规模云数据中心的能耗。

[0006] 本发明采用以下技术方案解决上述技术问题。

[0007] 一种基于节能树的大规模计算集群任务调度方法，所述大规模计算集群包括一个管理节点和多个数据节点，管理节点将用户提交的任务分割为多个大小相同的子任务，并为每一个子任务分配相应的数据节点；管理节点为子任务分配相应的数据节点，其分配策略具体按照以下方法得到：

[0008] 步骤A、构建一颗完全二叉树，以所有具有额外计算能力的活跃态数据节点作为该二叉树的叶结点；

[0009] 步骤B、对所有叶结点进行两两比较，分别选出其中的较节能者作为二叉树的上一层非叶结点；

[0010] 步骤C、对所述上一层非叶结点再进行两两比较，分别选出其中的较节能者作为二叉树的再上一层非叶结点；依此类推，直到选出二叉树的根结点为止，管理节点将该根结点所对应的数据节点作为当前子任务拟分配的数据节点；

[0011] 步骤D、更新数据节点的数据；

[0012] 步骤E、对于剩余的未分配的子任务，依次重复执行步骤B-步骤D，直至为所有子任务找到拟分配的数据节点，从而得到最终的分配策略。

[0013] 在子任务过多或云数据中心过于繁忙的情况下，很可能会出现活跃态数据节点数量不足的情况，即部分子任务未找到合适的活跃态数据节点，此时就需要激活部分处于休眠态的数据节点。为了避免云数据中心大量休眠节点被不必要的激活，从而造成额外的能源浪费，本发明进一步采用以下技术方案：

[0014] 在步骤E中，如具有额外计算能力的活跃态数据节点数量不足时，则执行以下步骤：

[0015] 步骤1、假设存在L个子任务未找到拟分配的数据节点，选择L个休眠态数据节点，作为一颗完全二叉树的叶结点；

[0016] 步骤2、对所有叶结点进行两两比较，分别选出其中的较节能者作为二叉树的上一层非叶结点；

[0017] 步骤3、对所述上一层非叶结点再进行两两比较，分别选出其中的较节能者作为二叉树的再上一层非叶结点；依此类推，直到选出二叉树的根结点为止，管理节点将该根结点所对应的数据节点作为当前子任务拟分配的数据节点；

[0018] 步骤4、更新数据节点的数据；

[0019] 步骤5、对于剩余未分配的子任务，依次重复执行步骤2-步骤4，直至为所有L个子任务找到拟分配的数据节点；

[0020] 步骤6、设L个子任务完成分配后，所述L个休眠态数据节点中有K个未部署任务，则激活L-K个休眠态数据节点后转至步骤A。

[0021] 优选地，从两个节点DNA、DNB中选出其中的较节能者，具体按照以下方法：

[0022] 假设使所述大规模计算集群达到最优资源配置时的单个数据节点的CPU利用率、磁盘传输速率分别为ORORU.CPU和ORORU.DIO，节点DNA当前的CPU利用率、磁盘传输速率分别为DNA.CPU、DNA.DIO，节点DNB当前的CPU利用率、磁盘传输速率分别为DNB.CPU、DNB.DIO，执行当前子任务所需的CPU利用率、磁盘传输速率分别为Task.CPU、Task.DIO；分别计算数组（（DNA.CPU+Task.CPU），（DNA.DIO+Task.DIO））、（（DNB.CPU+Task.CPU），（DNB.DIO+Task.DIO））、（DNA.CPU，DNA.DIO）、（DNB.CPU，DNB.DIO）与数组（ORORU.CPU，ORORU.DIO）之间的欧氏距离ED1、ED2、ED3、ED4；如ED1与ED4之和大于ED2与ED3之和，则节点DNA为较节能者；否则，节点DNB为较节能者。

[0023] 进一步地，如同时存在多个任务需要调度，则管理节点首先按照各任务的任务比较系数从大到小的顺序对多个任务进行排序，然后依次进行子任务分割及子任务分配；所述任务的任务比较系数按照下式得到：

[0024]

[0025] 式中，Weighti表示第i个任务的任务比较系数，Taski.CPU、Taski.DIO分别为执行第i个任务所需的CPU利用率、磁盘传输速率，ORORU.CPU、ORORU.DIO分别为使所述大规模计算集群达到最优资源配置时的单个数据节点的CPU利用率、磁盘传输速率。

[0026] 相比现有技术，本发明具有以下有益效果：

[0027] （1）使节点的存储方式和计算能力同该节点所分配的工作负载尽可能匹配，避免因节点不充分利用而造成的资源和能源浪费；

[0028] （2）使工作节点的数量同当前的任务量匹配，其余的节点在低能耗或休眠的节能模式下运行；

[0029] （3）随着云数据中心规模的增大，为某一个任务选择出合适的节点的时间呈指数增长，本发明考虑到云数据中心本身所具有的海量节点，在合理的时间内提供合适的结果；

[0030] （4）目前的云数据中心，节点通常被分为多种运行状态；本发明能够针对节点的多种状态进行有效的区分，不同状态的节点进行任务的不同分配，避免云数据中心大量休眠节点被不必要的激活，造成额外的能源浪费；

[0031] （5）云数据中心作为一个开放的平台，很可能在同一时段接受大量各种不同的任务，本发明在提供了单任务调度的策略的同时，考虑到多任务并行执行的情况，从而能够针对多任务情况提供一个合适的方法来对不同的任务进行有效的区分。

附图说明

[0032] 图1为节能树的结构示意图。

具体实施方式

[0033] 下面结合附图对本发明的技术方案进行详细说明：

[0034] 本发明的思路是在对任务分配数据节点时，利用节能树模型，将具有额外计算能力的活跃态数据节点作为一棵完全二叉树的叶结点，从能耗的角度将所有叶结点进行两两比较，较低能耗的节点作为节能者，选出的节能者作为上一层非叶结点，再进行两两比较，如此重复，直到选出根结点为止，根结点即为最合适的数据节点。

[0035] 在对本发明技术方案进行详细描述前，先对大规模计算集群的系统模型进行简要介绍：

[0036] 1)节点模型

[0037] 本发明采用的云数据中心的节点，从功能上分为两类：管理节点和数据节点，当用户将任务提交给云数据中心后，由管理节点负责将用户的任务切分成若干个子任务后选择合适的数据节点部署任务。并在所有子任务处理完成后，由管理节点将结果返回给用户。定义如下:

[0038] 定义1管理节点（Master Node，MN），云数据中心的管理节点，逻辑上唯一，负责整个云数据中心的管理。

[0039] 定义2数据节点（Data Node，DN），可被抽象为以下四元组：

[0040] DN=(ID,CPU,DIO,State) （1）

[0041] 上式中ID为数据节点的唯一标识；CPU为数据节点的当前CPU利用率，DIO为数据节点当前的磁盘传输速率，这两个指标用于表示数据节点当前已使用的计算能力；State为数据节点当前状态，且每个节点都可能处在下列两种工作状态之一：

[0042] 状态A（活跃态（Active））：节点上有计算任务，并可以继续承担系统部署的任务。

[0043] 状态B（休眠态（Dormant））：节点上无计算任务，但可以承担系统部署的任务。

[0044] 当一个处于活跃态的节点完成自身的任务后，将自动进入休眠状态（本发明指深度休眠，此时该节点不产生任何能耗）。管理节点可向处于休眠态的数据节点部署任务，当数据节点接收到任务后自动转为活跃态并立刻开始处理任务。

[0045] 对于一个特定规模的云数据中心，存在着一个CPU利用率和当前磁盘传输速率的最优资源组合。

[0046] 定义3最优资源配置（Optimal Configuration of Resource Utilizations，OCORU），可被抽象为以下二元组：

[0047] OCORU=(CPU,DIO) （2）

[0048] 当该云数据中心的每个数据节点的DN.CPU和DN.DIO都工作在ORORU.CPU和ORORU.DIO时，整个云数据中心处理单位数据的能耗最低，即此时每消耗单位电力所获得的回报最高。对某一特定的云数据中心OCORU.CPU和OCORU.DIO均为常数，可实际测得。

[0049] 2)任务模型

[0050] 定义4任务（Task），可被抽象为以下六元组

[0051] Task=(ID,Data,Code,CPU,DIO,Amount) （3）

[0052] 上式中ID为任务的编号，是该任务与其他任务相区别的唯一标识；Data表示用户向云计算中心提交的，其想要处理的原始数据，将会被管理节点切分成多份子数据，以便分布在若干个数据节点上进行处理；Code表示用户向云计算中心提交的处理Data的程序代码，Code中用户包含处理Data的方法和这些方法与Data的映射关系；CPU表示运行该任务所需的CPU利用率，管理节点只向OCORU.CPU-DN.CPU>Task.CPU的数据节点派遣该任务的子任务；DIO表示运行该任务所需的DIO利用率，管理节点只向OCORU.DIO-DN.DIO>Task.DIO的数据节点派遣该任务的子任务；Amount表示该任务子任务的数量，对于特定环境的特定任务而言是一个常数。

[0053] 用户租用云计算中心的设备，需要向云数据中心提供其想要处理数据以及处理数据的程序代码，管理节点将用户提供的任务切分成若干个的子任务分布到数据节点上执行。

[0054] 定义5子任务（SubTask），可被抽象为以下三元组：

[0055] SubTask=(ID,Data,Code) （4）

[0056] 上式中ID为子任务的编号，每个子任务有且只有一个与其他子任务不同的编号，是这个子任务与其他子任务相区别的唯一标识；子任务的ID与任务的ID存在对应关系，可以通过子任务ID推知这个子任务属于哪个任务；当所有子任务完成后，管理节点依据子任务的ID将结果有序汇总后返回给用户。Data表示由管理节点将用户提交的原始数据切分后得到的子数据。Code表示用户提交的代码中与该子任务的子数据相映射的部分代码，包含了该子任务相关的子数据的处理方法。

[0057] 根据上述描述可知，一个大规模云数据中心的任务调度问题可以抽象为以下情况：云数据中心的最优资源配置值为(OCORU.CPU,OCORU.DIO)，共有n个处于活跃态的同构数据节点{DN1，DN2，DN3……DNn}和k个处于休眠态的数据节点，第i个处于活跃态的数据节点表示为(DNi.CPU,DNi.DIO)。任务Task被切分成Task.Amount个子任务{SubTask1,SubTask2,SubTask3,……SubTaskTask.Amount}，管理节点需要将这Task.Amount个子任务部署在云数据中心的数据节点上。

[0058] 本发明在对子任务进行调度时，具体按照以下方法：

[0059] 步骤A、构建一颗完全二叉树，以所有具有额外计算能力的活跃态数据节点作为该二叉树的叶结点；

[0060] 步骤B、对所有叶结点进行两两比较，分别选出其中的较节能者作为二叉树的上一层非叶结点；

[0061] 步骤C、对所述上一层非叶结点再进行两两比较，分别选出其中的较节能者作为二叉树的再上一层非叶结点；依此类推，直到选出二叉树的根结点为止，管理节点将该根结点所对应的数据节点作为当前子任务拟分配的数据节点；

[0062] 步骤D、更新数据节点的数据；

[0063] 步骤E、对于剩余的未分配的子任务，依次重复执行步骤B-步骤D，直至为所有子任务找到拟分配的数据节点，从而得到最终的分配策略。管理节点按照最终的分配策略对子任务进行实际分配部署。

[0064] 在用完全二叉树定义节能树时，可用数组e[1...n]表示n名参加比较的数据节点的节点编号，用数组t[1...n-1]表示组成的完全二叉树的n-1个内部节点，t[i]的值是数组e[]中的比较节能者的下标，当外面节点个数为n是内部节点数为n-1。图1给出了n=5时的节能树中各节点与数组e[]和t[]之间的对应关系。

[0065] 设根到最远层内部节点的路径长度s为从根到该内部节点路径上的分支条数，则对有n个叶结点的节能树有：

[0066]

[0067] 这样，最远层最左端的内部节点的编号为2s，最远层的内部节点个数为n-2s。此处用lowExt代表最远层的外部节点数目，offset代表最远层外部节点之上所有节点数目：

[0068] offset=2s+1-1 （6）

[0069] 每一个外部节点e[i]所对应的内部节点t[k]，i和k之间存在如下的关系：

[0070]

[0071] 如图1中，外部节点数n=5，s=2，最远层最左端的内部节点为t[2s]=t[4]，该层的s内部节点数共有n-2=5-4=1。

[0072] 当数据中心分配一个子任务时，需新建一棵节能树，并以所有可用的数据节点为树的叶结点，将节能树进行初始化。初始化完成后，节能树的根结点，即为最合适的数据节点。通常，可直接以所有具有额外计算能力的活跃态数据节点作为可用数据节点，设n为具有额外计算能力的处于活跃态的数据节点的数量，由上述可知，根到最远层内部节点路径s上的分支条数 最远层的外部节点数目为lowExt=2×(n-2)，最远层外部节
点之上所有节点数目offset=2s+1-1，t[]用来存储比较的节能者的下标即数据节点的节点编号，winner(DNA,DNB)用于获得DNA、DNB,之间的节能者，初始化过程用伪代码表示如下：

[0073]

[0074]

[0075] 下面对上述伪代码作进一步说明：

[0076] 算法1中1~3行为预处理内容，分别对s、lowExt和offset值进行初始化。

[0077] 任务执行过程如下：

[0078] （1）（算法1第5行到7行）表示从节能树最远层的外部节点i开始逐层向上进行比较。

[0079] （2）（算法1第8行到11行）为了执行由其他n-lowExt个节点激活的比较，必须确定n是否为奇数。若n为奇数，则DNlowExt+1为右孩子，否则为左孩子。当n为奇数时，内部节点要与外部节点比较，对手为DNt[n-1]，父节点为DNt[(n-1)/2]。

[0080] （3）（算法1第12行到14行）表示从节能树最左侧剩余节点处开始，处理其他剩余外部节点的比较。t[1]为最终节能者（即最优的数据节点）。

[0081] 算法2（第15行到20行）为比较的实现过程，比较从DNk处开始，DNlc,DNrc是DNk的左孩子和右孩子。

[0082] 算法1和算法2中，仅当从一个节点的右孩子上升到该节点时，才在该节点进行一次比较。倘若是从左孩子上升到该节点，因其右子树的节能者尚末确定，因而不能在该节点上进行比较。

[0083] 算法3为叶结点之间进行比较并选出节能节点的方法，本发明采用以下方法进行比较：假设使所述大规模计算集群达到最优资源配置时的单个数据节点的CPU利用率、磁盘传输速率分别为ORORU.CPU和ORORU.DIO，节点DNA当前的CPU利用率、磁盘传输速率分别为DNA.CPU、DNA.DIO，节点DNB当前的CPU利用率、磁盘传输速率分别为DNB.CPU、DNB.DIO，执行当前子任务所需的CPU利用率、磁盘传输速率分别为Task.CPU、Task.DIO；分别计算数组（（DNA.CPU+Task.CPU），（DNA.DIO+Task.DIO））、（（DNB.CPU+Task.CPU），（DNB.DIO+Task.DIO））、（DNA.CPU，DNA.DIO）、（DNB.CPU，DNB.DIO）与数组（ORORU.CPU，ORORU.DIO）之间的欧氏距离ED1、ED2、ED3、ED4；如ED1与ED4之和大于ED2与ED3之和，则节点DNA为较节能者；否则，节点DNB为较节能者。举例来说，假设有两个数据节点DNA,DNB，DNA的当前CPU利用率为30，磁盘传输速度为30(表示为(30,30))，DNB的当前CPU利用率为40，磁盘传输速度为10(表示为(40,10))。管理节点将选择两个节点中的一个来承担某一需求(10,10)的任务，云数据中心的最优资源配置值为(80,50)。该方法首先计算欧几里得距离δ，数据节点DNA的初始距离 数据节点DNB的初始距离
若将任务分配给DNA则分配后的距离变为41.2，若将任务分配
给DNB则分配后的距离变为42.4。把作业分配给数据节点DNA后使得数据节点DNA和数据节点DNB的总的欧几里得距离更大，所以选择此方案。具体过程如下：

[0084] （1）（算法3第22到25行）用来考察叶结点是否有额外的计算能力才处理任务，若该数据节点不能满足OCORU.CPU-DN.CPU>Task.CPU且OCORU.DIO-DN.DIO>Task.DIO的条件则说明其没有足够的剩余计算能力来承担任务，直接判负。

[0085] （2）（算法3第26到29行）对两个DNA，DNB,计算其欧几里得距离并返回∑δ大的节点。

[0086] 在初始化节能树的过程中，第一次循环计算s需要O(log2n)的时间，第二次和第三次循环（包括方法2）共需O(n)，因此总的时间复杂度为O(n)。

[0087] 然而在子任务过多或云数据中心过于繁忙的情况下，很可能会出现活跃节点数量不足的情况。本发明也通过构建节能树的方式来决定需要激活的休眠节点的数量。基本思想是：假设存在L个剩余子任务，则以L个数据节点为树的叶结点，这L个数据节点的CPU,DIO都为零；初始化完成后，重新比较直到L个子任务都被分配为止并返回任务派遣数组；检查该数组，得到K个未被部署子任务的数据节点，L-k即为应当激活的数据节点的数目；重新初始化一棵节能树，以n个处于活跃态的数据节点和L-K个处于休眠态的数据节点作为叶结点，进行比较；最终得到的任务派遣数组即为最终的任务部署方案。具体地，在步骤E中，如具有额外计算能力的活跃态数据节点数量不足时，则执行以下步骤：

[0088] 步骤1、假设存在L个子任务未找到拟分配的数据节点，选择L个休眠态数据节点，作为一颗完全二叉树的叶结点；

[0089] 步骤2、对所有叶结点进行两两比较，分别选出其中的较节能者作为二叉树的上一层非叶结点；

[0090] 步骤3、对所述上一层非叶结点再进行两两比较，分别选出其中的较节能者作为二叉树的再上一层非叶结点；依此类推，直到选出二叉树的根结点为止，管理节点将该根结点所对应的数据节点作为当前子任务拟分配的数据节点；

[0091] 步骤4、更新数据节点的数据；

[0092] 步骤5、对于剩余未分配的子任务，依次重复执行步骤2-步骤4，直至为所有L个子任务找到拟分配的数据节点；

[0093] 步骤6、设L个子任务完成分配后，所述L个休眠态数据节点中有K个未部署任务，则激活L-K个休眠态数据节点后转至步骤A。

[0094] 整个执行过程用伪代码表示如下：

[0095]

[0096] 任务执行过程如下：

[0097] （1）（算法4第30行）表示新建一个节能树并初始化，得到第一个子任务要部署的数据节点的下标。

[0098] （2）（算法4第31行到37行）因为选择了一个数据节点并部署了子任务，该数据节点的CPU和DIO都已经发生了变化。更新节能树，重新组织比较，选出另一个数据节点，直到所有Task.Amount个子任务都得到部署。最终返回一个含有m个元素的数组a[]记录了Task.Amount个子任务所对应的数据节点的编号。

[0099] （3）（算法4第38行到57行）求得剩余子任务的数量L，以L个数据节点为树的叶结点，初始化节能树。重新比较得到K个未被部署子任务的数据节点，L-k即为应当激活的数据节点的数目。重新初始化一棵节能树，以n个处于活跃态的数据节点和L-K个处于休眠态的数据节点作为叶结点，进行比较，最终返回一个含有Task.Amount个元素的数组a[]记录了Task.Amount个子任务所对应的数据节点的编号。

[0100] 算法5（第59行到72行）为重新组织比较的过程，由于节能树已经初始化，更新后的节能树只有节能者的值发生改变。所以需重新执行从节能者对应的外部节点到根的路径上的所有比较。

[0101] 上面已经分析过，节能树初始化过程的时间复杂度为O(n)。在此基础上重构该节能树，每次重构节能树的时间代价为O(log2n)，因此整个过程的时间复杂度为O(nlog2n)。

[0102] 云系统是开放的大型多用户系统，这很大程度上增加了问题的复杂性，很可能出现在同一个时段，有多个用户都提交了各自的任务的情况。若此时同时有(10,10)和(50,20)两个任务。按照初始方法，将(10,10)分配给节点NDA后变为NDA(40.40)，NDB(40,20)此时为了部署(50,20)的任务需重新激活一个休眠节点，成为有三个数据节点(40,40),(40,20),(50,20)的情况。若先部署(50,20)的任务，可知NDA、NDB中只有前者有能力承载该任务，于是将其分配给NDA。后再部署(10,10)任务此时只有NDB有能力承载该任务，于是分配给NDB。最终只有两个数据节点分别为(80,50)、(50,50)。第一种分配方式不仅比第二种多用了一个数据节点，而且每个数据节点距离最优资源配置值都有一定的差距，从节能的角度来说显然第二种分配方式更为合理。

[0103] 计算量小的任务有更好的灵活性，优先部署大任务后再部署小任务，往往可以利用小任务的灵活性填补数据节点剩余的计算资源以接近最优资源配置，而不用激活休眠节点，减少了系统的开销。

[0104] 当任务分别为(10,10)和(50,20)时，10<50、10<50我们可以很直观的比较出任务的大小即(10,10)小于(50,20)。可是当两个任务变成(10,20)，(20,10)的时候，我们便不能通过原来的方法直接将任务进行比较。为了解决这个问题，我们定义一个任务比较系数Weight。

[0105] 定义6对某一个任务Taski来说，该任务所对应的任务比较系数如下所示：

[0106]

[0107] 本发明中每个数据节点所能提供的CPU和DIO均要小于OCORU.CPU和OCORU.DIO。通常情况下OCORU.CPU与OCORU.DIO的值并不接近，因此为了对任务的大小进行公平的比较，需要对任务需求的CPU和DIO依照最优资源配置值的不同进行区别对待，赋予不同的权重。 即为任务所需CPU的权重， 即为任务所需DIO的权重。设
(OCORU.CPU,OCORU.DIO)=(80,50),则(10,20)的比较系数为0.525，(20,10)的比较系数为0.45，由此任务(10,20)大于(20,10)，为这两者中的大任务。

[0108] 多 任 务 的 情 况 抽 象 为 如 下 形 式：假 设 有m个 任 务 {Task1，Task2，Task3......Taskm}，云数据中心共有n个处于活跃态的同构数据节点{DN1，DN2，DN3……DNn}和k个处于休眠态的数据节点，管理节点需要将这m个任务部署在云数据中心上。数据中心的最优资源配置值为(OCORU.CPU,OCORU.DIO)，所有节点均运行在该值之下。

[0109] 在云数据中心同时收到多个任务的情况下，本发明采取大任务优先的调度原则，其基本思想是：先利用节能树对所有任务进行排序，将比较系数大的任务选择为节能节点，重复进行比较，由此可得到一个优先级由大到小的任务队列。管理节点按所得的任务队列再依次进行分配直到所有任务都分配完毕为止。整个执行过程用伪代码表示如下：

[0110]

[0111] 任务执行过程如下：

[0112] （1）（算法6第73行）表示以m个Task为根结点新建一个节能树并初始化。

[0113] （2）（算法6第74行到78行）将节能树的根结点放入数组a[]中，更新节能树，将已经取得冠军的节点从节能树删除，重新组织比较，选出另一个数据节点，直到所有任务排序结束。最终返回一个含有m个元素的数组a[]，从a[1]到a[m]为依次处理任务的优先次序。

[0114] （3）（算法6第79行到82行）对每一个单任务，分别进行子任务分割及子任务分配，直到所有任务部署完毕。

[0115] 由上述可知，对单个任务部署的时间复杂度O(nlog2n)，对m个任务每次都需要进行一次单任务部署，因此时间复杂度为O(mnlog2n)。在一个云数据中心中，通常同时处理任务的数量m远小于将任务切分成的子任务的数量，所以方法的时间复杂度可以近似为O(nlog2n)。