关于任务调度相关研究文献综述

关于任务调度相关研究文献综述随着多核处理器的出现，多核处理器任务调度已成为当前高性能处理器研究的热点之一。任务调度是指系统为确定一系列任务的执行顺序所采取的调度策略。随着计算机技术的不断发展，学术界对任务调度问题的讨论也逐渐深入，旨在通过减少通信开销、改变任务执行顺序，以缩短整个任务的调度长度。近年来，由于多处理器的广泛应用，如何充分利用多处理器的计算性能成为了大家关注的焦点，针对多处理器的任务调度问题突显出来。在多处理器任务调度算法研究的早期，PDutot[24]等人在研究中指出，对于异构计算环境下的任务调度问题是NP难问题，难以在多项式时间内寻求最优解。正是该问题的重要性和复杂性，吸引了一大批专家学者对其进行研究，并提出了大量经典的算法。一、国外研究现状计算机任务调度的研究早在上世纪60年代就已开始。1967年，芝加哥大学的ManacherG.K在ACM期刊上第一次提出了“任务”的概念，并利用列表法和甘特图进行了基本的多核多任务调度算法研究，提出了能够保证调度稳定性的算法。同时文章对软实时系统和硬实时系统也给出了定义和说明。但是由于文章发表年代较为久远，文中提出的是同构多核处理器的模型，并不适用于当今迅速发展的异构多核处理器之间的任务调度。随后，刘炯朗和Layland在已有工作基础上提出了周期任务模型的概念，该模型对任务进行了较好的抽象，对周期性任务做出了一些假设，忽略计算机体系结构的复杂性以及应用程序的具体实现，可以借助各种数学方法对任务的可调度性进行分析。文中提出了可在单处理器上运行的三种调度算法：单调速率算法RM(ratemonotonicalgorithm)、最早结束优先EDF(earliestdeadlinefirst)算法[1]以及两者的混合算法。在RM算法中，根据任务的需求速度赋予其一定的优先级，即所谓的固定优先级。在EDF算法中，任务最终期限值较小的赋予更高的优先级，即动态调整任务的优先级。而综合算法将任务分开对待，分别使用上述的算法。文章分析了在上述几种任务调度算法下，CPU能够达到的最大利用率，并用数学方法给予了证明。为后来的研究奠定了基础。后续又提出了许多经典算法，包括时间片轮转(RoundRobin，RR)算法、先到先服务(FirstComeFirstServed，FCFS)算法、截止期单调调度(DeadlineMonotonicScheduling,DMS)算法等。在这些算法中，任务的优先1级都是基于任务的某些特征参数，如截止期、空闲时间或关键性等计算而得。然而，如果优先级仅由某个特征参数来确定是不够的，因为截止期或者空闲时间短的任务不一定是最关键的。而且这些算法主要是针对单核处理器，并不适用于多核处理器的任务调度。对于异构计算环境下的任务调度问题是NP完全问题，难以在多项式时间内寻求最优解。正是该问题的重要性和复杂性，吸引了一大批专家学者对其进行研究，并提出了大量经典的算法。HalukTopcuoglu和SalimHariri等人通过对异构环境下的任务调度进行大量分析，在1999年提出了两种到目前为止公认的调度效率较高的算法：基于处理器关键路径算法[8](CriticalPathOnaProcessor，CPOP)和异构最早结束时间算法[8](HeterogeneousEarliestFinishTime,HEFT)，是异构多处理器任务调度十分经典的调度算法。后期许多任务调度的算法都是在这两种算法的基础上提出的。这些算法都使用有向无环图(DirectedAcyclicGraph，DAG)来表示任务模型，节点上和节点间都根据时间开销赋予一个权值。在任务排序和任务分配两个阶段采用不同的方法来提高任务调度的效率。HEFT算法思想描述如下：在任务排序阶段，每个任务根据自身的运行时间和与后继任务的通信时间计算出一个向上排序值ranku(n)，根据ranku(n)降序排列每个任务；在任务分配阶段则根据最早完成时间进行分配，这种机制降低了算法复杂度，但同时处理器的利用率有待提高。与其它基于最早完成时间的调度算法有所不同，HEFT算法采用了区间插入技术，在同一处理器两个相邻任务间可能插入其它任务间隙处，插入一个新的任务来提高多核处理器的并行性和利用率，从而提高调度效率。但是该算法存在一些明显的缺点：任务排序只考虑到与后继任务的通信开销，让一些向上排序值高的节点优先运行，但没有从整体的拓扑结构考虑任务的关键程度，某节点向上排序值高并不代表此节点在整体拓扑结构的关键路径上，也就是说，有些关键节点可能得不到较高的优先级；能够利用区间插入技术插入到某个空闲时段的任务可能并不多；没有考虑较大任务间的通信开销，如果两个较大任务被分配到不同的处理器，任务间的通信开销可能远远超过任务本身的运行开销。HEFT算法的时间复杂度是O(n2*p),n表示任务个数，p表示处理器个数。考虑到HEFT算法存在的问题，HalukTopcuoglu等人又提出了一种CPOP算法。该算法在任务排序阶段不仅考虑了向上排序值ranku(n)，而且还考虑了向下排序值rankd(n)，通过两者的综合加上自身运行开销，计算每个节点的优先级权值，并且得到一个关键路径，然后选择一个串行执行这些关键路径任务时间最短的处理器CPP。任务分配阶段，把属于关键路径上的任务分配到CPP，非关键路径上的任务分配到具有最早完成时间的处理器上，后者结合了区间插入技术。关键路径是任务图中距离最长的路径，关键路径长度决定了整个任务图的完成时间，所以CPOP算法的目的是给关键路径上的任务更高的优先级，保证关键任务优先调度，以此来缩短整个任务完成时间。但CPOP算法同样存在一些不足：只考虑了提高关键路径节点的优先级，有可能忽视了某些关键节点的父节点，但这些父节点又不在关键路径上，CPOP算法中该类非关键路径节点的优先级可能很低，非关键路径节点的延迟调度将会影响关键路径的完成时间，降低整个调度算法的效率；同时，这种分配机制导致执行关键路径的处理器负载偏重，而其它处理器利用率并不一定很高，从而降低了处理器的利用率，导致处理器负载不均。此外，在异构多处理器任务调度算法中，经典的启发式算法还有Max-min、Min-min、Sufferage等。TracyD.Braun等人对这些算法做了比较和实验，给出了各种算法的实际性能[12]。Max-min算法首先计算任务的预期完成时间(ExpectedEarliestCompletionTime,EECT)，然后优先调度EECT最大的任务，优先对其进行资源分配。这种调度方法可以保证颗粒大的任务较好地被执行，能够在一定程度上实现负载均衡。但该方法没有考虑任务的执行频率，对于那些执行频繁的小任务，提高它的执行优先级可能会取得更好的整体性能。同Max-min算法相似，Min-min算法也是根据任务的EECT来确定任务调度优先级。不过，Min-min算法将EECT最小的任务对应最高的优先级，即将颗粒小的任务优先分配到最佳处理器上，依次完成任务的划分。该算法实现简单、复杂度较低。但算法策略单一，在按EECT从小到大顺序对任务划分时，容易引起处理器负载不平衡。Sufferage算法在Max-min和Min-min算法的基础之上进行改进。对于每个任务，计算其次早完成时间(放在次优处理器上执行的时间)与最早完成时间的差值，该差值命名为Sufferage值，反映出各个任务的调度代价。Sufferage算法按Sufferage值从大到小确定任务的优先级，以保证调度所带来的代价最小。但该算法只考虑任务单次执行的情况，没能考虑任务的执行频率，从而没有不能计算在一段时间内的总代价，不能取得很好地负载均衡。同时没有考虑任务最早完成时间，故系统总的执行时间难以最优。另外，SanjoyBaruah教授及其小组在任务调度与分析领域的研究比较活跃，相继发表了一系列有影响的文章[5][6][7]。同时，各研究者根据不同的应用需求，提出了多类调度算法。为了减少任务之间的通信开销，许多学者提出了基于任务复制(TaskDuplicationBased,TDB)及分组等多种调度算法。Kwok和Ahmed提出了关键路径快速复制(CriticalPathFastDuplication，CPFD)算法[20]，Bansal等提出了有限复制的调度算法[21]，Shin等人提出了最小复制算法[22]。这些算法都属于基于任务的调度算法，通过在多个处理器之间对任务进行复制，从而减少处理器之间的通信量。Abdelzaher和Shin在文献[23]中，根据实时任务的周期进行了分簇。他们的方法可以处理任务的异构性，扩展性强。传统的启发式算法无法适应所有的任务模型。在采用传统启发式算法之前往往需要对任务进行假设，这使得一种启发式算法只能应用于特定的任务模型。于是许多人工智能算法被运用到任务调度问题上来。人工智能方法通过模拟各种自然活动，通过演化迭代的方式来求取问题的解，越来越多地被引入到启发式算法当中。目前，对于人工智能方法的研究已经深入，许多方法形成自己的理论体系，为解决不同的复杂问题提供科学指导。这些方法有遗传算法(GeneticAlgorithm，GA)、模拟退火(SimulatedAnnealing，SA)算法、蚁群算法(AntColonyOptimization，ACO)以及粒子群优化算法(ParticleSwarmOptimization,PSO)等。这些算法都是模拟自然环境下的各种行为，从而求解过程具有随机性，比传统算法减少了人工干预。这些特点对于寻找全局最优解方面具有独特优势，为求解复杂问题提供了新的思路和解决方案，也广泛应用在任务调度这一复杂问题当中。二、国内研究现状相对于国外的研究,国内在多核处理器任务调度方面的研究起步比较晚,一直处于跟踪研究阶段,但随着近年来国内专家对任务调度研究的重视,仍取得了不少成果。中国科学院软件研究所的戴国忠、王宏安等人发表了一系列研究成果[32]，采用集中式的调度方案,考虑任务划分策略及软实时任务的服务质量，以统一方式完成对实时异构系统中硬实时和软实时任务的集成动态调度,提高了算法的调度成功率。此外，一些研究也对多处理器调度问题提出了新的算法和见解。针对fork-join图结构刘振英等人提出了一个新的算法TSA_FJ[34](TaskScheduleAlgorithmFork-Join)。TSA_FJ算法的原则是让Fork-join任务图中的最后一个任务节点尽早开始执行。该算法着眼于解决任务调度中被忽略的一个问题，通信信道使用冲突。在大多数任务调度算法中都是允许通信重叠的，也就是可以并行执行通信，在安排任务的起始执行时间时，仅考虑该任务接受最长消息需要的时间，实际任务需要的消息并没有全部获取就开始执行。但是现实中的并行计算系统处理器在接受发送消息时是串行进新的，所以传统调度算法和实际计算环境并不相同。为了解决这个问题作者提出了TAS_FJ来解决实际通信信道占用问题，并且力图使得处理器的消耗量最小。邱卫东、陈燕等人以提高现有启发式算法的性能为出发点，提出了一个异构分布式系统的动态BLevel优先算法[36]。该算法选择就绪任务中动态BLevel值最大的任务，考虑任务之间的依赖关系，将其划分到完成时间最早的处理器上。如果超过一个处理器具有相同的最早完成时间，则将任务分配到利用率最低的处理器上执行，以降低任务调度长度。清华大学的石威、郑纬民教授等对相关任务图的表调度算法进行了深入研究，分析了现有经典表调度算法中存在的不足。在此基础上，提出了一种均衡动态关键路径算法[27]。该算法综合考虑了关键路径节点和非关键路径节点的优先级，在调度过程中采用动态计算关键路径长度的方法，优先调度影响调度长度最大的任务，最终缩短了整个任务图的总调度长度。华中科技大学何琨、赵勇对分布式并行系统中有向无回路图的静态任务调度问题，以使调度长度最短为主要目标、减少资源数目为次要目标，提出了一种基于任务复制的分簇与调度算法──动态关键前驱算法DCP[31]。DCP算法将任务复制、分簇与优