多处理器实时系统可调度性分析的UPPAAL模型
作者:
基金项目:

国家自然科学基金(61332001, 61272104); 四川省应用基础研究项目(2014JY0112)


Schedulability Analysis Model for Multiprocessor Real-Time Systems Using UPPAAL
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [30]
  • |
  • 相似文献
  • | | |
  • 文章评论
    摘要:

    随着多处理器实时系统在安全性攸关系统中的广泛应用,保证这类系统的正确性成为一项重要的工作.可调度性是实时系统正确性的一项关键性质.它表示系统必须满足的一些时间要求.传统的可调度性分析方法结论保守或者不完备,为了避免这些方法的缺陷,提出使用模型检测的方法来实现可调度性分析.提出了一个用于多处理器实时系统可调度性分析的模板,将与系统可调度性相关的部分包括实时任务、运行平台和调度管理模块都用时间自动机建模,并使用UPPAAL验证可调度的性质是否总被满足.符号化模型检测方法被用于推断可调度性,但是由于秒表触发的近似机制,符号化模型检测方法不能用于证明系统不可调度.作为补充,统计模型检测方法被用于估算系统不可调度的概率,并在系统不可调度时生成反例.此外,在系统可调度时,通过统计模型检测方法获取一些性能相关的信息.

    Abstract:

    As multiprocessor real-time systems are increasingly applied in safety critical systems, it's important to ensure the correctness of such systems. One key attribute of the correctness of real-time system is the schedulability that guarantees to satisfy the timing requirements. The traditional methods for determining the schedulability are either pessimistic or unsafe. To tackle the drawbacks of those methods, this paper proposes a scheme to achieve the schedulability analysis using model checking. It provides a schedulability analysis framework for multiprocessor real-time system. All the components involved in the schedulability of the system, including the tasks, the execution infrastructure and the dispatching management unit, are modeled as timed automata and implemented in UPPAAL. Further, UPPAAL is employed to verify whether the schedulability property is always satisfied. Symbolic model checking is applied to determine schedulability. However, because of the over-approximation for stopwatches, symbolic model checking cannot be used to disprove schedulability. As a supplement, statistical model checking is used to estimate the probability of non-schedulability and generate concrete counterexamples going along with non-schedulability. Statistical model checking is also used to obtain some performance information when system is schedulable.

    参考文献
    [1] Guan N, Gu ZH, Lü MS, Deng QX, Yu G. Schedulability analysis of global fixed-priority or EDF multiprocessor scheduling with symbolic model-checking. In: Pettit R, ed. Proc. of the 11th IEEE Symp. on Object Oriented Real-Time Distributed Computing (ISORC 2008). IEEE Computer Society, 2008. 556-560.[doi: 10.1109/ISORC.2008.74]
    [2] Brekling A, Hansen MR, Madsen J. Models and formal verification of multiprocessor system-on-chips. The Journal of Logic and Algebraic Programming, 2008,77(1):1-19.[doi: 10.1016/j.jlap.2008.05.002]
    [3] Li RF, Liu Y, Xu C. A survey of task scheduling research progress on multiprocessor system-on-chip. Journal of Computer Research and Development, 2008,45(9):1620-1629 (in Chinese with English abstract).
    [4] David A, Illum J, Kim GL, Skou A. Model-Based framework for schedulability analysis using UPPAAL 4.1. In: Mosterman PJ, ed. Proc. of the Model-Based Design for Embedded Systems. Boca Raton: CRC Press, 2010. 93-119.
    [5] Schmitz MT, Al-Hashimi BM, Eles P. System-Level Design Techniques for Energy-Efficient Embedded Systems. Springer-Verlag, 2004.[doi: 10.1007/b106642]
    [6] Carpenter J, Funk S, Holman P, Srinivasan A, Anderson J, Baruah S. A Categorization of Real-time Multiprocessor Scheduling Problems and Algorithms. In: Joseph YT, ed. Handbook of Scheduling: Algorithms, Models and Performance Analysis. Boca Raton: Chapman and Hall/CRC Press, 2004. 641-659.
    [7] Behrmann G, David A, Larsen KG. A tutorial on UPPAAL. In: Bernardo M, ed. Proc. of the Formal Methods for the Design of Real-Time Systems. Springer-Verlag, 2004. 200-236.[doi: 10.1007/978-3-540-30080-9_7]
    [8] Davis RI, Burns A. A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys, 2011,43(4):1-44.[doi: 10.1145/1978802.1978814]
    [9] Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM (JACM), 1973,20(1):46-61.[doi: 10.1145/321738.321743]
    [10] Tindell K, Clark J. Holistic schedulability analysis for distributed hard real-time systems. Microprocessing and Microprogramming, 1994,40(2-3):117-134.[doi: 10.1016/0165-6074(94)90080-9]
    [11] Mikučionis M, Larsen KG, Rasmussen JI, Nielsen B, Skou A, Palm SU, Pedersen JS, Hougaard P. Schedulability analysis using UPPAAL: Herschel-Planck case, study. In: Margaria T, ed. Proc. of the Leveraging Applications of Formal Methods, Verification, and Validation. Springer-Verlag, 2010. 175-190.[doi: 10.1007/978-3-642-16561-0_21]
    [12] Boudjadar A, David A, Kim JH, Kim LG, Mikučionis M, Nyman U, Skou A. Hierarchical scheduling framework based on compositional analysis using UPPAAL. In: Fiadeiro JL, ed. Proc. of the Formal Aspects of Component Software. Springer-Verlag, 2014. 61-78.[doi: 10.1007/978-3-319-07602-7_6]
    [13] David A, Larsen KG, Legay A, Mikučionis M. Schedulability of Herschel-Planck revisited using statistical model checking. In: Margaria T, ed. Proc. of the Leveraging Applications of Formal Methods, Verification and Validation. Applications and Case Studies. Springer-Verlag, 2012. 293-307.[doi: 10.1007/978-3-642-34032-1_28]
    [14] Alur R, Dill DL. A theory of timed automata. Theoretical Computer Science, 1994,126(2):183-235.[doi: 10.1016/0304-3975(94) 90010-8]
    [15] Bengtsson J, Wang Y. Timed automata: Semantics, algorithms and tools. In: Desel J, ed. Proc. of the Lectures on Concurrency and Petri Nets: Advances in Petri Nets. Berlin: Springer-Verlag, 2004. 87-124.[doi: 10.1007/978-3-540-27755-2_3]
    [16] Cassez F, Kim LG. The impressive power of stopwatches automata. In: Palamidessi C, ed. Proc. of the CONCUR 2000—Concurrency Theory. Berlin: Springer-Verlag, 2000. 138-52.[doi: 10.1007/3-540-44618-4_12]
    [17] Legay A, Delahaye B, Bensalem S. Statistical model checking: An overview. In: Barringer H, ed. Proc. of the Runtime Verification. Springer-Verlag, 2010. 122-135.[doi: 10.1007/978-3-642-16612-9_11]
    [18] Clarke EM, Jr. Grumberg O, Peled DA. Model Checking. London: MIT Press, 1999.
    [19] Bulychev P, David A, Larsen KG, Mikučionis M, Poulsen DB, Legay A, Wang Z. UPPAAL-SMC: Statistical model checking for priced timed automata. In: Herbert W, ed. Proc. of the 10th Workshop on Quantitative Aspects of Programming Languages and Systems. Tallinn: Electronic Proceedings in Theoretical Computer Science, 2012. 1-16.[doi: 10.4204/EPTCS.85.1]
    [20] Bulychev P, David A, Larsen KG, Legay A, Li GY, Poulsen DB, Stainer A. Monitor-Based statistical model checking for weighted metric temporal logic. In: Bjorner N, ed. Proc. of the Logic for Programming, Artificial Intelligence, and Reasoning. Springer-Verlag, 2012. 168-182.[doi: 10.1007/978-3-642-28717-6_15]
    [21] UPPAAL HELP. 2014. http://www.uppaal.org/
    [22] Jensen K, Kristensen LM, Mailund T. The sweep-line state space exploration method. Theoretical Computer Science, 2012,429: 169-179.[doi: 10.1016/j.tcs.2011.12.036]
    [23] Clarke EM, Zuliani P. Statistical model checking for cyber-physical systems. In: Bultan T, ed. Proc. of the Automated Technology for Verification and Analysis. Springer-Verlag, 2011. 1-12.[doi: 10.1007/978-3-642-24372-1_1]
    [24] Buttazzo GC. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. 3rd ed., New York: Springer-Verlag, 2011.[doi: 10.1007/978-1-4614-0676-1]
    [25] Joseph M, Pandya P. Finding response times in a real-time system. The Computer Journal, 1986,29(5):390-395.[doi: 10.1093/ comjnl/29.5.390]
    [26] Amnell T, Fersman E, Mokrushin L, Pettersson P, Wang Y. TIMES: A tool for schedulability analysis and code generation of real-time systems. In: Larsen KG, ed. Proc. of the Formal Modeling and Analysis of Timed Systems. Springer-Verlag, 2003. 60-72.[doi: 10.1007/978-3-540-40903-8_6]
    [27] Fersman E, Krcal P, Pettersson P, Yi W. Task automata: Schedulability, decidability and undecidability. Information and Computation, 2007,205(8):1149-1172.[doi: 10.1016/j.ic.2007.01.009]
    [28] Fersman E, Mokrushin L, Pettersson P, Yi W. Schedulability analysis of fixed-priority systems using timed automata. Theoretical Computer Science, 2006,354(2):301-317.[doi: 10.1016/j.tcs.2005.11.019]
    [29] Krcal P, Stigge M, Yi W. Multi-Processor schedulability analysis of preemptive real-time tasks with variable execution times. In: Raskin JF, ed. Proc. of the Formal Modeling and Analysis of Timed Systems. Springer-Verlag, 2007. 274-289.[doi: 10.1007/978-3-540-75454-1_20]
    [30] Guan N, Gu ZH, Deng QX, Gao SH, Yu G. Exact schedulability analysis for static-priority global multiprocessor scheduling using model-checking. In: Obermaisser R, eds. Proc. of the Software Technologies for Embedded and Ubiquitous Systems. Springer-Verlag, 2007. 263-272.[doi: 10.1007/978-3-540-75664-4_26]
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

代声馨,洪玫,郭兵,杨秋辉,黄蔚,徐保平.多处理器实时系统可调度性分析的UPPAAL模型.软件学报,2015,26(2):279-296

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

京公网安备 11040202500063号