异构系统中带可用性约束的性能优化调度算法

孙健,张兴军,董小社

(西安交通大学电子与信息工程学院,710049,西安)

可用性是衡量复杂计算机系统的关键指标之一,特别是近年来异构系统的日益发展,伴随系统规模以及实时应用范围的逐步扩大,研究异构系统中多实时任务的可用性需求问题具有非常重要的理论与实际意义。该研究领域内涌现出诸多以满足实时任务的具体可用性需求,并通过带可用性约束的调度策略来实现系统内实时任务合理调度分配的实时任务调度算法[1-2]。

早期实时任务调度理论中对任务调度算法的最基本假设是系统内所有用于任务分配执行的处理机节点均可用[3]。该假设仅在理想状态的多处理机系统实时任务调度中是合理的,但在复杂计算机系统特别是异构系统中,由于系统故障宕机、失效修复等情况时有发生常导致系统不可用,此时该假设便不再适用。另外,异构系统内各处理机节点的实时任务执行时间即任务响应时间也各不相同,为选取系统内任务分配的处理机节点增添了难度。为此,在设计实时任务调度算法时应充分考虑各实时任务的具体可用性需求即可用性约束,并在此基础上权衡系统调度分配过程中的任务响应时间,保证在任务可调度性以及可用性的前提下实现异构系统中实时任务的合理调度。

针对上述问题,本文提出一种异构系统中带可用性约束的性能优化调度算法,构建系统内处理机节点、实时任务以及带可用性约束的实时任务调度模型,通过引入可用性成本和系统综合开销,考虑可用性成本与任务平均响应时间的折中,为实时任务分配系统综合开销最少的处理机节点,合理利用异构系统调度资源,在提升实时任务调度可用性的同时进一步优化异构系统的调度性能。

1 相关工作

目前,异构系统中可用性相关的实时任务调度算法大致可分为两类:一类是可用性受限的实时任务调度算法,即在满足实时任务可用性约束的前提下,对以往仅考虑任务执行时间的调度算法进行优化改进,典型算法如QoS-SAC[4]、SSAC[5]等;另一类是实时任务本身无可用性约束,而在算法设计中考虑可用性因素调度策略,旨在提升系统整体以及实时任务分配执行的可用性水平和性能,如HMSAS[6]、ADSS[7]等。

多处理机异构环境下的实时任务最优分配一直是一个难以解决的NP完全问题[8]。考虑可用性受限的实时任务调度算法,Xie等首次提出了异构系统中带可用性约束的多任务组调度策略(SSAC)[9],该策略的核心思想是结合任务平均响应时间和可用性约束对实时任务进行数学建模,根据任务的具体可用性约束,为其选择系统内满足该约束的候选处理机集合,并将任务分配至集合中任务平均响应时间最短的处理机处理执行,在提升调度性能的同时提高系统可用性。此外,Tong等考虑系统QoS以及可用性需求,在文献[5,9]的基础上,针对异构分布式系统设计可用性受限的实时任务调度算法(QoS-SAC)[4],以缩短实时任务的完成时间同时提高系统可用性。

本文提出的异构系统中带可用性约束的性能优化调度算法(PO-SSAC),在实时任务调度执行时考虑任务平均响应时间与可用性成本的折中,并为其分配系统综合开销最少的处理机节点,与SSAC以及其他现有算法相比,进一步提升了异构系统的实时任务调度可用性以及性能,实现了系统资源的合理利用。

2 实时任务调度模型

2.1 带可用性约束的实时任务调度框架结构

本文所需解决的具体问题是如何在可用性受限的情况下对异构系统中实时任务进行合理调度分配,并在提升系统任务调度可用性的基础上进一步优化调度性能。根据上述问题描述,异构系统中带可用性约束的实时任务调度框架结构如图1所示。

图1 带可用性约束的实时任务调度框架结构

调度器是实时任务调度框架结构的核心,负责调度分配来自各不同用户的任务组队列,并实时监测异构系统内所有处理机节点的运行状态,及时获取各处理机节点的运行状态信息。调度队列负责接收来自各用户的任务组,调度器按照先来先服务原则接收所有到达的实时任务,分配其至各处理机节点,并由处理机节点内本地队列实现对各实时任务的并行处理。

对于每个来自用户的实时任务,处理机定位器为其筛选一个候选处理机集合,集合包含所有满足该任务可用性需求即可用性约束的处理机节点。若集合非空,调度器从集合内选择系统综合开销最少的处理机节点,并分配任务至该处理机节点处理执行;若集合为空,说明没有候选处理机节点满足当前任务的可用性约束,此时可用性成本计算器计算系统内能够满足该任务可用性约束的处理机节点,并将其添加至候选处理机集合。负载均衡检测器检测候选处理机节点是否超载,超载时实时任务将被分配至负载最轻的处理机节点,否则分配至该处理机节点处理执行。

2.2 处理机和实时任务模型

对异构系统内处理机和实时任务进行如下的形式化数学描述。①处理机模型。异构系统指由一定数量内部构造不同且相互独立的自治节点,通过高速互联网络相互连接所共同组成的高性能、高可用计算机系统,能够作为一个整体为用户提供所需的应用服务。设异构系统处理机集合H={N1,N2,…,Nj,…,Nn,j=1～n},n为处理机节点数。H中各处理机节点处理能力由每秒百万条指令(MIPS)来衡量,同时由于是异构系统,假设各处理机节点处理能力和可用性均不相同。②实时任务模型。设实时任务集合TG={t1,t2,…,ti,…,tm,i=1～m},m为来自用户的实时任务数。系统根据用户的可用性需求为实时任务设定可用性约束,范围为0～1,实时任务必须分配至能够满足其可用性约束的处理机节点以确保得到成功处理。

定义实时任务ti在处理机节点Nj上执行的平均响应时间

φj))

(1)

式中:sj为实时任务集合TG在处理机节点Nj上的服务时间;sj2为sj的二阶矩;E(sj)为服务时间均值;E(sj2)为服务时间均方。处理机节点Nj的任务到达率为Λj,服务率为φj,假设异构系统内任务到达模式和服务率是先验的,则Λj与φj均可通过代码剖析和统计预测方法估算得出。

2.3 带可用性约束的实时任务调度模型

本文异构系统中可用性均为稳态可用性,是指在某个时间段内系统维持正常运行状态的概率。定义异构系统内处理机节点Nj的可用性为ξj,表示任意时间段内处理机节点Nj可提供持续运算处理的概率,相应的异构系统内处理机节点Nj的不可用性为θj。定义实时任务ti的可用性约束为ai,代表任务ti必须执行成功的概率,例如,当ai=0.85时,任务ti执行失败的概率不得高于0.15。

进一步定义aij为实时任务ti在处理机节点Nj上的可用性成本

aij=pijθj/μij

(2)

式中:pij为实时任务ti分配至处理机节点Nj的概率;μij为实时任务ti分配至处理机节点Nj的服务率。

本文引入综合性能开销的概念,定义Cij为实时任务ti在处理机节点Nj上的系统综合开销,结合式(1)和式(2),得到Cij的计算公式为

(3)

结合2.2小节对处理机和实时任务模型的相关分析,将带可用性约束的性能优化调度问题抽象为异构系统可用性与实时任务平均响应时间两者之间的折中,则本文调度算法的设计目标可描述为:提高实时任务调度分配的可用性;合理利用资源减少系统综合开销,即保证较短的实时任务平均响应时间和较低的处理执行可用性成本,得到如下数学模型

(4)

系统综合开销约束条件为

∀1≤i≤m,1≤j≤n,ai≤ξj:minCij

在该数学模型中,A为异构系统实时任务调度的系统可用性;λi为实时任务ti的到达率且符合泊松过程;λ为实时任务集合TG在异构系统中的总平均到达率。

3 带可用性约束的性能优化调度算法

实时任务平均响应时间在很大程度上依赖于异构系统中各处理机节点所采用的具体排序策略,因此本文所提PO-SSAC算法采用文献[10]中给出的最优排序策略以最大程度减少异构系统中实时任务集合的平均响应时间,并作如下命题。

命题1 已知m组实时任务队列和由n个处理机节点构成的异构系统,根据最优排序策略,在处理机节点Nj上,当μij≥μkj时,实时任务ti的优先级高于tk。

上述命题说明高服务率的实时任务在调度分配时必须拥有相对较高的优先级,以达到缩短任务平均响应时间的目的。为简化描述进一步作如下假设。

假设1 假设异构系统内实时任务集合TG按照服务率从高到低排序,即

ρ1≥ρ2≥…≥ρi…≥ρm

式中:ρi为实时任务ti分配至H的总服务率。根据该假设,调度策略可以在执行最初对所有实时任务按照服务率从高到低顺序进行重新排列,以方便之后的调度分配。

在PO-SSAC算法中,执行程序首先按照命题1和假设1为高服务率的实时任务分配高优先级并按照优先级进行排序,之后进入对实时任务集合的循环处理。循环处理是PO-SSAC算法的核心部分,首先判断候选处理机子集是否为空,若子集非空,说明子集内至少包含1个处理机节点能够满足实时任务ti的可用性约束,进而循环计算候选处理机子集中各候选处理机节点的系统综合开销Cij,选取子集中系统综合开销最少的处理机节点,并将该处理机节点选为任务调度的执行节点。

讨论调度的特殊情况,若候选处理机子集为空,说明此时异构系统中所有处理机节点均无法满足实时任务ti的可用性约束。在该情况下PO-SSAC算法将采取相应的措施尽可能对ti的调度执行可用性进行提升。循环计算ti在异构系统内处理机节点的可用性成本aij,并为ti分配系统内可用性成本最低的处理机节点。另外,如果系统内存在2个或2个以上可用性成本取值相同且最低的处理机节点,则ti将分配至其中平均响应时间相对较短的处理机节点上。

当某候选处理机节点Ns选定以后,PO-SSAC主函数将调用loadBalance()函数进行负载均衡检测并最终分配实时任务ti至相应的处理机节点处理执行。loadBalance()函数首先估算H内所有处理机节点的负载指标并找到其中负载最轻的处理机节点Nnmin,令该节点负载指标为Lmin。对于所选取的处理机节点Ns,如果Ns没有超载,系统将分配ti至该节点处理执行;如果Ns超载,系统将分配ti至H内负载最轻的处理机节点Nnmin处理执行,负载阈值为LT。

对于PO-SSAC主函数,TG按照服务率从高到低排序的时间复杂度为O(mlbm),处理机节点选取的时间复杂度为O(n),则对于实时任务集合TG,PO-SSAC主函数在最差执行情况下的时间复杂度为O(mn)。进一步分析loadBalance()函数,循环计算异构系统内所有处理机节点负载指标的时间复杂度为O(n),假设单次任务调度分配中,PO-SSAC主函数和loadBalance()函数中其他步骤执行时间复杂度为O(1),则对于实时任务集合TG,PO-SSAC算法任务分配的时间复杂度为O(m(n+1))。综合上述分析,PO-SSAC算法在最差执行情况下的整体时间复杂度为O(mlbm)+O(mn)+O(m(n+1))≈O(2mn)。

图2给出了PO-SSAC调度策略的一个抽象实例,假设异构系统由8个处理机节点(N1～N8)组成,其中各处理机节点可用性取值范围为0.68～0.97,任务平均响应时间取值范围为42～204 s,可用性成本取值范围为0.031～0.297。假设实时任务可用性约束为0.80,则符合该可用性约束的候选处理机集合为N3、N4、N6、N7和N8,各候选处理机的系统综合开销取值范围为2.94～21.42。按照PO-SSAC调度策略,调度器将最终分配实时任务至系统综合开销最少的处理机节点N3处理执行。

图2 PO-SSAC调度策略实例

4 实验分析

本文面向异构系统设计了带可用性约束的性能优化调度算法PO-SSAC,并通过随机实时任务集在异构系统内的调度分配对现有实时任务调度算法SSAC、MinMin、Sufferage以及PO-SSAC进行对比仿真实验。异构系统选用GridSim仿真工具进行构建,代码用Java通过eclipse编译实现,仿真环境为Red Hat Enterprise Linux 7.0操作系统,CPU为Inter Core i7-6700k@4.00 GHz四核,内存为16 GB,硬盘为希捷ST3000DM001-1ER166(3 TB)。

4.1 实验用例

实验主要从任务总平均到达率和处理机节点数的变化情况对异构系统内PO-SSAC算法以及对比算法的调度执行情况进行分析。实验运行200次并记录实验结果,去掉其中5次最大和最小结果,取剩余结果均值作为最终实验结果。实验参数和取值情况见表1,参数或者参照文献[5,9]中实验部分的参数取值,或者取自异构系统的实际评测经验值。

异构系统处理机节点数为n,实时任务集合TG通过GridSim仿真工具随机生成,任务平均响应时间Tij为1～500 s内随机整数。根据对实时任务调度模型的分析可知,任务总平均到达率λ服从泊松分布,任务平均响应时间Tij、处理机节点可用性ξj以及任务可用性约束ai均服从均匀分布,负载阈值LT取固定经验值。

实验选取与PO-SSAC算法相近似的另外3个调度算法进行对比,包括SSAC、MinMin[11]以及Sufferage算法[12],上述算法均适用于异构系统中的实时任务调度分配,同时也适用于分布式或同构系统的任务调度情况。

实验主要评价指标包括异构系统实时任务调度系统可用性、系统总平均响应时间以及系统综合开销。

4.2 实验结果分析

首先分析任务总平均到达率λ变化情况下异构系统实时任务调度的各评价指标。λ取值范围为0.2～1.0,增量为0.2,处理机节点数n=16。实时任务调度分配实验结果如图3所示。

(a)系统可用性

(b)系统平均响应时间

(c)系统综合性能开销图3 任务总平均到达率不同时系统的各项性能实验结果

由图3a可以看出,采用可用性约束调度策略的PO-SSAC与SSAC可用性提升明显,与MinMin算法相比,可用性提升约76.9%,与Sufferage算法相比,可用性提升约76.5%,同时PO-SSAC更优于SSAC,可用性提升约3.4%,原因在于PO-SSAC在实时任务处理机节点选取时考虑了实时任务可用性成本与平均响应时间的折中,为其分配系统综合开销最少的处理机节点调度执行,该策略使实时任务调度分配的可用性能够得到进一步的提升。图3b、图3c中实验结果表明,PO-SSAC在获取较高系统可用性的同时增加了异构系统内实时任务的调度执行时间,有效降低了系统综合开销,与系统综合开销最多的Sufferage算法相比,减少近30%,优化了异构系统的性能。

进一步分析处理机节点数n变化时异构系统实时任务调度的各评价指标。n取值为16、32、64、128时,任务总平均到达率λ=1。实时任务调度分配实验结果如图4所示。

(a)系统可用性

(b)系统平均响应时间

(c)系统综合开销图4 处理机节点数不同时系统的各项性能实验结果

与任务到达率变化实验结果类似,与其他3个算法相比,PO-SSAC系统可用性有所提升,但由于考虑可用性约束,增加了异构系统的实时任务调度执行时间。由图4c中实验结果可以看出,与其他3个算法相比,PO-SSAC系统综合开销最少。另外,本实验结果也说明当异构系统规模扩大,即处理机节点数增多时,系统综合开销会减少,实时任务调度可用性和系统性能将得到提升。

5 结 论

本文提出了一种异构系统中带可用性约束的性能优化调度算法,该算法对异构系统内处理机节点、实时任务以及带可用性约束的实时任务调度进行数学建模,引入系统综合开销概念并考虑可用性成本与任务平均响应时间的折中,将实时任务分配给系统综合开销最少的处理机节点,以达到系统调度资源合理利用的目的。实验结果表明,与现有算法相比,PO-SSAC算法提升了异构系统实时任务调度的系统可用性,系统调度性能也得到了进一步优化。

[1] FAN J, LU X W, LIU P H. Integrated scheduling of production and delivery on a single machine with availability constraint [J]. Theoretical Computer Science, 2015, 562: 581-589.

[2] BELMABROUK M, MARRAKCHI M. Optimal parallel scheduling for resolution a triangular system with availability constraints [C]∥Proceedings of the International Conference on Computer Systems and Applications. Piscataway, NJ, USA: IEEE, 2015: 1-7.

[3] SALFNER F, WOLTER K. A Petri net model for service availability in redundant computing systems [C]∥Proceedings of the 2009 Winter Simulation Conference. Piscataway, NJ, USA: IEEE, 2009: 819-826.

[4] TONG Z, LI K L, XIAO Z, et al. A Qos scheduling scheme with availability constraint in distributed systems [C]∥Proceedings of the 13th International Conference on Parallel and Distributed Computing, Applications and Technologies. Piscataway, NJ, USA: IEEE, 2012: 481-486.

[5] QIN X, XIE T. An availability-aware task scheduling for heterogeneous systems [J]. IEEE Transactions on Computers, 2008, 57(2): 188-199.

[6] KHOUDI A, BERRICHI A, YALAOUI F. Heuristics to maximize system availability on parallel machine scheduling problem [C]∥Proceedings of the International Symposium on Programming and Systems. Piscataway, NJ, USA: IEEE, 2015: 1-6.

[7] ZHU M, GUO W, XIAO S L, et al. Availability-driven scheduling for real-time directed acyclic graph applications in optical grids [J]. Journal of Optical Communications and Networking, 2010, 2(7): 469-480.

[8] 李智勇, 陈少淼, 杨波, 等. 异构云环境多目标Memetic优化任务调度方法 [J]. 计算机学报, 2016, 39(2): 377-390. LI Zhiyong, CHEN Shaomiao, YANG Bo, et al. Multi-object memetic algorithm for task scheduling on heterogeneous cloud [J]. Chinese Journal of Computers, 2016, 39(2): 377-390.

[9] XIE T, QIN X. Stochastic scheduling with availability constraints in heterogeneous clusters [C]∥Proceedings of the International Conference on Cluster Computing. Piscataway, NJ, USA: IEEE, 2006: 1-10.

[10]SETHURAMAN J, SQUILLANTE M S. Optimal stochastic scheduling in multiclass parallel queues [J]. ACM Sigmetrics Performance Evaluation Review, 1999, 27(1): 93-102.

[11]TAN M, SIEGEL H J, ANTONIO J K, et al. Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system [J]. IEEE Transactions on Parallel and Distributed Systems, 1997, 8(8): 857-871.

[12]SONG S S, HWANG K, KWOK Y K. Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling [J]. IEEE Transactions on Computers, 2006, 55(6): 703-719.