Abstract
Traditional timing analysis techniques rely on composing system-level worst-case behavior with local worst-case behaviors of individual components. In many complex real-time systems, no single local worst-case behavior exists for each component and it generally requires to enumerate all the combinations of individual local behaviors to find the global worst case. This paper presents a scalable timing analysis technique based on abstraction refinement, which provides effective guidance to significantly prune away state space and quickly verify the desired timing properties. We first establish the general framework of the method, and then apply it to solve the analysis problem for several different real-time task models.
Chapter PDF
Similar content being viewed by others
References
Amnell, T., Fersman, E., Mokrushin, L., Pettersson, P., Yi, W.: TIMES - A tool for modelling and implementation of embedded systems. In: Katoen, J.-P., Stevens, P. (eds.) TACAS 2002. LNCS, vol. 2280, pp. 460–464. Springer, Heidelberg (2002)
Baruah, S.K., Mok, A., Rosier, L.: Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings of the 11th Real-Time Systems Symposium (RTSS) (1990)
Bengtsson, J.E., Yi, W.: Timed automata: Semantics, algorithms and tools. In: Desel, J., Reisig, W., Rozenberg, G. (eds.) ACPN 2003. LNCS, vol. 3098, pp. 87–124. Springer, Heidelberg (2004)
Buttazzo, G.C., Bini, E., Buttle, D.: Rate-adaptive tasks: Model, analysis, and design issues. Technical Report (2013)
Davis, R.I., Feld, T., Pollex, V., Slomka, F.: Schedulability tests for tasks with variable rate-dependent behaviour under fixed priority scheduling. In: the 20th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS) (2014)
Fersman, E., Krcal, P., Pettersson, P., Yi, W.: Task automata: Schedulability, decidability and undecidability. Information and Computation (2007)
Guan, N., Yi, W.: Finitary real-time calculus: Efficient performance analysis of distributed embedded systems. Proceedings of the IEEE 34th Real-Time Systems Symposium (RTSS) (2013)
Joseph, M., Pandya, P.K.: Finding response times in a real-time system. The Computer Journal (1986)
Larsen, K.G., Pettersson, P., Yi, W.: Uppaal in a nutshell. International Journal on Software Tools for Technology Transfer, STTT (1997)
Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM (1973)
Pollex, V., Feld, T., Slomka, F., Margull, U., Mader, R., Wirrer, G.: Sufficient real-time analysis for an engine control unit with constant angular velocities. In: Design, Automation and Test Conference in Europe (DATE) (2013)
Stigge, M., Ekberg, P., Guan, N., Yi, W.: The digraph real-time task model. In: Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 71–80. IEEE (2011)
Martin, Stigge, N.G., Yi, W.: Refinement-based exact response-time analysis. In: the 26th EUROMICRO Conference on Real-Time Systems (ECRTS) (2014)
Martin Stigge and Wang Yi. Hardness results for static priority real-time scheduling. In: Proceedings of the 24th Euromicro Conference on Real-Time Systems (ECRTS), pp. 189–198. IEEE (2012)
Stigge, M., Yi, W.: Combinatorial abstraction refinement for feasibility analysis. In: Procedings of the 34th IEEE Real-Time Systems Symposium (RTSS), pp. 340–349 (2013)
Thiele, L., Chakraborty, S., Naedele, M.: Real-time calculus for scheduling hard real-time systems. In: Proc. Inti. Symposium on Circuits and Systems (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guan, N., Tang, Y., Abdullah, J., Stigge, M., Yi, W. (2015). Scalable Timing Analysis with Refinement. In: Baier, C., Tinelli, C. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2015. Lecture Notes in Computer Science(), vol 9035. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46681-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-662-46681-0_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46680-3
Online ISBN: 978-3-662-46681-0
eBook Packages: Computer ScienceComputer Science (R0)