面向AADL模型的存储资源约束可调度性分析
作者:
作者简介:

陆寅(1975-),男,博士,讲师,CCF专业会员,主要研究领域为嵌入式系统架构,嵌入式系统可靠性工程.
习乐琪(1996-),男,硕士,主要研究领域为嵌入式系统资源调度,嵌入式可信属性分析.
秦树东(1995-),男,硕士,CCF学生会员,主要研究领域为嵌入式系统分功能属性分析,嵌入式系统可靠性工程.
董云卫(1968-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为嵌入式软件设计与验证,信息物理融合,系统建模与分析.

通讯作者:

董云卫,yunweidong@nwpu.edu.cn

基金项目:

国家自然科学基金(61772423)


On Schedulability Analysis of AADL Architecture with Storage Resource Constraint
Author:
Fund Project:

National Natural Science Foundation of China (61772423)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [26]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    嵌入式实时系统在安全关键领域变得越来越重要,其广泛应用于航空航天、汽车电子等具有严格时间约束的实时系统中.随着嵌入式系统的复杂度越来越高,在系统开发的早期设计阶段就需要对其可调度性进行分析评估.系统中的存储资源会对可调度性产生一定影响,在抢占式实时嵌入式系统引入缓存后,任务的最坏执行时间可能发生变化.因此,分析缓存相关抢占延迟对实时嵌入式系统的可调度性影响,一直以来是困扰大规模复杂系统架构设计的一个技术难题.提出一种面向软件架构级别、基于抢占调度序列的缓存相关抢占延迟计算方法,用来分析缓存相关抢占延迟约束下AADL (架构分析和设计语言)模型的可调度性.扩展了AADL关于存储资源架构设计的模型元素,来支持对缓存属性进行建模,提出一种基于模型构件进行抢占序列排序、缓存相关抢占延迟时间计算和被抢占任务最坏执行时间的估算方法,来对系统架构各功能构件在共享系统存储资源下系统的可调度性进行分析.还实现了分析缓存相关抢占延迟约束下的系统任务可调度性分析工具原型,并以某型飞机机载开放式智能信息系统为例,在航空电子系统架构设计中进行尝试,验证了该方法的在复杂系统设计中的对实时性分析的可行性.

    Abstract:

    The embedded system has been wildly applied in real-time automatic control systems, and most of these systems are safety-critical. For example, the engine control systems in an automobile, and the avionics in an airplane. It is very important to verify the schedulability property of such real-time embedded system in its early design stages, so that to avoid unexpected loss for the debugging of architecture design frictions. However, it has been proved to be a tough challenge to evaluate the schedulability of a PSRT (preemptive-scheduling real-time) system, especially when taking the constraints of system resources into consideration. The cache memory build inside the processor is such a kind of exclusive-accessing resource that is shared by all the tasks deployed on the processor. In addition, the CPRD (cache-related preemption delay) caused by preemptive task scheduling will bring extra time to the execution time to all the tasks. Thus, the CPRD should be taken into consideration when estimating the WCET (worst case executing time) of tasks in a 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.

    参考文献
    [1] Liu YF, Zhang LC. Worst-Case execution time analysis for real-time systems. Application Research of Computers, 2005,22(11):16-18(in Chinese with English abstract).
    [2] Zhou GC, Guo BL, Gao X, et al. Fast estimation of WCET based on distribution function. Computer Science, 2016,43:157-161(in Chinese with English abstract).
    [3] SAE. Architecture analysis and design language (AADL) AS-5506A. The Engineering Society for Advancing Mobility and Sea Air and Space, Aerospace lnfonnation Report. Version 2.0. Tech. Rep. 2009.
    [4] Yang ZB, Pi L, Hu K, Gu ZH, Ma DF. AADL:An architecture design and analysis language for complex embedded real-time systems. Ruan Jian Xue Bao/Journal of Software, 2010,21(5):899-915(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3700.htm
    [5] Zhang J. Research on the earliest deadline priority real-time scheduling algorithm[Ph.D. Thesis]. Wuhan:Huazhong University of Science and Technology, 2009(in Chinese with English abstract).
    [6] Clarke D, Lee I, Xie H L. VERSA:A tool for the specification and analysis of resource-bound real-time systems. Nonlinear Dynamics, 2016,87(1):1-7.
    [7] Clavel M, et al. Maude Manuel. Version 2.1. Menlo Park:SRI Int'l, 2004. http://maude.cs.uiuc.edu
    [8] Jerad C, Barkaoui K, Grissa-Touzi A. On the use of real-time Maude for architecture description and verification:A case study. In:Proc. of the Visions of Computer Science-bcs Int'l Academic Conf. DBLP, 2015.
    [9] Hu K, Duan ZB, Wang JY, Ga LC, Shang LH. Template-Based AADL automatic code generation. Frontiers of Computer Science in China, 2019,13(4):698-714.
    [10] Singhoff F, Legrand J, Nana L, et al. Scheduling and memory requirements analysis with AADL. In:Proc. of the ACM Sigada Int'l Conf. on Ada:The Engineering of Correct & Reliable Software for Real-time & Distributed Systems Using Ada & Related Technologies. ACM, 2005. 1-10.
    [11] Zhen-Song LI. Research on verification method of AADL behavior model based on UPPAAL. Computer Science, 2012.
    [12] Ma BZ. The worst response time analysis considering the impact of cache replacement[Ph.D. Thesis]. Changsha:Hu'nan University, 2013(in Chinese with English abstract).
    [13] Tran HN, Singhoff F. Instruction cache in hard real-time systems:Modeling and integration in scheduling analysistools with AADL. In:Proc. of the Embedded and Ubiquitous Computing. IEEE, 2014. 104-111.
    [14] Lee CG, Hahn H, Seo YM. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. In:Proc. of the IEEE Computer Society. 1998. 700-713.
    [15] Delange J, Pautet L, Plantec A, et al. Validate, simulate, and implement ARINC653 systems using the AADL. ACM SIGAda Ada Letters, 2009,29(3):31-44.
    [16] Dimpsey RT, Iyer RK. Modeling and measuring multiprogramming and system overheads on a shared-memory multiprocessor:Case study. Journal of Parallel and Distributed Computing, 1991,12(4):402-414.
    [17] Tran HN, Singhoff F, Rubini S. Cache-Aware real-time scheduling simulator:Implementation and return of experience. ACM SIGBED Review, 2016,13(1):22-28.
    [18] Li C, Ding C, Shen K. Quantifying the cost of context switch. In:Proc. of the Workshop on Experimental Computer Science, Part of ACM FCRC. San Diego:ACM, 2007. 1-4.
    [19] Bastoni A, Brandenburg B, Anderson JH. Is semi-partitioned scheduling practical. In:Proc. of the Euromicro Conf. on Real-time Systems. IEEE Computer Society, 2011. 1-11.
    [20] Bini E, Buttazzo GC. Measuring the performance of schedulability tests. Real-time Systems, 2005,30(1-2):129-154.
    附中文参考文献:
    [1] 刘育芳,张立臣.实时系统最坏执行时间分析.计算机应用研究,2005,22(11):16-18.
    [2] 周国昌,郭宝龙, 高翔等. 基于分布函数的WCET快速估计.计算机科学,2016,43:157-161.
    [4] 杨志斌,皮磊,胡凯,等.复杂嵌入式实时系统体系结构设计与分析语言:AADL.软件学报,2010,21(5):899-915. http://www.jos.org.cn/1000-9825/3700.htm[doi:10.3724/SP.J.1001.2010.03700]
    [5] 张杰.最早截止期优先实时调度算法研究[博士学位论文].武汉:华中科技大学,2009.
    [12] 马炳周.考虑缓存替换影响的最坏响应时间分析研究[博士学位论文].长沙:湖南大学,2013.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

陆寅,秦树东,习乐琪,董云卫.面向AADL模型的存储资源约束可调度性分析.软件学报,2021,32(6):1663-1681

复制
分享
文章指标
  • 点击次数:1518
  • 下载次数: 4799
  • HTML阅读次数: 3241
  • 引用次数: 0
历史
  • 收稿日期:2020-08-31
  • 最后修改日期:2020-10-26
  • 在线发布日期: 2021-02-07
  • 出版日期: 2021-06-06
文章二维码
您是第19780646位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号