云计算平台中非定期任务并行调度仿真

赵男男

(广东海洋大学寸金学院，广东 湛江 524094)

1 引言

云计算是由分布式计算发展而来的新型计算模型与服务，运用模拟技术来完成扩展储存和计算资源，目前已广泛应用于医药医疗、工业制造、金融与能源等众多领域。伴随信息系统的复杂化，需要对云计算平台结构进行调整，做到低成本、高性能[1]。客户需求的不断改变和物理节点性能的不同会导致云计算负载不平衡，直接影响到云计算平台任务的处理效率、资源的利用率与资源消耗等问题[2]。相关专家学者针对云计算平台集群负载、资源的利用率、集合性能、任务时间与耗损等进行多方面探究，应用各类调度优化算法实现任务调度[3]。

文献[4]提出基于可靠性约束的非定期任务并行调度方法。该方法将云计算平台可靠性目标换做单个非定期任务的可靠性目标，给出非定期任务可靠性目标计算过程；针对此过程设计一种并行调度方法。文献[5]提出基于粒子群优化的非定期任务调度方法。该方法首先建立云计算平台中非定期任务调度能耗模型，针对该模型定义非定期任务调度多目标优化问题；采用粒子群算法对多目标优化问题进行求解，获取不同调度方案下的最优解集合，在不同调度策略对应的调度最优解集合中寻找最优解。

采用上述方法进行非定期任务并行调度过程中，无法避免由非定期任务调度的不确定性所带来的耗时长和高能耗等问题，对此，将模拟退火算法和粒子群算法相结合提出一种非定期任务调度方法。

2 云计算平台环境

图1为云计算平台环境系统模型图，分析图1可知，该系统模型中包含2点：分别为控制节点和计算节点。任务调度机器、数据调度器和信息中心3部分构成网络控制节点。监控系统作为一个关键环节，其通过任务调度器、数据调度器和计算网络节点来收集任务信息、储存空间和处理器等消息，反映给任务与数据调度器，调整数据安放与任务调度，达到策略调整的目的[6]。任务与数据调度器依据收集到的信息，参考相应的的策略，将非定期任务和相关数据分配到计算节点上[7]。处理器和存储空间共同组成计算节点，计算机节点主要负责对数据进行存储，对非定期任务进行执行，并且将存储空间和非定期任务执行的信息及时反馈到信息中心。

图1 云计算系统模型

(1)

对于∀i，j1，2…，|DN|，且i≠j，B中元素bi，j是节点dni和dnj之间的网络带宽值，其中bi，j=bj，i，∀i，j=1，2，…，|DN|且i≠j都成立，即带宽双向相等，并忽略它的实时波动。

通过上述过程完成云计算平台系统模型的建立，在云计算环境下应用平台运行环境，结合模拟退火算法和粒子群算法实现非定期任务并行调度。

3 云计算平台中非定期任务并行调度方法

3.1 非定期任务并行调度多约束条件建模

在构造多约束的云计算平台非定期任务调度策略之前，对非定期任务调度多目标约束条件进行建模。

假设，云计算平台环境中包含N个计算节点，用集合CN={CN1，…，CN1}来表示。未调度的任务集为t={t1，…，tr}，其中L为任务数量。S(CNi，Rk)为计算节点CNi可提供的能用资源Rk的计算能力；R(ti，Rk)表示调度非定期任务ti时所损耗的计算能力；将大小为T×N的资源的分布矩阵M以运行资源和其相应的计算节点之间的任务映射的关系来描述。

假设，非定期任务ti被划分到服务节点CNj上执行调度，则矩阵M中的元素Mij=1，否则Mij=0；vij与cij分别表示任务ti被转移到计算节点CNj实行调度的状况下，平台非定期任务的实际执行时间和调度开销超过截止时间底线与调度开销目标约束条件的概率；Min(Odeadline)与Min(Obudget)为指派非定期任务调度预算与任务调度的终止时间的状况下，在云计算平台中要实现的非定期任务调度目标。

客户期盼能在期望的时间线之前搞定所有的调度任务请求。因此，应尽可能将调度任务实施运行时间超越其结束时间底线约束条件的比例；同时在计算节点上指定资源Rk，全部任务在Rk上所消耗的计算能力累加和不能超过该资源能供给的总计算能力。上述过程所描述的任务调度截止时间底线的目标约束条件，用式(2)来表示。

(2)

服务需求得到满足后，云计算平台用户希望尽可能降低调度成本。同时，指定的非定期任务ti在其对应计算节点全部可用资源上消耗的总调度成本不能高于其事先制定的调度预算。以上关于非定期任务并行调度预算的目标约束条件，利用式(3)来表示

(3)

从客户的角度分析，他们期望任务调度运行时间能够缩短。一方面，非定期任务调度的开销与任务调度的截止时间有一定的关联性，截止时间越长、用户调度开销越大。因此，在非定期任务并行调度预算固定的前提下，云计算平台用户期望非定期任务调度截止时间底线尽可能达到最小[8]。在非定期任务调度估算固定时，可以采用关于终止时间的隶属度函数描述项式(4)来表达非定期任务的终止时间约束条件与调度目标之间的隶属关系。

(4)

另一方面，客户们期望任务调度开销越少越好。采用与相关任务的调度开销隶属度函数即式(5)来描述任务调度估算约束条件与调度目标的隶属关系。

(5)

其中：cmin表示期望的非定期任务ti调度开销，cij描述非定期任务ti在计算节点CNj上进行调度的调度开销。

通过上述过程对非定期任务调度终止时间底线和调度开销两个目标约束条件的分析可知，为了尽可能降低调度开销和最大程度上以最小终止底线完成非定期任务并行调度，需使上述两项目标的隶属度函数为最小[9]。基于此，采用上述两项隶属度函数将关于非定期任务并行调度的多目标约束优化问题变成单目标优化问题，如下式所示

Min(0)=ω1Min(Odeadline)+ω2Min(Obudget)=

(6)

其中：权重系数ω1+ω2=1，ωi≥0。在建立非定期任务调度求解目标函数过程中，由于不同云计算平台用户对于任务终止时间底线和调度开销的需求度不同，可根据参数ω1和ω2的调整来满足不同云计算平台用户对非定期任务调度目标约束需求。

3.2 非定期任务并行调度目标约束条件求解

3.1节给出的非定期任务并行调度目标求解问题实质为组合优化问题，为求取组合优化问题的最优解，采用模拟退火算法进行并行调度策略的选择。模糊退火算法通常是从较高的温度值开始，通过逐渐降低温度并结合相关概率的突变特性在全局解空间中随机搜索满足目标函数最优解[10]。

模拟退火算法可划分为三部分，包括目标函数、目标函数初始解和目标函数解空间。模拟退火算法求解过程如下：

1)最初化：设定最初温度为T(足够大)，最初解状态为S，设定T值的迭代次数为L。

2)对k=1，…，L运行过程3)～6)。

3)形成新解S′。

估计增长量Δt′=C(S′)-C(S)，C(S)中的C(S)为评估函数。

4)如果满足Δt′<0，则接收S′作为最新的当前阶段的最优解，否则以概率exp(-Δt′/T)接收S′作为最新的当前阶段的最优解。

5)如能满足算法截止条件，则输出当前阶段的最优解，结束算法迭代过程[11]。

6)T渐渐缩小，T→0，转为步骤2)。

经模拟退火算法推算出满足云计算平台用户服务时间和服务可靠性需求的最佳任务调度方式[12]。

4 实验结果及分析

为了有效验证基于模拟退火算法的非定期任务并行调度方法的综合有效性，在CloudSim模拟平台上完成仿真平台的构建。在上述仿真平台下进行实验，实验运行20次后选取平均值，作为最终测试结果。实验过程中选取基于可靠性约束的非定期任务并行调度方法、基于粒子群优化的非定期任务调度方法作为对比方法。

4.1 非定期任务量对数据传输的影响

图2 任务集数量对数据传输的影响

图2表示非定期任务集数量的增加对数据传输的影响。实验过程中，设定数据集数量最多为600，最少为100。为了简化描述，将本文提出的基于模拟退火算法的非定期任务并行调度方法、基于可靠性约束的非定期任务并行调度方法、基于粒子群优化的非定期任务调度方法分别表示为BUT、BD、BB。

分析图2可知：随着非定期任务集数量的增加，基于模拟退火算法的非定期任务并行调度方法、基于可靠性约束的非定期任务并行调度方法、基于粒子群优化的非定期任务调度方法传输次数、传输数量和传输时间呈线性趋势增长。这三种方法的传输次数与传输量相差不多，基于可靠性约束的非定期任务并行调度方法、基于粒子群优化的非定期任务调度方法之间相差较小；图2(a)中基于可靠性约束的非定期任务并行调度方法传输次数为最少，图2(b)中基于粒子群优化的非定期任务调度方法的传输量最小，基于模拟退火算法的非定期任务并行调度方法的传输数量与次数与其它两种方法相比，传输次数及传输量均是最多的。图2(c)中，本文方法的传输时间为最少，基于粒子群优化的非定期任务调度方法的传输时间较多，基于可靠性约束的非定期任务并行调度方法稍少于基于可靠性约束的非定期任务并行调度方法，本文方法的时间延长率比其它两种方法都小，在非定期任务集数量是600时，本文方法的传输时间比基于可靠性约束的非定期任务并行调度方法少约1/3，并且从变化趋势上来看，这种差距随着非定期任务数据集的增加而逐渐增大，说明本文方法能够有效降低非定期任务的传输时间，提高非定期任务的传输效率。

图3表示当非定期任务数量逐渐增加时，系统负载均衡变化情况。在实验过程中，设定工作节点数最低为10个，最高为60个。

图3 节点的数量

经过实验对比：随着节点数量的不断增加，本文方法、基于可靠性约束的非定期任务并行调度方法、基于粒子群优化的非定期任务调度方法负载均衡偏差呈线性增长。同时，基于粒子群优化的非定期任务调度方法的偏差最大，基于可靠性约束的非定期任务并行调度方法的偏差值稍少于基于粒子群优化的非定期任务调度方法，本文方法对应的偏差值最少；当节点数量为50～60时，本文方法的负载均衡偏差值为基于可靠性约束的非定期任务并行调度方法的1/4，说明本文方法的负载均衡性更强。

5 结论

本文指出了由于云计算平台的动态不确定性和非定期任务调度本身的复杂性，使得非定期任务调度过程存在耗时长和高能耗等问题。分析影响非定期任务传输时间的影响因素，提出基于模拟退火算法的非定期任务并行调度方法。根据仿真结果可知，与传统方法对比，在排除任务集与节点较少的情况下，本文方法能够有效降低非定期任务的传输时间，对系统负载进行有效均衡，从而提高了云计算平台的工作效率。

在未来的工作中，研究重点是，在不影响非定期任务传输时间的前提下，考虑算法的并行化实现，进一步提高算法的实际应用性能。