DOI: https://doi.org/10.15802/stp2018/133384

RESEARCH OF LIMIT TIME INDICES OF SOFTWARE ENVIRONMENTS OF REAL TIME OPERATING SYSTEMS

V. Y. Nechay, D. О. Voloshyn, O. I. Nezhumira

Abstract


Purpose. More than 20 years of the Worst Case Execution Time (WCET) studies have led to the development of many methods for its evaluation. So far, there are no definitive conclusions about usage of these methods. Therefore, the purpose of this paper is to determine the possibility of using a hybrid method for estimating WCET in real-time systems. Methodology. The approach for evaluating WCET for a hybrid method is to parse the input code in the C++ programming language and, after constructing the control flow graph, get the execution time of its base blocks. After finding the longest way of the graph, to estimate the time of execution of this way and get the WCET evaluation. To find the longest-running way, the reverse Dijkstra algorithm was chosen. After that, there was made a comparison of the limiting time estimations that were obtained by static and hybrid methods, as well as an analysis of the discrepancy between these results. Findings. Determining the worst execution time of programs is most important for "hard real-time" tasks. Underestimation of this indicator can lead to catastrophic consequences. An overestimation – to a significant overexpenditure of resources. Therefore, WCET was evaluated using static and dynamic methods. It was determined that the results obtained by the two methods correlate well. For the class of tasks that are under consideration, WCET execution time can be determined using a hybrid method. Adding an extra time of 15–20 % to the results, obtained by the hybrid method, allows getting a foolproof estimate of WCET in real-time systems. Originality. The hybrid method has been existing for some time, but the reliability of its use has not been sufficiently studied yet. The given study makes a step in determining the practical applicability of the hybrid method for time estimation of real-time tasks. Practical value. The results of this research allow us to conclude that a hybrid method could be used for obtaining WCET in "hard real-time" tasks. Furthermore, some unknown at this moment influence of the OS RT environment can be taken into account by adding extra time.


Keywords


worst case execution time (WCET); real-time operating systems (OS RT); real-time tasks; hybrid method; static method; dynamic method

References


Balashov, V. V. (undated). Vstroennye informatsionno-upravlyayushchie sistemy realnogo vremeni. Lektsiya 3: Otsenka naikhudshego vremeni vypolneniya programm (WCET). Retrieved from http://lvk.cs.msu.su/~sveta/Балашов_3_Оценка_WCET.pdf (in Russian)

Kozyrev, V. P. (2016). Estimation of the execution time in real-time systems. Programming, 42(1), 39-50. (in Russian)

Betts, A. (2010). Hybrid Measurement-Based WCET Analysis using Instrumentation Point Graphs. PhD thesis. University of York, Heslington. (in English)

Corti, M., Brega, R., & Gross, T. (2001). Approximation of Worst-Case Execution Time for Preemptive Multitasking Systems. In Languages, Compilers, and Tools for Embedded Systems. Lecture Notes in Computer Science (pp. 178-198). Berlin. doi: 10.1007/3-540-45245-1_12 (in English)

Damschen, M., Bauer, L., & Henkel, J. (2016). Extending the WCET Problem to Optimize for Runtime-Reconfigurable Processors. ACM Transactions on Architecture and Code Optimization, 13(4), 1-24. doi: 10.1145/3014059 (in English)

Damschen, M., Bauer, L., & Henkel, J. (2017). Timing Analysis of Tasks on Runtime Reconfigurable Processors. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25(1), 294-307. doi: 10.1109/TVLSI.2016.2572304 (in English)

Fellger, W., Gepperth, S., & Krause, F. (2011). Comparison of WCET Tools: Fachstudie Nr. 142. Stuttgart: Institute of Software Technology University of Stuttgart. (in English)

Lokuciejewski, P., & Marwedel, P. (2011). Worst-Case Execution Time Aware Compilation Techniques for Real-Time Systems. New York: Springer. doi: 10.1007/978-90-481-9929-7 (in English)

Puschner, P., & Nossal, R. (1998). Testing the results of static worst-case execution-time analysis. Proceedings of the IEEE Real-Time Systems Symposium, December 02-04, 134-143. doi: 10.1109/real.1998.739738 (in English)

Sewell, T., Kam, F., & Heiser, G. (2017). High-assurance timing analysis for a high-assurance real-time operating system. Real-Time Systems, 53(5), 812-853. doi: 10.1007/s11241-017-9286-3 (in English)

Stappert, F., & Altenbernd, P. (2000). Complete worst-case execution time analysis of straight-line hard real-time programs. Journal of Systems Architecture, 46(4), 335-339. doi: 10.1016/S1383-7621(99)00010-7 (in English)

Wilhelm, R., Engblom, J., & Ermedahl, A. (2008). The worst-case execution time problem – overview of methods and survey oftools. Transaction on Embedded Computing Systems, 7(3). doi:10.1145/1347375.1347389 (in English)


GOST Style Citations


  1. Балашов, В. В. Встроенные информационно-управляющие системы реального времени. Лекция 3: Оценка наихудшего времени выполнения программ (WCET) [Електронний ресурс] / В. В. Балашов ; каф. АСВК, Лаборатория Вычислительных Комплексов, МГУ им. В. М. Ломоносова. – Режим доступу: http://lvk.cs.msu.su/~sveta/Балашов_3_Оценка_WCET.pdf. – Назва з екрана. – Перевірено : 31.05.2018.
  2. Козырев, В. П. Методы оценки времени выполнения в системах реального времени / В. П. Козырев // Программирование. – 2016. – Т. 42, № 1. – С. 39–50.
  3. Betts, A. Hybrid Measurement-Based WCET Analysis using Instrumentation Point Graphs : PhD. Тhesis /
    A. Betts ; University of York. – Heslington, 2010. – 208 р.
  4. Corti, M. Approximation of Worst-Case Execution Time for Preemptive Multitasking Systems / Matteo Corti, Roberto Brega, Thomas Gross // Languages, Compilers, and Tools for Embedded Systems. – Berlin, 2001. –
     Р. 178–198. doi: 10.1007/3-540-45245-1_12
  5. Damschen, M. Extending the WCET Problem to Optimize for Runtime-Reconfigurable Processors / Marvin Damschen, Lars Bauer, Jörg Henkel // ACM Transactions on Architecture and Code Optimization. – 2016. – Vol. 13. – Iss. 4. – Р. 1–24. doi: 10.1145/3014059
  6. Damschen, M. Timing Analysis of Tasks on Runtime Reconfigurable Processors / Marvin Damschen, Lars Bauer, Jorg Henkel // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. – 2017. – Vol. 25. – Iss. 1. – P. 294–307. doi: 10.1109/TVLSI.2016.2572304
  7. Fellger, W. Comparison of WCET Tools / W. Fellger, S. Gepperth, F. Krause ; Institute of Software Technology University of Stuttgart. – Stuttgart, 2011. – 45 р.
  8. Lokuciejewski, P. Worst-Case Execution Time Aware Compilation Techniques for Real-Time Systems / P. Lokuciejewski, P. Marwedel. – Dordrecht : Springer, 2011. – 262 р. doi: 10.1007/978-90-481-9929-7
  9. Puschner, P. Testing the results of static worst-case execution-time analysis / P. Puschner, R. Nossal // Real-Time Systems Symposium : Proc. of the 19th Conf. (Washington, December 02–04, 1998). – Washington, 1999. – P. 134–143. doi: 10.1109/real.1998.739738
  10. Sewell, T. High-assurance timing analysis for a high-assurance real-time operating system / T. Sewell, F. Kam, G. Heiser // Real-Time Systems. – 2017. – Vol. 53. – Iss. 5. – P. 812–853. doi: 10.1007/s11241-017-9286-3
  11. Stappert, F. Complete worst-case execution time analysis of straight-line hard real-time programs / F. Stappert, P. Altenbernd // Journal of Systems Architecture. – 2000. – Vol. 46. – Iss. 4. – P. 339–355.
    doi: 10.1016/S1383-7621(99)00010-7
  12. Wilhelm, R. The worst-case execution time problem – overview of methods and survey oftools / R. Wilhelm, J. Engblom, A. Ermedahl // Transaction on Embedded Computing Systems. – 2008. – Vol. 7. – Iss. 3.
    Р. 1–53. doi: 10.1145/1347375.1347389




Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN 2307–3489 (Print)
ІSSN 2307–6666 (Online)