针对AADL 模型的可调度性分析方法研究

黄英兰

(航空计算技术研究所，西安 710119)

1 引言

随着嵌入式实时系统的广泛应用，嵌入式系统的重要性和规模发生了重要变化。如在航空领域，嵌入式系统从联合式发展到目前高度综合化、模块化的航空电子系统，传统中的子系统被集成到多个综合区中。为了避免整个系统综合的不可预测性、易出错性，避免系统前期设计的一些缺陷，近年来，美国SAE 组织为综合化航空电子系统定义了一组满足航空电子综合化设计用的建模语言AADL(Architecture Analysis ＆ Design Language)。

AADL 使用软件构件、硬件构件和系统构件描述系统的结构、使用端口、连接描述系统的连接和通信行为，使用各种属性来描述系统的功能和非功能属性。使用AADL 建立嵌入式实时系统模型后，可以对模型的各种非功能属性进行分析、仿真系统的行为、生成指定目标语言的源代码。使得过去只能够在系统实现后，才能验证的非功能性属性验证提前到系统设计阶段，提高了系统设计的正确性和可靠性。通过自动代码生成避免了手工编码的费时、费工和易出错性，最终得到满足功能和性能要求的系统。

近年来很多国内外研究机构积极投身于对AADL 语言的研究，并开发了多种支持AADL 建模、模型转换、性能分析、模型仿真和自动代码生成的工具。卡内基.梅隆大学下属的软件工程学会开发的一套支持使用AADL 进行综合建模、分析的开源工具集OSATE(Open Source AADL Tool Environment)就是其中最具代表性的工具集。

本文重点关注使用AADL 语言建立的嵌入式实时系统模型的可调度性。首先对AADL 语言进行概述，重点对可调度性分析工具可能使用到的属性进行简要介绍。然后针对几种使用AADL 模型进行可调度性分析的工具进行介绍，分析它们的优缺点，为使用者选择合适的分析工具提供依据。最后对可调度性分析工具的发展提出自己的看法。

2 AADL 语言概述

SAE的AADL是用于设计和分析性能关键实时系统的软、硬件结构的一个文本和图形语言［1］。这些系统的运行依赖于满足像可靠性、可用性、时序、响应率、吞吐率、安全性这些非功能的系统需求。

AADL 语言使用构件来表示要建模系统中的软、硬件实体。它定义了下面一些构件:数据、子程序、线程、线程组、进程、处理器、存储器、总线、设备和系统。其中软件构件有:数据、子程序、线程、线程组和进程构件;硬件构件，即执行平台构件有:处理器、存储器、总线和设备构件。AADL 语言使用端口、连接来描述构件间的功能接口。端口有数据端口、事件端口、事件数据端口。使用绑定来描述软件构件到硬件构件的映射。使用模式和模式转换来描述运行系统的动态行为。AADL 语言还支持使用附件库和附件子句对核心语言进行扩展。例如，通过添加错误模型附件来支持对模型进行可靠性分析，通过使用属性来描述构件的性能指标。

对AADL 模型进行可调度性分析可能使用到的属性有:

·Activate_Deadline:指定允许的执行线程活动的最大时间;

·Activate_Execution_Time:指定了在没有运行错误出现的情况下，线程执行它的活动序列所需的最小和最大执行时间;

·Actual_Processor_Binding:指定了线程所绑定的处理器;

·Allowed_Period:指定了允许绑定到某个处理器上周期任务的周期集合;

·Allowed_Processor_Binding:指定了线程允许绑定的处理器;

·Clock_Period:指定了处理器或系统的两个时钟中断之间的时间值;

·Clock_Period_Range:指定了Clock_Period 最大和最小值;

·Compute_Deadline:指定了执行一个线程计算序列的最大时间;

·Compute_Execution_Time:指定了在一个线程派发后和在下一次派发前一个线程执行的时间范围;

·Deadline:指定了一个线程派发的时间和线程开始等待另一次派发的时间之间的最大时间;

·Dispatch_Protocol:指定了一个线程的派发行为;

·Period:当线程的调度协议为周期或零散的协议时，指定了两次派发之间的时间间隔;

·Scheduling_Protocol:指定了处理器的线程调度器使用的调度协议。

对AADL 模型进行可调度性分析将可能使用到上述的属性。在使用时，可以参考文献［1］来详细了解属性的含义、适用的构件类型。本文所分析的可调度性分析工具有Scheduling、VERSA、aadl2sync、Cheddar 工具。

3 Scheduling

Scheduling是集成到 OSATE (Open Source AADL Tool Environment)工具集中的可调度性分析工具。OSATE是由软件工程学会为AADL 开发的基于Eclipse的集成开发环境［2］。集成在该环境下的可调度性分析插件以AADL 描述的一个系统实例为输入进行可调度性分析，只支持最早截止期优先(EDF)、速率单调算法(RMS)的分析，目前它还只是一个示例性的插件，功能还较为简单。

用户可以通过点击Analyses－ ＞Scheduling－ ＞Bind and schedule threads 菜单来启动绑定和调度线程插件，此插件尝试在系统实例中绑定线程实例到处理器实例，以线程的Period、Deadline、Clock_Period、Scheduling_Protocol 和allowed_processor_binding属性为输入。如果线程可以在该处理器中调度，此插件报告线程和处理器的绑定，并返回处理器的利用率。由于需要使用独立于处理器的计算执行时间，因此该插件将线程的执行时间转换为时钟周期个数。该插件实现了EDF 和RMS 调度协议。如果没有指定协议，则默认是EDF。例如，针对两个线程绑定到一个处理器上的例子，该例子的AADL 文本表示如下，分析结果如图1 所示。

图1 OSATE 中集成的可调度性分析工具分析结果图

目前该插件也只是一个示例性的插件，软件工程学会计划下一步扩充该插件的功能，使得该插件支持更多的调度算法，支持对模型的不同模式进行可调度性分析。并且该插件可以与已有的调度性分析工具连接，将AADL 模型生成已有模型识别的模型表示，例如，可以生成一个针对TimeWiz的时序模型(TimeWiz是一个商用调度性分析执行跟踪分析工具)，调用该工具，分析结果显示在该工具中，但将结果状态映射回AADL 环境中。

4 VERSA

VERSA(Verification Execution and Rewrite System for ACSR)是宾夕法尼亚大学开发的使用ACSR(Algebra of Communicating Shared Resources)来进行资源有限的实时系统的自动分析工具［3］。ACSR 能够对敏感资源进行描述，还能够对系统的时序限制进行描述。ACSR 还包括资源、时序和优先级的精确概念。

VERSA 使用ACSR 来构造和分析系统，它具有下列特征:

·支持ACSR的完全语法和语义;

·支持过程表示的语法和语义检查;

·支持对过程的等值检测;

·支持与ACSR 过程对应的系统交互执行。

VERSA 对ACSR时序属性的分析包括对任意任务模型的可调度性分析，如多处理器和资源、任务依赖。VERSA 实现了:①ACSR的语义;②状态空间的探测，死锁的检测;③诊断结果是失败场景。对时序和资源分析包括将资源冲突视为死锁，允许编辑任务模型、调度策略、内部任务的依赖。

目前宾夕法尼亚大学研究利用VERSA的功能来分析AADL 模型的可调度性，并开发了VERSA 插件集成到OSATE 平台中。该插件的示意图如图2 所示。该插件首先将AADL 模型转换为ACSR 模型，然后利用VERSA 已有的功能进行AADL 线程的可调度性分析，并将分析结果返回到OSATE 平台中。在AADL 模型转换到ACSR 模型时，将基于线程的语义自动机线程建模为ACSR 进程;处理器和访问链接建模为资源;事件和数据连接建模为通信通道。

图2 OSATE 中集成的VERSA 插件示意图

此插件实现了将AADL 模型转换、可调度性分析、结果显示的功能，使得用户可以不用切换工具环境即可进行从建模到分析的工作。但是没有证明两种模型的等价性。

5 aadl2sync

aadl2sync 工具集支持对AADL 模型进行仿真和形式化验证［4］，它能够仿真模型的调度方法，目前的版本支持仿真速率单调调度方法。给定AADL模型和构件实现，aadl2sync 支持执行自动仿真和形式化验证。这是通过转换AADL 模型为Lustre 编程语言来实现的，利用仿真和形式化验证工具链，来执行仿真验证。此工具链允许设计者在机器代码生成和开发阶段的早期就关注于功能属性。该转换的主要困难是建模不确定和将异步AADL 描述为一个同步语言。为了达到此目的，aadl2sync 使用基于零散活动条件、输入条件和类同步时钟的技术。

在转换时，AADL 模型与Lustre 节点的对应关系如下:

·AADL 系统构件:转换为Lustre的一个高级节点，系统的每个输入端口映射为Lustre 节点的一个输入。系统实现中的每个子构件映射为一个Lustre节点;

·硬件构件:设备构件用于AADL 模型与外部环境进行连接，因此设备的输入作为系统输出，设备的输出作为系统输入。处理器是用于执行和调度进程的硬件和软件的一个抽象。Clock_period 属性声明处理器内部的时钟频率，在转换时用于建模处理器时钟之间的关系。在系统包含几个处理器时，使用Clock_period 来生成类同步时钟;

·内存构件:转换时用于指定其他构件可以使用的内存类别和大小;

·总线构件:转换时将它视为通常的连接来看;

·进程构件:转换时作为调度和执行线程的一个抽象软件;

·线程构件:转换时作为调度和执行线程的一个抽象软件;

·数据构件:转换时作为Lustre 类型，而不是Lustre 节点。

目前aadl2sync 对有些AADL 模型概念还不支持，例如包含输入和输出的端口组、作为系统子构件的系统、线程组、模式、零散、非周期和后台线程、执行故障处理的线程等概念。aadl2sync 对AADL 支持的详细介绍可以参考文献［4］。

aadl2sysnc是独立可执行的工具。Aadl2sync 并不以aadl 文件作为输入，而是以aadl 文件对应的aaxl 文件作为输入。此aaxl 文件可以通过使用OSATE 工具集中的插件来获得。启动aadl2sysc 工具来处理某个aaxl 模型文件，将编译生成6个文件:

文件名.lus:包含高层次的Lustre 节点文件，可分别用于仿真和形式化验证;

文件名_nodes.lus:包含模型中所有AADL 构件的Lustre 表示;

文件名_scheduler.lus:包含在翻译时引入的驱动所有计算的调度器;

fillme_文件名_nodes.lus:包含与aadl 模型叶节点对应的节点接口。需要提供这些节点的实体;

fillme_文件名_const.lus:包含各种需要定义的常量，例如构件初始值;

fillme_文件名_types.lus:包含数据类型构件的Lustre 类型定义。

该转换目前还没有做到自动化。后面的3个以前缀fillme 开头的文件需要填充，填充完成后要将前缀删除进行重命名。作为任何一个xml 文档，aaxl文件应该在文件头定义URI 用来查找它们满足的xml schema，但是由OSATE 生成的aaxl 文件定义了一个错误的URI(http://AADL/)。为了逆转这个问题，aadl2sync 拷贝了那些schema 文件到/tmp/aadl－schema/路径。因此，只需要修改aaxl 文件使得它指向该路径即可。

aadl2sync 工具集只能够以后缀为aaxl的AADL模型文件为输入进行仿真，它不具有建模功能，也不具有证明两种模型等价性的功能，而且目前还有一些AADL 模型概念不支持。

6 Cheddar

Cheddar 由布雷斯特大学开发，是一个免费的实时调度框架［5］。它是由Ada 语言实现的框架，能够检查一个实时应用是否满足它的时间限制。在Cheddar 中，一个应用由处理器、任务、缓存、共享资源和消息的集合组成［6］。Cheddar为单处理器、多处理器和分布式系统提供了方便的时间可行性分析。它也提供了一个方便的仿真机制，允许设计者描述和运行特定系统的仿真。该框架是开放的，并且便于与CASE(计算机辅助软件工程)工具，例如编辑器、设计工具、仿真器等工具连接。

开发Cheddar 主要为了三个目的:

(1)提供一个实现大多数传统实时调度原理方法的工具。可行性测试可应用于单处理器和分布式系统的常用调度方法，如最早截止期优先、截止期单调、最早松弛度优先和POSIX 调度器的SCHED_FIFO、SCHED_RR、SCHED_OTHERS 队列策略。可行性测试也关注于任务间共享缓存或任务抢占系统。人们可以通过Cheddar 来研究实时调度原理的基础;

(2)提供一个开放的、轻便的和易使用的工具。对于那些对实时调度原理没有概念的人该工具也很方便使用。因为开放性，该工具容易与其它工具，如仿真器、CASE 工具、监控服务器等连接。该工具的输入和所有输出都是XML 格式的。为了轻便性和可维护性，使用Ada 语言来实现该框架;

(3)提供一个灵活的扩展。可行性测试仅仅支持几个已知的调度方法，而Cheddar 仿真器可以灵活的仿真具有特定时序行为的系统。用户可以使用类Ada的仿真语言来扩展该工具，使用该语言描述的用户扩展并不被编译，而是在仿真时由工具进行解释。这使得设计者在不是很深入了解工具设计和Ada 语言的基础上也可以快速的编写和测试新的调度特征。

Cheddar 提供了工具来检查AADL 线程是否在执行时满足它们的截止期［7］。它可以将AADL 描述转换为Ada 描述来执行可调度性分析。大部分Cheddar的可调度分析服务可以直接应用于AADL描述。然而，为了支持其它一些实时调度分析算法，需要添加一些额外的AADL 属性。

在Cheddar 中，一个应用由处理器、缓存、共享资源、消息和任务的集合组成。对这些任务集合，在Cheddar 中可以执行可调度性仿真和可行性分析。调度仿真结果由任务分配的处理器的时间单位组成，如果任务满足它们的截止期，Cheddar 继续执行计算。图3 给出了一个使用Cheddar 进行可调度性仿真分析的例子，在该例子中有3个周期任务(T1、T2 和T3)，周期分别为10、20、35，执行时间分别为3、8、7，截止期为10、20、35，这三个周期任务运行在同一处理器上，使用速率单调调度(RATE_MONOTONIC_PROTOCOL)方法。在窗口的上部，显示了调度仿真结果。这些任务以可抢占的单调速率方法可调度。

图3 Cheddar 调度仿真结果示例

在可调度性分析后，可以抽取出最好、最坏、平均情况下的响应时间，阻塞时间、抢占次数、上下文转换次数、端对端消息通信延迟等。给定一个任务集合，如果难以执行调度仿真，Cheddar 将使用可行性测试代替仿真给出可行性测试结果。目前cheddar 提供3种可行性测试:基于处理器利用率的测试、任务响应时间满足任务截止期测试、缓存利用率测试。详细的使用方法可参考文献［6］。

Cheddar 支持以AADL 模型为输入，进行可调度性分析和仿真，并且支持定制特定调度方法的分析和仿真，界面简单、易学易用，但是不支持建模，也不能够直接与建模工具集成。

7 结束语

从对上述工具的研究来看，目前针对AADL 模型进行可调度性分析主要有两种方式。第一种方式是直接设计实现针对AADL 模型的可调度性分析工具，如OSATE 工具集中的Scheduling;第二种方式是将AADL 模型转换为其它模型，利用针对其它模型的可调度性工具进行可调度性分析，这种方式要考虑两种建模语言的差异，转换后模型的一致性问题，如VERSA、aadl2sync、Cheddar。对AADL 模型进行可调度性分析使用的方法有两种:第一种是根据模型所采用的调度方法进行静态分析，给出是否可调度的结论，如OSATE 中的Scheduling、VERSA;第二种是采用仿真的方法给出是否可调度结论，如aadl2sync。而Chedda 既可以采用分析，也可以采用仿真方法对模型的时序进行分析，并且Chedda 提供了方便、灵活的机制，允许使用者根据需要来对一种新的调度方法进行可调度性分析和仿真。

虽然目前针对AADL 模型的可调度性分析工具多种多样，但是集AADL 建模与分析为一体的建模工具却不是很多，目前只有OSATE、STOOD 具有此功能。其它分析工具都不具有AADL 建模功能，只能以AADL 模型为输入，进行分析。而且大多数分析工具也只是针对一些常用的调度方法进行分析。

为了方便使用，后续需要继续研究各种工具的集成问题，以及针对近年来关注较多的调度方法，如层次调度方法的研究。

［1］Peter Feiler.Architecture Analysis ＆ Design Language(AADL)［S］.Carnegie Mellon University:SAE Aerospace，2004.

［2］Software Engineering Institute ，Open Source AADL Tool Environment (OSATE)Online Help［R］.Carnegie Mellon University :Software Engineering Institute，2006.

［3］Duncan Clarke，VERSA:Verification，Execution and Rewrite System for ACSR［R］.Technical Report of University of Pennsylvania，1995.

［4］Erwan Jahier，Louis Mandel，Nicolas Halbwachs，and Pascal Raymond.The AADL2sync User Guide［R］.Unite Mixte de Recherche CNRS，2008，http://www－ verimag.imag.fr/DIST－TOOLS/SYNCHRONE/aadl2sync/aadl2sync－man.pdf.

［5］Frank Singhoff，Jér?me Legrand，Laurent Nana，Lionel Marcé，Cheddar 1.3 user＇s guide［R］.EA 2215 Team，2006，http://beru.univ－ brest.fr/～singhoff/cheddar/ug/cheddar－r1.pdf.

［6］F Singhoff，J Legrand，L Nana，L Marc＇e.Cheddar:a Flexible Real Time Scheduling Framework［C］.Proceedings of the ACM SIGADA International conference Proceedings，Atlanta，Georgia，USA，2004.

［7］F Singhoff，J Legrand，L Nana，L Marc'e.Scheduling and Memory requirements analysis with AADL［C］.Proceedings of the ACM SIGADA International conference Proceedings，Atlanta，Georgia，USA，2005.