实时多核系统面向负载均衡的任务分区调度算法

方 兴

(武汉藏龙北路1号 武汉 430205)

实时多核系统面向负载均衡的任务分区调度算法

方 兴

(武汉藏龙北路1号 武汉 430205)

实时应用对系统性能存在迫切需求,基于多核和众核架构的并行处理成为提升性能的主要途径。为了充分发挥多核处理器的性能,必需尽可能提高实时应用的并行度。只有如此,才能同时高效利用处理器的每个核心。为了保证实时性能,同时高效利用多核资源,需要一种同时考虑可调度性和负载均衡的任务调度方法。当前已有的针对多核系统的实时任务调度方法,仅考虑调度性或负载均衡,而未能对两者进行全面考虑。文中提出了一种实时多核系统面向负载均衡的任务分区调度算法,不仅可以保证实时任务性能,而且能够针对多核系统对任务进行高效分配。实验结果表明,文中提出的方法在负载均衡效果和可调度性方面优于对比算法。此外,所提出算法的另外一个优点在于通过负载均衡降低了系统能耗。

多核; 实时; 负载均衡; 利用率; 可调度性

Class Number TP391

1 引言

实时处理在工业自动化、医疗设备、电子产品等应用领域发挥重要的作用[1]。计算技术在这些领域的应用需要具有实时性。随着微处理器架构越来越多核化,处理器中实时任务的高效执行成为密集计算应用的重要保障。为了充分利用多核资源,实时应用必需具备一定的并行度,保证任务能同时分配到多个核心,这也是多核处理器相对于传统单核处理器能够提供更有效实时性能的主要途径。

针对多核处理器中的实时应用,合理的任务调度算法需具备以下特征: 1) 高可调度性,即任务可以在满足截止时间的前提下被调度; 2) 各个核心中的任务分配均保持负载均衡,资源利用不会引起过度配置和潜能浪费。

已有的多处理器实时任务调度方法可以分为分区调度和全局调度[2]。文献[3]的研究表明,分区调度比全局调度具有更好的硬实时调度性。因此,本文采取分区调度方法,通过任务分区机制分配任务,单处理机调度器调度分配到每个处理器的任务,从而获得高可调度性和良好的负载均衡。

目前分区任务调度方法相关的研究主要考虑可调度性[4～6],由于对任务分配中的并行度或负载均衡关注较少,常常会导致性能降低以及资源利用率不足。当前的大部分实时调度算法主要考虑可调度性,已有部分算法开始考虑降低能耗,低能耗特性在移动和嵌入式设备中显得尤为重要。文献[7]提出在动态电压调节方式下,基于任务划分的负载均衡方法可以降低能耗。但是,已有的负载均衡算法在实时任务的可调度性方面表现不佳。

随着多核处理器的普及,保证多核心之间的负载均衡也愈发重要。负载均衡旨在均匀分配任务负载,保证每个核心承担近似相同的工作量。通过均衡分配每个核心的任务量,资源得以有效利用,不会引起过度配置或浪费。此外,结合负载均衡技术和动态电压[8]调节方式可以有效降低能耗。同时负载均衡还具备以下优势:优化吞吐量,并提高可靠性。

基于分区调度方法,本文提出了一种实时多核系统面向负载均衡的任务分区调度算法(Real-Time Task Partitioning Scheduling for Multicore Systems with Load Balancing,RTTP),不仅可以实现负载均衡,还可以获得高可调度性。所提出的算法主要面向彼此独立、互不影响的任务,首先通过任务划分机制获得高可调度性,然后在不影响调度性的前提下实现负载均衡。

任务重新划分过程中,任务重新划分机制无需检测是否满足可调度标准,只需满足负载均衡标准,从而获得一个满足截止时间限定条件的解决方案。重新划分操作在无法进一步提高负载均衡时停止,这一特性可以降低划分算法执行开销。RTTP算法虽然从负载均衡的角度无法实现最有效的任务映射,但是在保证一定负载均衡的基础上,实现了可调度性,通过动态电压调节机制降低了能耗。实验结果表明与考虑调度性的FFDU(First-Fit Decreasing Utilization)算法相比,RTTP算法与其调度性效果相近;与考虑负载均衡的WWDU(Worst-Fit Decreasing Utilization)算法相比,RTTP算法与其负载均衡效果类似。

2 算法设计

2.1 算法框架

通过降低处理器速度可以降低供电电压,从而减少执行任务时的能耗。因此,为了降低每个任务的能耗,给每个核心上的任务分配一个最优速度。核心ci上所有任务的最优速度Si是一个常量,表示为Si=Ui,其中Ui表示ci的利用率。

2.2 负载均衡

不均衡程度越大,负载均衡算法的效果越差。文献[4]中Aydin和Yang给出了利用核心的利用率和任务来表征任务分配的不均衡程度形式化描述。

定义1 当两个核心ci和cj,如果其利用率满足条件:Ui-Uj>uk,此处tk∈∏i,则上述两个核心之间存在负载不平衡。

3 分区实时任务调度

云平台在同一时刻会收到有多个用户的服务请求,因此高效的资源分配和任务调度是云计算的一个重要方面。许多学者提出了多种分配、调度和衡量云资源的方法。云的调度过程可以归纳为以下三个过程:通过将多核处理器调度问题分解为多个单核处理器问题,可以获得当前系统的分区任务调度方法。该方法因不依赖集中化数据结构,不会造成冲突和高速缓存一致性,从而获得较好的可调度性,并且开销较低。鉴于可扩展性和可调度性开销在应用领域至关重要,本文采取分区实时任务调度方法。图1表示分区方法的框架结构,包含以下操作:

步骤1:将任务分配到各个核心,保证任务可以在截止时间内完成。任务可以按照利用率、截止时间等进行分类。图1中的分区模块执行此操作。

步骤2:核心分配完成后,在每个核心的时间期限内,运用单核心调度算法(如EDF,RMS)调度分配的任务。图1中的调度模块执行此操作。

步骤1早于系统执行时间,步骤2在步骤1完成后,与系统执行时间同步。步骤1中,任务划分用于将任务分配到符合可调度标准的合适核心,其本质而言是装箱问题的一种衍生,可以用首次适应算法[9]、最佳匹配法[10]、下次匹配法[11]、最坏匹配法[12]等启发式方法来解决。首次适应算法经证实可以保证高可调度性和低开销,但其任务分配过程会导致多个核心之间的负载难以均衡。

同时,相对于首次适应算法,最坏匹配法可以保证较好的负载均衡,但可调度性不高。针对多核系统的高效实时算法不仅需要保证实时性能,即可调度性,也需要高效的资源利用率,即负载均衡。为解决上述问题,本文提出了一个实时任务划分策略,不仅可以保证高可调度性,而且可以实现多个或多核系统的负载均衡。

4 基于负载均衡的任务划分

如图1所示,部署在划分模块的任务划分机制对可调度性和负载均衡均有重大影响。为了同时保证可调度性和负载均衡,本文提出了一个实时多核系统面向负载均衡的任务分区调度算法,RTTP。RTTP算法执行以下操作:

1) 任务排序:根据利用率从高到底对任务进行排序。

2) 任务划分:在符合截止时间限制条件的基础上,将排序后的每个任务分配到符合要求的第一个核心上。

3) 任务重新划分:若任务划分后还可以调度,则进行重新划分。排序后的任务按照逆序,即利用率从低到高,重新分配到对应的各个核心。重新划分过程遵守负载均衡标准,而无需重新检测是否符合可调度性标准。重新划分操作得到的解决方案符合定理1。负载均衡无法进一步提高时,重新划分操作结束。

FFDU算法可以保证高可调度性,首先采用该算法执行任务划分,因为任务在截止时间内及时完成是实时系统任务调度的必要条件。任务划分过程中,检查每个可用核心上的任务是否符合可调度标准。任务划分到符合可调度标准的第一个核心。本文引入EDF,作为RTTP算法中每个核心的本地调度器。对于EDF调度算法,核心ci上任务可调度的必要条件为Ui≤1,Ui为核心ci的利用率。若FFDU无法为给定的任务集生成合理的调度方案,则输出一个值,表明任务划分失败。只有FFDU能生成调度方案时才会执行任务重新划分。

然后,利用FFDU调度算法重新划分任务,提高负载均衡。重新划分机制遵循最坏匹配法,但有别于先前的划分操作,任务按照利用率从低到高排序后进行重新划分,从而在无需检测是否满足可调度性的前提下,获得任务重新划分的调度方案,尽管此调度方案与FFDU生成的调度方案可能不一致。此外,鉴于该调度方案操作过程中不会降低负载均衡效果,从而可以有效降低开销。对任务按照利用率从低到高排序后进行重新划分操作后,操作就已完成,因为任务之前已按照利用率从高到低的顺序划分过。FFDU算法与WF算法相结合,可以提高任务利用率,称之为Worst-Fit Increasing Utilization(WFIU)。与WFDU算法相比,WFIU算法可调度性和负载均衡程度不高。但是,在FFDU算法操作之后,通过WFIU重新划分,可以保证高可调度性和较好的负载均衡,降低调度开销。当无法进一步提高负载均衡时,任务重划分操作停止。

定义2 若对当前的任务进行重划分后,利用率的差值大于或等于当前分配方案的(Umax-Umin),则对任务不进行重新分区。

论证:对任务进行重新划分前,首先根据当前的任务分配方案分别求得核心利用率的最大值Umax和最小值Umin。当前任务分配方案可能与FFDU分配结果不同,因为在任务重新划分过程会导致任务分配结果发生变化。基于定义1,对于需要重新划分的任务,其最大利用率小于核心最大值和最小值的差值,若大于此差值,则无需重新划分。鉴于任务是按照利用率由低到高的顺序依次考虑是否需要重新划分,当满足上述条件时重新划分机制停止,无需对剩余任务进行操作

RTTP算法在FFDU可以生成合理的解决方案的前提下,会得到合理的任务分配方案,在重新划分过程中无需进行可调度性测试。因而,RTTP算法与FFDU算法的可调度性类似。

定理1 如果FFDU可以生成合理的解决方案,则RTTP也可以生成合理的解决方案。

证明:对于通过FFDU算法实现的分配,若每个核心ci(ci∈C)的利用率均不高于1,就可以满足该核心上所有任务的截止时间限定条件。对于核心ci,任务tk当前分配于该核心上,核心ci的利用率小于等于1,因为截止时间必须得到满足:

Ui≤1,tk∈∏i

(1)

任务将重新划分到利用率值最低的目标核心,该核心利用率低于1,已分配的任务满足截止时间要求因为重新划分的核心利用率不能达到1。

Uj<1,st.minck∈CUk

(2)

假设任务tk的利用率小于当前分配核心的利用率与核心最低利用率的差值,则根据定义1,当前分配是不均衡的。

Uk

(3)

基于此,RTTP算法将任务tk从核心ci移出,并重新将任务tk分配到利用率最低的核心cj。根据式(1)、(3)和(4),随着任务tk的迁入,核心cj的利用率升高,但仍低于1。

Uj=Uj+uk

(4)

Uj<1

(5)

随着任务tk的迁出,核心ci的利用率低于1。uk>0且核心ci重新划分后的利用率不会为1,即Ui≠1,同时:

Ui=Ui-uk<1

(6)

根据式(5)和式(6),核心的利用率小于1,表明重新划分后的分配结果满足截止时间条件。根据定义2,重新划分机制终止:若下一个任务满足以下条件,则不再进行重新划分:uk≥(Umax-Umin)。此条件与式(3)相反。在重新划分过程中,式(1)～式(6)中定义的关系均得到满足。因此,若FFDU分配满足所有截止时间限定条件,则RTTP分配也满足截止时间限定条件。

5 实验

为了验证RTTP算法的有效性,本文对RTTP、FFDU和WFDU算法进行了分析比较。FFDU算法可以提供较好的可调度性,而WFDU算法可以提供较好的负载均衡。可调度性可以通过能够被调度且满足截止时间的任务在任务集中所占的比率进行衡量,而负载均衡可以通过被调度的任务集所在核心的利用率的归一化标准差进行衡量。

实验中,根据任务集的总利用率Utot和任务利用率因子α(α≤1)随机生成各个任务集,其中α表示任务集中所有任务的最大利用率。任务利用率ui均匀分布在[0,1]区间内,并且任务利用率的总和不高于任务集总体利用率。

连续生成任务,直到任务的总利用率达到给定的任务集总利用率,从而获得任务集。任务集的总利用率数值在1(轻负载)到核心数m(重负载)之间。图中所示利用率(x轴)表示为Utot/m的百分比。核心的数量在8～1000之间。鉴于核心数量对结果没有显著影响,实验采用48个核心。每个数据采样点均生成1000个任务集。本文根据文献[1]中的功耗模型和方法,采用DVS对功耗进行测量。

图2表示FFDU、WFDU和RTTP三种算法在可调度性、负载均衡和功耗方面的性能对比。RTTP和FFDU算法可调度性相似,如定理1所述。实验证明使用FFDU算法调度后,利用率高于WFDU。实验结果表明,对于RTTP算法,即使在利用率达到98%的高负荷情况下,也能够在截止时间之前执行完成任务。相比与WFDU算法,RTTP算法在同样的利用率水平下,任务的可调度性提高了9%～12%,FFDU算法在任务的可调度性方面则具有和WFDU算法相当的性能表现。并且,RTTP算法的负载均衡性能是FFDU算法的5倍。实验还表明,在通常情况下,结合DVS技术的使用,负载均衡有效地降低了单个核心的功耗,并从整体上降低了总体功耗。相比与FFDU算法,RTTP算法降低了高达65%的功耗。

6 结语

在多核平台中运行实时应用需要一个高效的调度算法以保障任务的高可调度性和负载均衡。本文提出了一个任务划分的算法。该算法不仅可以保证实时性能,也能够针对多核系统对任务进行高效分配。实验结果表明该算法性能明显优于对比算法。此外,RTTP算法可以有效降低能耗。该算法稍作修改即可运用到现有的实时系统调度器。

[1] Robert Davis, Alan Burns. A Survey of Hard Real-time Scheduling for Multiprocessor Systems[J]. ACM Computing Surveys(CSUR),2011,43(4):1-44.

[2] Joel Goossens, Pascal Richard. Partitioned Scheduling of Multimode Multiprocessor Real-Time Systems with Temporal Isolation[C]//Proceedings of the 21st International Conference on Real-Time Networks and Systems(RTNS’13). Sophia Antipolis: ACM,2013:297-305.

[3] B. B. Brandenburg, J. M. Calandrino, J. H. Anderson. On the Scalability of Real-time Scheduling Algorithms on Multicore Platforms: A case Study[C]//Real-Time Systems Symp. Barcelona: IEEE,2008:157-169.

[4] Sanjoy B, Fisher N. The Partitioned Multiprocessor Scheduling of Deadline-constrained Sporadic Task Systems[J]. Computers, IEEE Transactions on,2006,55(7):918-923.

[5] 代声馨,洪玫,郭兵,等.多处理器实时系统可调度性分析的UPPAAL模型[J].软件学报,2015,2:279-296.

[6] 郭秀岩,张武,王劲林,等.基于改进EDF的多核处理器混合任务调度算法[J].高技术通讯,2012,22(3):231-239.

[7] H. Aydin, Q. Yang. Energy-aware Partitioning for Multiprocessor Real-time Systems[C]//Proc. IEEE International Symp. on Parallel and Distributed Processing(IPDPS’03), Nice: IEEE,2003:157-166.

[8] G. Magklis, G. Semeraro, D. H. Albonesi, et al. Dynamic Frequency and Voltage Scaling for a Multiple-Clock-Domain Microprocessor[J]. I Micro IEEE,2003,23(6):62-68.

[9] Binzhou Xia, Zhiyi Tan. Tighter Bounds of the First Fit Algorithm for the Bin-packing Problem[J]. Discrete Applied Mathematics,2010,158(15):1668-1675.

[11] S Martello, D Pisinger, D Vigo. The Three-Dimensional Bin Packing Problem[J]. Operations Research,1998,48(2):256-267.

[12] 陆一江,邢文训.在线A形装箱问题:模型及算法研究[J].清华大学学报(自然科学版),2001,41(12):1-4.

Real-Time Task Partitioning Scheduling for Multicore Systems with Load Balancing

FANG Xing

(No. 1 Canglong North Road, Wuhan 430205)

Real-time applications continuously drive the urgent demand for performance scaling. Parallel processing based on multicore and manycore architectures becomes the principal approach for enhancing system performance. To fully utilize multicore processors, it is necessary to improve parallelism, where tasks can use multiple cores simultaneously. To guarantee real-time performance and make full use of multicore resources requires a scheduling strategy that takes both schedulability and load balancing into consideration. Most existing real-time scheduling policies for multicore systems fail to consider both at the same time. To solve this problem, this paper proposes a real-time task partitioning scheduling for multicore systems with load balancing (RTTP) that not only ensures real-time performance but also achieves load balancing across the cores. The experimental results demonstrate that our algorithm performs well in terms of load balancing and schedulability. Besides, another benefit of the presented method is energy reduction through load balancing.

multicore, real-time, load balancing, utilization, schedulability

2016年7月1日,

2016年8月26日

方兴,男,硕士,高级工程师,研究方向:舰载实时操作系统技术。

TP391

10.3969/j.issn.1672-9730.2017.01.008