面向云计算的任务优化调度技术

（1）FIFO调度算法

FIFO调度算法中应用任务存放队列存放用户提交的任务，所有任务按照用户提交时间顺序执行，任务的分配由指定的分配模块完成。

FIFO算法的思想是对用户提交的任务不做优先区分，而按照先来后到的顺序执行，算法实现起来简单。但在实际应用中，不同任务会有不同的优先级别要求，这样在执行该算法时，例如在一个生产型任务被调度之后，系统资源将被长时间占用，之后的交互型任务会消耗内存资源。所以在应用该调度算法时，就要保证该任务会被分配到内存资源充分的任务跟踪程序上执行，避免由于资源不足造成任务无法执行或者执行速度缓慢的情况发生。

（2）推测式任务调度算法

MapReduce将作业划分成许多个任务，然后并行运行这些任务，从而使作业的总运行时间少于串行运行的时间。但一个并行运行的作业，它的运行时间对于那些运行缓慢的任务很敏感，因为运行一个缓慢的任务会使整个作业所用的时间增加很多。在运行由成百上千个任务组成的作业时，出现这种少数缓慢的任务的情况是很常见的。为了解决这一问题，在MapReduce的开源实现Hadoop中，采用了推测式任务调度（Speculative Task）。

推测式任务调度算法是指在分布式集群环境下，因为程序问题、负载不均衡或者资源分布不均，造成同一个工作的多个任务运行速度不一致，有的任务运行速度明显慢于其他任务（比如，一个工作的某个任务进度只有10%，而其他所有任务已经运行完毕），则这些任务拖慢了作业的整体执行进度，为了避免这种情况发生，Hadoop会为该任务启动推测式任务，让推测式任务与原始任务同时运行，先使用运行完的任务。

推测式任务调度算法的思路是以空间换时间，同时启动多个相同任务，哪个完成得早，则采用哪个任务的结果，这样可以明显提高任务的计算速度，但是，这样却会占用更多的资源，在集群资源紧缺的情况下，合理地控制推测式任务，可在利用少量资源的情况下，减少大作业的计算时间。

（3）LATE算法

现有的Hadoop调度器都是建立在同构集群的假设前提下，具体假设：

① 集群中各个节点的性能完全一样；

② 对于Reduce Task，它的三个阶段：复制、分类和规约，用时各占1/3；

③ 同一工作的同类型的任务是一批一批完成的，在使用时它们基本一样。(www.xing528.com)

现有的Hadoop调度器存在较大缺陷，主要体现在探测落后任务的算法上：如果一个任务的进度落后于同类型任务进度的20%，则把该任务当作落后任务从而为它启动一个备份任务。如果集群是异构的，对于同一个任务，即使是在相同节点上的执行时间也会有较大差别，因而在异构集群中很容易产生大量的备份任务。

LATE调度器从某种程度上解决了现有调度器的问题，它定义了三个阈值：系统调度上限，系统中最大同时执行的任务数目；慢节点阈值，计算节点的特定得分低于该阈值的节点（快节点）时不会启动任务；慢任务阈值，当任务进度低于同批同类任务的平均进度的慢节点阈值时，会为该任务启动计时。它的调度策略：当一个节点出现空闲资源且系统中总的备份任务数小于系统调度上限时，如果该节点是慢节点（节点得分高于慢节点阈值），则忽略这个请求。对当前正在运行的任务按估算的剩余完成时间排序：选择剩余完成时间最长且进度低于慢节点阈值的任务，为该任务启动备份任务。

（4）公平调度算法

公平调度算法是由 Facebook提出的一种新的调度算法，其基本思想是最大限度地把系统中的资源平均分配给用户提交的任务。假如在系统中仅存在一个执行的任务，那么它会占用全部的系统资源，如有新的任务进入系统，一些任务跟踪程序会被释放并被安排执行新的任务，而且要保证各个任务之间能够获得几乎没有差别的资源。

公平调度算法为每个用户建立一个单独的任务池用于存放任务，这样使得系统可以根据用户的数量平均分配系统资源，而不用考虑每个用户实际提交了多少个任务。公平调度算法根据任务的资源差值来决定各任务之间获得资源的水平，任务差值就是任务在理论上应该获得的系统资源和任务实际获得的系统资源的差值。任务差值越大表示任务当前获得的资源水平越低，越小表示当前获得的资源水平越高，则可以演变为两种任务优先级分配算法：优先分配差值大的任务和优先分配差值小的任务。

在实际应用中，公平调度算法通常会给不同的任务和任务池赋予不同的权值，可以根据任务的优先级等因素合理地为不同用户的不同任务分配系统资源，把该算法演变为相对公平的任务分配，使其能够更符合实际应用。该算法具有很强的交互性，可以提高用户的体验性，但对于存在大量用户和任务请求的场景，存在频繁地释放资源、调度任务等方面的弊端。

（5）计算能力调度算法

计算能力调度是由 Yahoo提出的任务调度算法，该算法使用多个工作队列维护用户提交的任务，每个工作队列都可以根据配置获取一定的任务跟踪程序来执行任务，计算能力调度算法按照配置策略给不同的队列分配合理的系统资源。

计算能力调度算法的内容：当某个系统资源已经被分配给某工作队列但未被使用时，每个工作队列公平地分享这些资源；当没有按照配置的设定数值获得充足资源的工作队列中的任务处理量增大时，之前分配给该工作队列又被其他工作队列占用的系统资源在完成当前任务后，立刻返还给它应属的工作队列。计算能力调度算法以此提高系统的资源利用率。

计算能力调度算法将每一个工作队列模拟成一个具有特定处理能力的独立Hadoop集群资源，在每个工作队列中采取基于优先级的FIFO调度算法，每个工作队列中的工作按照优先级排列依顺序获得系统资源。

计算能力调度算法是非抢占式的，即当一个任务开始执行后，它不会因为工作队列中又进来一个优先级更高的任务而被迫放弃已占用的系统资源。新加入的任务只能等待正在执行的任务执行完成后，再按照优先级访问系统资源。此外，计算能力调度算法还会根据任务的不同类型进行按需调度，如果一个任务需要大量的内存资源，那么调度算法就要保证该任务会被分配到内存资源充分的任务跟踪程序上去执行。