一种基于深度信念网络的云数据中心请求流调度方法

摘要

本发明公开一种基于深度信念网络的云数据中心请求流调度方法，综合考虑了不同种类请求所能带来的价值以及计算集群能耗等因素在请求处理时间内的变化。使用历史数据：包括每种请求的数量、资源申请量，处理请求所能带来的收益、时间，集群资源总量等，通过建立的利润计算模型计算所能得到的价值。使用请求流数据对深度信念网络(Deep Belief Network,DBN)进行训练，而后使用分类器和其输出对DBN进行调整。使用调整好的DBN获取调度树配置方案，对调度树进行调整，并结合节点效率图进行对节点资源的调度，同时根据实际调度情况对节点效率图进行修改，最终使得云数据中心处理该批次的请求获得的利润最大化。

权利要求

1.一种基于深度信念网络的云数据中心请求流调度方法，其特征在于，包括如下步骤：S1、根据建立的利润计算模型对历史数据进行计算，从而得到该数据条件下，所能获得的利润，并使用所计算得到的利润作为评判标准给历史数据添加标签；

S2、将添加了标签的历史数据分为训练集和测试集，并将训练集的数据进行归一化处理，使用处理之后的训练集对DBN网络进行训练；而后使用分类器和其输出对DBN网络的权值w和偏差值b进行调整；

S3、使用测试集对训练完毕的DBN进行测试，并根据测试结果对DBN的超参数进行调整；

S4、使用当前时刻的请求流数据和已经调整好的DBN获取最优的调度树配置方案并对调度树进行调整，其后根据节点效率图对请求流进行调度，以使调度当前请求流的获利最大，同时根据实际调度情况对节点效率图实时进行修改，为下一次调度做准备；

所述利润计算模型的结果为Profit，所描述的利润计算模型为：Profit＝Revenue‑Cost其中，Revenue表示处理在时间间隔t内到来的任务请求所能带来的收益；Cost表示在时间间隔t内，集群处理请求所消耗的能量成本与人力使用成本之和； 表示在时间间隔t内第k类请求的个数；gm表示在时间间隔t内第k类请求的平均资源申请量；tk表示在时间间隔t内每一个请求的实际执行时间；R表示集群资源的总量； 是代表调度延迟的变量，n表示延迟调度的时间，如果在时间间隔t内该请求进行了调度，则 否则qt代表在时间间隔t内调度该请求，并在一段时间完成之用户可能拥有的满意度,i代表超时调度的折损率；l表示请求的个数； 表示在时间间隔t内实际处理完成第k类请求的个数；zt表示在时间间隔t内该节点能耗与使用效率间的关系系数；pmax和pmin表示每个集群资源的最大和最小使用率； 表示在时间间隔t内单位能耗所需要花费的价格；

所述利润计算模型的约束包括：在时间间隔t内，总CPU和内存需求均不能超过限定所给出的最大配置，总需求不能超过计算集群原本的容量限制：dtCPUt≤CPUl；

dtMemoryt≤Memoryl；

其中，CPUt表示在时间间隔t内每个请求所需要的CPU的平均个数；Memoryt表示在时间间隔t内每个请求所需要的内存的平均大小；CPUl表示系统对单个请求所能申请的CPU资源数量的限制；Memoryl表示系统对单个请求所能申请的内存资源数量的限制；CPUR表示计算集群的CPU的容量限制；MemoryR表示计算集群的内存的容量限制；

非线性约束优化模型的约束还包括：如果该请求可以在t时间内完成，即或 如果未在t时间内完成，则 或

具体约束为：

步骤2中使用的DBN网络由2层RBM和1层BP网络构成，权值w和偏差值b用来对DBN网络层与层之间关系以及激活概率p进行计算，使用对比散度算法(CD‑k)来对每层RBM进行无监督贪婪训练；通过将输入值赋值给显层，计算出隐层中每个神经元被激活的概率，从计算得到的概率中采用Gibbs抽样抽出样本，计算显层中每个神经元被激活的概率，若干次计算之后，隐层可以精准的显示显层的特征；训练完毕后的每层RBM只能保证在自身层内权值w和偏差值b达到最优，所以使用BP网络根据其输出结果和给定对应的历史数据的标签进行判断，将错误信息自顶向下传播至每一层RBM，微调整个DBN网络，使整个DBN网络中的权值w和偏差值b达到最优；

步骤3中需要调整的超参数包含：影响DBN网络学习速度的学习率η、对网络出现过拟合情况进行调整的正则化参数λ、影响分类正确率的学习的回合数Epoch和每个隐层中神经元的个数j；通过使用Spark运行DBN网络同时通过反复迭代S2、S3，根据以往的经验和测试结果的图表规律对这些超参数进行方差分析、拟合优度检验，而后根据结果对其进行调整，直至其测试出现最优结果；

建立调度树配置计算模型，其参数为根据数据请求所计算出的调度算法的配置方案，和当前调度树的配置参数，具体为：

其中，fold为调度树目前同种类请求子节点下可以存储的非叶子节点的最大数量，fnew为根据作业请求的数量、平均资源申请量和fold所计算的同种类请求子节点下可以存储的非叶子节点的最大数量；lold为调度树中叶子节点可以存放的待调度请求的最大数量，lnew为根据请求数据和lold所计算的叶子节点可以存放的待调度请求的最大数量。

说明书

一种基于深度信念网络的云数据中心请求流调度方法

技术领域

[0001] 本发明涉及云数据中心任务调度技术领域。更具体地，涉及一种基于深度信念网络的云数据中心请求流调度方法。

背景技术

[0002] 现如今我们正处于一个信息化的社会，随着信息的日益增加，信息所能带来的价值也愈发巨大。各个拥有大型数据的企业也逐渐在从中获取利益并将其扩大。淘宝网可以
利用自身的数据解读出中国的消费趋势，对数据进行分析根据用户的喜好推荐类别相同的
产品，以扩大销售额。交管局可以根据实时的交通信息，对交通红绿灯进行管控，来动态调
节道路车流量减少拥堵，提高出行效率。

[0003] 由于计算中心的造价是高昂的，所以云计算服务可以通过网络向海量的用户提供计算的模式也借此得以大力发展.云服务为企业带来的便利性,吸引了越来越多的公司将
其应用部署在云数据中心中。但是不管是企业自身，还是云服务提供商的数据中心,都面临
着相同的问题—计算框架以及计算需求的多样化。这些不同的需求使得对计算资源的调度
更加复杂。不管是对于企业或是云服务服务提供商，不同种类或是不同提出者所提交的计
算请求，往往会带来不同的计算收益。企业的一些耗费资源巨大的计算带来的收益可能却
是极少，但是这种计算往往又是必需的。云平台等计算服务提供者，通常是通过为用户提供
计算服务来按需收费，但是不同级别的用户所能带来的收益也不尽相同。所以根据每种计
算请求价值的不同来对资源进行分配，以获取最大利益具有重要意义。

[0004] 国际著名科技咨询机构Gartner表明数据中心所消耗的能源是巨大的，影响计算能耗的最大原因为集群负载，不同的负载所带来的能源损耗也不同。但是按照最低的可能
负载配置服务器资源会造成体验服务等级目标(Service Level Objective，SLO)的违背，
所以用户请求的运行时间为影响获利的另外一个重要因素。同时，因为计算集群的种种物
理原因，会拥有不同计算瓶颈，带来的计算效率也会有很大差别。当海量不同种类型的请求
来临时，在不拖慢集群运行效率的情况下，充分利用集群资源，以缩短请求的平均处理时
间，对以最大获利为目标的调度策略具有重要意义。

[0005] 所谓调度就是将调取器通过一定的规则(调度算法)，对被调度的作业进行一系列的处理(资源分配)，来达到一定的目的(将任务进行合理的分配，使其对集群资源进行合理
使用，减少任务的平均响应时间)。目前已知的调度算法，根据其算法本身的特性和解决调
度问题思路的不同，可以分为实时调度算法和启发式调度算法两类。实时调度算法以快速
实时为中心思想，作业一旦到来就对其进行快速处理，进而在极短的时间内为其进行调度，
完成资源的合理分配。调度作业所需的时间短，不需要耗费额外的计算资源，但其因为无法
更加细致的对集群中各个节点的负载进行考虑，可能会使集群各个节点出现负载不均衡的
情况。启发式调度算法，将需要多维资源的作业调度当成一个类多维背包问题，将集群中的
各类资源视为背包，作业对各类资源的需求作为物品，将任务完成时间或集群利用率作为
参数，通过使用蚁群、粒子群、遗传、模拟退火、人工神经网络等启发式算法求解，根据其求
出的全局近似最优解来进行调度。虽然可以将集群中资源利用率最大化，一定程度上减少
任务完成所需要的时间，并对集群负载的均衡进行了充分的考虑，但是其计算过为复杂，需
要消耗额外的计算资源，当集群中的节点和任务过多时，将会带来巨大的计算开销。鉴于这
两者的优缺点，本发明将二者有机结合，提出以获利最大为目标的树形层级调度策略。

[0006] Hadoop这一分布式文件系统目前正被广泛使用，而其上的MapReduce分布式计算框架由于其高效和易用性得到了广泛的认可，被应用于各种计算。但随着大数据的发展，人
们对于信息的认知也越发细腻，对信息处理的要求逐渐提高，单一的离线计算框架已经不
能满足研究人员的计算需求，可以进行用于迭代计算的实时计算框架Spark、针对流数据的
计算框架Storm等各种计算框架应运而生。Hadoop为了将这些计算框架进行统合，提出了资
源管理系统YARN。

[0007] 本发明基于Hadoop的pull‑base通信机制，以及基于事件驱动的Hadoop调度器，提出一种以获取最大利益为目标的调度策略。

发明内容

[0008] 本发明的目的在于提供一种以获利最大为目标的树形层级调度策略，综合考虑每类请求所能带来的收益、计算集群的单位时间内的能耗以及服务等级目标SLO，并根据实时
型调度算法与启发式调度算法的优缺点，提出自适应的树形层级调度策略，从而达到获取
最大收益的目标。

[0009] 为达到上述目的，本发明采用下述技术方案：

[0010] 根据本发明的一个方面，建立了Hadoop环境下计算处理一段时间内所有请求所能获取的最大利益的计算模型，将历史数据，包括每种请求的数量，处理该类请求所能带来的
收益，此时集群的总资源，每种请求所申请的资源(CPU和内存)，请求处理完成所需的时间，
作为参数进行建模，进而最终得到处理一段时间内所有请求所能获取的最大利益的计算模
型。同时通过根据节点资源使用率和在该使用率下平均任务完成时间建立节点效率图，作
为对节点资源调度的约束，以保证在不减慢任务运行速度的情况下，最大化的利用节点资
源。

[0011] 根据本发明的另一方面，对优先级、公平分享法、主资源公平分享法、先来先服务、短任务优先，五种调度算法，在不破坏其自身特点的情况下，根据Hadoop的调度模式以及使
用特点进行调整。使用树形层级的调度模型，以缩短调度时间并提高调度效率。其中，此调
度模型的参数如下：

[0012] (1)请求的种类，决定根节点下子节点的数量；

[0013] (2)不同种类请求间的调度策略，用以调度根节点下存储不同请求的子节点间的调度；

[0014] (3)同种类请求子节点下可以存储的非叶子节点的最大数量，为每个节点所能拥有的子节点的数量的约束，以减少在调度过程中不必要的计算；

[0015] (4)同种类请求子节点下非叶子节点的调度策略。用以对其下的叶子节点或非叶子节点进行调度；

[0016] (5)叶子节点可以存放的待调度请求的最大数量以及其对请求进行调度的策略。

[0017] 根据五种调度策略的特点约束其使用位置，使用历史数据，包括：每种请求的数量，处理该类请求所能带来的收益，此时集群的总资源，每种请求所申请的资源(CPU和内
存)，将要使用的三种调度算法，叶子节点所存储的请求的最大数量，中间子节点所存储的
叶子节点的最大数量，所设定的收益标记结果，对DBN(深度信念神经网络)进行训练。然后
根据其输出结果选取最优的调度策略，根据当前节点的使用情况和已经得知的节点效率图
进行任务分配。

[0018] 根据本发明的上述方面，针对Hadoop的pull‑base通信模式和基于事件驱动的调度器的特点，综合考虑请求所花费的时间、申请资源和请求类型等数据，建立利润计算模
型，并对DBN进行训练，以根据下一批数据的特点来对调度算法做出决定，使得集群计算获
得的利润最大化。

[0019] 综上所述，一种基于深度信念网络的云数据中心请求流调度方法，包括如下步骤：

[0020] S1、根据建立的利润计算模型对历史数据进行计算，从而得到该数据条件下，所能获得的利润，并使用所计算得到的利润作为评判标准给历史数据添加标签；

[0021] S2、将添加了标签的历史数据分为训练集和测试集，并将训练集的数据进行归一化处理，使用处理之后的训练集对DBN网络进行训练；而后使用分类器和其输出对DBN网络
的权值w和偏差值b进行调整；

[0022] S3、使用测试集对训练完毕的DBN进行测试，并根据测试结果对DBN的超参数进行调整。

[0023] S4、使用当前时刻的请求流数据和已经调整好的DBN获取最优的调度树配置方案并对调度树进行调整，其后根据节点效率图对请求流进行调度，以使调度当前请求流的获
利最大，同时根据实际调度情况对节点效率图实时进行修改，为下一次调度做准备。

[0024] 作为优选，所述利润计算模型的结果为Profit，所描述的利润计算模型为：

[0025] Profit＝Revenue‑Cost

[0026]

[0027]

[0028] 其中，Revenue表示处理在时间间隔t内到来的任务请求所能带来的收益；Cost表示在时间间隔t内，集群处理请求所消耗的能量成本与人力使用成本之和； 表示在时间间
隔t内第k类请求的个数；gm表示在时间间隔t内第k类请求的平均资源申请量；tk表示在时间
间隔t内每一个请求的实际执行时间；R表示集群资源的总量； 是代表调度延迟的
变量，n表示延迟调度的时间，如果在时间间隔t内该请求进行了调度，则 否
则 qt代表在时间间隔t内调度该请求，并在一段时间完成之用户可能拥
有的满意度,i代表超时调度的折损率；l表示请求的个数； 表示在时间间隔t内实际处理
完成第k类请求的个数； 表示在时间间隔t内该节点能耗与使用效率间的关系系数；pmax
和pmin表示每个集群资源的最大和最小使用率； 表示在时间间隔t内单位能耗所需要花费
的价格。

[0029] 作为优选，所述利润计算模型的约束包括：在时间间隔t内，总CPU和内存需求均不能超过限定所给出的最大配置，总需求不能超过计算集群原本的容量限制：

[0030] dtCPUt≤CPUl；

[0031] dtMemoryt≤Memoryl；

[0032]

[0033]

[0034] 其中，CPUt表示在时间间隔t内每个请求所需要的CPU的平均个数；Memoryt表示在时间间隔t内每个请求所需要的内存的平均大小；CPUl表示系统对单个请求所能申请的CPU
资源数量的限制；Memoryl表示系统对单个请求所能申请的内存资源数量的限制；CPUR表示
计算集群的CPU的容量限制；MemoryR表示计算集群的内存的容量限制。

[0035] 作为优选，所述非线性约束优化模型的约束还包括：如果该请求可以在t时间内完成，即 或 如果未在t时间内完成，则 或
具体约束为：

[0036]

[0037]

[0038] qt∈[0,1]。

[0039] 作为优选，步骤2中使用的DBN网络由2层RBM和1层BP网络构成，权值w和偏差值b用来对DBN网络层与层之间关系以及激活概率p进行计算，使用对比散度算法(CD‑k)来对每层
RBM进行无监督贪婪训练；通过将输入值赋值给显层，计算出隐层中每个神经元被激活的概
率，从计算得到的概率中采用Gibbs抽样抽出样本，计算显层中每个神经元被激活的概率，
若干次计算之后，隐层可以精准的显示显层的特征；训练完毕后的每层RBM只能保证在自身
层内权值w和偏差值b达到最优，所以使用BP网络根据其输出结果和给定对应的历史数据的
标签进行判断，将错误信息自顶向下传播至每一层RBM，微调整个DBN网络，使整个DBN网络
中的权值w和偏差值b达到最优。

[0040] 作为优选，步骤3中需要调整的超参数包含：影响DBN网络学习速度的学习率η、对网络出现过拟合情况进行调整的正则化参数λ、影响分类正确率的学习的回合数Epoch和每
个隐层中神经元的个数j；通过使用Spark运行DBN网络同时通过反复迭代S2、S3，根据以往
的经验和测试结果的图表规律对这些超参数进行方差分析、拟合优度检验，而后根据结果
对其进行调整，直至其测试出现最优结果。

[0041] 作为优选，建立调度树配置计算模型，其参数为根据数据请求所计算出的调度算法的配置方案，和当前调度树的配置参数，具体为：

[0042]

[0043]

[0044] 其中，fold为调度树目前同种类请求子节点下可以存储的非叶子节点的最大数量，fnew为根据作业请求的数量、平均资源申请量和fold所计算的同种类请求子节点下可以存储
的非叶子节点的最大数量；lold为调度树中叶子节点可以存放的待调度请求的最大数量，
lnew为根据请求数据和lold所计算的叶子节点可以存放的待调度请求的最大数量。

[0045] 本发明的有益效果如下：

[0046] 本发明所述技术方案能够解决请求的到达、种类、资源申请量无规律和因为计算集群自身资源的限制给使用Hadoop平台请求调度带来的难题，使得Hadoop的资源管理系统
YARN智能的根据处理请求所能带来的利益和计算集群自身的条件约束，使用DBN网络对调
度策略进行选择，同时使用树形层级调度方法，减少对请求进行调度时所额外花费的计算
资源。且本发明所述技术方案综合考虑了计算集群的单位时间使用成本、节点资源使用情
况与其计算效率之间的关系，能够在不减少节点计算效率的情况下最大程度的使用节点资
源，从而能够最大化处理请求所能带来的利润并提高资源利用率减少能耗。

附图说明

[0047] 下面结合附图对本发明的具体实施方式作进一步详细的说明：

[0048] 图1示出一种深度信念网络的结构图。

[0049] 图2示出一种基于深度信念网络的云数据中心请求流调度方法调度器的树层级结构图；

[0050] 图3示出一种基于深度信念网络的云数据中心请求流调度方法的流程图；

[0051] 图4示出一种基于深度信念网络的云数据中心请求流调度方法的架构图。

具体实施方式

[0052] 为了更清楚地说明本发明，下面结合优选实施例和附图对本发明做进一步的说明。附图中相似的部件以相同的附图标记进行表示。本领域技术人员应当理解，下面所具体
描述的内容是说明性的而非限制性的，不应以此限制本发明的保护范围。

[0053] 如图2和3所示，本发明公开的一种基于深度信念网络的云数据中心请求流调度方法，包括如下步骤：

[0054] S1、根据建立的利润计算模型对历史数据进行计算，从而得到该数据条件下，所能获得的利润，并使用所计算得到的利润作为评判标准给历史数据添加标签。

[0055] 对云服务提供商而言，计算不同种类的请求会带来不同种的收益，但是不能仅仅只从用户所交付的金额方面来考虑所能获取的最大利益的内容，在对用户请求做出延迟处
理的时候会带来负面影响，在用户期待的时间内结束会增进用户对于云平台的好感，而在
超出用户预期的超短时间内完成，则会给用户带来惊喜。而使用企业自身所拥有的计算集
群也是同样如此，请求带来的价值不同，申请资源不同，运行周期不同。在不同等的时间内
处理请求会带来不同的价值。在大规模请求来临之时，这一情况更为明显。根据此，提出以
请求的种类，请求的处理周期类型，以及处理时间等参数提出利润计算模型，并根据计算结
果对历史数据进行标记而后存储以备使用。

[0056] 节点的能耗与CPU和内存的使用率有关，而不同的CPU却有着不同的最佳使用率，在CPU的使用超过该最佳使用率之后，可能会导致运行在该节点上的所有请求的效率同时
变低。本发明为所有节点建立了CPU最佳使用率的图谱，以节点名为标签，节点最佳使用率
为内容的关系图。通过CPU和内存的使用率计算出节点的能耗，从而得出计算集群在t时间
内所消耗的资源和收益。

[0057] 所述利润计算模型的结果为Profit，所描述的利润计算模型为：

[0058] Profit＝Revenue‑Cost

[0059]

[0060]

[0061] 其中，Revenue表示处理在时间间隔t内内到来的任务请求所能带来的收益；Cost表示在时间间隔t内，集群处理请求所消耗的能量成本与人力使用成本之和； 表示在时间
间隔t内第k类请求的个数；gm表示在时间间隔t内第k类请求的平均资源申请量；tk表示在时
间间隔t内每一个请求的实际执行时间；R表示集群资源的总量； 是代表调度延迟
的变量，n表示延迟调度的时间，如果在时间间隔t内该请求进行了调度，则 否
则 qt代表在时间间隔t内调度该请求，并在一段时间完成之用户可能拥
有的满意度,i代表超时调度的折损率；l表示请求的个数； 表示在时间间隔t内实际处理
完成第k类请求的个数；zt表示在时间间隔t内该节点能耗与使用效率间的关系系数；pmax和
pmin表示每个集群资源的最大和最小使用率； 表示在时间间隔t内单位能耗所需要花费的
价格。

[0062] 上述利润计算模型的约束包括下述两项：

[0063] (1)在时间间隔t内，总CPU和内存需求均不能超过限定所给出的最大配置，总需求不能超过计算集群原本的容量限制：

[0064] dtCPUt≤CPUl；

[0065] dtMemoryt≤Memoryl；

[0066]

[0067]

[0068] 其中，CPUt表示在时间间隔t内每个请求所需要的CPU的平均个数；Memoryt表示在时间间隔t内每个请求所需要的内存的平均大小；CPUl表示系统对单个请求所能申请的CPU
资源数量的限制；Memoryl表示系统对单个请求所能申请的内存资源数量的限制；CPUR表示
计算集群的CPU的容量限制；MemoryR表示计算集群的内存的容量限制。

[0069] (2)如果该t时间内的请求可以在t时间内完成，即 或如果未在t时间内完成，则 或 具体为：

[0070]

[0071]

[0072] qt∈[0,1]。

[0073] S2、将添加了标签的历史数据分为训练集和测试集，并将训练集的数据进行归一化处理，使用处理之后的训练集对DBN网络进行训练。而后使用分类器和其输出对DBN网络
的权值w和偏差值b进行调整。

[0074] 为了使数据更加规范，进而加快DBN网络收敛的速度，将数据进行归一化，使用的数据归一化的计算模型将原本的数据等比例缩放到0～1之间，提高学习效率。具体为：

[0075]

[0076] 其中，X指数据本身，Xmin和Xmax分别指数据归一化之前数据中的最大值和最小值。

[0077] 使用的DBN网络由2层RBM和1层BP网络构成如图1所示，权值w和偏差值b用来对DBN网络层与层之间关系以及激活概率p进行计算，使用对比散度算法(CD‑k)来对每层RBM进行
无监督贪婪训练，以加快其学习效率。通过将输入值赋值给显层，计算出隐层中每个神经元
被激活的概率，从计算得到的概率中采用Gibbs抽样抽出样本，计算显层中每个神经元被激
活的概率，若干次计算之后，隐层可以较为精准的显示显层的特征。训练完毕后的每层RBM
只能保证在自身层内权值w和偏差值b达到最优，所以使用BP网络根据其输出结果和给定对
应的历史数据的标签进行判断，将错误信息自顶向下传播至每一层RBM，微调整个DBN网络，
使整个DBN网络中的权值w和偏差值b达到最优。同时为了不影响调度树的运行效率，将用以
决策的DBN网络作为整个调度器的外部插件，以方便对DBN网络的超参数进行调整，同时降
低调度器的计算负载。

[0078] S3、使用测试集对训练完毕的DBN进行测试，并根据测试结果对DBN的超参数进行调整。

[0079] 需要调整的超参数主要有：影响DBN网络学习速度的学习率η、对网络出现过拟合情况进行调整的正则化参数λ、影响分类正确率的学习的回合数Epoch和每个隐层中神经元
的个数j。主要通过使用Spark运行DBN网络同时通过反复迭代S2、S3，根据以往的经验和测
试结果的图表规律对这些超参数进行方差分析、拟合优度检验，而后根据结果对其进行调
整，直至其测试出现最优结果。

[0080] S4、使用当前时刻的请求流数据和已经调整好的DBN获取最优的调度树配置方案并对调度树进行调整，其后根据节点效率图对请求流进行调度，以使调度当前请求流的获
利最大，同时根据实际调度情况对节点效率图实时进行修改，为下一次调度做准备。

[0081] 使用当前请求流数据对已经调整好的DBN网络进行使用之后，会得到对应图2的每层节点所应该使用的调度算法u，以及调度树每层的配置参数fnew、lnew。在t时间内建立调度
树配置计算模型其参数为：根据数据请求所计算出的出调度算法的配置方案fnew、lnew，和当
前调度树的配置参数fold、lold，具体为：

[0082]

[0083]

[0084] 其中，fold为调度树目前同种类请求子节点下可以存储的非叶子节点的最大数量，fnew为根据作业请求的数量和平均资源申请量所和fold所计算同种类请求子节点下可以存
储的非叶子节点的最大数量；lold调度树目前为叶子节点可以存放的待调度请求的最大数
量，lnew为根据请求数据和lold所计算的叶子节点所能存储的最大数量。其树形层级结构如
图2所示。

[0085] 可选的调度策略u和使用范围如下所述：

[0086] DRF(主资源公平分享)适用于子节点间和请求间调度，将所有需求资源中needResource(某一种资源需求)/allResource(可以使用的该类资源的总量)最大的作为
主资源，根据所决定的主资源的比值进行递增排序，主资源比值相同以次一级资源比值为
依据，若次一级资源比值依旧相等，则以名字为依据，从而决定调度顺序。

[0087] Fair(公平分享)适用于子节点间和请求间调度，根据usedResource(已使用中的内存资源)与demand(子节点和请求所需要的内存资源)的比值进行递增排序，同比值则以
优先级为排序依据，同优先级则根据名字进行排序。

[0088] Priority First(优先级优先)适用于子节点间和请求间调度，以需求资源和优先级为依据，根据demand/Priority进行递增排序，同比值以优先级为依据，同优先级则根据
名字进行排序。

[0089] Shortest First(短作业优先)可应用于同种作业之间的子节点调度，亦可以应用于作业之间的调度，以内存资源为依据进行递增排序，优先解决资源需求量小的子节点或
请求，若同需求则以名称为排序依据，从而决定调度顺序。

[0090] FIFO(先入先出)无法用于子节点之间调度，适用于叶子节点内部请求间的调度。根据请求的入队时间进行递增排序，时间相当的以请求ID为依据进行排序。

[0091] 五种调度策略各有优点Fair、DRF保证了请求调度的公平性，防止高优先级请求数量大的情况下，对低优先级请得不到调度的情况发生，使每种类型的子节点中都有部分请
求正在被处理。DRF在保证请求调度公平性的同时有效的提高集群资源的利用率，Fair的公
平性计算比DRF更简单，耗时更短。Priority First在兼顾高优先级请求可以优先完成的同
时，也对低优先级请求进行了照顾，在一定程度上保证了调度的公平性。FIFO则考虑了请求
在子节点中的等待时间，优先调度等待时间长的请求，避免因请求长时间等待，而使用户的
体验性变差。因为其先来先服务的性质，若将其应用于子节点之间的调度，将会对调度的公
平性造成巨大的影响，所以不将其应用于子节点间的调度。Shortest First则优先解决资
源请求较少的子节点，通常情况下资源请求代表了执行的时间，所以也可以将其理解成优
先解决执行时间最短的请求或子节点，以快速增加处理完成的请求数量，减少请求的平均
等待数量，进而减少等待请求处理完毕的用户的数量。

[0092] 由于物理环境或其它环境的不同，会使得CPU拥有不同的最佳使用率，在CPU的使用超过该最佳使用率之后，可能会导致运行在该节点上的所有请求的效率同时变低，因此
本发明为集群中所有节点建立了节点效率关系图，其key值为节点名，value为节点的最佳
使用效率，在调度的过程中。调度器根据节点的最佳使用效率为该节点分配任务，以加快请
求的处理速度，减少节点的能耗，从而使该次调度所获得的利益最大化。

[0093] 综上所述，本发明的上述实施仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定，对于所属领域的普通技术人员来说，在上述说明的基础上还
可以做出其它不同形式的变化或变动，这里无法对所有的实施方式予以穷举，凡是属于本
发明的技术方案所引伸出的显而易见的变化或变动仍处于本发明的保护范围之列。