混合云环境下多QoS约束的并行任务调度成本优化方法

摘要

本发明涉及一种混合云环境下多QoS约束的并行任务调度成本优化方法，该方法包括：私有云的任务调度、任务重新调度和公有资源最小化租赁成本。在私有云任务调度方法中，根据改进的极大极小的策略给任务分配资源，提出一个快速启发式算法—TSOPR。在任务重新调度中，根据RSD算法完成：决定什么任务应该安排到公有云；判断公有云是否可以满足最后期限约束和预算约束；如果约束条件都能满足，系统为提交作业中的任务生成一个调度表。本发明能够在满足预算控制约束的前提下最小化公有云资源的租赁成本。

说明书

技术领域

本发明涉及一种混合云环境下的任务调度方法，特别涉及最后期限约束和预算控制约束的混合云环境下多QoS约束的并行任务调度成本优化方法。

背景技术

近年来云计算成为一个日益重要的研究课题。许多现有的云服务平台，如Google云计算平台、IBM蓝云计算平台、Amazon弹性计算云和Microsoft云计算平台已经证明了他们的成功并向公众提供一种即付即用的方式。云环境可以简单地分为私有云与公有云。运行一个私有云数据中心，数据中心机构要购买、维护、管理和操作所有的软件和硬件基础设施，但仍然面临着供不应求的风险。有研究人员连续46天动态监测美国第二大在线视频分享网站雅虎视频每小时的工作量。峰值负荷远远大于平均值，但是峰值负荷是短暂且不可预测的。如果一个私有数据中心试图满足工作负载的所有约束，高峰负荷将迫使业主在私有云中投资更多的硬件资源。在这种情况下，它会导致在大部分时间硬件资源是浪费的。即付即用的公有云可以帮助我们处理这些不可预知的工作量峰值，并且只用在公有云处理超载任务的这段时间需要支付额外的费用，而在私有云中没有任何多余的资源。因此，如果私有云已经存在，搭建混合云的方法可以避免部署成本和运营成本的浪费。而并行任务调度是混合云的主要挑战之一。

不同的调度策略可能改变资源利用率、响应时间、可靠性、运行成本和维修成本。此外，在系统遵守QoS约束的前提下，用户通常更喜欢符合成本效益的方式获取资源。混合云为用户提交任务时选择不同的服务水平提供灵活性。由于公有云是即付即用的，当私有云不能满足用户需求时，找到满足QoS约束且成本效益最优的公有云资源成为混合云的一个重要研究课题。国内外研究人员对任务分配与调度问题已经做了大量的研究，并提出了很多启发式驱动方法，然而这些方法都是针对网格或分布式等异构环境的，不能应用在混合云环境中，而目前提出的混合云任务调度成本优化方法较少。

因此，有必要提供混合云环境下多QoS约束的并行任务调度成本优化方法以克服上述现有技术的不足。

发明内容

本发明目的就在于克服上述现有技术的不足而提供一种本发明混合云环境下多QoS约束的并行任务调度成本优化方法(Multi-QoS ConstraintsCost Optimal Algorithm for Parallel Task Scheduling in Hybrid Cloud，以下简称MQCOHC)，该方法能够在满足预算控制约束的前提下最小化公有云资源的租赁成本。

实现本发明目的采用的技术方案是一种混合云环境下多QoS约束的并行任务调度成本优化方法，该方法包括私有云任务调度和公有云任务调度，

所述私有云任务调度包括：在混合云环境中，根据作业的需要为每个提交的作业分配私有云资源槽，如果私有云资源槽不能满足作业的最后期限约束，根据作业的最后期限约束决定哪一项作业的任务应该调度到公有云，私有云并生成该作业的两个调度表，一个用于私有云调度一个用于公有云调度；

所述公有云任务调度包括任务重新调度和公有资源最小化租赁成本，其中，

所述任务重新调度包括：决定什么任务应该安排到公有云；判断公有云是否可以满足最后期限约束和预算约束；如果约束条件都能满足，系统为提交作业中的任务生成一个调度表；

所述公有资源最小化租赁成本资源槽根据资源质量、CPU总时间、总使用存储空间和总消耗带宽来收费，在满足预算控制约束的前提下最小化公有云资源的租赁成本。

在上述技术方案中，所述私有云任务调度包括以下步骤：

(1)定义J_i、PrR_i和RT{1…m}；其中J_i表示需要提交的作业，该作业包含n个任务，PrR_i表示分配私有云资源槽，且该私有资源槽数量为m，RT{1…m}记录一个私有资源槽从当前变成可用的最短时间；

(2)根据数据量大小DS_i,j把作业J_i的所有任务按照降序排列；

(3)计算每个任务T_i,j的估计执行时间Eet[i,j,k]；

(4)给任务T_i,j分配资源槽，并且记录映射；

(5)如果所有的RT都小于最后期限约束，则返回一个私有云任务调度表；否则，利用QoS综合评估方法选择与作业J_i的安全性和可靠性相匹配的公有云资源。

在上述技术方案中，决定什么任务应该安排到公有云包括以下步骤：

(1)定义Z_i，PrR_i，RT[1…m]，JR；其中Z_i表示作业J_i安排在私有云上运行的调度表，PrR_i表示私有云资源槽，其资源槽数量为m，RT[1…m]表示记录一个私有资源槽从当前变成可用的最短时间，JR是QoS综合评估方法的输出结果；

(2)将需要分配到公有云上的任务集置空，计TPPU＝φ；

(3)将任务根据估计执行时间的大小进行升序排序得到TPPR；

(4)当私有资源槽k上任务的执行时间大于最后截止期限，查询分配在资源槽k的任务集，将该任务集添加到TPPU，即将私有云资源槽中前n个任务从TPPR移到TPPU；

(5)计算公有云任务的完成时间小于最后截止极限时，再把n′个任务从TPPU移到TPPR；

(6)输出二元组<Z′_i,TP_i>，其中Z′_i是作业J_i在公有云上的调度表，TP_i是转移到公有云上的任务集。

在上述技术方案中在满足预算控制约束的前提下最小化公有云资源的租赁成本包括以下步骤：

(1)定义TP_i，PRT，t_init；其中TP_i是作业J_i运行在公有云上的任务集，PRT是公有云资源槽的类型集，t_init是公有云资源槽的时间初始值；

(2)初始化变量，NR_i＝φ，Z_i＝φ，TotalCost＝0，其中NR_i表示一组公有云资源槽，Z_i表示公有云上任务的调度表，TotalCost表示公有云的租赁成本；

(3)在公有云上为任务寻找合适的资源类型，该资源满足最后期限约束的条件下价格最低；

(4)如果最好的资源类型被找到，系统会在公有云上创建一个实例类型并且分配任务到该公有云资源实例，即分配任务T_i,j到资源k并且在Z_i中记录映射；

(5)计算在k上运行的T_i,j的成本并且加入到TotalCost；

(6)返回公有云的调度表和为作业中的任务相应地调度公有云资源槽。

本发明利用执行时间估算方法以及快速调度方法，将最后期限约束和预算控制约束引入到任务调度方法中，在满足最后期限约束和预算控制约束的前提下，最小化租赁公有云资源的成本。

附图说明

图1为混合云环境下并行任务自适应调度模型。

图2为本发明混合云环境下多QoS约束的并行任务调度成本优化方法的流程图。

具体实施方式

下面结合附图和具体实施例对本发明作进一步的详细说明。

混合云可以使用其内部基础设施和公有云资源来控制成本，满足数据保密性、安全性、性能和延迟方面的具体需求。每个企业的IT平台都有自己的网络、服务器和存储硬件，这样就可以组成一个私有云。从成本的方面考虑处理工作负载峰值问题，私有云资源可以动态地添加到一个公有云资源而构成一个混合云环境。

云联盟旨在注重成本效益和资源优化，在异构环境下所有云共同合作以获得无限的计算资源，因此成为新的商机。任何一个组织的私有云达到一个特定的工作负载阈值时，一经需求，都可以选择一个公有云资源而变成混合云环境。

本发明首先建立如图1所示的混合云环境下并行任务自适应调度模型，用户通过一个接口获取资源，该接口允许用户设定应用程序性能、最后期限和使用公有云的预算。当一个新作业(任务)到来时，调度程序组件将被触发，然后调度程序获得任务的信息和资源，如数据大小、负载大小等。不同类型的调度程序可能有不同的子组件，提出的调度机制含有四个子组件：执行时间估计算法，成本函数，动态编程模块和调度选择算法。估计执行时间和成本函数通过任务和资源的信息获得。其中，估计算法分别估计执行时间、传输时间和完成时间；成本函数对不同的公有云资源槽生成其成本值。基于执行时间估计算法和成本函数的结果，提出的调度机制采用动态编程技术从成本价值和完成期限方面来计算最佳资源配置。调度选择算法通过使用动态编程组件的结果来分派任务，保证所有提交的作业都能以最低成本并在最后期限之前完成。这些任务具体被分派到私有云还是公有云，这要取决于调度选择方法的结果。

本发明混合云环境下多QoS约束的并行任务调度成本优化方法中，把QoS约束下的任务调度问题转换成一种变异的多维多选择背包问题，利用执行时间估算方法以及快速调度方法，把任务执行时间降到最低，并将租用公有云资源的费用可以控制在预算之内。即MQCOHC最大化私有云的利用率，最小化公有云的租赁成本。

上述提出的混合云环境下并行任务自适应调度模型参数进行如下定义：

在上述提出的混合云环境下并行任务自适应调度模型中，用户将作业提交给混合云，每个作业包括n个任务。多个任务可以由一个资源槽处理，一个资源槽通常构造成一个虚拟机。下面定义作业和任务：

定义1(作业J_i和截止期限D_i)作业i定义为J_i，在模型中，一个作业i可能由n个任务{T_i,1,T_i,2,…,T_i,j,…,T_i,n}组成，T_i,j表示作业i中的第j个任务并且1≤j≤n。每个作业i有一个截止期限D_i，这是用户定义的，是作业i的最大执行时间。

定义2(任务T_i,j)T_i,j是作业J_i的一个任务，是用户请求的基本单位，一个资源槽一次处理一个任务。任务为四元组T_i,j＝{D_i,SC_i,j,SD_i,j,M_i}，其中：

(1)D_i是截止期限，表示用户对作业J_i定义的最后期限。每个作业J_i有一个截止期限D_i，这是用户定义的，是作业J_i的最大执行时间。作业J_i的每个任务应该在最后期限之前完全执行并把结果返回给用户。如果作业完成时间超过指定的期限，就违反了QoS约束。

(2)SC_i,j是工作负载，表示任务T_i,j的工作量的大小，是任务T_i,j被一个标准资源槽执行的时间。

(3)SD_i,j是数据量大小，表示任务T_i,j数据的大小。它影响数据传输的时间。数据量用MBs衡量。

(4)M_i是执行成本，表示在公有云中执行作业J_i的费用。

在提出的混合云调度模型中，物理机是可以有与CPU的资源内核同样多插槽数目的资源。尽管一个物理机可以分配比物理机的CPU内核更多的插槽，但在超过供应的情况下资源槽的效率将大幅度下降。资源槽根据资源的计算能力和资源共享的方式有着不同的计算能力。根据现有的云系统，具有不同价格的公有云资源可能有不同的性能。下面定义资源槽：

定义3(资源槽)一个资源槽k表示为P_k，P_k由私有云或公有云创建。资源槽用一个七元组P_k＝{prμ_k,x_k,y_k,dti_k,dto_k,NB,L_k}来表示。

(1)prμ_k是私有云资源槽k的计算能力，表示资源槽k每秒百万条指令的计算能力。

(2)x_k是公有云资源槽k的计算成本，表示公有云中每百万指令的执行成本。

(3)y_k是公有云资源槽k的存储成本，表示在公有云中保存数据每MB的成本。

(4)dti_k是向资源槽k输入数据的成本，表示输入数据到资源槽的成本。

(5)dto_k是资源槽k输出数据的成本，表示从资源槽输出数据的成本。

(6)NB是私有云与公有云之间的网络带宽，它影响数据的传输时间。

(7)L_k是资源槽k中的缓存任务，它包含任务的多个副本。当一个作业被发送到私有云，作业的任务将自动部署到私有云资源槽上。

在提出的混合云任务调度模型中，私有数据中心操作和维修成本认为是非常低的因此可以忽略不计，设置为x_k＝0,y_k＝0,dti_k＝0和dto_k＝0。然而，租赁的公有云资源槽有各种各样的价格。这是因为不同的公有云提供商有不同的定价策略。如果只考虑操作和维护成本，通常公有云的资源比私有云的资源昂贵的多。

服务质量(QoS)是一个综合指标，能够对不同的应用程序提供不同的优先级、用户、数据流或保证一定性能的数据流。提出的混合云调度模型着重于QoS标准的执行时间(最后期限)和价格(成本值)。接下来定义所需QoS的参数：

定义4(估计完成时间Est_k)Est_k代表资源槽k预计完成的时间。它由运行在资源槽k上的剩余工作量大小决定。基于这个估计，当有新的任务被用于该资源时我们可以预测估计完成时间。

定义5(数据传输时间Dtt)数据传输发生在当一个资源槽k没有任务T_ij的数据时。如果必要这些数据会传输到资源槽。传输时间取决于网络带宽NB。数据传输时间Dtt如下定义：

$>\mathrm{Dtt}[i,j,k]=\frac{{\mathrm{SD}}_{i,j}}{\mathrm{NB}}---\left(1\right)$>

定义6(估计执行时间EEt)估计执行时间等于工作量大小SC_i,j除以资源槽k的计算能力p_k加上数据传输时间Dtt。估计任务在不同资源槽的执行时间是有必要的，这样可以为带特定QoS标准的作业恰当的分配资源。估计执行时间EEt如下定义：

$>\mathrm{EEt}[i,j,k]=\frac{{\mathrm{SC}}_{i,j}}{P_k}+\mathrm{Dtt}[i,j,k]---\left(2\right)$>

定义7(成本函数CostF)一般公有云服务提供商，收费服务有三个方面：计算、存储和数据传输。因此，成本函数可以通过计算任务T_i,j的工作量大小SC_i,j来计算开销，计算租用一个资源槽的价格xk，数据量大小SD_i,j的存储开销，租用存储服务的存储开销y_k，数据大小SD_i,j的传输开销，数据输入开销dti_k和数据输出开销dto_k。在私有云中，我们设置任何资源槽的开销等于0。

CostF[i,j,k]＝SC_i,j×x_k+SD_i,j×y_k+SD_i,j×(dti_k+dto_k)    (3)

定义8(最后期限约束)给定一个作业J_i＝{T_i,1,T_i,2,…,T_i,n}，k个资源槽，最后期限是D_i，作业J_i的截止期限是最后一个资源槽完成任务的时间小于或等于D_i。因为最后期限只涉及到用于作业计算的资源槽，我们设置两个选择变量a_i,j,k和b_k。a_i,j,k表示任务T_i,j是否分配给资源槽k，当a_i,j,k＝1表示任务T_i,j分配给资源槽k，当a_i,j,k＝0，反之。b_k表示资源槽是否在被使用，当b_k＝1表示资源槽k在被使用，当b_k＝0，反之。最后期限约束必须满足下面公式：

$>\underset{k=1~m}{\max }((\underset{j=1}{\overset{n}{\Sigma }}\left(\mathrm{EEt}\right[i,j,k]\times a_{i,j,k})+{\mathrm{Est}}_k)\times b_k)\le D_i---\left(4\right)$>

定义9(预算控制约束)给定一个作业J_i，预算M_i是一个用户定义的变量，表示作业J_i在公有云中执行的费用。换句话说，工作量大小为SC_i,j和数据量大小为SD_i,j的任务T_i,j执行在公共资源槽q∈{PuR₁,PuR₂,…,PuR_m}费用要低于计算成本x_q与存储成本y_q的和，即预算M_i。预算控制约束如下定义：

$>\underset{k=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}\left(\mathrm{CostF}\right[i,j,k]\times a_{i,j,k})\le M_i---\left(5\right)$>

多维多选择背包问题DO-MMKP(the Dual-Objective Multi-dimensionMulti-choice Knapsack Problem)

因为本专利需要为每个任务分配资源槽，最小化公有云上的执行成本和最小化总的执行时间。因此，资源选择问题可以归结为双目标多维多选择背包问题，给定一个作业J_i包含了n个任务，有m个可用资源槽(定义为资源槽D_i>Est_k)，双目标多维多选择问题可以如下定义：

定义10双目标多维多选择背包问题TDO-MMKP(The Dual-ObjectiveMulti-dimension Multi-choice Knapsack Problem)

函数)

使估计执行时间要小于最后期限

本发明需要为每个任务分配资源槽，一个混合云调度机制必须构造出调度表以满足用户的QoS约束和最大化利用私有云而最小化使用公有云的成本。资源选择问题映射为一个变化的多维多选择背包问题：①在TDO-MMKP中，作业的每个任务被映射到一个资源槽，每个资源槽映射到一组中的一个对象；②在TDO-MMKP中，每个任务的QoS约束映射到对象所需的资源。③成本函数映射到对象的第一种利润必须优化；④使用资源槽的最小估计完成时间映射到对象的第二种利润必须优化；⑤最后期限约束和预算约束被看作为背包中可用资源的限制；⑥在TDO-MMKP中，使用选择变量来表示一组中的某一对象是否被选用；⑦有较好第一种利润的解决方案是较好的解决方案，但如果两个方案有相同的第一种利润，有着更好的第二种利润的方案是更好。

在m个资源槽上为带有约束限制的n个任务的调度寻找最优的解决方案，我们列举出所有可能情况下，通过从每个对象组(任务)中选择一个对象(资源槽)，然后计算其相应的利润。这个解决方案只有在n和m都比较小时是可行的，并且时间复杂度是O(n^m)。不幸的是，公有云资源的资源槽数量是非常大的。因此，在一个混合云环境下它几乎不可能找到最优的解决方案。必须使用启发式方法来解决这个问题，在此我们采用改进的Max-Min算法(具体见5.1节)，Max-Min算法的时间复杂度是O(n²·m)，这样就大大降低了寻找最优解的时间，可以实现双目标的优化。

本发明混合云环境下多QoS约束的并行任务调度成本优化方法具体包括以下步骤：

S100、私有云任务调度TSOPR(Task Scheduling On Private)

在混合云环境中，根据作业的需要为每个提交的作业分配私有云资源槽，如果私有云资源槽不能满足作业的最后期限约束，根据作业的最后期限约束决定哪一项作业的任务应该调度到公有云，私有云并生成该作业的两个调度表，一个用于私有云调度一个用于公有云调度。

当作业分配给一组私有云资源槽并开始执行时，任务调度程序将给每个任务分配资源槽。基于上述定义10，第一目标任务调度优化以使用资源为代价。假设使用的私有云资源槽是费用为0，因此如果私有云能够处理提交的作业，调度程序可以直接集中在第二个目标执行时间优化。

本发明采用改进的Max-Min的策略，该策略选择任务的最大工作量和任务的最小完成时间。本发明通过一个快速启发式算法—TSOPR，计算一个好的解决方案而不需要消耗太多的时间。

TSOPR方法的步骤

(1)定义J_i、PrR_i和RT{1…m}；其中J_i表示需要提交的作业，该作业包含n个任务，PrR_i表示分配私有云资源槽，且该私有资源槽数量为m，RT{1…m}记录一个私有资源槽从当前变成可用的最短时间；

(2)根据数据量大小DS_i,j把作业J_i的所有任务按照降序排列；

(3)计算每个任务T_i,j的估计执行时间Eet[i,j,k]；

(4)给任务T_i,j分配资源槽，并且记录映射；

(5)如果所有的RT都小于最后期限约束，则返回一个私有云任务调度表；否则，利用QoS综合评估方法选择与作业J_i的安全性和可靠性相匹配的公有云资源，进入RSD方法步骤。

S200、公有云任务调度

公有云任务调度包括任务重新调度和公有资源最小化租赁成本，具体包括以下步骤：

S201、任务的重新调度RSD(Rescheduling Decision)

当私有资源槽被占用完，新传入的作业为了满足其期限约束可能需要被派遣到公有云。问题是在混合云中我们需要为作业计算一个调度表。调度安排需要满足最后期限约束，租用公共资源槽最小化成本和最小化作业完成时间。这里我们采用任务重新调度技术来解决这个问题。当一个作业未能被安排到私有云，该系统应该将一些任务分配到公有云，这样作业中的每个任务都满足最后期限约束。提出的调度机制使用四个步骤来完成这个目标：①系统必须决定什么任务应该安排到公有云；②系统需要判断公有云是否可以满足最后期限约束和预算约束；③如果约束条件都能满足，系统应该为提交作业中的任务生成一个调度表；④最小化公有云的租赁成本。

当一个作业到达了私有云，调度程序应该为这个作业分配私有资源并使用TSOPR算法为作业计算一个调度表，这样可以决定作业是否可以在私有云上运行。如果可以，基于计算调度，调度程序直接发送任务和他们的数据到相应私有云资源槽。否则，计算调度不能在最后期限约束条件下完成作业，调度程序将调用RSD算法，决定什么任务应该安排到公有云。

RSD算法需要来自TSOPR算法结果的三个参数。

RSD方法的步骤

(1)定义Z_i，PrR_i，RT[1…m]，JR；其中Z_i表示作业J_i安排在私有云上运行的调度表，PrR_i表示私有云资源槽，其资源槽数量为m，RT[1…m]表示记录一个私有资源槽从当前变成可用的最短时间，JR是QoS综合评估方法的输出结果；

(2)将需要分配到公有云上的任务集置空，TPPU＝φ；

(3)将任务根据估计执行时间的大小进行升序排序得到TPPR；

(4)当私有资源槽k上任务的执行时间大于最后截止期限，查询分配在资源槽k的任务集，将该任务集添加到TPPU，即将私有云资源槽中前n个任务从TPPR移到TPPU；

(5)计算公有云任务的完成时间小于最后截止极限时，再把n′个任务从TPPU移到TPPR；

(6)输出二元组<Z′_i,TP_i>，其中Z′_i是作业J_i在公有云上的调度表，TP_i是转移到公有云上的任务集。

S202、公有资源的最小化租赁成本MRCPR(Minimizing Renting Cost ofPublic Resource)

分配任务到公有云之后，提出的调度机制下一步就是最小化租赁成本并且形成一个公有云上的任务调度表。问题是在公有云的调度任务涉及到公有云服务模型。用户利用现用现付的方式可以租任何类型的资源槽。资源槽根据资源质量、CPU总时间、总使用存储空间和总消耗带宽来收费。我们采用MRCPR算法，在满足预算控制约束的前提下最小化公有云资源的租赁成本。输入算法需要的三个参数，参数TP_i来自RSD的结果和其他两个参数来自调度机制数据维护。

MRCPR方法包括以下步骤：

(1)该方法需要输入三个参数，其中一个TP_i参数来自RSD方法的结果和另外两个参数来自调度机制元数据的维护。定义TP_i，PRT，t_init；其中TP_i是作业J_i运行在公有云上的任务集，PRT是公有云资源槽的类型集，t_init是公有云资源槽的时间初始值；

(2)初始化变量，NR_i＝φ，Z_i＝φ，TotalCost＝0，其中NR_i表示一组公有云资源槽，Z_i表示公有云上任务的调度表，TotalCost表示公有云的租赁成本；

(3)在公有云上为任务寻找合适的资源类型，该资源满足最后期限约束的条件下价格最低；

(4)如果最好的资源类型被找到，系统会在公有云上创建一个实例类型并且分配任务到该公有云资源实例，即分配任务T_i,j到资源k并且在Z_i中记录映射；

(5)计算在k上运行的T_i,j的成本并且加入到TotalCost；

(6)返回公有云的调度表和为作业中的任务相应地调度公有云资源槽。