Response Time Analysis of Embedded Systems by Taking Interrupt and Context Switch Overheads into Account
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (91118007, 61502031, 61632005)

  • Article
  • | |
  • Metrics
  • |
  • Reference [30]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Interrupt and context switch are basic mechanisms for multi-task scheduling in real-time and embedded systems. During schedulability analysis, the overheads of the interrupt and context switch should be considered in the calculation of tasks' worst-case response time. The current calculation methods of response time add interrupt as task with high priority, and simply add the overheads of context switch in the meantime. However, these methods neglect the details of practical systems and roughly give an inaccurate worst-case response time. In this paper, the mechanisms and time flow of interrupt and context switch are thoroughly described. In addition, their influence on tasks' critical instant is discussed. More importantly, a much more accurate calculation method for response time is presented. At last, simulations is conducted to validate the improvement in accuracy of this new method. The response time analysis accounting for scheduling overheads is extended in this paper for the resource-constrained hard real-time systems which need to accurately calculate the response time.

    Reference
    [1] Liu JWS. Real-Time Systems. Prentice Hall, 2000.
    [2] Yang MF, Gu B, Guo XY, Dong XG, Wang Z, Chen R. Aerospace embedded software dependability guarantee technology and application. Scientia Sinica Technologica, 2015,45(1):198-203(in Chinese with English abstract).[doi:10.1360/N092014-00485]
    [3] Joseph M, Pandya P. Finding response times in a real-time systems. The Computer Journal, 1986,29(5):390-395.
    [4] Audsley NC, Burns A, Richardson M, Tindell K, Wellings AJ. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 1993,8(5):284-292.
    [5] Regehr J. Safe and structured use of interrupts in real-time and embedded software. In:Lee I, Leung JYT, Son SH, eds. Handbook of Real-Time and Embedded Systems. Chapman and Hall/CRC Press, 2007.[doi:10.1201/9781420011746.ch16]
    [6] Brylow D, Palsberg J. Deadline analysis of interrupt-driven software. IEEE Trans. on Software Engineering, 2004,30(10):634-655.[doi:10.1109/TSE.2004.64]
    [7] Jonathan K, Dorsa S, Sanjit AS. Timing analysis of interrupt-driven programs under context bounds. In:Proc. of the Formal Methods in Computer-Aided Design (FMCAD). 2011.
    [8] Leyva-del-Foyo LE, Mejia-Alvarez P, Niz D. Integrated task and interrupt management for real-time systems. ACM Trans. on Embedded Computing Systems, 2012,11(2):1-31.[doi:10.1145/2220336.2220344]
    [9] Jeffay K, Stone DL. Accounting for interrupt handling costs in dynamic priority task sysetms. In:Proc. of the IEEE Real-Time Systems Symp. 1993. 212-221.
    [10] Sandström K, Eriksson C, Fohler G. Handling interrupts with static scheduling in an automotive vehicle control system. In:Proc. of the IEEE Int'l Conf. on Real-Time Systems and Applications (RTAS). 1998.
    [11] Brandenburg BB, Leontyev H, Anderson JH. An overview of interrupt accounting techniques for multiprocessor real-time systems. Journal of Systems Architecture, 2011,57:638-654.[doi:10.1016/j.sysarc.2010.05.011]
    [12] Cofer D, Rangarajan M. Formal verification of overhead accounting in an avionics RTOS. In:Proc. of the IEEE Real-Time Systems Symp. 2002. 181-190.[doi:10.1109/REAL.2002.1181573]
    [13] Bimbard F, George L. FP/FIFO feasibility conditions with kernel overheads for periodic tasks on an event driven OSEK system. In:Proc. of the IEEE Int'l Symp. on Object and Component-Oriented Real-Time Distributed Computing. 2006.[doi:10.1109/ISORC. 2006]
    [14] Katcher DI, Arakawa H, Strosnider JK. Engineering and analysis of fixed priority schedulers. IEEE Trans. on Software Engineering, 1993,19(9):920-934.[doi:10.1109/32.241774]
    [15] Burns A, Tindell K, Wellings A. Effective analysis for engineering real-time fixed priority schedulers. IEEE Trans. on Software Engineering, 1995,21(5):475-480.
    [16] Gabriëls R, Gerrits D. Accounting for overhead in fixed priority pre-emptive scheduling. Department of Mathematics & Computer Science, Technische Universiteit Eindhoven, 2007.
    [17] Echagüe J, Ripoll I, Crespo A. Hard real-time preemptively scheduling with high context switch cost. In:Proc. of the Euromicro Workshop on Real-Time Systems (ECRTS). 1995.[doi:10.1109/EMWRTS.1995.514310]
    [18] Yomsi PM, Sorel Y. Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems. In:Proc. of the Euromicro Conf. on Real-Time Systems (ECRTS). 2007.
    [19] Liu CL, Layland JW. Scheduling algorithms for mul-tiprogramming in a real-time environment. Journal of the ACM, 1973,20(1):46-61.
    [20] Bryant RE, O'Hallaron DR. Computer Systems:A Programmer's Perspective. 2nd ed., Prentice Hall, 2011.
    [21] Buttazzo GC. Hard Real-Time Computing Systems:Predictable Scheduling Algorithms and Applications. 3rd ed., Boston:Springer-Verlag, 2011.[doi:10.1007/b102312]
    [22] Yu GL, Yang MF, Xu J, Jiang H. Worst case response time analysis of multilevel interrupt systems. Chinese Space Science and Technology, 2016,36(2):28-36(in Chinese with English abstract).[doi:10.16708/j.cnki.1000-758X.2016.0003]
    [23] LEON3. http://www.gaisler.com/
    [24] Yu GL, Yang MF. Timing analysis of register windows traps for real time system based on SPARC. Aerospace Control, 2015,33(6):70-75(in Chinese with English abstract).[doi:1006-3242(2015)06-0070-06]
    [25] Baker TP, Shaw A. The cyclic executive model and ada. In:Proc. of the IEEE Real-Time Systems Symp. (RTSS'88). 1988.
    [26] MAST. http://mast.unican.es/
    附中文参考文献:
    [2] 杨孟飞,顾斌,郭向英,董晓刚,王政,陈睿.航天嵌入式软件可信保障技术及应用研究.中国科学:技术科学,2015,45(2):198-203.
    [22] 于广良,杨孟飞,徐建,姜宏.面向多级中断系统的任务最差响应时间分析.中国空间科学技术,2016,36(2):28-36.
    [24] 于广良,杨孟飞.基于SPARC的实时系统寄存器窗口溢出时间分析.航天控制,2015,33(6):70-75
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

于广良,杨孟飞.考虑中断和上下文切换开销的响应时间分析.软件学报,2018,29(6):1681-1698

Copy
Share
Article Metrics
  • Abstract:3523
  • PDF: 7405
  • HTML: 3676
  • Cited by: 0
History
  • Received:July 01,2017
  • Revised:September 01,2017
  • Adopted:November 06,2017
  • Online: December 28,2017
You are the first2044807Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063