云计算的任务优化调度技术研究

（1）贪心算法

贪心算法即在对问题求解时，总是做出在当前看来是最好的选择，即所做出的选择是在某种意义上的局部最优解的算法过程。用户在选择贪心算法时必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

贪心算法解决问题的过程：首先，将被调度对象分为两个集合，一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象，通过算法给定的函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优，另外一个函数检查一个候选对象的集合是否是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解，和上一个函数一样，此时不考虑解决方法的最优性。然后，随着算法的进行，选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。最后，目标函数给出解的值。为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，使得贪心算法逐步进行。

但对于贪心算法而言，找到一个简单可行的最优解是不切实际的，因此该算法具有一定的最优解查询的局限性。

（2）Min-Min算法

Min-Min算法通过获取任务执行的最早执行开始时间和最快执行速度，完成启发选择，当把所有任务指派给执行该任务最早而且执行该任务的资源时，则全部的任务完成的时间最短。算法的过程：获得每个任务的最早执行时间及其资源的需求，再将具有最短最早完成时间的任务指派给获得它的资源，指派完成后更新资源的就绪时间，并将分配过的任务从任务集合中删除。如此重复，直到全部任务被分配完毕为止。

该算法容易导致负载过度集中在能力较强的节点上，造成高性能节点超负荷运转，而其余性能较低节点的处理能力却没有得到很好的利用，导致资源并不能够得到充分的利用。

（3）Max-Min算法

Max-Min算法与 Min-Min算法类似。一旦某个任务获得最早执行时间的资源，将具有最长最早完成时间的任务指派给该资源节点，并更新资源的就绪时间。如此重复，直到所有任务分配完毕。将Max-Min算法与Min-Min算法进行比较，可以得出，对于Min-Min算法，先执行完成时间短的任务，然后执行完成时间长的任务，而 Max-Min算法则先完成执行时间长的任务，然后执行完成时间短的任务。(www.xing528.com)

在同构非均匀的计算系统中，Min-Min算法的调度性能优于 Max-Min算法，在异构计算环境中，当执行时间短的任务数量远超过执行时间长的任务数量时，Max-Min算法性能也可能优于Min-Min算法。

（4）Sufferage算法

Sufferage算法在比较各任务之间的执行损失，尤其是任务之间具有冲突时，将损失最大的任务最终分配给候选资源，从而使得调度结果更逼近最优解，其调度思想为资源总是应该被分配到估计的执行损失最大的资源节点上，不然，将会遭受估计到的最大的损失。

在Sufferage算法中，任务的执行损失被定义为任务的实际完成时间与最短完成时间之间的差值，称之为Sufferage值。如果在Sufferage值大的应用场景中，由于实际完成时间与最短完成时间之间的差距较大，若本次任务不被调度在具有最短完成时间的最优资源上，在下次调度时将对整个调度跨度造成较大的影响。该算法也属于贪心算法的一种，其贪心的对象不是最短完成时间或最长完成时间，而是最大任务执行时间的损失。

（5）DAG任务调度算法

DAG，即有向无环图（Directed Acyclic Graph，DAG）。在当前的大数据处理应用中，DAG用来表示将计算任务在内部分解成若干个子任务，将这些子任务之间的逻辑关系或顺序构建成 DAG结构。分布式结构 Dryad、Flumejava和Tez，都是明确构建DAG计算模型的典型，其中的计算任务均以DAG形式出现。

利用DAG完成任务调度算法，分三层结构表示：最上层是应用层，即通过一定手段将计算任务分解成由若干子任务形成的DAG结构，方便应用商快速搭建架构。中间层是DAG执行引擎层，主要目的是将上层DAG计算任务通过转换和映射，将其部署到下层的物理机集群中运行，该层是运行DAG计算的核心部件，完成计算任务的调度、底层硬件的容错、数据与管理信息的传递以及整个系统的管理与正常运转。最下层是物理机集群，即由大量物理机器搭建的分布式计算环境，完成计算任务的最终调度执行。