Robust and sustainable schedulability analysis of embedded software

ABSTRACT

For real-time systems, most of the analysis involves efficient or exact schedulability checking. While this is important, analysis is often based on the assumption that the task parameters such as execution requirements and inter-arrival times between jobs are known exactly. In most cases, however, only a worst-case estimate of these quantities is available at the time of analysis. It is therefore imperative that schedulability analysis hold for better parameter values (Sustainable Analysis). On the other hand, if the task or system parameters turn out to be worse off, then the analysis should tolerate some deterioration (Robust Analysis). Robust analysis is especially important, because the implication of task schedulability is often weakened in the presence of optimizations that are performed on its code, or dynamic system parameters.

In this work, we define and address sustainability and robustness questions for analysis of embedded real-time software that is modeled by conditional real-time tasks. Specifically, we show that, while the analysis is sustainable for changes in the task such as lower job execution times and increased relative deadlines, it is not the case for code changes such as job splitting and reordering. We discuss the impact of these results in the context of common compiler optimizations, and then develop robust schedulability techniques for operations where the original analysis is not sustainable.

REFERENCES

• 1: Aloysius K. Mok , Wing-Chi Poon, Non-Preemptive Robustness under Reduced System Load, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.200-209, December 05-08, 2005 [doi>10.1109/RTSS.2005.31]
• 2: K. Altisen , G. Gössler , J. Sifakis, Scheduler Modeling Based on the Controller Synthesis Paradigm, Real-Time Systems, v.23 n.1-2, p.55-84, July-September 2002 [doi>10.1023/A:1015346419267]
• 3: Madhukar Anand , Arvind Easwaran , Sebastian Fischmeister , Insup Lee, Compositional Feasibility Analysis of Conditional Real-Time Task Models, Proceedings of the 2008 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing (ISORC), p.391-398, May 05-07, 2008 [doi>10.1109/ISORC.2008.47]
• 4: Preemptive Multiprocessor Scheduling Anomalies, Proceedings of the 16th International Symposium on Parallel and Distributed Processing, p.12, April 15-19, 2002
• 5: Sanjoy Baruah , Alan Burns, Sustainable Scheduling Analysis, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.159-168, December 05-08, 2006 [doi>10.1109/RTSS.2006.47]
• 6: Sanjoy K. Baruah, Dynamic- and Static-priority Scheduling of Recurring Real-time Tasks, Real-Time Systems, v.24 n.1, p.93-128, January 2003 [doi>10.1023/A:1021711220939]
• 7: S. K. Baruah, A General Model for Recurring Real-Time Tasks, Proceedings of the IEEE Real-Time Systems Symposium, p.114, December 02-04, 1998
• 8: Hanene Ben-Abdallah , Jin-Young Choi , Duncan Clarke , Young Si Kim , Insup Lee , Hong-Liang Xie, A Process Algebraic Approach to the Schedulability Analysisof Real-Time Systems, Real-Time Systems, v.15 n.3, p.189-219, Nov. 1998 [doi>10.1023/A:1008047130023]
• 9: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 10: Alan Burns and Sanjoy Baruah. Sustainability in real-time scheduling. Journal of Computing Science and Engineering, Vol 2(No. 1):72--94, 2008.
• 11: Giorgio Buttazzo, Achieving Scalability in Real-Time Systems, Computer, v.39 n.5, p.54-59, May 2006 [doi>10.1109/MC.2006.148]
• 12: G. C. Buttazzo and J. Stankovic. Red: A robust earliest deadline scheduling algorithm. In Proceedings of Third International Workshop on Responsive Computing Systems, 1993. URL citeseer.ist.psu.edu/buttazzo93red.html.
• 13: Ya-Shu Chen , Li-Pin Chang , Tei-Wei Kuo , Aloysius K. Mok, Real-time task scheduling anomaly: observations and prevention, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066881]
• 14: http://doi.acm.org/10.1145/1066677.1066881.
• 15: R. I. Davis , A. Burns, Robust Priority Assignment for Fixed Priority Real-Time Systems, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.3-14, December 03-06, 2007 [doi>10.1109/RTSS.2007.43]
• 16: Xiang (Alex) Feng , Aloysius K. Mok, A Model of Hierarchical Real-Time Virtual Resources, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.26, December 03-05, 2002
• 17: Christian Ferdinand , Reinhold Heckmann , Marc Langenbach , Florian Martin , Michael Schmidt , Henrik Theiling , Stephan Thesing , Reinhard Wilhelm, Reliable and Precise WCET Determination for a Real-Life Processor, Proceedings of the First International Workshop on Embedded Software, p.469-485, October 08-10, 2001
• 18: Arkadeb Ghosal , Alberto Sangiovanni-Vincentelli , Christoph M. Kirsch , Thomas A. Henzinger , Daniel Iercan, A hierarchical coordination language for interacting real-time tasks, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176887.1176907]
• 19: Daniel Iercan. TSL Compiler. Master's thesis, Politehnica University of Timisoara, September 2005.
• 20: Sheayun Lee , Insik Shin , Woonseok Kim , Insup Lee , Sang Lyul Min, A design framework for real-time embedded systems with code size and energy constraints, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.2, p.1-27, February 2008 [doi>10.1145/1331331.1331342]
• 21: J.Y.T. Leung and J. Whitehead. On the complexity of fixed-priority scheduling of periodic real-time tasks. Performance Evaluation, 2:37--250, 1982.
• 22: G. Lipari and E. Bini. Resource partitioning among real-time applications. In Proc. of Euromicro Conference on Real-Time Systems, July 2003.
• 23: S.P. Marlowe, T.J.; Masticola. Safe optimization for hard real-time programming. Systems Integration, 1992. ICSI '92., Proceedings of the Second International Conference on, pages 436--445, 15-18 Jun 1992. doi: 10.1109/ICSI.1992.217244.
• 24: Razvan Racu , Rolf Ernst, Scheduling Anomaly Detection and Optimization for Distributed Systems with Preemptive Task-Sets, Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, p.325-334, April 04-07, 2006 [doi>10.1109/RTAS.2006.40]
• 25: Ha Rhan and J.W.S. Liu. Validating timing constraints in multiprocessor and distributed real-time systems. Distributed Computing Systems,1994., Proceedings of the 14th International Conference on, pages 162--171, 21-24 Jun 1994. doi: 10.1109/ICDCS.1994.302407.
• 26: Insik Shin , Insup Lee, Periodic Resource Model for Compositional Real-Time Guarantees, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.2, December 03-05, 2003
• 27: R. Yerraballi, R. Mukkamala, K. Maly., and H.A. Wahab. Issues in schedulability analysis of real-time systems. Real-Time Systems, 1995. Proceedings., Seventh Euromicro Workshop on, pages 87--92, 14-16 Jun 1995. doi: 10.1109/EMWRTS.1995.514297.
• 28: Mohamed F. Younis , Thomas J. Marlowe , Grace Tsai , Alexander D. Stoyenko, Toward Compiler Optimization of Distributed Real-Time Processes, Proceedings of the 2nd IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '96), p.35, October 21-25, 1996

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Design, Theory

Keywords:
robust schedulability analysis, schedulability analysis, sustainable schedulability analysis