Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems

Mouaaz Nahas; Ricardo Bautista-Quintero

doi:doi:10.11648/j.ajesa.20140204.12

| Peer-Reviewed

Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems

Mouaaz Nahas, Ricardo Bautista-Quintero

Published in American Journal of Embedded Systems and Applications (Volume 2, Issue 4)

Received: 6 September 2014 Accepted: 15 September 2014 Published: 30 September 2014

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

For many real-time embedded systems, Time-Triggered Co-operative (TTC) scheduling algorithms provide simple and reliable solution at low cost. Previous work in this area has focused on the development of a wide range of TTC implementations for various purposes (e.g. for achieving low-jitter characteristics, reducing CPU power consumption or dealing with task-overruns). Despite the great deal of work in this area, it can be said that each previous scheduler implementation was created to address only one particular problem in TTC algorithm. For applications which require extremely high degree of reliability, a combinational TTC architecture – that incorporates multiple features – can be an appropriate solution. This paper describes the implementation of an adaptive, highly-predictable TTC scheduler that addresses both jitter and task-overrun problems simultaneously. Furthermore, the presented scheduler incorporates an online technique for measuring the practical “worst-case execution time” for each task during system runtime. The behavior of the proposed scheduler is compared with a set of previously developed schedulers in terms of timing jitter, task-overrun handling capability and resource requirements for practical real-time implementations.

Published in	American Journal of Embedded Systems and Applications (Volume 2, Issue 4)
DOI	10.11648/j.ajesa.20140204.12
Page(s)	38-50
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Time-Triggered, Co-Operative, Cyclic Executive, Jitter, Worst Case Execution Time, Multiple Timer Interrupts, Task-Overrun, Task Guardian, Adaptive Scheduler

References

[1]	A.C. Shaw, Real-time systems and software, New York, John Wiley & Sons Inc, 2001.
[2]	N. Nissanke, Realtime Systems, Prentice-Hall, 1997.
[3]	A. Albert, “Comparison of event-triggered and time-triggered concepts with regard to distributed control systems,” in Proceedings of Embedded World, Nurnberg, Germany, 17-19 Feb, 2004. pp. 235-252
[4]	H. Kopetz, Real-time systems: Design principles for distributed embedded applications, Kluwer Academic, 1997.
[5]	T. P. Baker, and A. Shaw, “The cyclic executive model and Ada”. Real-Time Systems, Vol. 1, No. 1, 1989, pp. 7-25.
[6]	C. D. Locke, “Software architecture for hard real-time applications: cyclic executives vs. fixed priority executives.” Real-Time Systems, Vol. 4, No. 1, 1992, pp. 37-53.
[7]	M. Short, “Analysis and redesign of the ‘TTC’ and ‘TTH’ schedulers”. Journal of Systems Architecture, Vol. 58, No. 1, 2012, pp. 38-47.
[8]	M.J. Pont, Patterns for time-triggered embedded systems: Building reliable applications with the 8051 family of microcontrollers, ACM Press / Addison-Wesley, 2001.
[9]	M. J. Pont, and M. Banner, “Designing embedded systems using patterns: A case study”, Journal of Systems and Software, Vol. 71, No. 3, 2004, 2004, pp. 201-213.
[10]	S. Kurian, and M.J. Pont, “Maintenance and evolution of resource-constrained embedded systems created using design patterns”. Journal of Systems and Software, Vol. 80, No. 1, 2007, pp. 32-41
[11]	E. Anbarasi, N. Karthik, and R. Prabakaran, “Analysis of time triggered schedulers in embedded system”. In Electronics Computer Technology (ICECT), 2011 3rd International Conference on, Vol. 1, IEEE, 2011, pp. 134-137.
[12]	M. Nahas, and A.M. Nahhas, “Ways for Implementing Highly-Predictable Embedded Systems Using Time-Triggered Cooperative (TTC) Architectures”. In Dr. Kiyofumi Tanaka (Ed.), Embedded Systems - Theory and Design Methodology, ISBN: 978-953-51-0167-3, InTech, 2012.
[13]	I.J. Bate, “Scheduling and Timing Analysis for Safety Critical Real-Time Systems”, PhD dissertation, Department of Computer Science, University of York, 1998.
[14]	G. Buttazzo, Hard real-time computing systems: predictable scheduling algorithms and applications, Second Edition, Springer, 2005.
[15]	T. Phatrapornnant, and M.J. Pont, “Reducing jitter in embedded systems employing a time-triggered software architecture and dynamic voltage scaling”, IEEE Transactions on Computers, Vol. 55, No. 2, 2006, pp. 113-124.
[16]	M. Nahas, Pont, M.J., and A. Jain, “Reducing task jitter in shared-clock embedded systems using CAN”, In: Koelmans, A., Bystrov, A. and Pont, M.J. (Eds.) Proceedings of the UK Embedded Forum 2004, Birmingham, UK, October 2004, pp. 184-194. Published by University of Newcastle upon Tyne.
[17]	M. Nahas, “Employing two ‘sandwich delay’ mechanisms to enhance predictability of embedded systems which use time-triggered co-operative architectures”, International Journal of Software Engineering and Applications, Vol. 4, No. 7, 2011, pp. 417-425.
[18]	F. Cottet, and L. David, “A solution to the time jitter removal in deadline based scheduling of real-time applications”, 5th IEEE Real-Time Technology and Applications Symposium - WIP, Vancouver, Canada, 1999, pp. 33-38.
[19]	A.J. Jerri, “The Shannon sampling theorem: its various extensions and applications a tutorial review”, Proceeding of the IEEE, Vol. 65, 1977, pp. 1565-1596.
[20]	M. Torngren, “Fundamentals of implementing real-time control applications in distributed computer systems”, Real-Time Systems, Vol. 14, 1998, pp. 219-250.
[21]	P. Marti, J.M., Fuertes, R. Villà, and G. Fohler, “On Real-Time Control Tasks Schedulability”, European Control Conference (ECC01), Porto, Portugal, 2001, pp. 2227-2232
[22]	F. Abugchem, M. Short, and D. Xu, “An experimental HIL study on the jitter sensitivity of an adaptive control system”, Emerging Technologies & Factory Automation (ETFA), 2013 IEEE 18th Conference on, Cagliari, Italy, 2013, pp. 1-8.
[23]	Z.H. Hughes, and M.J. Pont, “Design and test of a task guardian for use in TTCS embedded systems”, In: Koelmans, A., Bystrov, A. and Pont, M.J. (Eds.) Proceedings of the UK Embedded Forum 2004, Birmingham, UK, October 2004, pp. 16-25
[24]	K. L. Chan, and M. J. Pont, “Real-time non-invasive detection of timing-constraint violations in time-triggered embedded systems”, In Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on, Bradford, UK, 2010, pp. 1978-1986.
[25]	C.L. Liu, and J.W. Layland, “Scheduling algorithms for multi-programming in a hard real-time environment”, Journal of the AVM 20, Vol. 1, 1973, pp. 40-61.
[26]	E. Nett, H. Streich, P. Bizzarri, A. Bondavalli and F. Tarini, “Adaptive Software Fault Tolerance Policies with Dynamic Real-Time Guarantees”. WORDS 96, IEEE Second Int. Workshop on Object oriented Real-time Dependable Systems, Laguna Beach, California, U.S.A., 1996.
[27]	Y. Domaratsky, and M. Perevozchikov, “Highly Dependable Time-Triggered Operating System”, Dedicated Systems Magazine, Vol. 4, 2000, pp. 77-80.
[28]	L.B. Becker, and M. Gergeleit, “Execution Environment for Dynamically Scheduling Real-Time Tasks”. RTSS 2001, 22nd IEEE Real-Time Systems Symposium, 2001.
[29]	J. Engblom, A. Ermedahl, M. Sjoedin, J. Gustafsson, and H. Hansson, “Worst-Case Execution-Time Analysis for Embedded Real-Time Systems”. Journal of Software Tools for Technology Transfer, 2001.
[30]	M. Gergeleit, and E. Nett, “Scheduling Transient Overload with the TAFT Scheduler”. GI/ITG specialized group of operating systems, Berlin, 2002.
[31]	P. Puschner, “Is WCET Analysis a Non-Problem? - Towards New Software and Hardware Architectures”. 2nd Intl. Workshop on Worst Case Execution Time Analysis, Vienna, Austria, 2002.
[32]	L.B. Becker, E. Nett, S. Schemmer, and M. Gergeleit, “Robust scheduling in team-robotics”. 11th International Workshop on Parallel and Distributed Real-Time Systems, Nice, France, 2003.
[33]	R. Kirner, and P. Puschner, “Discussion of Misconceptions about Worst-Case Execution-Time Analysis”. 3rd Euromicro International Workshop on WCET Analysis, 2003.
[34]	J. Lelli, D. Faggioli, T. Cucinotta, and G. Lipari, “An experimental comparison of different real-time schedulers on multicore systems”, Journal of Systems and Software, Vol. 85, No. 10, 2012, pp. 2405-2416.
[35]	R. Wilhelm and D. Grund, “Computation Takes Time, but How Much?,” Communications of the ACM, Vol. 57, no. 2, pp. 94–103, Feb. 2014.
[36]	K.S. Vallerio, and N.K. Jha, “Task graph extraction for embedded system synthesis”, Proceedings 16th International Conference on VLSI Design concurrently with the 2nd International Conference on Embedded Systems Design, 2003, pp. 480-486
[37]	A.K. Gendy, and M.J. Pont, “Automatically configuring time-triggered schedulers for use with resource-constrained, single-processor embedded systems”, IEEE Transactions on Industrial Informatics, Vol. 4, No. 1, 2008, pp. 37-46.
[38]	J. Ganssle, The art of programming embedded systems, Academic Press, San Diego, USA, 1992.
[39]	M.J. Pont, and H.L.R. Ong, “Using watchdog timers to improve the reliability of TTCS embedded systems”. in Hruby, P. and Soressen, K. E. [Eds.]Proceedings of the First Nordic Conference on Pattern Languages of Programs, September, 2002 pp.159-200. Published by Micrsoft Business Solutions.
[40]	F. Lakhani and M.J. Pont, “Applying Design Patterns to Improve the Reliability of Embedded Systems through a Process of Architecture Migration”, High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS), 2012 IEEE 14th International Conference on, 25-27 June, 2012, pp. 1563-1570.
[41]	L. Bougueroua, L. George, and S. Midonnet, “An Execution Overrun Management Mechanism for the Temporal Robustness of Java Real-time Systems,” in Proceedings of the 4th International Workshop on Java Technologies for Real-time and Embedded Systems, New York, NY, USA, 2006, pp. 188–195.
[42]	F. Fauberteau, S. Midonnet, and L. George, “Robust Partitioned Scheduling for Real-Time Multiprocessor Systems,” in Distributed, Parallel and Biologically Inspired Systems, M. Hinchey, B. Kleinjohann, L. Kleinjohann, P. A. Lindsay, F. J. Rammig, J. Timmis, and M. Wolf, Eds. Springer Berlin Heidelberg, 2010, pp. 193–204.
[43]	R.E. Kontak, “Applicability of Ada tasking for avionics executives”, Proceedings of the IEEE 1988 National Aerospace and Electronics Conference (NAECON), 23-27 May, Vol. 2, 1988, pp. 739-746.
[44]	J.A. Stankovic, “Misconceptions about real-time computing”, IEEE Computers, Vol. 21, No. 10, 1988.
[45]	W.A. Halang, and A.D. Stoyenko, “Comparative evaluation of high-level real-time programming languages”, Real-Time Systems, Vol. 2, No. 4, 1990, pp. 365-382.
[46]	Z.M. Hughes, and M.J. Pont, "Reducing the impact of task overruns in resource-constrained embedded systems in which a time-triggered software architecture is employed", Transactions of the Institute of Measurement and Control, Vol. 30, 2008, pp.427 – 450.
[47]	Philips Semiconductors, LPC2106/2105/2104 USER MANUAL, 2003, available online (Last accessed: September 2014) http://www.standardics.nxp.com/products/lpc2000/datasheet/lpc2104.lpc2105.lpc2106.pdf
[48]	Z.M. Hughes, M.J. Pont, and H.L.R. Ong, "The PH Processor: A soft embedded core for use in university research and teaching In: Koelmans, A., Bystrov, A., Pont, M.J., Ong, R. and Brown, A. (Eds.), Proceedings of the Second UK Embedded Forum, Birmingham, UK, October 2005,pp. 224-245. Published by University of Newcastle upon Tyne.
[49]	Ashling Microsystems LPC2000 Evaluation and Development Kits datasheet, 2007, available online (Last accessed: September 2014) http://www.ashling.com/pdf_datasheets/DS266-EvKit2000.pdf
[50]	National Instruments, Low-Cost E Series Multifunction DAQ – 12 or 16-Bit, 200 kS/s, 16 Analog Inputs, 2006, available online (Last accessed: September 2014): http://www.ni.com/pdf/products/us/4daqsc202-204_ETC_212-213.pdf
[51]	LabVIEW (2007) “LabVIEW 7.1 Documentation Resources”, WWW website (Last accessed: September 2014): http://digital.ni.com/public.nsf/allkb/06572E936282C0E486256EB0006B70B4

Cite This Article

Plain Text BibTeX RIS

APA Style

Mouaaz Nahas, Ricardo Bautista-Quintero. (2014). Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems. American Journal of Embedded Systems and Applications, 2(4), 38-50. https://doi.org/10.11648/j.ajesa.20140204.12

Copy | Download

ACS Style

Mouaaz Nahas; Ricardo Bautista-Quintero. Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems. Am. J. Embed. Syst. Appl. 2014, 2(4), 38-50. doi: 10.11648/j.ajesa.20140204.12

Copy | Download

AMA Style

Mouaaz Nahas, Ricardo Bautista-Quintero. Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems. Am J Embed Syst Appl. 2014;2(4):38-50. doi: 10.11648/j.ajesa.20140204.12

Copy | Download

@article{10.11648/j.ajesa.20140204.12,
  author = {Mouaaz Nahas and Ricardo Bautista-Quintero},
  title = {Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems},
  journal = {American Journal of Embedded Systems and Applications},
  volume = {2},
  number = {4},
  pages = {38-50},
  doi = {10.11648/j.ajesa.20140204.12},
  url = {https://doi.org/10.11648/j.ajesa.20140204.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajesa.20140204.12},
  abstract = {For many real-time embedded systems, Time-Triggered Co-operative (TTC) scheduling algorithms provide simple and reliable solution at low cost. Previous work in this area has focused on the development of a wide range of TTC implementations for various purposes (e.g. for achieving low-jitter characteristics, reducing CPU power consumption or dealing with task-overruns). Despite the great deal of work in this area, it can be said that each previous scheduler implementation was created to address only one particular problem in TTC algorithm. For applications which require extremely high degree of reliability, a combinational TTC architecture – that incorporates multiple features – can be an appropriate solution. This paper describes the implementation of an adaptive, highly-predictable TTC scheduler that addresses both jitter and task-overrun problems simultaneously. Furthermore, the presented scheduler incorporates an online technique for measuring the practical “worst-case execution time” for each task during system runtime. The behavior of the proposed scheduler is compared with a set of previously developed schedulers in terms of timing jitter, task-overrun handling capability and resource requirements for practical real-time implementations.},
 year = {2014}
}

Copy | Download

TY  - JOUR
T1  - Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems
AU  - Mouaaz Nahas
AU  - Ricardo Bautista-Quintero
Y1  - 2014/09/30
PY  - 2014
N1  - https://doi.org/10.11648/j.ajesa.20140204.12
DO  - 10.11648/j.ajesa.20140204.12
T2  - American Journal of Embedded Systems and Applications
JF  - American Journal of Embedded Systems and Applications
JO  - American Journal of Embedded Systems and Applications
SP  - 38
EP  - 50
PB  - Science Publishing Group
SN  - 2376-6085
UR  - https://doi.org/10.11648/j.ajesa.20140204.12
AB  - For many real-time embedded systems, Time-Triggered Co-operative (TTC) scheduling algorithms provide simple and reliable solution at low cost. Previous work in this area has focused on the development of a wide range of TTC implementations for various purposes (e.g. for achieving low-jitter characteristics, reducing CPU power consumption or dealing with task-overruns). Despite the great deal of work in this area, it can be said that each previous scheduler implementation was created to address only one particular problem in TTC algorithm. For applications which require extremely high degree of reliability, a combinational TTC architecture – that incorporates multiple features – can be an appropriate solution. This paper describes the implementation of an adaptive, highly-predictable TTC scheduler that addresses both jitter and task-overrun problems simultaneously. Furthermore, the presented scheduler incorporates an online technique for measuring the practical “worst-case execution time” for each task during system runtime. The behavior of the proposed scheduler is compared with a set of previously developed schedulers in terms of timing jitter, task-overrun handling capability and resource requirements for practical real-time implementations.
VL  - 2
IS  - 4
ER  -

Copy | Download

Author Information

Mouaaz Nahas

Department of Electrical Engineering, College of Engineering and Islamic Architecture, Umm Al-Qura University, Makkah, KSA
Ricardo Bautista-Quintero

Department of Mechanical Engineering, Instituto Tecnologico De Culiacan, Sinaloa, Mexico

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Mouaaz Nahas, Ricardo Bautista-Quintero. (2014). Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems. American Journal of Embedded Systems and Applications, 2(4), 38-50. https://doi.org/10.11648/j.ajesa.20140204.12

Copy | Download

ACS Style

Mouaaz Nahas; Ricardo Bautista-Quintero. Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems. Am. J. Embed. Syst. Appl. 2014, 2(4), 38-50. doi: 10.11648/j.ajesa.20140204.12

Copy | Download

AMA Style

Mouaaz Nahas, Ricardo Bautista-Quintero. Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems. Am J Embed Syst Appl. 2014;2(4):38-50. doi: 10.11648/j.ajesa.20140204.12

Copy | Download

@article{10.11648/j.ajesa.20140204.12,
  author = {Mouaaz Nahas and Ricardo Bautista-Quintero},
  title = {Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems},
  journal = {American Journal of Embedded Systems and Applications},
  volume = {2},
  number = {4},
  pages = {38-50},
  doi = {10.11648/j.ajesa.20140204.12},
  url = {https://doi.org/10.11648/j.ajesa.20140204.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajesa.20140204.12},
  abstract = {For many real-time embedded systems, Time-Triggered Co-operative (TTC) scheduling algorithms provide simple and reliable solution at low cost. Previous work in this area has focused on the development of a wide range of TTC implementations for various purposes (e.g. for achieving low-jitter characteristics, reducing CPU power consumption or dealing with task-overruns). Despite the great deal of work in this area, it can be said that each previous scheduler implementation was created to address only one particular problem in TTC algorithm. For applications which require extremely high degree of reliability, a combinational TTC architecture – that incorporates multiple features – can be an appropriate solution. This paper describes the implementation of an adaptive, highly-predictable TTC scheduler that addresses both jitter and task-overrun problems simultaneously. Furthermore, the presented scheduler incorporates an online technique for measuring the practical “worst-case execution time” for each task during system runtime. The behavior of the proposed scheduler is compared with a set of previously developed schedulers in terms of timing jitter, task-overrun handling capability and resource requirements for practical real-time implementations.},
 year = {2014}
}

Copy | Download

TY  - JOUR
T1  - Implementing Adaptive Time-Triggered Co-Operative Scheduling Framework for Highly-Predictable Embedded Systems
AU  - Mouaaz Nahas
AU  - Ricardo Bautista-Quintero
Y1  - 2014/09/30
PY  - 2014
N1  - https://doi.org/10.11648/j.ajesa.20140204.12
DO  - 10.11648/j.ajesa.20140204.12
T2  - American Journal of Embedded Systems and Applications
JF  - American Journal of Embedded Systems and Applications
JO  - American Journal of Embedded Systems and Applications
SP  - 38
EP  - 50
PB  - Science Publishing Group
SN  - 2376-6085
UR  - https://doi.org/10.11648/j.ajesa.20140204.12
AB  - For many real-time embedded systems, Time-Triggered Co-operative (TTC) scheduling algorithms provide simple and reliable solution at low cost. Previous work in this area has focused on the development of a wide range of TTC implementations for various purposes (e.g. for achieving low-jitter characteristics, reducing CPU power consumption or dealing with task-overruns). Despite the great deal of work in this area, it can be said that each previous scheduler implementation was created to address only one particular problem in TTC algorithm. For applications which require extremely high degree of reliability, a combinational TTC architecture – that incorporates multiple features – can be an appropriate solution. This paper describes the implementation of an adaptive, highly-predictable TTC scheduler that addresses both jitter and task-overrun problems simultaneously. Furthermore, the presented scheduler incorporates an online technique for measuring the practical “worst-case execution time” for each task during system runtime. The behavior of the proposed scheduler is compared with a set of previously developed schedulers in terms of timing jitter, task-overrun handling capability and resource requirements for practical real-time implementations.
VL  - 2
IS  - 4
ER  -

Copy | Download