分布式计算系统的多层子树堆排序任务匹配调度算法.doc

第8A期徐秀等：分布式计算系统的多层子树堆排序任务匹配调度算法81分布式计算系统的多层子树堆排序任务匹配调度算法徐秀，张申(中国矿业大学 计算机科学与技术学院, 江苏 徐州 221008)摘 要：为能够给计算任务的分配与资源的调度提供更好的依据，提出了将分布式计算系统的资源组织成层次化结构来进行管理。依据堆排序匹配递归的特点，在单一数据插入堆结点方法的基础上，提出了子树成堆判断方法。并在改进子树堆排序算法的基础上，设计了一种基于多层子树堆排序任务匹配调度的算法。经对算法的分析和实验的结果的验证表明，该算法能够对资源树的信息需求量进行合理、快速、有效的进行任务的匹配，从而提高了任务调度和资源获取的效率。关键词：任务调度；分布式计算；任务树；资源树；堆排序中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)8A-0074-08Task match scheduling algorithm on distributed computing systems using heap sort of multi-layer sub-treeXU Xiu, ZHANG Shen(School of Computer Science and Technology, China University of Mining, Xuzhou 221008, China)Abstract: To organize the distributed computing system resources to form the level structure to carry on the management provides the basis for the computation task assignment and the dispatch resources. According to the characteristic of the arrangement matching recursion , based on the sole data inserting in the cru-node, one method of sub-tree to be formed one pile was proposed, one algorithm of sub-tree heap sort was advanced, and then one task matching algorithm based on multi-layers sub-tree heap sort was designed. The algorithmic analysis and the experimental result indicated that, this algorithm can carry on reasonable, fast, and effective task matching for the resources trees information need quantity, enhancing the efficiency of the task scheduling and the resources gain. Key words: task scheduling; distributed computing; mission tree; resource tree; ordered pile1 引言收稿日期：2007-06-20基金项目：山东省煤炭工业科技发展计划项目(2005-110)；中国矿业大学科研基金项目(OD4551)Foundation Items: ShanDong Province Coal Industry Science and Technology Develops the Plan Project (2005-110); China University of Mining Technology Scientific Research Fund Project (OD4551)通过将网络上分布、功能独立、能力有限的资源组织起来，形成一个集成、功能更加强大的资源，通过中间件对底层的计算资源进行协调组织，为应用程序提供合理利用底层资源的方法1，用户就可以在具有多层体系结构特征的资源环境中获取资源。网络计算和分布式计算都需要在物理上和逻辑上分布的计算资源的协作下完成2。这些资源信息一部分是静态资源（如资源网络地址、地理位置、总处理器数目、处理器主频等），另一部分是随时间变化而变化的动态资源（如资源的当前计算能力、可用处理器数目、负载大小、可用内存大小、可用外存大小等）。如果将静态资源和动态资源都进行统一的表示，那么用户就可以根据需要来选择自己所关注的资源信息3,4。任务调度是分布计算研究中的一个关键问题。一个好的任务调度策略不但直接影响和决定着整个集群系统的运行效率，同时也能够为用户提供一个有效、实时的共享资源环境5。在任务调度研究的工作中，已经有大量的研究应用到实践中。例如：在高通信延迟多处理机系统上的任务调度算法中曾运用了任务图调度与其偶图的匹配关系6提出启发式算法并通过模拟试验显示本算法具有较好的调度效果。在针对的输入队列交换机调度的统一符号表示与描述方法中运用了基于定长分组(信元)双向图匹配7算法。在有效解决制造网格中的资源调度中，通过资源-任务匹配矩阵8方法进行任务/子任务及资源的数学定义等问题的解决。为使大部分任务能够在执行时间最短且完成时间最早的处理机上执行，运用任务调度的双匹配动态调度9算法，可将任务与处理机实现双匹配。在网格资源管理系统中，以资源状态和距离计算资源共享开销为任务资源匹配调度依据10，使任务请求分配最好的资源。用户获取资源时，是在两个或多个软件上互相共享信息的，这些软件可以是同一台计算机上，也可以是通过互联网连接起来的多台计算机上运行。在由早期的单向链表逐个结点遍历的单向任务调度方法中，是通过一个无限循环来判断任务的标志量，然后通过中断来激活新的任务，最后进入固定任务中断程序入口来实现任务调度的。在这种调度方式下，系统的大多数时间被任务等待的无限循环所占据，无法进行任务之间有效的上下文切换，导致系统的实时性不强 11,12 。通过改进原有单向任务调度模型，然后运用双向匹配模型的“均衡适度”分布调度策略13，在分配到服务机上的子任务调度过程中执行双向匹配的动态策略调度方法14,15。虽然这种运用双向匹配模型的方法使整个系统的资源使用效率得到了提高，但核心任务的调度机制仍然是将所有可用的任务控制块通过指针连成一个可用任务双向链表的无限循环方式，而且由于每个任务的优先级要求不一样且惟一，所以任务调度的工作首先需要查找准备就绪的最高优先级的任务并进行上下文切换，而优先级数又被分解为高三位和低三位，并且需要通过查找任务在就绪组和就绪表数组中的相应位置来区分高三位和低三位以计算最高优先级任务的优先级。显然，这种方法的效率也很有限。本文依据用统一的资源表示方法、树型结构的特点，基于堆排序的原理，选择子树及多层子树的树结构方式来组织资源，并在此基础上进行资源查找、资源管理和任务调度。这种基于调度子系统的堆排序递归匹配算法，为每一个任务找到目标结点执行调度过程，在进行任务分解之后再执行相应的匹配算法。因为任务树不同层次的任务结点的匹配是在不同的计算资源上完成的，对由树状结构组成的任务树中每一个非叶结点匹配成功后都开始进行分解，分解出来的每一个子任务再执行匹配过程，所以任务树匹配算法的执行是一个分层次的完全分布式的匹配算法。本文提出的方法可以减少在系统中寻找匹配循环时间、提高了匹配效率，并对于大规模并行任务问题也可以消除将所有并行任务分配和调度在同一资源上执行所产生的占用大量内存资源和CPU资源而导致的性能瓶颈问题，从而最终能更有效地获取资源、提高资源利用率。2 层次化资源模型对计算资源进行有效地描述、组织、管理，能使用户高效地为计算任务寻找合适的资源。本文构建的资源树结构是一个层次化的资源组织形式，计算资源可以是所有能为计算问题提供处理器周期的分布式并行计算系统或集群计算系统。2.1 资源树资源树是一个逻辑结构，它对资源查找、资源管理及任务调度等起到指导作用。资源树按树型结构将系统的计算资源的集合组织起来，资源树中的结点为资源结点，某资源结点连同所有其后继结点的集合为以该结点为根的资源子树，如图1所示。图1 资源树结构资源树中的非叶结点只负责对以它为根的资源子树进行管理，并为其上层结点提供该子树的信息，并不参与实际的计算；而叶结点是实际参与计算的结点，通过这些资源的计算能力可以决定任务的分配方案。在资源树中每一个结点的资源量都是以该结点为根的资源子树的总的计算能力的参数值。假设资源结点N的子结点的信息为m1,m2,mk，计算能力由资源树的底层向上层逐步聚集，资源树的根结点上则记录着整个网格环境所拥有的计算能力的总和，即该结点的计算能力为C（N）= 。2.2 资源树建立与资源查找为确保分布式并行系统的通信延迟最小，分布式并行系统数据通道的带宽足够大，本文依据网络邻近原则来建立资源树、向资源树中增加新结点。当出现不同的任务类型时，将大型任务放置在层次较高的资源树中运行，以获得更多的计算资源，将小型任务放在层次较深的资源子树中运行，以充分利用局部计算环境的性能优势。查找资源时，通过给定资源的查找条件，从源结点出发，在资源树上查找满足用户不同需求的满意解、局部最优解、全局最优解的目标结点16。依据资源树的计算能力向上聚集的原则，可知资源树的深度为lnN，即资源的找时间复杂度为O(lnN)。3 层次化任务调度3.1 任务树任务调度目的是将计算任务以最优的方式分配到合适的计算资源上进行计算。在分布式并行计算环境中的任务调度方法的好坏直接关系到计算问题的计算性能和整个系统的整体性能。如果将并并行任务作为调度单位，将其组织成层次化结构，则可以构建一个层次化的任务树。通过层次化任务树可以将任务分层分组，使得并行任务的调度可以分布到资源树中不同的结点来完成，从而减轻任一个资源结点的负载。将所有并行任务在任务树中作为叶结点，并且将互相有通信的叶子结点上的任务尽量组织在任务树中的相同的分支上。假设任务A与B在运行过程中需要互相通信，任务C、D和E在运行过程中互相通信，则构造的任务树如图2所示。图2 任务树实例3.2 任务调度方法在构建了任务树与资源树的基础上，依据任务树与资源树计算能力需求都是向上聚集的特征，为满足资源树中每一个结点都要维护以该结点为根的资源子树的总计算能力值的要求及每一个并行任务给出完成该任务所要的计算能力需求总值的要求，在资源树与任务树之间进行调度映射。这种调度映射实质上是一个将任务树与资源树的任一棵子树进行匹配的过程，匹配的依据是资源子树的计算能力要能够满足计算任务的需求。4 任务匹配调度任务匹配算法是一个递归过程，它不仅对一个任务结点的匹配过程是递归的，而且对由树结构组成的任务树中的每个非叶结点匹配成功之后分解出来的每一个子任务的匹配过程也是递归的。在任务树匹配算法中寻求解时，为选择到请求量中子结点的资源量最大的结点，在遵循资源树计算能力向上聚集以保证任一结点计算能力不小于其所有子结点计算能力的条件下，通过堆排序算法建立初始堆和在每次输出堆顶元素后重新建堆的方法找到满足条件且最接近参考值的结点。4.1 堆排序方法所谓堆是指N个元素的序列K1, K2, K3,Kn，当且仅当该序列满足特性：KiK2i 且KiK2i+1或KiK2i且KiK2i+1(1in/2)。堆排序是一种树形选择排序，在排序过程中，它将R1N看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小(大)的元素17。如果堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆；反之，则称为大根堆。在堆排序过程中，正是利用小根堆（或大根堆）来选取当前无序数据区域中关键字小（或最大）的记录实现排序的。给定一个结点数为n的堆，将根结点H1和Hn交换来提取堆上的最大值，然后对H1Hn1组成的完全二叉树进行调整，就得到一个结点数为n1的堆，重复上述操作可以实现堆排序。相反，给定一个结点数为n1的堆，在已有堆的基础上生成若干个结点数为n的堆。如果将当前无序数据区域调整为一个大根堆，则选取关键字最大的堆顶为记录，将它和无序数据区域中最后一个记录交换。4.2 任务匹配调度算法资源树与任务树进行任务匹配调度过程是以递归方式进行的。基于堆排序递归匹配任务调度算法是为每个任务结点找到目标结点执行调度过程，在进行任务分解后再次执行相应的匹配算法执行任务调度过程。任务树匹配算法执行是一个分层次的分布式匹配过程。在匹配过程中，任务树中不同层次任务结点的匹配是在不同的计算资源上完成的。将任务调度的过程分布到不同的计算资源上，对于大规模、并行任务多的计算问题可以消除将所有并行任务分配和调度在同一资源上所产生的占用大量内存和CPU资源而导致的性能瓶颈问题。4.2.1 单个数据插入堆结点的判断堆排序算法按照层次遍历的顺序将堆内的数据组织成一维数组，并且数组中的各元素满足路径的单调性。如果有n个不相同的数据值用以生成堆，用数据H来存放待生成的堆，那么，首先将这n个数值按照从大到小的顺序排序存放到一维数组T中，然后，从其中选定数据值放置到堆H中，在放置之前首先进行单个数据判断。所谓单个数据判断法是指用来初步判断当前这个数据是否可以插入到堆中某个结点的方法。如果将当前数据x存放到堆中编号为d(1dleft0，则结束算法。4）从数组t中，找出所有值小于或者等于s_left1的元素，按从大到小的顺序放入数组t_left中，用来生成左子树。5) j_left =j_left+1，用单个数据插入堆判断法来生成左子树。若左子树栈s_left的当前结点指针j_left等于n_left，即左子树生成了一个堆，则转到步7）。如果栈顶指针top_left=0，那么说明当前左子树根结点的所有可能已经枚举完毕，h=h+1转步3）。6) 开始右子树的生成。将po和po_left中所有已经被选中过的元素合并放入数组po_mid中，由此可以将数组t中尚未被选中的元素按从大到小的顺序放入数组t_right作为组成右子数的元素。t_right中的元素与右子树中应有的元素个数相同。7) 将一维数组t_right中最大的元素t_right1作为右子树根结点st_right1=t_right1， po_right1=1，j_right=1。8) j_right= j_right +1，使用单个数据插入堆判断法和层次判断法生成右子树。若j_right等于n_right，则右子树生成了一个堆，此时左右子树都满足堆的条件，即整个堆找到完整的结果集。9) 如果top_right=0，说明在当前左子树的情况下，右子树所有可能组合已经生成完毕，s_left和st_left退栈转步6）生成左子树的下一个结果。10) 输出由栈s_left和s_right组成的整个堆，s_right和st_right退栈转步9）。4.2.3 多层子树递归匹配对于分布式计算环境，需要构成具有更多层的层次结构20。为此，我们提出了多层子树生成堆的匹配算法。在子树生成堆算法基础上，将子树生成过程递归化，即分别在左、右子树的判断过程中，再次运用子树生成堆算法对左子树和右子树分别进行生成堆，并且依次递归下去。用k表示递归生成的层数，一个堆的生成过程递归划分成2k个n-k层的子堆来完成。在2k个子堆全部生成完毕之后，再根据递归关系将它们组合起来，生成了完整的堆。多层子树递归匹配算法是任务调度过程的核心：1) 初始的接收结点为问题提交结点；2) If（接收结点资源量匹配当前任务的请求量）then 轮询所有子结点，寻找是否有资源量匹配请求量的子结点；If (没有找到匹配子结点) then 接收结点成为初始结点，开始执行并行任务，匹配完毕else 选择所有大于请求量的子结点中资源量最大的结点；移交任务请求，在该子结点中重新执行匹配 else向父结点转交任务请求，在父结点重新执行匹配算法;多层子树生成堆算法是将堆生成过程进一步划分成更多个更小的子堆，然后再将生成好的各个子堆组合起来，得到完整的堆。这样可以更进一步突出子树生成堆算法的优点，提高枚举效率。4.3 堆排序任务匹配调度算法在多层子树生成堆算法中，通过在每次划分子树的时候，将可以作为子树根结点的值存储在数组中，然后以此数组的长度作为循环次数，控制子树生成堆过程中子树根结点依次取值，用循环替代递归达到生成所有可能满足条件的堆的目的。堆排序特点在于将初始待排序的记录序列建堆，则堆顶元素为含最大关键字或最小关键字的记录，输出该记录，然后将剩余记录再调整为堆，如此反复直至排序结束。堆排序的时间主要由建立初始堆和不断重复建堆这两部分的时间开销构成。堆排序不依赖于原来数组的有序情况，在最佳、最差、平均情况下的时间代价均为O(n log n)，堆排序的优点在于建堆很快，只需要O(n)的时间，而且只需要一次建堆就可以反复利用，因此n越大效率就越高。基于堆排序的优点，在分布式计算系统中，n值越大越有利于用户对资源的需求，运用堆排序方法在资源管理中进行合理的匹配任务并进行有效的调度，对资源共享及用户实时、高效的调用资源都能体现更高的效率。在不同地域、不同网络环境下的多层结构下建立堆，时间复杂度都是O(n)。这与现有的启发式调度算法相比，要具有更好的实时性。现有的启发式调度算法大多是基于独立任务的，它们实现容易，使用方便。因是利用任务执行时间和系统负载的历史数据来调度任务。所以都没能兼顾实时性与负载均衡能力。5 实验5.1 实验一算法采用C语言编程实现，并在CPU为1.2GHz、内存为256MByte的PC机上进行测试。实验结果如表1和图3所示。表1不同算法生成堆的运行时间n堆的数目单数据插入堆判断法子树生成堆算法多层子树生成堆算法1221549007.6s3.2s1.3s132069850057.6s29.6s10.6s14117809000436.6s197.3s64.7s158112181003251.3s1506.4s512.6s图3 算法模拟结果依据表中数据，为多层子树算法与子树算法再进行一次效率值的对比，如图4所示。图4 多层子树堆排序与子树堆排序运行效率实验结果表明，在实际运行时间的对比中，子树生成堆判断法比单个数据插入堆判断法的效率高，而多层子树生成堆法又比子树生成堆判断法的效率高。因此可以得出多层子树判断法比子树判断法的效率更有优势。在将多层子树堆排序算法运用到任务调度的分布式匹配过程时，采用分而治之策略，将任务树中的每一部分分解成为整个计算问题的一部分，可减少在整个系统中寻找匹配循环的时间，从而提高了匹配效率。5.2 实验二多层子树堆排序匹配调度算法最大的优势是在分式计算系统中节点越多越能体现查找资源的有效性，在任务调度匹配时的成功机会越多，CPU的利用率越高。多层子树的堆排序是一个分层次的分布式匹配过程，并通过建好的堆如此反复直至排序结束，需求到合适的资源。我们以任务调度的成功率、处理机的利用率作为调度方法的评价标准，将本文提出的多层子树堆排序匹配调度算法与启发式调度方法进行比较以验证算法的合理性。模拟任务调度的成功率中，设连续任务数总共为10个，假设系统中所有任务的初始释放时间为0。其模拟结果如图4所示,图4的模拟结果说明堆排序匹配任务调度算法与启发式调度方法相比，任务被调度的成功率比较接近一个水平的效率值，且效率也比启发式调度算法效率高。模拟处理机的利用率时，设参数如下：1) 处理机节点数设为6； 2) 任务执行时间相同且服从参数均匀分布；3) 任务到达系统的时间间隔服从参数为处理机负载值的泊松分布；其模拟结果如图5，可以看出在不同的处理机负载情况下，越小，处理机负载越重。将本文提出的堆排序匹配任务调度算法与启发式调度方法相比较，能使得处理机利用率更高。处理机负载值图5 算法模拟结果6 结束语本文提出一种将分布式并行处理系统中的资源采用树型结构组织计算资源与层次化任务匹配调度方法。这种树结构的资源组织方式与任务树的匹配调度方法，使用户可以高效地为计算任务寻找合适的资源。任务树的构造对计算问题的各并行部分也可以按照相互之间的通信关系进行分组，将任务调度过程分布到不同的计算资源上完成，这样既解决了单结点的瓶颈问题，同时又提高了任务调度的性能。依据堆排序匹配递归的特点，在单一数据插入堆结点方法的基础上，提出子树成堆判断方法并改进子树堆排序算法，进而设计一种基于多层子树堆排序的任务匹配调度算法。算法分析和实验结果表明，该算法.法能够对资源树的信息需求量进行合理、快速、有效的任务匹配，提高了分布并行任务调度和资源获取效率。参考文献：1徐志伟，冯百明，李伟网格计算机技术M北京：电子工业出版社, 2004.XU Z W, FENG B M, LI W. Hundred Understands Covers Lattice ComputeringM. Beijing: Electronic Industry Press, 2004.2陈渝. 先进计算基础设施若干关键技术的研究D博士后报告, 2001.CHEN Y. Some Key Technology ResearchD. Postdoctor Report Advanced Calculation of Chen Chongqing Infrastructural Facilities, 2001.3都志辉，陈渝，刘鹏网格计算M北京：清华大学出版社, 2002.DOU Z H, CHEN Y, LIU P. Grid Computing MBeijing: Tsinghua University Press, 2002.4金海，袁平鹏，石柯网格计算M. 北京：电子工业出版社, 2004.JIN H,YUAN P P,SHI K.Grid Computing M. Beijing: Electronic Industry Press, 2004.5陈渝, 庬立会, 钱方. 并行系统模拟环境的研究与实现M. 上海, 2001.CHEN Y. Processdings of the Conference on High Performance ComputtingM. Shanghai, 2001.6周向东,陈国勋,施伯乐. 基于图匹配的多处理机调度算法J.小型微型计算机系统, 2003. ZHOU X D,CHEN G X,SHI B L.Manage an algorithm owing to pursuing the multiprocessor mating J. Minitype Minitype Computer System, 2003.7鄂大伟. 基于输入交换队列的双向图匹配调度算法的协议模型表示J. 集美大学学报(自然科学版), 2005.E D W. Agreement model of controller algorithm mating owing to importing two-way picture exchanging a queues is expressedJ. Ji Mei College Journal (natural science printing plate),2005.8刘丽兰,俞涛.制造网格中基于服务质量的资源调度研究J.计算机集成制造系统,2005.LIU L L,YU T.Study in creating the net lattice owing to service quality resource controller J. Computer Integrated Manufacturing Systems,2005.9支青, 蒋昌俊.一种双匹配动态调度算法J.信息与控制. 2005.ZHI Q, JIANG C J. One kind of the development controller algorithm who mates pairJ. Information and Control, 2005.10王小根, 须文波. 一种基于资源状态预测的资源调度模型J.上海理工大学学报,2006.WANG X G, XU W B. One kind of the resource controller model that state forecasts owing to resourceJ. Shanghai Technique College Journal, 2006.11何剑兰.基于Web 的嵌入式数控系统实现.中国科技论文EB/OL. .HE J L.Owing tothe Web implantation style, numerical control system comes trueEB/OL. Chinese Science And Technology Thesis. Http:/.12李曦. C/OS-分析EB/OL. 6/embedded/ llxx9. pdf. 2006. 9.LI X. C/OS-EB/OL. 6/embedded/llxx9. pdf. 2006. 9.13孙芳, 张敏. 分布计算环境下任务调度双向动态策略的研究J.计算机与数字工程, 2006.SUN F, ZHANG M. The distribution secretly scheme against environment issues two-way development of task scheduling tactics research J. Computer and Figure Project, 2006.14苏蕊,徐炜民,钱晓竞.基于双向匹配模型的任务调度策略的研究J.计算机工程与设计, 2005.SU