一种作业调度和计算资源动态分配方法

杨涌 潘波 郑建 刘光文 林小光 成亮

摘要

首先概述计算资源分配和作业调度技术现状，然后以当前作业调度事务特点为基础，为了解决现有作业调度方法中计算资源划分不灵活、使用效率低等问题，提出了一种计算资源动态分配方法;另外，充分了考虑任务的类型或关系等因素，提出了一种基于业务信息判断的作业调度方法，该方法能够避免优先级低的作业不能及时调度的问题。通过具体测试验证，该方法对基于高性能计算集群的各种应用有很大的参考作用。

【关键词】计算资源 作业调度 动态分配

1 研究背景

随着信息技术的飞速发展，计算机系统需要处理的事务量大幅度增长。在摩尔定律巅峰时期，一切相对简单，计算机系统可以期待处理器指数级的性能提升。随着摩尔定律的终结，计算机性能提升很难直接通过升级硬件获得，信息系统已变得越来越复杂。

超算集群系统以其卓越的性能价格比和良好的可扩展性等因素成为当今高性能计算机系统的主流体系结构。如何合理高效地使用超算集群系统所包含的丰富的计算资源是非常紧迫的问题。作业调度算法是作业调度系统的核心，调度算法的优劣决定了作业调度系统本身的质量，决定了作业运行的稳定性、高效性等。在超算服务业务开展过程中，主要使用 FIFO（First In First Out，先入先出）调度机制分配任务，将所有的作业统一提交到一个队列中，并按照提交的先后顺序依次运行队列中的作业，但随着超算用户、业务量、业务类型的增多，传统的FIFO调度机制已经不能满足目前超算业务调度的需求。另外，在只考虑作业优先级的调度方法中，由于考虑因素单一，导致优先级低的业务不能及时调度，降低了作业调度的公平性和时效性。在现有的资源分配方法中，通常只考虑将所有计算资源作为一个统一的计算资源池，用户如果有计算需求，就分配一块固定的计算资源，导致计算资源划分不灵活、使用效率低。

2 算法總体框架

作业调度程序从后备作业中选取若干个作业到内存并投入运行。它为被选中作业建立进程并分配必要的资源，这时，这些被选中的作业处于执行状态。作业调度的功能是记录系统中各作业的状况，从后备作业队列中挑选一批作业进入执行状态，以及为被选中作业分配资源建立进程和在作业执行结束后释放所占用的资源等。其中最主要的是从后备作业队列中选取一批作业进入执行状态。根据不同的目标，将会有不同的调度算法。

本文提出了一种结合作业调度和计算资源动态分配的方法，旨在通过结合作业的信息对作业进行优化调度，实现其调度公平性，另外，通过资源的动态分配，实现资源的合理分配和利用，该方法的总体运行流程如下：

（1）根据用户业务需求为用户分配计算资源;

（2）根据用户业务需求建立作业队列，记录每个作业的优先级、作业提交时间、作业要求计算完毕时间等信息，并为每个作业分配相应的计算资源;

（3）计算各队列中各个作业预计运行时间长度;

（4）以用户为调度范围，采用作业的优先级、预计运行时间长度为依据进行作业调度;

（5）以作业包含的任务类型和关系为依据进行任务调度;

（6）计算完毕，释放计算资源。

3 计算资源动态分配方法

需要针对每个用户建立一张作业信息表，用于记录该用户所有作业的计算资源、作业优先级、记录作业提交时间、作业要求计算完毕时间、当前是否占用计算资源等信息。

作业信息表示例如表1所示。

根据每个用户的业务需求，为其分配分配计算资源Ki（i=1，2，"""n，i为用户编号）;管理节点将分配给节点i的计算资源分成两部分：一部份为Ki*P，作为该用户实际的计算资源，另外一部份为Ki*（1-P），作为该用户的预留计算资源，其中，P为该用户实际使用的计算资源与该用户分配的总计算资源的比值，0≤P≤1。

另外，为了保证整个系统超算业务调度的顺利进行，在为每个用户分配预留资源外，系统还将预留一部份资源备用。资源分配原理如图1所示。

根据用户需求建立作业队列，并为每个作业分配计算资源，确定作业优先级、记录作业提交时间。

4 作业调度算法分析

为了优化作业调度机制，提高作业调度的公平性和实时性，方法通过考虑计算时长估计和用户设定的计算时长因素，提出的一种计算资源动态分配方法，具体作业调度算法如下：

（1）计算各队列中各个作业预计运行时间;

其中，S为当前作业的计算量，S'为历史作业的计算量，T₀为历史作业的运行时间。

（2）进行作业调度;作业调度示意如图2所示。

步骤1，以用户为单位，对本用户的所有作业优先级进行排序;

步骤2.对于每个用户，以每个作业的预计完成时间长度为依据，判断是否立即处理;计算作业要求计算完毕时间一当前时间的值，并判断作业要求计算完毕时间一当前时间与作业的预计完成时间长度的关系;

步骤3，如果作业要求计算完毕时间一当前时间>作业的预计完成时间长度，则不作处理，按作业优先级顺序进行调度;

步骤4，如果作业要求计算完毕时间一当前时间≤作业的预计完成时间长度，立即进行作业调度，将该作业分配到本用户的预留计算资源进行调度;如果本用户的预留计算资源不够用，则申请系统独立的计算资源进行调度。

（3）以该作业的所有任务的关系为依据进行任务调度，如图3所示;

步骤1，在任务调度过程中，首先判断该作业的所有任务的类型和关系;

步骤2，如果任务间是串行关系，则将任务按FIFO顺序，分配该作业的全部资源进行计算;

步骤3，如果任务间是并行关系，则需要确定该并行关系的任务数M，然后将该作业的计算资源分成M份，每个任务对应其中1份计算资源，最后进行并行计算。

（4）计算资源使用完毕，释放计算资源。

当作业使用资源完毕，更新作业信息表中占用资源信息为空，即释放资源，并更新作业信息表中相关信息。

5 实验与分析

通过将该算法应用到超算平台作业调度系统中，验证该方法在不同业务类型作业调度中的运行情况，图4为应用了该算法的超算平台实际作业调度情况。

通过一段时间的应用验证，能够保障不同优先级的业务能够被及时调度，优化了作业调度的公平性问题，说明了该方法是实用可行的。

6 结束语

本文提出的一种作业调度和计算资源动态分配方法，将计算资源按用户需求进行划分，在每个用户划分的计算资源中预留计算资源，并在每个用户划分的计算资源外预留系统的计算资源：在作业调度时以用户为单位进行作业调度，充分考虑作业的优先级、预计运行时间长度等因素进行作业调度，充分了考虑任务的类型和关系等因素进行任务调度，能够避免优先级低的作业不能及时调度的问题，保障所有作业在规定的时间能够完成计算，提高了作业调度的公平性和时效性。该方法在超算平台业务调度系统中具有较强的可操作性和一定的实用价值。

参考文献

[1]Esmaeilzadeh H，Blem E，Amant R St，etal.Dark Silicon and the End ofMulticore Scaling[C].InternationalSymposium on Computer Architecture.IEEE，2012：122-134.

[2]Corujo A，Almeida B.Dynamic loadbalancing on heteroge-neousmulticore，multi GPU systems[C].International Conference on HighPerformance Computing&Simulation;（HPCS 2010），2010.

[3]张爱科，谢翠兰.基于公平性和负载均衡的云计算任务调度算法[J]，计算机应用与软件，2015，32（02）：268-271.

[4]余祖峰，蔡启先.基于工SM的动态优先级调度算法[J].计算机工程，2011，7（04）：8-9.

[5]张登银，许扬扬.基于时延的动态优先级调度算法[J].计算机技术与发展，2011，33（02）：7-9.

[6]韩建民，鹿玲杰，王传斌，贾莉抑.作业调度机制在计算机控制系统中的应用[J].计算机应用，1999（08）.

[7]丛龙水.动态优先级作业调度算法与实现[J].计算机工程与应用，2013，49（10）：267-270.

[8]涂刚，阳富民.基于动态优先級策略的最优软非周期任务调度算法[J].计算机研究与发展，2004，12（11）：23-24.