Studying the Impact of Scheduler Implementation on Task Jitter in Real-Time Resource-Constrained Embedded Systems

Mouaaz Nahas^1,

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

Cite this paper:
Mouaaz Nahas. Studying the Impact of Scheduler Implementation on Task Jitter in Real-Time Resource-Constrained Embedded Systems. Journal of Embedded Systems. 2014; 2(3):39-52. doi: 10.12691/jes-2-3-2

Abstract

Over recent decades, many studies have considered the development, assessment and refinement of scheduling algorithms for use in real-time embedded applications. Various studies have also considered the impact of variations in the interval between the executions of periodic tasks (i.e. jitter) on the behaviour of such systems. Despite interest in both of these areas, there has been comparatively little attention paid to the impact of scheduler implementation techniques on jitter behaviour. This is unfortunate because – as we demonstrate in the course of this paper – there is a ‘one-to-many’ mapping between scheduler algorithms and scheduler implementations, and even comparatively small changes in the scheduler implementation can have a significant impact on jitter behaviour. Throughout this paper, our focus is on implementations of a form of “cyclic executive” which is one of the simplest scheduling algorithms in widespread use. The results presented demonstrate that – even for this very simple scheduling algorithm – implementation decisions can have a significant impact on both jitter behaviour and on resource requirements. We would expect that the results obtained would also apply to more complicated algorithms: indeed, as the algorithms grow more complicated, we would expect that the number of implementation options would increase, with a corresponding increase in the jitter variation.

Keywords:
real-time scheduling algorithm scheduler implementation jitter time-triggered co-operative cyclic executive on-line schedule off-line schedule

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]	M. Sanfridson, “Timing problems in distributed real-time computer control systems,” Mechatronics Lab, Dept. of Machine Design, Royal Inst. of Technology, Stockholm, 2000.
[2]	K.-J. Lin and A. Herkert, “Jitter control in time-triggered systems,” in System Sciences, 1996., Proceedings of the Twenty-Ninth Hawaii International Conference on ,, 1996, vol. 1, pp. 451-459.
[3]	P. Marti, J. M. Fuertes, G. Fohler, and K. Ramamritham, “Jitter compensation for real-time control systems,” in 22nd IEEE Real-Time Systems Symposium, 2001. (RTSS 2001). Proceedings, 2001, pp. 39-48.
[4]	T. Nolte, H. Hansson, and C. Norstrom, “Minimizing CAN response-time jitter by message manipulation,” in Eighth IEEE Real-Time and Embedded Technology and Applications Symposium, 2002. Proceedings, 2002, pp. 197-206.
[5]	M. Nahas and M. J. Pont, “Using XOR operations to reduce variations in the transmission time of CAN messages: A pilot study,” in Proceedings of the Second UK Embedded Forum, Birmingham, UK, 2005, pp. 4-17.
[6]	M. Nahas, M. J. Pont, and M. Short, “Reducing message-length variations in resource-constrained embedded systems implemented using the Controller Area Network (CAN) protocol,” Journal of Systems Architecture, vol. 55, no. 5-6, pp. 344-354, May 2009.
[7]	F. Cottet and L. David, “A Solution to the Time Jitter Removal in Deadline Based Scheduling of Real-time Applications,” presented at the 5th IEEE Real-Time Technology and Applications Symposium-WIP, Vancouver, Canada, 1999, pp. 33-38.
[8]	A. J. Jerri, “The Shannon sampling theorem #8212; Its various extensions and applications: A tutorial review,” Proceedings of the IEEE, vol. 65, no. 11, pp. 1565-1596, Nov. 1977.
[9]	S. H. Hong, “Scheduling algorithm of data sampling times in the integrated communication and control systems,” IEEE Transactions on Control Systems Technology, vol. 3, no. 2, pp. 225-230, Jun. 1995.
[10]	A. Stothert and I. M. Macleod, “Effect of Timing Jitter on Distributed Computer Control System Performance,” in Proceedings of the 15th IFAC Workshop on Distributed Computer Control Systems (DCCS’98), 1998.
[11]	M. Nahas, M. Short, and M. J. Pont, “The impact of bit stuffing on the real-time performance of a distributed control system,” presented at the Proceeding of the 10th International CAN conference iCC, Rome, Italy, 2005, pp. 10-1-10-7.
[12]	T. P. Baker and A. Shaw, “The cyclic executive model and Ada,” Real-Time Syst, vol. 1, no. 1, pp. 7-25, Jun. 1989.
[13]	B. Koch, “The Theory of Task Scheduling in Real-Time Systems: Compilation and Systematization of the Main Results,” Studies Thesis, University of Hamburg, 1999.
[14]	M. J. Pont, Patterns for time-triggered embedded systems: building reliable applications with the 8051 family of microcontrollers. Harlow: Addison-Wesley, 2001.
[15]	S. K. Baruah, “The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors,” Real-Time Systems, vol. 32, no. 1-2, pp. 9-20, Feb. 2006.
[16]	C. Mwelwa, “Development and Assessment of a Tool to Support Pattern-Based Code Generation of Time-Triggered (TT) Embedded Systems,” PhD Thesis, University of Leicester, Leicester, UK, 2006.
[17]	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, pp. 113-124, Feb. 2006.
[18]	M. J. Pont, S. Kurian, H. Wang, and T. Phatrapornnant, “Selecting an appropriate scheduler for use with time-triggered embedded systems.,” in Proceedings of the 12th European Conference on Pattern Languages of Programs (EuroPLoP ’2007), Irsee, Germany, 2007, pp. 595-618.
[19]	C. D. Locke, “Software architecture for hard real-time applications: Cyclic executives vs. fixed priority executives,” The Journal of Real-Time Systems, vol. 4, no. 1, pp. 37-53, Mar. 1992.
[20]	C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” J. ACM, vol. 20, no. 1, pp. 46-61, Jan. 1973.
[21]	Y. Cho, S. Yoo, K. Choi, N.-E. Zergainoh, and A. A. Jerraya, “Scheduler implementation in MP SoC design,” in Design Automation Conference, 2005. Proceedings of the ASP-DAC 2005. Asia and South Pacific, 2005, vol. 1, pp. 151-156 Vol. 1.
[22]	J. Y.-T. Leung and J. Whitehead, “On the complexity of fixed-priority scheduling of periodic, real-time tasks,” Performance Evaluation, vol. 2, no. 4, pp. 237-250, Dec. 1982.
[23]	A. K.-L. Mok, “Fundamental design problems of distributed systems for the hard-real-time environment,” Thesis, Massachusetts Institute of Technology, 1983.
[24]	G. C. Buttazzo, Hard real-time computing systems: predictable scheduling algorithms and applications. New York: Springer, 2005.
[25]	S. Key, M. J. Pon, and S. Edwards, “Implementing Low-cost TTCS Systems using Assembly Language.,” in Proceedings of the Eighth European conference on Pattern Languages of Programs (EuroPLoP 2003), Germany, 2003, pp. 667-690.
[26]	Z. H. Hughes and M. J. Pont, “Design and test of a task guardian for use in TTCS embedded systems,” in Proceedings of the UK Embedded Forum 2004, Birmingham, UK, 2004, pp. 16-25.
[27]	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, no. 5, pp. 427-450, Dec. 2008.
[28]	M. Nahas, M. J. Pont, and A. Jain, “Reducing task jitter in shared-clock embedded systems using CAN,” in Proceedings of the UK Embedded Forum 2004, Birmingham, UK, 2004, pp. 184-194.
[29]	M. Nahas, “Employing Two ‘Sandwich Delay’ Mechanisms to Enhance Predictability of Embedded Systems Which Use Time-Triggered Co-Operative Architectures,” Journal of Software Engineering and Applications, vol. 04, no. 07, pp. 417-425, 2011.
[30]	D. I. Katcher, H. Arakawa, and J. K. Strosnider, “Engineering and analysis of fixed priority schedulers,” IEEE Transactions on Software Engineering, vol. 19, no. 9, pp. 920-934, Sep. 1993.
[31]	J. Xu, “On inspection and verification of software with timing requirements,” IEEE Transactions on Software Engineering, vol. 29, no. 8, pp. 705-720, Aug. 2003.
[32]	G. S. Avrunin, J. C. Corbett, and L. K. Dillon, “Analyzing partially-implemented real-time systems,” IEEE Transactions on Software Engineering, vol. 24, no. 8, pp. 602-614, Aug. 1998.
[33]	Bosch, CAN Specification Version 2.0. Bosch, 1991.
[34]	T. Nolte, H. Hansson, C. Norström, and S. Punnekkat, “Using bit-stuffing distributions in CAN analysis,” presented at the IEEE Real-Time Embedded Systems Workshop, London, 2001.
[35]	Keil Software, “C166 Compiler, Optimizing 166/167 C Compiler and Library Reference, User Guide.” Keil Elektronik GmbH., and Keil Software, Inc., 1998.
[36]	National Instruments, “Low-Cost E Series Multifunction DAQ 12 or 16-Bit, 200 kS/s, 16 Analog Inputs.” [Online]. Available: http://www.ni.com/pdf/products/us/4daqsc202-204_ETCx2_212_213.pdf. [Accessed: 08-Mar-2014].
[37]	“LabVIEW System Design Software,” National Instruments. [Online]. Available: http://www.ni.com/labview/. [Accessed: 08-Mar-2014].
[38]	K. Baynes, C. Collins, E. Fiterman, B. Ganesh, P. Kohout, C. Smit, T. Zhang, and B. Jacob, “The performance and energy consumption of embedded real-time operating systems,” IEEE Transactions on Computers, vol. 52, no. 11, pp. 1454-1469, Nov. 2003.
[39]	M. J. Pont, S. Kurian, and R. Bautista-Quintero, “Meeting Real-Time Constraints Using ‘Sandwich Delays,’” in Transactions on Pattern Languages of Programming I, J. Noble and R. Johnson, Eds. Springer Berlin Heidelberg, 2009, pp. 94-102.
[40]	J. Xu and D. L. Parnas, “Priority Scheduling Versus Pre-Run-Time Scheduling,” Real-Time Systems, vol. 18, no. 1, pp. 7-23, Jan. 2000.
[41]	D. Ayavoo, M. J. Pont, M. Short, and S. Parker, “Two novel shared-clock scheduling algorithms for use with ‘Controller Area Network’ and related protocols,” Microprocessors and Microsystems, vol. 31, no. 5, pp. 326-334, Aug. 2007.
[42]	M. Nahas, “Estimating Message Latencies in Time-Triggered Shared-Clock Scheduling Protocols Built on CAN Network,” Journal of Embedded Systems, vol. 2, no. 1, pp. 1-10, 2014.
[43]	M. Nahas, “Developing a Novel Shared-Clock Scheduling Protocol for Highly-Predictable Distributed Real-Time Embedded Systems,” American Journal of Intelligent Systems, vol. 2, no. 5, pp. 118-128, Dec. 2012.
[44]	Texas Instruments, “74LS08 Datasheet.” [Online]. Available: http://www.cs.amherst.edu/~sfl<aplan/courses/spring-2002/cs14/74LS08-datasheet. pdf. [Accessed: 08-Mar-2014].
[45]	M. Farsi and M. B. M. Barbosa, CANopen implementation: applications to industrial networks. Baldock, Hertfordshire, England; Philadelphia, PA: Research Studies Press, 1999.
[46]	Infineon Technologies, “C167CR Derivatives: 16-Bit Single-chip Microcontroller; Microcontrollers. User’s manual V 3.1.” Mar-2000.
[47]	L. Hatton, “Programming Languages and Safety-Related Systems,” in Achievement and Assurance of Safety, F. Redmill and T. Anderson, Eds. Springer London, 1995, pp. 48-64.
[48]	J. A. de la Puente and J. Zamorano, “Execution-time Clocks and Ravenscar Kernels,” in Proceedings of the 12th International Workshop on Real-time Ada, New York, NY, USA, 2003, pp. 82-86.