A Note on the Period Enforcer Algorithm for Self-Suspending Tasks

Jian-Jia Chen, Björn B. Brandenburg

Abstract


The period enforcer algorithm for self-suspending real-time tasks is a technique for suppressing the "back-to-back" scheduling penalty associated with deferred execution. Originally proposed in 1991, the algorithm has attracted renewed interest in recent years. This note revisits the algorithm in the light of recent developments in the analysis of self-suspending tasks, carefully re-examines and explains its underlying assumptions and limitations, and points out three observations that have not been made in the literature to date: (i) period enforcement is not strictly superior (compared to the base case without enforcement) as it can cause deadline misses in self-suspending task sets that are schedulable without enforcement; (ii) to match the assumptions underlying the analysis of the period enforcer, a schedulability analysis of self-suspending tasks subject to period enforcement requires a task set  transformation for which no solution is known  in the general case, and which is subject to exponential time complexity (with current techniques) in the limited case of a single self-suspending task; and (iii) the period enforcer algorithm is incompatible with all existing analyses of suspension-based locking protocols, and can in fact cause ever-increasing suspension times until a deadline is missed.


Keywords


Period Enforcer; Deferred Execution; Self-suspension; Blocking

Full Text:

PDF

References


Neil Audsley, Alan Burns, Mike Richardson, Ken Tindell, and Andy J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284-292, 1993. URL: http://dx.doi.org/10.1049/sej.1993.0034

Aaron Block, Hennadiy Leontyev, Björn B. Brandenburg, and James H. Anderson. A flexible real-time locking protocol for multiprocessors. In Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 47-56. IEEE Computer Society, 2007. URL: http://dx.doi.org/10.1109/RTCSA.2007.8

Björn B. Brandenburg. Improved analysis and evaluation of real-time semaphore protocols for P-FP scheduling. In Proceedings of the 19th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 141-152. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/RTAS.2013.6531087

Björn B. Brandenburg. Blocking optimality in distributed real-time locking protocols. Leibniz Transactions on Embedded Systems, 1(2):01:1-01:22, 2014. URL: http://dx.doi.org/10.4230/LITES-v001-i002-a001

Björn B. Brandenburg and James H. Anderson. A comparison of the M-PCP, D-PCP, and FMLP on LITMUSRT. In Proceedings of the 12th International Conference on Principles of Distributed Systems (OPODIS), volume 5401 of Lecture Notes in Computer Science, pages 105-124. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92221-6_9

Björn B. Brandenburg and James H. Anderson. An implementation of the PCP, SRP, D-PCP, M-PCP, and FMLP real-time synchronization protocols in LITMUSRT. In Proceedings of the 14th IEEE Internationl Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 185-194. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/RTCSA.2008.13

Jian-Jia Chen. Computational complexity and speedup factors analyses for self-suspending tasks. In Proceedings of the 37th IEEE Real-Time Systems Symposium (RTSS), pages 327-338. IEEE Computer Society, 2016.

Jian-Jia Chen. A note on the exact schedulability analysis for segmented self-suspending systems. The Computing Research Repository (CoRR), abs/1605.00124, 2016. URL: http://arxiv.org/abs/1605.00124.

Jian-Jia Chen and Cong Liu. Fixed-relative-deadline scheduling of hard real-time tasks with self-suspensions. In Proceedings of the 35th IEEE Real-Time Systems Symposium (RTSS), pages 149-160. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/RTSS.2014.31

Jian-Jia Chen, Geoffrey Nelissen, Wen-Hung Huang, Maolin Yang, Björn B. Brandenburg, Konstantinos Bletsas, Cong Liu, Pascal Richard, Frédéric Ridouard, Neil Audsley, Ragunathan Rajkumar, and Dionisio de Niz. Many suspensions, many problems: A review of self-suspending tasks in real-time systems. Technical Report 854, Department of Computer Science, TU Dortmund, 2016. URL: http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-chen-techreport-854.pdf.

Hiroyuki Chishiro and Nobuyuki Yamasaki. Global semi-fixed-priority scheduling on multiprocessors. In Proceedings of the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 218-223. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/RTCSA.2011.32

Wen-Hung Huang and Jian-Jia Chen. Self-suspension real-time tasks under fixed-relative-deadline fixed-priority scheduling. In Proceedings of the 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1078-1083. IEEE, 2016. URL: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=7459469.

Junsung Kim, Björn Andersson, Dionisio de Niz, and Ragunathan Rajkumar. Segment-fixed priority scheduling for self-suspending real-time tasks. In Proceedings of the 34th IEEE Real-Time Systems Symposium (RTSS), pages 246-257. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/RTSS.2013.32

Karthik Lakshmanan. Scheduling and Synchronization for Multi-core Real-time Systems. PhD thesis, Carnegie Mellon University, 2011. URL: https://www.ece.cmu.edu/research/publications/2011/CMU-ECE-2011-040.pdf.

Karthik Lakshmanan, Dionisio de Niz, and Ragunathan Rajkumar. Coordinated task scheduling, allocation and synchronization on multiprocessors. In Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS), pages 469-478. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/RTSS.2009.51

Karthik Lakshmanan and Ragunathan Rajkumar. Scheduling self-suspending real-time tasks with rate-monotonic priorities. In Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 3-12. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/RTAS.2010.38

John P. Lehoczky, Lui Sha, and Jay K. Strosnider. Enhanced aperiodic responsiveness in hard real-time environments. In Proceedings of the 8th IEEE Real-Time Systems Symposium (RTSS), pages 261-270. IEEE Computer Society, 1987.

John P. Lehoczky, Lui Sha, Jay K. Strosnider, and Hideyuki Tokuda. Fixed priority scheduling theory for hard real-time systems. In Andreé van Tilborg and Gary Koob, editors, Fondations of Real-Time Computing: Scheduling and Resource Management, chapter 1, pages 1-30. Kluwer Academic Publishers, 1991.

C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1):46-61, 1973. URL: http://dx.doi.org/10.1145/321738.321743

Cong Liu and James H. Anderson. Task scheduling with self-suspensions in soft real-time multiprocessor systems. In Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS), pages 425-436. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/RTSS.2009.10

Cong Liu and James H. Anderson. Improving the schedulability of sporadic self-suspending soft real-time multiprocessor task systems. In Proceedings of the 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 13-22. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/RTCSA.2010.14

Cong Liu and James H. Anderson. Scheduling suspendable, pipelined tasks with non-preemptive sections in soft real-time multiprocessor systems. In Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 23-32. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/RTAS.2010.12

Cong Liu and Jian-Jia Chen. Bursty-interference analysis techniques for analyzing complex real-time task models. In Proceedings of the 35th IEEE Real-Time Systems Symposium (RTSS), pages 173-183. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/RTSS.2014.10

Aloysius Mok. Fundamental Design Problems of Distributed Systems for the Hard-Real-Time Environment. PhD thesis, Massachusetts Institute of Technology, 1983. URL: https://dspace.mit.edu/handle/1721.1/15670.

Geoffrey Nelissen, José Fonseca, Gurulingesh Raravi, and Vincent Nélis. Timing analysis of fixed priority self-suspending sporadic tasks. In Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS), pages 80-89. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/ECRTS.2015.15

Ragunathan Rajkumar. Real-time synchronization protocols for shared memory multiprocessors. In Proceedings of the 10th International Conference on Distributed Computing Systems (ICDCS), pages 116-123. IEEE Computer Society, 1990. URL: http://dx.doi.org/10.1109/ICDCS.1990.89257

Ragunathan Rajkumar. Dealing with suspending periodic tasks. Technical report, IBM T. J. Watson Research Center, 1991.

Ragunathan Rajkumar. Synchronization in Real-Time Systems: A Priority Inheritance Approach. Kluwer Academic Publishers, Norwell, MA, USA, 1991.

Ragunathan Rajkumar, Lui Sha, and John P. Lehoczky. Real-time synchronization protocols for multiprocessors. In Proceedings of the 9th IEEE Real-Time Systems Symposium (RTSS), pages 259-269. IEEE Computer Society, 1988. URL: http://dx.doi.org/10.1109/REAL.1988.51121

Frédéric Ridouard, Pascal Richard, and Francis Cottet. Negative results for scheduling independent hard real-time tasks with self-suspensions. In Proceedings of the 25th IEEE Real-Time Systems Symposium (RTSS), pages 47-56. IEEE Computer Society, 2004. URL: http://dx.doi.org/10.1109/REAL.2004.35

Jay K. Strosnider, John P. Lehoczky, and Lui Sha. The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments.IEEE Transactions on Computers, 44(1):73-91, 1995. URL: http://dx.doi.org/10.1109/12.368008

Jun Sun and Jane W.-S. Liu. Synchronization protocols in distributed real-time systems. In Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS), pages 38-45. IEEE Computer Society, 1996. URL: http://dx.doi.org/10.1109/ICDCS.1996.507899




DOI: http://dx.doi.org/10.4230/LITES-v004-i001-a001

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v004-i001-a001-pdf1



Copyright (c) 2016 Jian-Jia Chen and Björn B. Brandenburg

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en

Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing.