基于主机性能度量的异构集群作业调度算法

王超 陈刚 黄刚 王彪

摘要：传统经典作业度算法在集群应用中实现简单、执行效率高，但在异构集群环境下由于缺乏在线节点运行状态动态反馈能力和负载均衡能力，降低了计算资源利用率和系统吞吐率。为解决上述问题，设计了一种在异构集群环境下基于主机性能度量的作业负载均衡调度算法，该算法通过收集集群中在线节点的状态信息和作业响应时间遴选出可信节点集合，计算出各可信节点的HPM值，利用负载均衡运算规则生成候选的作业分配节点集合，最终按照预先设计的优先原则把不同作业分配至各计算节点，并更新各节点运行状态。实验结果表明，在异构集群环境下调度同类型作业时，该算法在总完成时间和负载均衡性能等指标上均优于传统经典算法。

关键词：异构集群;主机性能度量;负载均衡;作业调度

中图分类号：TP301文献标志码：A文章编号：1008-1739（2021）08-67-7

0引言

集群是多台相互独立的计算机，通过高速网络互联形成一个整体系统后，对外提供服务并对集群本身加以管理。集群运行过程的作业调度策略对集群资源利用率起着关键作用[1]，调度策略的优劣决定了集群中作业完成的效率。作业调度算法大致分为相互依赖和相互独立2种算法。前者算法缺陷明显，工程应用不多，后者算法因实现简单，大多数集群管理系统都在采用。目前在国内外广泛应用的相互独立的经典作业调度算法中，主要包括先来先到服务（First Come First Service，FCFS）、Min-Min算法和基于优先级调度（Priority）等[2]。

常见的算法还包括轮询调度算法、最小链接算法、遗传算法、模拟退火算法等，但是轮询调度算法和最小链接算法，没有考虑各服务节点的性能差异[13]，遗传算法和模拟退火算法适应于对复杂问题的优化，时效性较差[14]。在异构集群环境下，由于各节点计算机性能差异较大，上述算法的缺陷显得更为明显。为提升对异构集群资源的利用率，本文提出了主机性能度量（Host Performance Measurement，HPM）的概念，对集群各节点计算机的性能进行量化，并设计了一种基于主机性能度量的作业负载均衡调度（Host Performance Measurement Load Balancing，HPMLB）算法。该算法主要通过度量主机性能和判断作业响应时间容忍度实现动态的HPMLB，由集群的调度节点根据集群各节点的HPM信息，结合作业响应状态，依据负载均衡调度策略，将请求分配到集群中的各个计算节点，被派发作业的计算节点将接收请求并进行作业处理。该算法采用分层设计理念，使得作业调度层与计算执行层相分离，实现了对异构集群环境下具有相同功能不同实现的计算作业的调度。

1问题建模

在集群作业调度中，有一个节点作为调度节点，完成对所有作业的计算资源调度与分配，各计算节点完成业务计算。系统整体调度与管理流程如下：

①集群节点的网络代理软件接收作业请求命令;

②集群调度节点获取调度状态;

③集群调度节点的负载均衡调度器根据负载均衡调度算法进行调度计算和作业派发;

④受理作业计算节点进行具体的计算处理，同时根据作业执行情况更新本机状态;

⑤各集群节点通过集群状态同步机制动态实现各节点服务器状态同步。

针对上述流程，本文设计的HPMLB算法主要思想是：

①通过HPM、执行工作列表（Executive Job List，EJL）和作业响应时间容忍度来动态地描述集群各节点当前负载情况;

②由集群调度节点根据集群各节点的HPM和EJL等关键信息，结合作业响应状态，依据负载均衡调度策略，将请求分配到集群中各计算节点;

③各计算节点中的作业组织流程负责接受请求并组织作业执行器进行作业处理;

④各计算节点实时更新和对外发布本机的HPM和EJL等信息。

作业调度总体流程如图1所示。

整个作业调度由集群中的调度节点完成，当进行HPMLB时，调度节点首先收集集群中在线节点并筛选出可信节点。然后计算各可信节点的HPM值，根据负载均衡运算规则生成候选集合。最后，依据同等条件下的优先原则进行作业分派，分派完成后进行各节点状态更新。

为准确描述上述过程，给出集群节点性能、EJL和网络状态信息等概念的定义：

②EJL具体内容如表1所示。

③集群节点状态信息（The Cluster Node Status information，CNS）：各集群节点服务器维护本机的状态以及本机与其余節点的状态信息，如表2所示。

2算法设计

2.1生成可信节点

（1）收集在线节点

集群各节点都保存集群状态信息列表，包含本节点与集群其他所有节点当前的网络状态情况，并以固定周期△轮询检测更新整个集群的状态信息，其检测方式为集群中各节点以固定周期△循环接收集群节点的状态信息和第三方心跳;接收调度节点信号，确定调度节点的状态;完成节点状态信息的同步与更新;调度节点根据心跳检测和集群节点的状态信息，生成集群在线节点的集合A。

（2）筛选可信节点

在生成的集群在线节点集合A中，调度节点查询集合A中各个的IGHOST_INFO[].mainstatus值，若该值为1，则表示该对应的节点与调度节点通信正常，若为0，则表示与调度节点通信状态异常，将其中值为1的生成与调度节点通信正常的节点集合B;

然后筛选出满足作业响应时间容忍度的节点，生成可信节点集合C，根据式（3）进行本节点与集合B中节点的网络路径计算，获取本地的当前时间，然后获取本节点接收到的最近一次该发送的节点心跳时间，计算出该与调度节点的系统路径长度。

作业响应时间容忍度Dpt作为系统常数进行配置，通过式（5）进行作业响应状态运算。（）=1表示作业响应正常，（）=0表示作业响应超时，并将值为1的放在集合C中。

2.2作业调度

调度节点在生成的可信节点集合C中，计算HPM值，选取HPM值最小的节点集合生成候选集合D。在候选集合生成后，按如下原则进行作业分配：

①若系统满负荷，即HPM值为Mhpm，作业拒绝;

②若候选节点唯一，即集合D中的元素唯一，则作业直接派发给该;

③若候选節点不唯一，即集合D中的元素不唯一，则选取值最大的进行派发。

详细处理流程如图2所示。

①获取调度请求;

②获取节点计算机的状态信息;

③查询集群状态列表，获取其为在线状态的计算机节点集合A;

④在集合A中查询与调度节点网络状态正常的计算机节点集合B;

⑤在集合B中遴选出满足（）=1的集合C，其中作业响应的容忍时间Dpt一般设置为3△;

⑥在集合C中计算并选择HPM值最小的集合D;

⑦判断集合D的元素个数是否为1，若为1，则将该“+调度请求”作为调度请求结果对外发出，否则将集合中“最大值的+调度请求”作为调度请求结果对外发出;若集合D中各对应的计算机的HPM值>Mhpm（系统允许的最大负荷0<≤1）时，置为MAX_HOSTNUM+1;

⑧更新各节点当前的值。

2.3状态动态同步

HPMLB算法在进行作业调度时，为了及时获取集群各节点的动态负载情况以及对整个集群系统的集中管控，设计了集群状态动态同步机制，集群各节点实时收集更新本节点状态，并将本节点状态对外发出，同时接收其余节点状态信息，将接收到的其他节点状态信息更新到本机。其同步及发布内容有：维护本节点作业执行状态;维护本节点HPM值;对外发布工作列表数据;更新本节点保存的其余节点发布的状态信息;维护本节点与其余节点的网络状态，若本节点与某一节点的节点网络状态函数nets （）的值为0，则将本节点与该节点之间的网络状态设置为超时;对外发布本节点状态信息。

2.4整体算法描述

根据以上设计思路，本节给出了HPMLB算法的整体描述，其处理过程主要包括选取生成在线可信节点的集合，并计算节点的HPM值，选取最小HPM值的最大进行作业分派。

3算法分析

选取5台服务器构建集群，设定集群整体性能，即总计算能力固定。针对单一作业类型，不同作业数量集合，对HPMLB算法、FCFS算法和Min-Min算法从作业总完成时间和节点负载均衡情况进行分析。

3.1作业总完成时间

衡量作业调度器性能的标准之一，总的作业完成时间越小，说明该作业调度器作业处理速度越快，反之越慢。针对HPMLB算法、FCFS算法和Min-Min算法，设置4组规模不同的单一作业集合，选取5台服务器构建集群，在总计算能力固定的情况下，分为各节点服务器计算能力相同和计算能力2种不同情况对作业总完成时间进行统计。

（1）节点计算能力相同

现假定集群每个节点的计算能力为可并行执行30个作业，则整个集群总的计算能力为并行执行150个作业。其计算资源分配如表3所示。

设置每个作业耗时20 s，作业按均匀分布到达，选取4组不同规模的作业集合，分别为50，100，700，1 000，作业规模包括小于系统并行作业数量和大于系统并行作业数量的情况，统计整个作业集合的总完成时间，结果如图3所示。

从图3可以看出，当作业类型一致，在同构集群中FCFS，HPMLB总作业完成时间相当，优于Min-Min算法。Min-Min算法耗费时间多的原因在于其计时限量等待需要耗费一定时间，并在每个作业分配完毕后需遍历和更新作业的期望完成时间，因此随着作业量的增大，其耗费的时间越长。

（2）节点计算能力不同

在节点计算能力不同的情况下，构建异构集群，每台计算机性能是不一致的，即每个节点，，三个参数值配置不同，，1，2三个参数值配置相同，现模拟异构集群下计算资源分配如表4所示。

上述作业集作业的总完成时间如图4所示。

从图4可以看出，在各节点性能差异较大的异构集群中，当作业规模数小于系统并行作业数量时，HPMLB、FCFS和Min-Min三种算法的总完成时间相当，当作业规模数大于系统并行作业数量时，HPMLB作业总时间明显优于FCFS和Min-Min算法，而且随着作业规模的不断增加，差距越发明显。在HPMLB算法中，作业调度器能够实时获取各节点服务器的动态负载，能够较准确地把作业分配给能够立即执行的节点服务器，从而大大节省了作业的等待时间。

同时，对3种算法针对2种不同的服务器集群作业调度时间做了比较，发现HPMLB算法对不同的集群环境适应性最好，在2种集群环境下作业总完成时间相当。其次是Min-Min算法，在2种集群环境下作业总完成时间有所变化，但是变化幅度不大，FCFS算法适应性最差。结果如图5所示。

综上所述，3种算法都会随着作业数量的增加，总时间呈上升趋势。HPMLB算法對不同集群环境适应性最好，Min-Min算法性能次之，FCFS算法性能最差。

当作业规模小于集群可并行运行的最大作业数时，3种算法作业总完成时间相当，当作业规模大于集群可并行运行的最大作业个数时，HPMLB算法的总完成时间明显小于Min-Min算法和FCFS算法的总完成时间。

3.2节点负载均衡情况

负载均衡是指作业调度到各节点计算机上时，确保大多数节点计算机有作业运行，即充分利用集群计算资源。由于FCFS算法只是静态地把先来先到的作业按节点顺序依次分配给各节点计算机，因此这里不分析该算法的负载均衡性，只对HPMLB算法和Min-Min算法的节点负载均衡情况进行分析比较。

依据表4的计算资源构建异构集群，针对单一类型作业，在集群每个节点的计算能力和集群总体计算能力固定的情况下，当整个集群系统未达到满载时，设置不同规模的单一作业集合，考虑2种作业调度算法下系统的负载均衡情况。

为减少负载均衡情况的计算量，假定所有作业的执行时间满足整个作业集被分配完毕后，没有作业运行结束。此时，集群每个节点的负载情况均可用当前执行的作业数与当前节点能承担的最大作业数之比来衡量，即用HPM值来进行衡量。

从图6和图7可以看出，Min-Min算法优先将作业分配给性能好的服务器，导致整个集群各节点负载不均衡，出现了SOCAS05节点已经满负荷运行，而SOCAS01仍处在空闲无作业执行的状态。而HPMLB算法在不同规模的作业集合下，整个集群各节点的负载情况相对均衡，未出现空置服务器情况。通过在同一作业规模下，利用2种算法调度集群各节点负载情况的方差统计情况，比较2种调度算法的负载均衡性能。方差值越小，均衡性越好，结果如图8所示。

从图8可以看出，HPMLB算法的负载均衡性在不同作业规模下，其负载均衡性均优于Min-Min算法。

当作业数大于系统的总负载作业数时，Min-Min算法会导致集群中某些节点超载，某些节点空闲的情况，而HPMLB算法由于在实时收集各服务器动态的负载情况，当节点服务器作业运行结束后，该节点最新负载情况会被调度器动态感知。因此，当作业规模过大时，在负载均衡性方面，HPMLB算法优于Min-Min算法。

综上所述，HPMLB算法在异构集群下，针对同一作业类型，从作业总完成时间以及节点的负载均衡性方面均优于FCFS和Min-Min算法。

4结束语

本文根据异构集群特点，提出了一种基于HPM的HPMLB算法。实验结果表明，HPMLB算法在异构集群环境下，对同类型作业的调度性能在总完成时间和负载均衡性上均优于FCFS和Min-Min算法。该算法在准实时性应用设计中具有一定的通用性，已用于航天测控中心轨道计算分析平台系统，为航天器在轨安全管理和稳定运行提供了有效保障。

参考文献

[1] KHAN K H， QURESHI K， ABD-EL-BARR M. An Efficient Grid Scheduling Strategy for Data Parallel Applications[J].J Supercomput，2014，68（3）：1487-1502.

[2]宋俊辉，冯岩.负载均衡的分布式系统任务调度优化算法[J].吉林大学学报（理学版），2017，55（2）：383-387.

[3] LATIP R， IDRIS Z. Highest Response Ratio Next （HRRN） vs First Come First Served （FCFS） Scheduling Algorithm in Grid Environment[J].Software Engineering and Computer Systems， 2011，11（1）：689-691.

[4]杜玉霞，刘方爱，郭磊.Min-Min调度算法的研究与改进[J].计算机工程与应用，2010，46（24）：107-109.

[5]王文豪，严云洋.周静波.基于负载均衡的Min-Min作业调度算法优化[J].南京理工大学学报，2015，39（4）：398-404.

[6]姜凯华，韩锐，孙鹏，等.基于Min-Min算法的智能终端服务迁移技术研究[J].网络新媒体技术，2020，9（4）：37-40.

[7] HUANKAI C，WANG F，HELIAN N.User-priority Guided Min-Min Scheduling Algorithm for Load Balancing in Cloud Computing[C]//In： Proceedings of the 2013 National Conference on Parallel Computing Technologies（ PARCOMPTECH）.Bangalore：IEEE，2013：1-8.

[8]王钊，刘钊远.一种改进的流媒体集群动态负载均衡调度算法[J].计算机与数字工程，2018，46（2）：241-246.

[9]劉斌.基于云计算中的任务调度算法研究[D].长春：长春理工大学，2019.

[10] MAHESWARAN M， SIEGEL HJ.A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems[C]//Proceedings Seventh Heterogeneous Computing Workshop（HCW98）. Orlando： IEEE，1998： 59-69.

[11] AMIN S，MOHAMED O，HAMIDAH I，et al. New Method for Scheduling Heterogeneous Multi-installment Systems[J]. Future Generation Computer Systems，2012，28（8）：1205-1216.

[12]王晓萍，孟坤.异构分布式系统的可分任务作业调度算法[J].小型微型计算机系统，2015，36（4）：797-800.

[13]张腊，刘淑芬，韩璐.基于负载均衡的作业调度算法[J].吉林大学学报（理学版），2014，52（4）：769-773.

[14]朱晓敏，陆佩忠.异构集群系统中安全关键实时应用调度研究[J].计算机学报，2010，33（12）：2364-2377.