Abstract
Predictable system behaviour is a necessary (but not sufficient) condition when creating safety-critical and safety-related embedded systems. At the heart of such systems there is usually a form of scheduler: the use of time-triggered schedulers is of particular concern in this paper. It has been demonstrated in previous studies that the problem of determining the task parameters for such a scheduler is NP-hard. We have previously described an algorithm (“TTSA1”) which is intended to address this problem. This paper describes an extended version of this algorithm (“TTSA2”) which employs task segmentation to increase schedulability. We show that the TTSA2 algorithm is highly efficient when compared with alternative “branch and bound” search schemes.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Domaratsky, Y., Perevozchikov, M.: Highly dependable time-triggered operating system-static scheduling approach and effective run-time implementations, Dedicated Systems Magazine, pp. 77–84 (October-December 2000)
Kopetz, H.: Real-Time Systems, Design Principles for Distributed Embedded Applications. Kluwer Academic, Dordrecht (1997)
Pont, M.J.: Patterns For Time-Triggered Embedded Systems. Addison-Wesley, Reading (2001)
Scheler, F., Schröder-Preikschat, W.: Time-Triggered vs. Event-Triggered: A matter of configuration? In: Dulz, W., Schröder-Preikschat, W. (eds.) MMB Workshop Proceedings (GI/ITG Workshop on Non-Functional Properties of Embedded Systems Nuremberg, pp. 107–112. VDE Verlag, Berlin (2006) ISBN 978-3-8007-2956-2
Albert, A.: Comparison of Event-Triggered and Time-Triggered Concepts with Regard to Distributed Control Systems, Embedded World 2004, Nuremberg, WEKA Verlag, pp. 235–252 (2004)
Xu, J.: Making Software Timing Properties Easier to Inspect and Verify. IEEE Software 20(4), 34–41 (2003)
Xu, J., Parnas, D.L.: Priority Scheduling Versus Pre-Run-Time Scheduling. Int. Journal of Time-Critical Systems 18, 7–23 (2000)
Baker, T.P., Shaw, A.: The Cyclic Executive Model and Ada. Real-Time Systems 1(1), 7–25 (1989)
Tindell, K., Burns, A., Wellings, A.: Allocating Hard Real-Time Tasks: An NP-Hard Problem Made Easy. Real-Time Systems 4(2), 145–165 (1992)
Baruah, S.K.: The Non-Preemptive Scheduling of Periodic Tasks Upon Multiprocessors. Real-Time Systems 32(1-2), 9–20 (2006)
Gendy, A.K., Pont, M.J.: Automatically Configuring Time-Triggered Schedulers for Use with Resource-Constrained, Single-Processor Embedded Systems. IEEE Trans. on Industrial Informatics 4(1), 37–46 (2008)
Gangoiti, U., Marcos, M., Estévez, E.: Using Cyclic Executives for Achieving Closed Loop Co-Simulation. In: Proc. of the Joint 44th IEEE Control and Decision Conference and European Control Conference CDC-ECC 2005, Sevilla, pp. 3790 –4785 (2005)
Buttazzo, G.C.: Rate monotonic vs. EDF: Judgement day. Real-Time Systems 29(1), 5–26 (2005)
Huang, C., Chang, L., Kuo, T.: A Cyclic-Executive-Based QoS Guarantee over USB. In: IEEE 9th Real-Time and Embedded Technology and Applications Symposium, Toronto, Canada, May 27-30, 2003, pp. 88–95 (2003)
Burns, A.: Generating Feasible Cyclic Schedules. Control Engineering Practice 3(2), 151–162 (1995)
Locke, C.D.: Software Architecture for Hard Real-Time Applications: Cyclic Executives Vs. Fixed Priority Executives. Real-Time Systems 4(1), 37–52 (1992)
Phatrapornnant, T., Pont, M.J.: Reducing Jitter in Embedded Systems Employing A Time-Triggered Software Architecture and Dynamic Voltage Scaling. IEEE Transactions on Computers (Special Issue on Design and Test of Systems-On-a-Chip) 55(2), 113–124 (2006)
Allworth, S.T.: An Introduction to Real-Time Software Design. Macmillan, London (1981)
Maaita, A., Pont, M.J.: Using Planned Pre-Emption to Reduce Levels ff Task Jitter in a Time-Triggered Hybrid Scheduler, UK Embedded Forum, Birmingham, UK, University of Newcastle (2005)
Kalinsky, D.: Context Switch. Embedded Systems Programming 14(1), 94–105 (2001)
Schlindwein, F.S., Smith, M.J., Evans, D.H.: Spectral Analysis of Doppler Signals and Computation of the Normalized First Moment in Real Time. Using a Digital Signal Processor, Medical & Biological Engineering & Computing 26, 228–232 (1988)
Liu, C.L., Layland, J.W.: Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM 20(1), 40–61 (1973)
Gendy, A.K., Pont, M.J.: Towards a Generic Single-Path Programming Solution with Reduced Power Consumption. In: Proceedings of the ASME 2007 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference (IDETC/CIE 2007), Las Vegas, Nevada, USA, September 4-7 (2007)
Puschner, P., Burns, A.: Writing Temporally Predictable Code. In: Proc. 7th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems, pp. 85–91 (January 2002)
Puschner, P.: The Single-Path Approach Towards WCET-Analysable Software. In: Proc. IEEE International Conference on Industrial Technology, pp. 699–704 (December 2003)
Cucu, L., Sorel, Y.: Non-Preemptive Multiprocessor Scheduling for Strict Periodic Systems with Precedence Constraints. In: Proc. 23rd Annual Workshop of the UK Planning and Scheduling Special Interest Group, PLANSIG 2004, Cork, Ireland (December 2004)
Buttazzo, G.: Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer Academic, Dordrecht (1997)
Xu, J., Parnas, D.L.: Scheduling Processes with Release Times, Deadlines, Precedence and Exclusion Relations. IEEE Transactions on Software Engineering 16(3), 360–369 (1990)
Sandström, K., Norström, C.: Managing Complex Temporal Requirements in Real-Time Control Systems. In: 9th IEEE Conf. Engineering of Computer-Based Systems. IEEE, Sweden (2002)
Ekelin, C., Jonsson, J.: Evaluation of Search Heuristics for Embedded System Scheduling Problems. In: Proc. Int. Conf. Principles and Practice of Constraint Programming, Paphos, Cyprus, pp. 640–654 (2001)
Reeves, G.: What Really Happened on Mars?, – Authoritative Account (1997), research.microsoft.com
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gendy, A.K., Pont, M.J. (2008). Automating the Processes of Selecting an Appropriate Scheduling Algorithm and Configuring the Scheduler Implementation for Time-Triggered Embedded Systems. In: Harrison, M.D., Sujan, MA. (eds) Computer Safety, Reliability, and Security. SAFECOMP 2008. Lecture Notes in Computer Science, vol 5219. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87698-4_36
Download citation
DOI: https://doi.org/10.1007/978-3-540-87698-4_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87697-7
Online ISBN: 978-3-540-87698-4
eBook Packages: Computer ScienceComputer Science (R0)