ARINC653分区操作系统多核处理器任务调度设计①

黎 明,莫 军

(中电科航空电子有限公司,成都 611731)

1 引言

综合模块化航空电子系统被广泛应用于新一代民用客机,如空客 A380、波音 787 等,相对传统的航电系统,采用IMA架构的航电系统具备集成度高、维护方便以及设备重量减轻等优势.

ARINC653规范[1]是美国航空电子工程委员会制定的适用于软件的实时操作系统标准,它定义了IMA架构下的实时操作系统的行为逻辑和向应用程序提供的接口规范.在该规范中实时操作系统将硬件资源划分为时间和空间相互独立的资源分区,应用程序加载于这些时空独立的资源分区之上.分区是ARINC653 规范的一个核心概念,它实现了应用程序的时空隔离.用户实现的一个应用程序是一组计算任务的集合,加载于一个资源分区之上.这些计算任务在分区内进行本地调度[2–4],与其他分区内的任务调度相互独立,若干个时间资源分区之间进行分区间调度以共享处理器的计算时间资源.

随着机载电子系统综合化、模块化的发展,分区操作系统成为航空计算机的主流操作系统.宏内核、微内核曾被分区操作系统所采用,但单核处理器已经达到性能瓶颈,很难满足综合化航空电子高性能计算要求,本文基于分区单核操作系统环境的任务调度,结合传统多核操作系统的特点,重点研究了机载综合化航空电子多核处理分区操作系统的任务调度.

ARINC653规范指定单核处理器作为硬件平台,面对机载单核处理器系统任务调度有很多的学者做了大量深入的研究[5,6].随着实时多核处理器技术的发展,多核处理器已经逐步在航空电子系统中得到了广泛的应用,但是如何进行任务分配和调度[7,8],满足机载系统的实时性要求则成为一个关键问题,因此对符合ARINC653规范的,运行在多核处理器上的实时调度方法的研究则成为航空电子系统领域的研究热点[9–11].基于上述原因,本文提出一种基于多核的任务负载比例轮转的调度方法 (Multi-kernel Load Proportional Round Robin,MLPRR),该方法采用基于任务负载比例算法生成多核处理器任务调度的任务就绪队列,对任务就绪队列采用轮转调度的方式将各个任务分配到空闲的处理器核上,以任务的负载比例计算任务权值,完成任务在多核处理器上的调度,从而满足多核分区操作系统的实时性要求.

2 实时调度模型

2.1 任务模型

多核处理器负载比例轮转调度多任务多核处理器建模如下:

设子系统任务集为T={T1,T2,…,Tn},采用实时周期性任务模型,每个任务可表示为Ti=(Zi,Ci,Pi,Di).其中,Zi为任务的分区标示,Ci为任务处理时间,Pi为任务处理周期,Di为任务最大允许延迟,一般设置

权值计算方法决定了对任务的权值分配,直接影响到算法的实时可调度性.本文采用基于负载比例的权值计算方法,具体计算方法为:

1)根据单个任务Ti在任务集T所占负载比例计算权值:

2)任务负载率:

3)总负载率为:

其中,Ci为第i个任务的处理时间,Pi为第i个任务的处理周期,Ui为第i个任务的任务负载率,U为系统中所有任务的任务负载率总和.

2.2 任务调度模型

针对上述任务模型,设计周期性分区任务在多核处理器上的任务调度模型如图1所示.任务调度模型S={S1,S2,…,Sn},Si=(Ti,Ki),K={K1,K2,…,KM}.任务调度模型中,采用基于任务负载比例算法生成多核处理器任务调度的任务就绪队列,对任务就绪队列采用轮转调度的方式将各个任务分配到空闲的处理器核上.

图1 任务调度模型图

2.3 实时轮转调度约束

在多核处理器任务调度算法中,除了计算任务的权值Wi外,系统参数主要包括轮转长度TRL、处理器核的数目M.合理的参数设计对任务的可调度性有很大的影响[12].

要满足实时需求,必须要求调度算法为任务Ti分配的权值Wi满足两个约束条件.

1) 轮转处理时间约束

对于n个周期事件,事件i以周期Pi发生,事件需要Ci秒处理时间,需要满足的条件是:

对于具有M个核的多核处理器,忽略处理器内部消耗,需要满足的条件是:

2) 轮转调度权值约束

对于n个分区任务数,需要满足的条件是:

式中Wi为任务的权值,M为多核处理器的核数目,TRL为轮转调度周期时长.

2.4 多任务负载比例轮转调度方法

多任务负载比例轮转调度方法主要分为如下4个步骤:

1) 确定多核处理器轮转周期TRL;

2) 基于任务权值分配方法,分别计算每个任务在每轮调度中的权值Wi;

3) 搜索任务队列中的所有任务,将权值高的任务排在等待处理队列的最前面;

4) 搜索处理器的各个核是否空闲,将搜索到的第一个空闲处理器核分配给等待队列队首的任务.

具体的处理流程如图2所示.

图2 任务调度处理流程图

3 模型参数

3.1 可调度性分析

对系统内M个处理器核上的n个任务启动负载比例权值轮转调度算法,为保证任务的实时性,任务的最大延迟不大于轮转周期[13].

定理.当M满足:

时,多核处理器任务负载比例权值调度算法,确保系统内所有任务满足实行性.

证明.任务Ti按负载比例分配权值:

多核处理器轮转调度下任务Ti的最大延迟为:

为了满足任务的实时性,对分区内各个任务应满足的条件是:

证毕.

3.2 系统参数评价函数

轮转长度TRL越大,调度算法用于任务间切换的消耗越小,处理器数目M越小,系统资源浪费越少[13],令评价函数

将综合模块化航空电子系统的多核实时调度问题转换为非线性最优化问题,函数值越小,系统任务的可调度性越高.

4 仿真实验与分析

为了验证提出的基于多核的任务负载比例轮转的调度方法的有效性,利用离散事件仿真方法建立分区任务多核处理调度模型,对任务集进行离散事件仿真实验.

仿真实验采用JDK1.5自带的任务调度工具Timer类搭建模拟仿真环境,实现基于多核的任务负载比例轮转调度方法.该方法利用Timer类的两个内部类TaskQueue和TaskThread类,分别模拟任务调度模型中的任务集 T={T1,T2,…,Tn}和处理器核集K={K1,K2,…,Km}.

实验主要考量基于任务负载比例权值计算,不同的轮转周期TRL对系统性能的影响.进一步地,验证算法的可调度性,即对调度方法的可调度性进行判定[14].将基于MLPRR的判定方法与文献[15]提出的BAR判定方法以及文献[16]提出的RTA判定方法进行了比较.

具体实验方法如下:

每个任务可表示为Ti=(Zi,Ci,Pi,Di),仿真时不区分任务所属的分区,且设Di为Pi,故可以简化任务模型为Ti=(Ci,Pi,Di).

实验参照文献[8]方式随机生成任务,任务的利用率Ui的分布符合以δ为期望的指数分布,生成过程中排除Ui>1的情况; 周期Ti服从[1,200]上的均匀分布.

实验步骤按照下述三步进行:

1) 初始化任务集,任务个数为n+1;

2) 采用文献[14]提出的任务集具有可行性的必要条件进行检验.若该任务集可行,则使用相应的判定方法对任务集进行可调度性判定;

3)若该任务集被判定为可调度任务集,则向该任务集中增加一个新任务,得到一个新的任务集,重复步骤2).

此处设定处理器核的数量M=4,平均利用率δ=0.6,最终的测试任务集为1000个任务.其实验结果如图3,图4所示.

图3 任务处理时间比较

图3列示了10个任务在不同轮询周期TRL=5和TRL=12 的任务处理时间.由图3可以得出:TRL=12所需的任务处理时间比TRL=5所需的任务处理时间少,任务的可调度性越高,实时性更好.

从图4可以得出: 满足可调度性的任务集有767个任务.其中,通过BAR判定方法的任务集有285个,通过RTA判定方法的任务集有426个,通过本文提出的MLPRR判定方法的任务集有458个.

图4 可调度性判定比较

实验表明: 本文提出的MLPRR方法具有更好的可调度性,尤其是随着判定任务集数量的增加,MLPRR方法显示出了更强的判定优势.这充分本文提出的基于多核负载比例轮转的调度方法MLPRR为分区操作系统多核处理器任务调度提供了一种有效的调度策略.

5 小结

本文提出了一种基于ARINC653分区操作系统的多核处理器任务调度的任务负载比例轮转调度方法MLPRR,该方法以任务的负载比例计算权值,完成任务在多核处理器上的调度,从而满足多核分区操作系统的实时性要求.针对影响调度算法的参数设计了合理的评价函数.本文的设计方法、仿真分析和研究结论有助于未来符合ARINC653标准的多核处理器分区实时任务的设计和分析.

参考文献

1AEEC,Aeronautical Radio Inc.ARINC 653P0 Avionics application software standard interface.2551 RIVA ROAD,ANNAPOLIS,MARYLAND 21401-7435,2014.

2Lee YH,Kim D,Younis M,et al.Partition scheduling in APEX runtime environment for embedded avionics software.Proceedings of the Fifth International Conference on Real-Time Computing Systems and Application.Hiroshima,Japan.1998.103–109.

3Lim S,Hyun J,Shin SM,et al.A feasibility study for ARINC 653 based operational flight program development.Proceedings of the 31st Digital Avionics Systems Conference.Williamsburg,VA,USA.2012.6C2-1–6C2-7.

4Ruan WL,Zhai ZJ.Kernel-level design to support partitioning and hierarchical real-time scheduling of ARINC 653 for VxWorks.Proceedings of the 2014 IEEE 12thInternational Conference on Dependable,Autonomic and Secure Computing.Dalian,China.2014.388–393.

5Tindell KW,Burns A,Wellings AJ.Allocating hard realtime tasks: An NP-hard problem made easy.Real-Time Systems,1992,4(2): 145–165.[doi: 10.1007/BF00365407]

6何锋,宋丽茹,熊华钢.航空电子双层任务分区调度设计.北京航空航天大学学报,2008,34(11): 1364–1368.

7Saidi S.On the benefits of multicores for real-time systems.Proceedings of 2017 Euromicro Conference on Digital System Design.Vienna,Austria.2017.383–389.

8Marko B,Michele C,Giuseppe L.Schedulability analysis of global scheduling algorithms on multiprocessor platforms.IEEE Transactions on Parallel and Distributed Systems,2009,20(4): 553–566.[doi: 10.1109/TPDS.2008.129]

9代声馨,洪玫,郭兵,等.多处理器实时系统可调度性分析的 UPPAAL 模型.软件学报,2015,26(2): 279–296.[doi:10.13328/j.cnki.jos.004781]

10何翔,任晓瑞,刘帅.嵌入式多核操作系统确定性研究.航空计算技术,2014,44(3): 96–100.

11刘鸽,叶宏,李运喜,等.基于多分区操作系统的多核确定性调度方法设计.航空计算技术,2016,46(1): 99–102.

12黄金,许渤,凌云,等.机载波分复用网络强实时性调度算法设计.光学学报,2013,33(4): 0406001.

13周立,丁凡,熊华钢.航空电子WDM网络多信道强实时调度设计.北京航空航天大学学报,2010,36(2): 1392–1395.

14石林勇,晏立.多处理器全局单调比率的可调度性分析.计算机应用,2010,30(10): 2735–2737.

15Baruah S. Techniques for multiprocessor global schedulability analysis.Proceedings of the 28th IEEE International Real-Time Systems Symposium.Tucson,AZ,USA.2007.119–128.

16Bertogna M,Cirinei M.Response-time analysis for globally scheduled symmetric multiprocessor platforms.Proceedings of the 28th IEEE International Real-Time Systems Symposium.Tucson,AZ,USA.2007.149–160.