陈平，魏峰，李蜀瑜
（陕西师范大学计算机科学学院，陕西西安710100）
摘要：实时调度算法是嵌入式系统的核心组成部分，高效的调度算法能增强系统的实时性和可靠性，ARINC653标准已经广泛地应用于综合航空电子系统中。首先介绍了几种实时调度算法，从满足ARINC653标准的角度出发，选取近几年的双层调度算法进行综述，讨论了现有的双层调度模型和双层调度算法，不同的分区间与分区内的调度算法组合会产生不同的效果。通过对各种双层模型和算法的比较与分析给出了各自的优缺点，对常用调度分析工具进行了叙述，以供设计和分析人员选择。最后，分析了双层调度算法有待深入研究的难点，并对其发展趋势进行展望。
教育期刊网 http://www.jyqkw.com
关键词 ：实时算法；双层调度；ARINC653；嵌入式系统
中图分类号：TN911-34 文献标识码：A 文章编号：1004-373X（2015）12-0029-04
收稿日期：2014-12-31
基金项目：国家自然科学基金项目：云计算环境下旅游信息个性化服务模型研究（41271387）
0 引言
嵌入式系统被广泛地使用在诸多对安全要求的行业。嵌入式系统在规模上已发生重大改变，在航空领域，嵌入式系统由联合式发展到目前的高度综合化、模块化的航空电子系统（Integrated Modular Avionics，IMA）。也就是说，软件的规模变大，复杂度增加。因此，为了确保软件的可靠性，模型驱动结构方法（MDA）应运而生，MDA 的核心思想用模型抽象现实将模型与现实分离，通过模型来对系统进行开发和维护。在软件设计阶段就可以通过对模型的验证发现潜在错误，以此来提高系统的可靠性。
针对嵌入式软件存在的问题，美国SAE组织给出了一种建立在MDA思想上的建模语言。它就是体系结构分析设计语言（Architecture Analysis and Design Lan-guage，AADL），其支持对嵌入式系统软硬件结构及功能、非功能需求建模，并提供多种模型分析工具，可支持对系统模型的分析、验证、测试和自动代码生成等，并且可以针对特定领域进行扩展。AADL的语法相对简单，具有很多的功能，并且具有很好的可扩展性。使基于AADL 的MDA 过程具有很好的应用前景。ARINC653作为接口标准，已经应用于航空系统的设计中。在对航空系统的模型建立时要参照该标准的要求。文献[1]将其定义了为航空电子计算机的操作系统和应用程序软件之间的通用的应用/执行（APEX）软件接口。
近几年来有不少学者都对实时调度算法进行了研究，已提出了多种算法和模型。本文重点关注嵌入式实时系统的调度性算法，首先介绍一些近年来较为新颖实用的实时调度算法，然后介绍满足ARINC653标准的双层调度算法，最后介绍几种调度性工具，为使用者提供一个参考。
1 实时调度算法
因为实时调度算法是双层调度算法的基础，因此研究一些较为新颖的实时调度算法以备研究双层调度算法时使用。在实时调度算法中，对于静态调度来说，大都在RMS 算法之上进行改进，而动态调度则是以最早截止时间优先算法或最低松弛度优先算法为主。在这些经典的调度算法之上，业界提出以下若干新的实时调度算法。
文献[2]提出基于RM 和EDF 的一种新的实时调度算法SBRD（Schedule Based on Rate and Dead line） 。在SBRD中引入了重要性因子来描述任务的重要程度，引入紧急因子用来描述任务的紧急程度。在SBRD 中对于调度优先级由一对数值对决定。数值对包括2个元素priority和urgency，其中前者表示重要性因子，它不表示时间属性，而是由用户决定的，反应用户的要求。后者表示紧急性因子，它是一种动态因子，它会随当前截止期限不同而不同。SBRD 相比于与RM 和EDF 算法，能更好地利用CUP资源，因为它能保证紧急任务优先执行、保证重要任务顺利执，因此它能更大程度上的满足更多任务在截止期限之前被执行。
文献[3]给出了名为MLLF（Modified Least Laxity）调度算法。MLLF 调度算法相对于最早截止时间优先算法或最低松弛度优先算法来说，它的适应性更广，其优先级计算公式为di（t）-t-f × ei（t），f 在0~1 之间。若f 为0，则MLLF 调度算法退化为最早截止时间优先算法，f=1，MLLF算法退化为最低松弛度优先算法。MLLF只考虑周期任务，没有对突发任务的实时调度进行考虑。另外要求周期任务不能有关联并且独自占用系统资源。
文献[4]针对实时调度，针对在多任务的情况下优先级较低的任务延迟问题，给出一种因优先级较低而出现延迟任务的优先级，周期性地与较高任务的优先级互换的算法。该算法中，周期是固定的，选择2个相互独立的、优先级不同的任务周期性地交换其优先级，这样在不同的周期内原优先级较低的任务的优先级级别是不一样的，这样就能使优先级较低的任务尽快的被执行同时不影响较高优先级任务的执行。这样做的好处是缩短优先级较低任务的延迟时间，能够使优先级较低任务的实时性得到保障，因此能够改善实时系统在执行多任务时的整体性能。该算法以时间片轮转算法为基础，同时考虑了系统开销和算法的灵活性。其不足之处在于固定时间片的长度，预先定义好任务的优先级别并且不能同时进行多组任务的同时互换优先级。
2 双层调度
2.1 双层调度算法概述
在IMA的架构下，软件被封装于分区中。就分区这一概念而言它由2部分组成，一部分是空间分区，另一部分是时间分区。分区是进行调度、资源分配、隔离保护的单位。空间分区指各个分区的地址空间是不同的，使用存储管理器（Memory Manage Unit）将虚拟地址映射到物理地址，使分区的物理存储空间相互隔离，不被其他分区所使用，从而对其进行保护。时间分区指不同分区在同一周期内被调度并且不同分区的优先级别相同，由系统建立一个时长确定的主时间框架并且周期性的重复，它可以被分成若干时间窗口，要求时间窗口个数要不小于分区数目，这样才能保证每个分区占有至少一个时间窗口，并且只能在它占有的时间窗口内才能被调度。因此在ARINC653系统中当某一分区故障时，其他分区不会受到影响，仍然能正常执行。时间隔离表示每个分区都具有固定的、相互独立的时间框架来执行。操作系统内的主时间框的长度是全部分区周期总和的倍数。操作系统由各分区的不同需求为其划分时间窗口，每个分区将获得一个或多个时间窗口，可将其称之为时间片。这样就在时间上和空间上将分区隔离开来。
ARINC653 系统包含两级调度即分区间调度和分区内调度。在下图所示的调度模型中在系统层依据ARINC653标准使用一定的调度策略去进行分区调度，在区间层根据分区内定义的调度策略进行任务调度。每一个分区内部的任务只能在当前分区处于激活状态才有可能被执行，从而使得模块中各分区相互独立。
2.2 双层调度算法
为了满足ARINC653的两级调度要求，目前已经有不少学者提出了双层调度的模型和算法，主要包括模型的建立和改进[5-7]、分区参数的设计[8，6]和解析以及对时间片算法的改进[9-11]等方面。
文献[8]中较早地提出了双层调度的概念，给出了部分相关分区的参数，并针对分区的调度考虑任务最大响应时间，在单处理器情况下借用Tindell提出的一种精确的分析算法。该算法引入“关键时刻”这一概念，在对分区进行调度性分析时可以得到“关键时刻”的“关键条件”。最后通过分析给出了分区成功调度的一些要求。但是文中仅考虑单处理器情况下的算法，双层模型有待进一步的扩充和完善，并且不考虑释放抖动等复杂情形下的调度。文献[5]中建立的双层调度模型，上层使用轮转调度策略，下层使用EDF调度策略，对于分区调度的关键参数，在文中给出了它的解析表达式和解析模型。对于其他算法设计者有很好的参考价值。文中给出的算法上层使用传统时间片轮转，分区之间优先级相同，虽然算法简单却不够灵活，并且时间片长度确定，为了满足分区对时间片的最大要求，时间片就应该设置为分区要求最大时间，因此存在不必要的时间开销。
文献[6]中对于ARINC653 分区管理模型进行了扩展。提出上层调度使用动态优先级的调度策略的分区设计方法。相比较于上层为静态优先级的调度算法，这种调度策略有很好的灵活性，但同时也增加其复杂性。上层考虑最大响应时间，使用改造的针对动态优先级任务的算法。文中还探讨了下层采用固定优先级和动态优先级调度策略下的分区设计方法，并且通过价值函数给出了一些分区设计的参数。
文献[7]提出了一种静态双层调度模型。在该模型中使用固定周期分区和优先级位图算法。为了确保分区内的任务在规定时间内正确执行，在分区内使用两种调度方式，一种是静态优先级，另一种是EDF动态优先级。文中对任务调度时的条件约束及任务的可调度性做了相关的研究。这种调度策略存在的不足是在确定分区优先级时是采用RM调度算法，忽略了分区执行周期不确定的情况。
文献[9]给出了一种改进的时间片轮转算法。文中将最后一次时间片的分配进行优化，改进算法对原算法做了下述改变：当前进程即将执行完毕，但是仍有剩余工作，这时通过增加一定的时间片将当前任务执行完成而不必等待下一次系统调用。增加时间片的时机是可以调整的，正在执行进程需要继续执行的时间不足系统原来分配的时间片值得若干分之一时，通过调度算法为其增加一定的时间片值，使当前进程能在该时间片内完成。该算法在一定程度上减少了进程的切换也就是说减少了调度的次数，从这一点上来说增强了实时性。但是文中没有给出如何确定增加时间片长度的一般方法，也没有给出具体参数确定方法。
文献[10]提出了一种加权轮转调度算法。分区通过核心调度器以加权轮转（Weighted Round Robin）调度的方式逐一被激活，当分区激活后拥有对CPU 内存等资源的使用权。分区内部采用可抢占式FP调度算法，即在分区被激活时，在时间片结束前优先级高的任务优先被调度，高优先级任务可以抢占低优先级任务，从而减少高优先级任务的响应时间。文中将该调度策略命名为WRP-FP，以加权轮转调度策略来激活分区，同时将时间窗口固定，提高了系统的可预测性。该调度算法允许进行混合任务集的调度。对强实时的周期任务建立具有任意时限的任务模型，使模型具有更强的通用性，文中通过对响应时间上限的计算，给出了可调度条件；文中将“期望可调度”概念引入弱实时的非周期任务，以此来确保在统计条件下任务是可调度的。
上述算法在起始时时间片都是人为确定好的，在文献[11]中提出了基于ARINC653航空电子设备实时操作系统，将其模拟为2层分级制度。使用具有非零偏移值的处理过程技术，扩展了现有的基于资源模型。提出了一种分区抢占策略，使用这些技术和策略来自动的生成分区时间表，文中所提出的技术作为分区级调度原则可用来设计的平台。此外还提供了正确性分析和验证，从而确保在系统认证中可以使用。文献[12]提出了一个资源模型能够描述分区占用资源的周期性行为，并提供精确的调度条件。对于分级调度框架，提出了桥接两个独立开发的调度模型的接口模型，这种调度接口模型、可以使用任何独立的调度算法对其进行调度性分析，与另一个调度模型是没有任何交互的。在图1中详细给出了几种双层模型和调度算法的优缺点。
3 调度分析工具
3.1 OSATE
OSATE（Open Source AADL Tool Environment）是一款开源的AADL工具，它是Eclipse平台下的AADL模型开发工具。它由SEI开发，集建模，分析，验证，转换为一体，功能全面且集成度高。OSATE适用于终端用户和工具开发人员，OSATE向终端用户提供文本、图形编辑器以及一些分析验证工具。OSATE中已经集成了几种调度分析的插件，包括VERSA 插件和Scheduling插件，支持EDF、RMS等调度算法。只需要在模型建立好之后通过点击相应的调度算法，就可以得到调度结果。而且越来越多的调度策略和算法将被作为插件集成进入OSATE中。
3.2 Cheddar
Cheddar由布雷斯特大学开发，是一种开源的实时调度框架。它的框架使用Ada编写，能够对实时应用的时间要求进行验证。Cheddar 将一个应用定义为处理器、任务、缓存、共享资源和消息的集合。Cheddar不仅支持单处理器的时间可行性分析，它还支持多处理器和分布式系统，同时还提供了仿真机制。文献[13] 介绍了正在为了增加实时调度理论的可用性研究的Cheddar项目3个可能的方向。提出了一套开源的工具，帮助设计人员自动将理论应用于具体案例。这个工具可以让不同层次的人员使用，并能执行写入标准化设计语言模型的分析。该Cheddar项目一直集中在AADL上。还提出了一个领域特定语言，它可以被用来研究结构的性能，因为现有的实时调度理论没有提出合适的分析方法。
3.3 Marzhin
在文献[14]中介绍了使用Marzhin 模拟器，相比于Cheddar，Marzhin基于多Agent技术，提供实时系统的调度分析结果，该模拟器集成在AADL 中，同时提供了逼真的3D 动画效果增强了可视性。通常，实时仿真器的实现是基于实时操作系统（RTOS）的仿真。这些仿真器必须因此提供相同的应用程序编程接口（API），并且具有相同的动态行为作为真正的软件。Marzhin是基于现有的多代理仿真内核VAgent的重用。相对于实施确定性调度算法传统模拟器，该内核随机刺激的一组自主互连的基本实体（Agent），以显示出所得的宏观行为。Cheddar不能给任何种类的AADL架构提供一个显著结果。但是，Marzhin的作用是专门为具有不能在确定的方式进行处理的情况下对Cheddar的一个补充。
4 结语
本文首先介绍了3种较新颖的实时调度算法，然后对满足ARINC653 要求的双层调度算法做了详细的介绍，实时调度算法对于实时系统起着至关重要的作用。在ARINC653标准下，双层调度算法出现并使用在航电系统模型中，上层调度和下层调度的不同组合和不断地优化势必会产生更好的调度模型，因此在未来一段时间内双层调度算法将成为研究热点。对于分区间的调度，时间片轮转算法是其基础算法，对于如何进行时间片大小的确定、轮转方式以及空闲时间的利用将有待进一步的研究。分区内的调度算法需要考虑如何确保实时任务在结束时间到来之前被调度，同如何调度非周期的弱实时任务，分区调度的参数的解析和优化以及如何提高效率。最后，介绍了3种用于调度性分析的工具，以供设计人员选择使用。
教育期刊网 http://www.jyqkw.com
参考文献
[1] Anon. ARINC specification 653 -2，part I：engineering stan-dards for avionics and cabin systems [M]. [S.l.]：AEEC，2006.
[2] 洪雪玉，张凌，袁华.Linux下的实时调度算法木[J].华南理工大学学报：自然科学版，2008，36（4）：104-109.
[3] 翟鸿鸣.单处理器系统的实时调度算法研究[J].微机发展，2003，13（10）：99-101.
[4] 王彬，王聪，薛洁，等.优先级周期性互换的实时调度算法[J].计算机应用，2014，34（3）：668-672.
[5] 何锋，宋丽茹，熊华钢.航空电子双层任务分区调度设计[J].北京航空航天大学学报，2008，34（11）：1365-1368.
[6] 何锋，顾健，熊华钢.基于动态优先级的核心处理安全分区优化设计[J].北京航空航天大学学报，2011，37（10）：1282-1287.
[7] 杨霞，桑楠，雷剑，等.嵌入式高可信架构中基于静态模型的调度研究[J].航空学报，2009（12）：2387-2394.
[8] 何锋，熊华钢，宋丽茹.航空电子分区调度研究[J].系统仿真学报，2008（z1）：522-525.
[9] 肖建明，张向利.一种改进的时间片轮转调度算法[J].计算机应用，2005（z1）：447-448
[10] 周天然，熊华钢.航空电子系统混合实时任务的双层调度[J].航空学报，2011（6）：1067-1074.
[11] EASWARAN A，LEE I，SOKOLSKY O，et al. A compositional scheduling framework for digital avionics systems [C]// 200915th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. [S.l.]： IEEE，2009：371-380.
[12] SHIN I，LEE I. Periodic resource model for compositional real-time guarantees[C]// 2003 24th IEEE Real-Time Systems Sym-posium. [S.l.]：IEEE，2003：2-13.
[13] SINGHOFF F， PLANTEC A， DISSAUX P， et al. Investi-gating the usability of real - time scheduling theory with theCheddar project [J/OL]. [ 2014-08-13]. http：// www.9512.net/read/f6ae...990.htm.
[14] DISSAUX Pierre，MARC Olivier，RUBINI Stephane，et al.The SMART Project：multi-agent scheduling simulation of real-time architectures [J/OL]. [2014-12-26]. http：//www.research-gate.net.
[15] FEILER P H，GLUCH D P，HUDAK J J. The architecture analysis & design language （AADL）：An introduction [R].USA：Pittsburgh PA Software Engineering Inst，Carnegie-Mel-lon University，2006.
[16] DELANGE J，PAUTET L，PLANTEC A，et al. Validate，simulate，and implement ARINC653 systems using the AADL [J]. ACM SIGAda Ada Letters，2009，29（3）：31-44.
[17] DAVIS R I，BURNS A. Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems [J]. Real-Time Systems，2011，47（1）：1-40.
[18] MOHANTY R，BEHERA H S，PATWARI K，et al. Prioritybased dynamic round robin（PBDRR） algorithm with intelli-gent time slice for soft real time systems [J]. InternationalJournal of Advanced Computer science and Application，2011，2（2）：46-50.
[19] LIANG B，YONGHENG J，DEXIAN H. A novel two-level op-timization framework based on constrained ordinal optimiza-tion and evolutionary algorithms for scheduling of multipipe-line crude oil blending [J]. Industrial & Engineering Chemis-try Research，2012，51（26）：9078-9093.
[20] SINGHOFF F， PLANTEC A， DISSAUX P， et al. Investi-gating the usability of real - time scheduling theory with the Cheddar project [J/OL]. [2014 - 12 - 18]. http：//www.research-gate.net.
[21] LEE Y H，KIM D，YOUNIS M，et al. Resource scheduling in dependable integrated modular avionics [C]// Proceedings of 2000. Proceedings International Conference on Dependable Systems and Networks. [S.l.]：IEEE，2000：14-23.
作者简介：陈平（1991—），男，陕西宝鸡人，硕士。研究方向为嵌入式软件设计与验证。
魏峰，硕士。研究方向为嵌入式软件设计与验证。
李蜀瑜，副教授，博士。研究方向为嵌入式与云计算。