Page 90 - 《软件学报》2021年第6期

1664 Journal of Software 软件学报 Vol.32, No.6, June 2021

real-time system. A model-based architecture level schedulability evaluate and verification method, which is designed for priority based
PSRT system, is proposed in this study, in order to do cache resource constrained, and CPRD related schedulability evaluation based on
AADL system architecture model. In the first step, the study enhances the property set of AADL storage elements, so that to be
compatible with cache memory properties in system architecture model constructing. Secondly, the study proposes a set or algorithms to:
estimate the CPRDs of a task before it is completed; do system schedule simulation and construct the schedule sequence with the
constraint of Cache resource and CPRDs involved; and WCET estimation of the tasks in such a CPRD considered, preemptive-scheduling
execution sequence. Finally, methods mentioned above are implemented within a prototype software toolkit, which is designed to do
system level schedulability evaluation and verification with CPRD constraints considered. The toolkit is tested with a use case of aircraft
airborne open-architecture intelligent information system. The result shows that, compared with schedule sequence constructed without
cache memory resource constraints, the WCET estimated for most tasks are extended, and sequence order is changed. In some extreme
cases, when CPRD is taken into consideration, some tasks are evaluated to be incompletable. The test shows that the method and
algorithms proposed in this study are feasible.
Key words: AADL; complex embedded system; cache related preemption delay; resource constraint schedulability

复杂嵌入式实时系统广泛地应用于航空航天、汽车电子、远程医疗等安全攸关应用领域,它对系统可靠性、
安全性和实时性有着严格的要求,特别对实时性要求具有严格时间约束,通过使用截止期来对系统中任务的执
行时间进行描述,表示任务必须在此时间之前完成执行.因此,这类系统在设计初期就要求面向软件架构进行实
时性分析,根据分析结果来指导系统设计和实现,这对保障系统实时性有着积极的作用.
传统嵌入式系统可调度性判定是基于系统中每个任务的最坏执行时间(worst case execution time,简称
WCET)以及特定的调度算法,判断系统中各个任务的最坏响应时间能否满足截止期约束.WCET 可以表示为任
[1]
务在处理器上执行时间的上界 ,因此,在系统模型设计阶段进行实时性分析需估算任务的 WCET.然而,最坏的
执行时间又往往依赖于系统计算平台的多种资源约束,目前,在程序 WCET 估算的静态计算和动态计算中大多
[2]
只考虑处理器一种资源 .静态计算主要是通过获取到任务的控制流图,分析程序在执行过程中可能的最大路
[2]
径,然后得出任务的 WCET .动态计算则是通过多次运行程序,在每次运行过程中测试程序的执行时间,选取这
些测试结果中最大的执行时间作为该任务的 WCET.但是该过程是面向软件程序代码来计算 WCET,并不能在
软件需求规划和模型设计阶段对软件的可调度性进行分析和评价.
随着嵌入式系统复杂度越来越高,软件开发采用逐步求精、层次化建模的过程来保障软件非功能属性的实
现,软件非功能属性的保障是制约软件质量的一个重要挑战.近年来,人们提出一种新的架构设计与分析语言
(architecture analysis and design language,简称 AADL) [3,4] 来解决复杂系统非功能属性设计与分析困难的问题.
AADL 支持文本化和图形化的软件架构设计,采用自顶向下的系统工程思想,可以大大缩短开发周期并节约成
本.AADL 模型的可调度性验证是 AADL 非功能属性设计与验证的一个重要研究方向.AADL 模型可调度性验
证一般情况下是基于给定的某种调度算法,比如单调速率调度算法(rate monotonic schedule,简称 RMS)、最早截
止期优先调度算法(earliest deadline frist,简称 EDF)、固定优先级调度算法(fixed priority scheduling,简称 FPS)
等.一般情况下,应用程序执行过程中,任务的优先级会随着时间动态变化,那么在调度过程中则会根据任务优
先级的高低,动态进行调度.EDF 调度算法就是典型的优先级动态变化的调度策略,离截止期越近的任务优先级
越高.基于 EDF 调度策略,处理器利用率的可调度性计算方法也被提出来,即:只要任务集中的所有任务处理器
[5]
利用率之和小于 1,那么任务集在 EDF 调度策略下就是可调度的任务集 .
基于时间自动机模型的 AADL 模型可调度性分析逐渐成为一个研究复杂系统实时性保障的一种方法,它
利用时间自动机模型来模拟系统架构中各模型构件的动态行为,进而依据系统的实时性需求和行为规约对设
计的系统模型进行可调度性分析,这对于复杂系统的功能划分和早期设计的性能指标分解具有重要的指导意
义.一些国内外研究机构进行了卓有成效的尝试,例如:宾夕法尼亚大学开发的可调度性分析工具 VERSA
(verification execution and rewrite system for ACSR)将 AADL 模型自动转化为 ACSR 模型,并在 VERSA 工具中
[6]
建立线程的时间自动机模型,将处理器与访问连接建模为资源,数据、事件端口建模为通信通道 ;伊利诺大学
香槟分校开发的一种支持对实时系统进行形式化描述、仿真和分析的语言和工具 Real-Time Maude [7,8] ,其首先