分布式集群任务调度概述

分布式集群任务调度

在以往单机的任务执行中，任务都在一台机器上执行，所有任务都需要有序排队等待执行，多个任务执行的时间大致为每个任务在单机上执行的时间。但是当执行任务的机器数量变多之后，就需要将任务有序合理的分配到不同的机器上去执行，这也催生了一些分布式集群中任务调度的算法。

集群任务调度算法

当前较为主流的经典算法有如下两个，Min-Min算法和Max-Min算法，这两种算法计算过程相对简单并且不复杂，但是缺点也很明显就是对任务的负载均衡，长短任务的分配效果会差点。

Min-Min算法

1.假设网格任务集为Tasks={T1，T2，T3，．．．，Tn}，集合内有n个待调度的独立任务。

2.网格资源集为Hosts={H1，H2，H3，．．．，Hm}，该资源集合内有n1个资源。设资源Hi的就绪时间(即资源最早的可以使用的时间)为R(i)。

3.任务Ti在资源Hj上的完成时间定义为ECT(i，i)，定义任务在资源上的执行时间为ETC(i，j)。

4.从上面定义得出，一个任务Ti在资源Hj上的完成时间计算公式如下： ECT(i，j)=ETC(i，j)+R(j) 。

5.n个任务在m个资源上的ETC可以用一个nxm的矩 阵来表示，矩阵元素ETC(i．i)表示第i个任务在第j个资源上 的执行时间，该矩阵的一行表示任务Ti在资源集合Hosts中 所有资源的执行时间，一列表示在同一资源上n个任务的执行时间。

Min-Min算法的思想是：

首先，计算出任务列表中所有任 务在所有资源上的最小完成时间。其次，从这些最小完成时间中找出一个值最小的，把这个最小时间对应的任务资源对找出来，把该任务提交给该资源执行，从任务列表中删除这个任务。最后，更新最小完成时间矩阵。重复以上步骤，直到任务列表为空。该算法的目的是将任务指派给不仅完成它最早的，而且执行它最快的机器，使得全部的任务完成时间最小。

该算 法的执行过程如下：

1.计算任务集合中的任务Ti在m个资源上的完成时间，得到n*m的ECT矩阵。 如果任务集合Tasks不为空时，重复以下步骤直到任务全部调度。

2.得出每个任务的最小完成时间即ECT(i，j)，把这些最小完成时间放入一个集合M内，然后找出这个集合内最小的值，根据最小值所对应的任务资源对(i，j)，这就是任务到资源的映射。

3.把该任务Ti提交到对应的资源Hi上执行，同时还要更新此ECT矩阵。

该算法容易将性能较好的机器分配更多的任务，有时会造成负载不均衡导致部分资源浪费。

Max-Min算法

Max-Mim算法，非常类似Mim—Mim算法，同样需要计算待派发任务的最小期望完成时间。与Min-Min算法的区别是，Max-Mim算法首先调度最大期望完成时间的任务到 其对应的机器上。由于Mim-Mim算法，每次都是讲最小期望完成时间的任务派发到性能高的执行机上，这样会使得性能高的执行机上会源源不断的被分配任务过来，导致系统中执行机的负载不均衡。 而Max-Mim算法，首先调度期望时间大的任务，这样执行效率高的机器在第一次被派发任务后，其他未派发的任务更新任务的最小期望时间后，已经被派发任务的机器上的最小期望时间就会增大， 再次派发任务时，一般会派发到其他机器上，这样在一定程度上保证了负载均衡。Max-Mim算法与 Mim-Mim算法有相同的时间复杂度，但是在系统处理多数小任务时，Max-Mm算法要比Mm—Min算法性能高。

改进算法分析

当前有些算法基于Min-Min算法进行优化，尝试优化该算法的分配效率，分别了解如下两种优化思路。

资源分级的Min-Min算法

分布式计算中基于资源分级的自适应 Min-Min 算法

该方案是基于将资源进行设置评级，因为每个计算资源有可能对于的cpu、内存或者带宽都不同，从而可能会适合执行不同的任务，此时类似与通过输入这些资源的属性然后再Min-Min算法中配置不同的阈值从而完成任务的适应性分级从而快速调度。

算法流程概述

从任务长短因素角度考虑，将其长度具体化，设定自适应阈值，调解长短任务的调度优先级。本文将重点参考长任务在所有子任务中的比例，设定自适应阈值的大小，然后通过自适应阈值重新划分长任务的优先级，从而得到改进的自适 应 Min-Min 任务调度算法(SMM)。

首先建立需要计算的子任务序列，将子任务在所有资源上的执行时间与资源等级作乘积运算，即 t=t×δ，从而得到基于资源分级后的 RETC 矩阵和向量 W;初始化MCT，以及总体任务分解后的子任务集 T，任务集 T映射到待分配任务集 S，MCT 矩阵中的每个元素为对应作业任务在各机器上的预测执行时间与资源就绪时间之和，即 MCT[e,f]=RETC[e,f]+r[f]，其中 r[f]为资源就绪时间。

1. 循环取值从 1行到第 n 行，计算 RETC矩阵中每行的均值，将均值结果存储到向量 W中，即 w[i]表示任务 s[i]的平均预测执行时间。
2. 判断:如果待分配任务集S不为空，完成步骤2-9;否则任务调度结束。
3. 从向量W找出最大值Wmax、最小值Wmin，并计算出均值w和向量元素数量 p。
4. 参考定义，从子任务集找出长任务，并确定数量q。判断:如果存在长任务，即 q>0，则跳转到步骤 5;如果不存在长任务，即 q=0，则跳转到步骤 7。
5. 计算得到长任务占整个任务集的比例 K=q/p。
6. 得到自适应阈值ζ=kI，在MCT矩阵中对长任务所占的行作乘ζ的运算。
7. 遍历矩阵MTC找出最小完成时间矩阵MMCT;
8. 遍历矩阵MMCT确认当前最短执行时间的任务，记录该任务并将其 调度到指定的机器上完成计算任务。
9. 将该任务从未分配的子任务集中删除，更新资源就绪时间r[f]、W和MCT。跳转到步骤2。

其中，W是指该任务所有的执行的历史时间的集合，Wmax值执行时间的最大值，Wmin值执行时间的最小值，w是指执行任务的平均值；长短任务的定义如下，记T1=Wmax-w>0，T2=w-Wmin>0，当T1>T2时，令A=T1,B=T2，当T1<T2时，令B=T1，A=T2，此时M=A/B，如果任务的时间大于M*任务的平均时间则为长任务，否则为短任务。I定义为q/p，即长任务除以短任务的数量；δ=o×P×n+p×V+q×B+R×y其中CPU处理能力为P，CPU数量n，内存性能R，磁盘容量V，通信带宽B。

算法的整个流程中，引入了长短任务的概念，并且引入了长短任务的比值，如果都是短任务则直接调用性能最好的即可执行更合适，如果遇到了长任务则可以通过资源等级不同来选择不同的资源。该算法缺点就是需要先调试好参数，任务资源需要定义合适，适用范围有一定的局限。

Min-Min添加资源属性

Review on Max-Min Task scheduling Algorithm for Cloud Computing

Step 1: Start
Step 2: for all submitted tasks in meta-task Ti
Step 3: for all resource Rj
Step 4: compute Cij = Eij + rj
Step 5: While meta-task is not empty
Step 6: Sort all the tasks in descending order as per Burst Time.
Step 7: Give priority to tasks which have highest and lowest
        priority.
Step 8: Consider remaining tasks as normal priority tasks.
Step 9: Consider three groups according to priority:
        (1)Highest priority group
        (2)Normal priority group
        (3)Lowest priority group
Step 10: First load the tasks of highest priority group and
         arrange task in descending order according to their
         burst time.
Step11: Arrange Vm list in descending order on the basis of Resource Cost as
        Resource cost = (RAM of Virtual machine * Cost/memory )
         +(Size of Virtual machine*Cost/storage)
        (1) For all tasks in highest priority group Ti,
        (2) Select resource from resource list sequentially
        (3) Select task sequentially and schedule on selected resource
        (4) Remove Task Tk from Meta-tasks set.
        (5) Update ready time rj for select Rj
        Update Cij for all Ti
Step 10: Repeat above steps till the each and every task executed
         completely in highest priority group.
Step 11: Repeat above step 9 first for Normal priority group and
         at last for lowest priority group until each and every
         task executed completely.
Step 12: End
           

该算法将任务进行分级，可以尝试分成三个等级即高优先级、中优先级和低优先级三个等级，然后优先调度高优先级的任务，然后遍历所有的资源并通过考虑资源的消耗如内存硬盘等代价再选择一个资源去执行。然后从高优先级一直处理到低优先级直到任务执行完成。

总结

本文都是主要都是整理自网上相关论文文献，主要是了解在分布式集群下对任务的相关调度的一些基础方式，最要是两个经典的Min-Min和Max-Min算法，后续也有许多基于该算法改进而成的调度算法，在现实的开源的软件的调度算法中，常用的方式还是轮训、权重和hash等，因为这些方式相对简单稳定，从算法的整理来看，实现本文的算法需要考虑的因为较多，并且通用性相对不强，从而难以满足大家普遍的使用场景，如果大家有兴趣可自行实现一下，本文只做摘录学习。由于本人才疏学浅，如有错误请批评指正。