Employing Two ‘Sandwich Delay’ Mechanisms to Enhance Predictability of Embedded Systems Which Use Time-Triggered Co-Operative Architectures
Author(s)
Mouaaz Nahas
ABSTRACT
In many real-time resource-constrained embedded systems, highly-predictable system behavior is a key design requirement. The “time-triggered co-operative” (TTC) scheduling algorithm provides a good match for a wide range of low-cost embedded applications. As a consequence of the resource, timing, and power constraints, the implementation of such algorithm is often far from trivial. Thus, basic implementation of TTC algorithm can result in excessive levels of task jitter which may jeopardize the predictability of many time-critical applications using this algorithm. This paper discusses the main sources of jitter in earlier TTC implementations and develops two alternative implementations – based on the employment of “sandwich delay” (SD) mechanisms – to reduce task jitter in TTC system significantly. In addition to jitter levels at task release times, we also assess the CPU, memory and power requirements involved in practical implementations of the proposed schedulers. The paper concludes that the TTC scheduler implementation using “multiple timer interrupt” (MTI) technique achieves better performance in terms of timing behavior and resource utilization as opposed to the other implementation which is based on a simple SD mechanism. Use of MTI technique is also found to provide a simple solution to “task overrun” problem which may degrade the performance of many TTC systems.
In many real-time resource-constrained embedded systems, highly-predictable system behavior is a key design requirement. The “time-triggered co-operative” (TTC) scheduling algorithm provides a good match for a wide range of low-cost embedded applications. As a consequence of the resource, timing, and power constraints, the implementation of such algorithm is often far from trivial. Thus, basic implementation of TTC algorithm can result in excessive levels of task jitter which may jeopardize the predictability of many time-critical applications using this algorithm. This paper discusses the main sources of jitter in earlier TTC implementations and develops two alternative implementations – based on the employment of “sandwich delay” (SD) mechanisms – to reduce task jitter in TTC system significantly. In addition to jitter levels at task release times, we also assess the CPU, memory and power requirements involved in practical implementations of the proposed schedulers. The paper concludes that the TTC scheduler implementation using “multiple timer interrupt” (MTI) technique achieves better performance in terms of timing behavior and resource utilization as opposed to the other implementation which is based on a simple SD mechanism. Use of MTI technique is also found to provide a simple solution to “task overrun” problem which may degrade the performance of many TTC systems.
KEYWORDS
Time-Triggered, Co-Operative, Cyclic Executive, Jitter, Sandwich Delay, Multiple Timer Interrupts, Task Overrun
Time-Triggered, Co-Operative, Cyclic Executive, Jitter, Sandwich Delay, Multiple Timer Interrupts, Task Overrun
Cite this paper
nullM. 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. 4 No. 7, 2011, pp. 417-425. doi: 10.4236/jsea.2011.47048.
nullM. 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. 4 No. 7, 2011, pp. 417-425. doi: 10.4236/jsea.2011.47048.
References
[1] A. C. Shaw, “Real-Time Systems and Software,” John Wiley & Sons Inc., New York, 2001. [2] N. Nissanke, “Real-time Systems,” Prentice-Hall, Upper Saddle River, 1997. [3] A. Albert, “Comparison of Event-Triggered and Time-Triggered Concepts with Regard to Distributed Control Systems,” Proceedings of Embedded World, Nurnberg, 17-19 February 2004, pp. 235-252. [4] H. Kopetz, “Real-Time Systems: Design Principles for Distributed Embedded Applications,” Kluwer Academic, Boston, 1997. [5] S. T. Allworth, “An Introduction to Real-Time Software Design,” Macmillan, London, 1981. [6] N. Storey, “Safety-Critical Computer Systems,” Addison-Wesley, Boston, 1996. [7] I. Bates, “Introduction to Scheduling and Timing Analysis,” The Use of Ada in Real-Time System, IEE Conference Publication 00/034, 2000. [8] R. Obermaisser, “Event-Triggered and Time-Triggered Control Paradigms,” Kluwer Academic, Boston, 2004. [9] B. Zhang, “Specifying and Verifying Timing Properties of a Time-Triggered Protocol for in-Vehicle Communication,” 9th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, Phuket, 6-8 August 2008, pp. 467-472. doi:10.1109/SNPD.2008.99 [10] J. Zhang, F. Xiang, B. Wang and J. Lu, “An Extensible Software Framework for Reliable Distributed Embedded System Modelling,” 2nd International Asia Conference on Informatics in Control, Automation and Robotics, Wuhan, 6-7 March 2010, pp. 234-237. doi:10.1109/CAR.2010.5456558 [11] F. Scheler and W. Schro?der-Preikschat, “The RTSC: Leveraging the Migration from Event-Triggered to Time-Triggered Systems,” 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, Carmona, 5-6 May 2010, pp. 34-41. [12] J. W. S. Liu, “Real-Time Systems,” Prentice Hall, Upper Saddle River, 2000. [13] N. J. Ward, “The Static Analysis of a Safety-Critical Avionics Control Systems,” Offshore Safety and Reliability: Sarss’91 - Proceedings of the Safety and Reliability Society Symposium, SaRS, Ltd., Roselle, 1991. [14] M. J. Pont, “Patterns for Time-Triggered Embedded Systems: Building Reliable Applications with the 8051 Family of Microcontrollers,” ACM Press/Addison-Wesley, Boston, 2001. [15] T. P. Baker and A. Shaw, “The Cyclic Executive Model and Ada,” Real-Time Systems, Vol. 1, No. 1, 1989, pp. 7- 25. doi:10.1007/BF02341919 [16] 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-52. doi:10.1007/BF00365463 [17] M. J. Pont and M. P. Banner, “Designing Embedded Systems Using Patterns: A Case Study,” Journal of Systems and Software, Vol. 71, No, 3, 2004, pp. 201-213. doi:10.1016/S0164-1212(03)00006-2 [18] D. Ayavoo, M. J. Pont and S. Parker, “Does a ‘Simulation First’ Approach Reduce the Effort Involved in the Development of Distributed Embedded Control Systems?” 6th UKACC International Control Conference, Glasgow, 30 August-1 September 2006. [19] T. Nghiem, G. J. Pappas, R. Alur and A. Girard, “Time-Triggered Implementations of Dynamic Controllers,” Proceedings of the 6th ACM & IEEE International Conference on Embedded Software, Seoul, 22-25 October 2006, pp. 2-11. [20] 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. doi:10.1109/TC.2006.29 [21] M. Short and M. J. Pont, “Fault-Tolerant Time-Triggered Communication Using CAN,” IEEE Transactions on Industrial Informatics, Vol. 3, No. 2, 2007, pp. 113-142. doi:10.1109/TII.2007.898477 [22] I. J. Bate, “Scheduling and Timing Analysis for Safety Critical Real-Time Systems,” Ph.D. Dissertation, Department of Computer Science, University of York, Heslington, 1998. [23] G. Buttazzo, “Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications,” Springer, New York, 2005. [24] 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, Vancouver, 2-4 June 1999, pp. 33-38. [25] A. J. Jerri, “The Shannon Sampling Theorem: Its Various Extensions and Applications a Tutorial Review,” Proceedings of the IEEE, Vol. 65, No. 11, 1977, pp. 1565- 1596. doi:10.1109/PROC.1977.10771 [26] M. Torngren, “Fundamentals of Implementing Real-Time Control Applications in Distributed Computer Systems,” Real-Time Systems, Vol. 14, No. 3, 1998, pp. 219-250. doi:10.1023/A:1007964222989 [27] P. Marti, J. M. Fuertes, K. Ramamritham and G. Fohler, “Jitter Compensation for Real-Time Control Systems,” 22nd IEEE Real-Time Systems Symposium, London, 3-6 December 2001, pp. 39-48. [28] S. R. Gulliver and G. Ghinea, “The Perceptual Influence of Multimedia Delay and Jitter,” IEEE International Conference on Multimedia and Expo, Beijing, 2-5 July 2007, pp. 2214-2217. doi:10.1109/ICME.2007.4285125 [29] R. E. Kontak, “Applicability of Ada Tasking for Avionics Executives,” Proceedings of the IEEE 1988 National Aerospace and Electronics Conference, Dayton, 23-27 May 1988, Vol. 2, pp. 739-746. [30] J. A. Stankovic, “Misconceptions about Real-Time Computing: A Serious Problem for Next-Generation Systems,” Computers, Vol. 21 No. 10, 1988, pp. 10-19. doi:10.1109/2.7053 [31] 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. doi:10.1007/BF01995678 [32] M. J. Pont, S. Kurian and R. Bautista-Quintero, “Meeting Real-Time Constraints Using ‘Sandwich Delays’,” Transactions on Pattern Languages of Programming I, Springer, Berlin, 2009, pp. 94-102. [33] 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. doi:10.1016/j.jss.2006.04.007 [34] M. Nahas, M. J. Pont and A. Jain, “Reducing Task Jitter in Shared-Clock Embedded Systems Using CAN,” In: A. Koelmans, A. Bystrov and M. J. Pont, Eds., Proceedings of the UK Embedded Forum, University of Newcastle upon Tyne, Newcastle, 2004, pp. 184-194. [35] 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, 2008, pp. 427-450. doi:10.1177/0142331207086183 [36] A. Burns and A. J. Wellings, “Concurrent and Real-Time Programming in Ada 2005,” Cambridge University Press, Cambridge, 2007. [37] Ashling Microsystems, “LPC2000 Evaluation and Development Kits Datasheet,” 2007. http://www.ashling.com/pdf_datasheets/DS266-EvKit2000.pdf [38] Philips Semiconductors, “LPC2106/2105/2104 USER MANUAL,” 2003. http://www.standardics.nxp.com/products/lpc2000/datasheet/lpc2104.lpc2105.lpc2106.pdf [39] National Instruments, “Low-Cost E Series Multifunction DAQ – 12 or 16-Bit, 200 kS/s, 16 Analog Inputs,” 2006. http://www.ni.com/pdf/products/us/4daqsc202-204_ETC_212-213.pdf [40] LabVIEW, “LabVIEW 7.1 Documentation Resources,” 2007. http://digital.ni.com/public.nsf/allkb/06572E936282C0E486256EB0006B70B4
[1] A. C. Shaw, “Real-Time Systems and Software,” John Wiley & Sons Inc., New York, 2001. [2] N. Nissanke, “Real-time Systems,” Prentice-Hall, Upper Saddle River, 1997. [3] A. Albert, “Comparison of Event-Triggered and Time-Triggered Concepts with Regard to Distributed Control Systems,” Proceedings of Embedded World, Nurnberg, 17-19 February 2004, pp. 235-252. [4] H. Kopetz, “Real-Time Systems: Design Principles for Distributed Embedded Applications,” Kluwer Academic, Boston, 1997. [5] S. T. Allworth, “An Introduction to Real-Time Software Design,” Macmillan, London, 1981. [6] N. Storey, “Safety-Critical Computer Systems,” Addison-Wesley, Boston, 1996. [7] I. Bates, “Introduction to Scheduling and Timing Analysis,” The Use of Ada in Real-Time System, IEE Conference Publication 00/034, 2000. [8] R. Obermaisser, “Event-Triggered and Time-Triggered Control Paradigms,” Kluwer Academic, Boston, 2004. [9] B. Zhang, “Specifying and Verifying Timing Properties of a Time-Triggered Protocol for in-Vehicle Communication,” 9th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, Phuket, 6-8 August 2008, pp. 467-472. doi:10.1109/SNPD.2008.99 [10] J. Zhang, F. Xiang, B. Wang and J. Lu, “An Extensible Software Framework for Reliable Distributed Embedded System Modelling,” 2nd International Asia Conference on Informatics in Control, Automation and Robotics, Wuhan, 6-7 March 2010, pp. 234-237. doi:10.1109/CAR.2010.5456558 [11] F. Scheler and W. Schro?der-Preikschat, “The RTSC: Leveraging the Migration from Event-Triggered to Time-Triggered Systems,” 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, Carmona, 5-6 May 2010, pp. 34-41. [12] J. W. S. Liu, “Real-Time Systems,” Prentice Hall, Upper Saddle River, 2000. [13] N. J. Ward, “The Static Analysis of a Safety-Critical Avionics Control Systems,” Offshore Safety and Reliability: Sarss’91 - Proceedings of the Safety and Reliability Society Symposium, SaRS, Ltd., Roselle, 1991. [14] M. J. Pont, “Patterns for Time-Triggered Embedded Systems: Building Reliable Applications with the 8051 Family of Microcontrollers,” ACM Press/Addison-Wesley, Boston, 2001. [15] T. P. Baker and A. Shaw, “The Cyclic Executive Model and Ada,” Real-Time Systems, Vol. 1, No. 1, 1989, pp. 7- 25. doi:10.1007/BF02341919 [16] 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-52. doi:10.1007/BF00365463 [17] M. J. Pont and M. P. Banner, “Designing Embedded Systems Using Patterns: A Case Study,” Journal of Systems and Software, Vol. 71, No, 3, 2004, pp. 201-213. doi:10.1016/S0164-1212(03)00006-2 [18] D. Ayavoo, M. J. Pont and S. Parker, “Does a ‘Simulation First’ Approach Reduce the Effort Involved in the Development of Distributed Embedded Control Systems?” 6th UKACC International Control Conference, Glasgow, 30 August-1 September 2006. [19] T. Nghiem, G. J. Pappas, R. Alur and A. Girard, “Time-Triggered Implementations of Dynamic Controllers,” Proceedings of the 6th ACM & IEEE International Conference on Embedded Software, Seoul, 22-25 October 2006, pp. 2-11. [20] 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. doi:10.1109/TC.2006.29 [21] M. Short and M. J. Pont, “Fault-Tolerant Time-Triggered Communication Using CAN,” IEEE Transactions on Industrial Informatics, Vol. 3, No. 2, 2007, pp. 113-142. doi:10.1109/TII.2007.898477 [22] I. J. Bate, “Scheduling and Timing Analysis for Safety Critical Real-Time Systems,” Ph.D. Dissertation, Department of Computer Science, University of York, Heslington, 1998. [23] G. Buttazzo, “Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications,” Springer, New York, 2005. [24] 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, Vancouver, 2-4 June 1999, pp. 33-38. [25] A. J. Jerri, “The Shannon Sampling Theorem: Its Various Extensions and Applications a Tutorial Review,” Proceedings of the IEEE, Vol. 65, No. 11, 1977, pp. 1565- 1596. doi:10.1109/PROC.1977.10771 [26] M. Torngren, “Fundamentals of Implementing Real-Time Control Applications in Distributed Computer Systems,” Real-Time Systems, Vol. 14, No. 3, 1998, pp. 219-250. doi:10.1023/A:1007964222989 [27] P. Marti, J. M. Fuertes, K. Ramamritham and G. Fohler, “Jitter Compensation for Real-Time Control Systems,” 22nd IEEE Real-Time Systems Symposium, London, 3-6 December 2001, pp. 39-48. [28] S. R. Gulliver and G. Ghinea, “The Perceptual Influence of Multimedia Delay and Jitter,” IEEE International Conference on Multimedia and Expo, Beijing, 2-5 July 2007, pp. 2214-2217. doi:10.1109/ICME.2007.4285125 [29] R. E. Kontak, “Applicability of Ada Tasking for Avionics Executives,” Proceedings of the IEEE 1988 National Aerospace and Electronics Conference, Dayton, 23-27 May 1988, Vol. 2, pp. 739-746. [30] J. A. Stankovic, “Misconceptions about Real-Time Computing: A Serious Problem for Next-Generation Systems,” Computers, Vol. 21 No. 10, 1988, pp. 10-19. doi:10.1109/2.7053 [31] 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. doi:10.1007/BF01995678 [32] M. J. Pont, S. Kurian and R. Bautista-Quintero, “Meeting Real-Time Constraints Using ‘Sandwich Delays’,” Transactions on Pattern Languages of Programming I, Springer, Berlin, 2009, pp. 94-102. [33] 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. doi:10.1016/j.jss.2006.04.007 [34] M. Nahas, M. J. Pont and A. Jain, “Reducing Task Jitter in Shared-Clock Embedded Systems Using CAN,” In: A. Koelmans, A. Bystrov and M. J. Pont, Eds., Proceedings of the UK Embedded Forum, University of Newcastle upon Tyne, Newcastle, 2004, pp. 184-194. [35] 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, 2008, pp. 427-450. doi:10.1177/0142331207086183 [36] A. Burns and A. J. Wellings, “Concurrent and Real-Time Programming in Ada 2005,” Cambridge University Press, Cambridge, 2007. [37] Ashling Microsystems, “LPC2000 Evaluation and Development Kits Datasheet,” 2007. http://www.ashling.com/pdf_datasheets/DS266-EvKit2000.pdf [38] Philips Semiconductors, “LPC2106/2105/2104 USER MANUAL,” 2003. http://www.standardics.nxp.com/products/lpc2000/datasheet/lpc2104.lpc2105.lpc2106.pdf [39] National Instruments, “Low-Cost E Series Multifunction DAQ – 12 or 16-Bit, 200 kS/s, 16 Analog Inputs,” 2006. http://www.ni.com/pdf/products/us/4daqsc202-204_ETC_212-213.pdf [40] LabVIEW, “LabVIEW 7.1 Documentation Resources,” 2007. http://digital.ni.com/public.nsf/allkb/06572E936282C0E486256EB0006B70B4