Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results

Florian Kluge


The concept of a firm real-time task implies the notion of a firm deadline that should not be missed by the jobs of this task. If a deadline miss occurs, the concerned job yields no value to the system. For some applications domains, this restrictive notion can be relaxed. For example, robust control systems can tolerate that single executions of a control loop miss their deadlines, and still yield an acceptable behaviour. Thus, systems can be developed under more optimistic assumptions, e.g. by allowing overloads. However, care must be taken that deadline misses do not accumulate. This restriction can be expressed by the model of (m,k)-firm real-time tasks that require that from any k consecutive jobs at least m are executed successfully. In this article, we extend our prior work on the MKU scheduling heuristic. MKU uses history-cognisant utility functions as means for making decisions in overload situations. We present new theoretical results on MKU and on other schedulers for (m,k)-firm real-time tasks. Based on extensive simulations, we assess the performance of these
schedulers. The results allow us to identify task set characteristics that can be used as guidelines for choosing a scheduler for a concrete use case.


Real-time Scheduling; (m,k)-Firm Real-Time Tasks

Full Text:



Saud Ahmed Aldarmi and Alan Burns. Dynamic value-density for scheduling real-time systems. In 11th Euromicro Conference on Real-Time Systems (ECRTS 1999), 9-11 June 1999, York, England, UK, Proceedings, pages 270-277. IEEE Computer Society, 1999. URL: http://dx.doi.org/10.1109/EMRTS.1999.777474

Neil C. Audsley, Alan Burns, Mike M. 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

Sanjoy K. Baruah, Gilad Koren, Bhubaneswar Mishra, Arvind Raghunathan, Louis E. Rosier, and Dennis E. Shasha. On-line scheduling in the presence of overload. In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 100-110. IEEE Computer Society, 1991. URL: http://dx.doi.org/10.1109/SFCS.1991.185354

Guillem Bernat, Alan Burns, and Albert Llamosí. Weakly hard real-time systems.IEEE Trans. Computers, 50(4):308-321, 2001. URL: http://dx.doi.org/10.1109/12.919277

Alan Burns and Sanjoy K. Baruah. Sustainability in real-time scheduling.JCSE, 2(1):74-97, 2008. URL: http://jcse.kiise.org/PublishedPaper/year_abstract.asp?idx=15.

Giorgio C. Buttazzo, Marco Spuri, and Fabrizio Sensini. Value vs. deadline scheduling in overload conditions. In 16th IEEE Real-Time Systems Symposium, Palazzo dei Congressi, Via Matteotti, 1, Pisa, Italy, December 4-7, 1995, Proceedings, pages 90-99. IEEE Computer Society, 1995. URL: http://dx.doi.org/10.1109/REAL.1995.495199

Ken Chen and Paul Mühlethaler. A scheduling algorithm for tasks described by time value function. Real-Time Systems, 10(3):293-312, 1996. URL: http://dx.doi.org/10.1007/BF00383389

Hyeonjoong Cho, Yongwha Chung, and Daihee Park. Guaranteed dynamic priority assignment scheme for streams with (m, k)-firm deadlines. ETRI Journal, 32(3):500-502, June 2010. URL: http://dx.doi.org/10.4218/etrij.10.0109.0544

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen. Utility accrual real-time scheduling for multiprocessor embedded systems. J. Parallel Distrib. Comput., 70(2):101-110, 2010. URL: http://dx.doi.org/10.1016/j.jpdc.2009.10.003

Hyeonjoong Cho, Haisang Wu, Binoy Ravindran, and E. Douglas Jensen. On multiprocessor utility accrual real-time scheduling with statistical timing assurances. In Edwin Hsing-Mean Sha, Sung-Kook Han, Cheng-Zhong Xu, Moon-hae Kim, Laurence Tianruo Yang, and Bin Xiao, editors, Embedded and Ubiquitous Computing, International Conference, EUC 2006, Seoul, Korea, August 1-4, 2006, Proceedings, volume 4096 of Lecture Notes in Computer Science, pages 274-286. Springer, 2006. URL: http://dx.doi.org/10.1007/11802167_29

Raymond Keith Clark.Scheduling Dependent Real-Time Activities. PhD thesis, Carnegie Mellon University, August 1990.

Robert I. Davis, Sasikumar Punnekkat, Neil C. Audsley, and Alan Burns. Flexible scheduling for adaptable real-time systems. In 1st IEEE Real-Time Technology and Applications Symposium, Chicago, Illinois, USA, May 15-17, 1995, pages 230-239. IEEE Computer Society, 1995. URL: http://dx.doi.org/10.1109/RTTAS.1995.516220

Wanfu Ding and Ruifeng Guo. Design and evaluation of sectional real-time scheduling algorithms based on system load. In Proceedings of the 9th International Conference for Young Computer Scientists, ICYCS 2008, Zhang Jia Jie, Hunan, China, November 18-21, 2008, pages 14-18. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/ICYCS.2008.208

Felicioni Flavia, Jia Ning, Françoise Simonot-Lion, and Yeqiong Song. Optimal on-line (m, k)-firm constraint assignment for real-time control tasks based on plant state information. In Proceedings of 13th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2008, September 15-18, 2008, Hamburg, Germany, pages 908-915. IEEE, 2008. URL: http://dx.doi.org/10.1109/ETFA.2008.4638504

Oliver Gettings, Sophie Quinton, and Robert I. Davis. Mixed criticality systems with weakly-hard constraints. In Julien Forget, editor, Proceedings of the 23rd International Conference on Real Time Networks and Systems, RTNS 2015, Lille, France, November 4-6, 2015, pages 237-246. ACM, 2015. URL: http://dx.doi.org/10.1145/2834848.2834850

Joël Goossens. (m,k)-firm constraints and dbp scheduling: Impact of the initial k-sequence and exact feasibility test. In 16th International Conference on Real-Time and Network Systems (RTNS'08), pages 61-66, October 2008.

Joël Goossens and Christophe Macq. Limitation of the hyper-period in real-time periodic task set generation. In Proceedings of the 9th International Conference on Real-Time Systems (RTS'01), pages 133-148, March 2001.

Moncef Hamdaoui and Parameswaran Ramanathan. A dynamic priority assignement technique for streams with (m, k)-firm deadlines.IEEE Trans. Computers, 44(12):1443-1451, 1995. URL: http://dx.doi.org/10.1109/12.477249

E. Douglas Jensen, C. Douglas Locke, and Hideyuki Tokuda. A time-driven scheduling model for real-time operating systems. In 6th Real-Time Systems Symposium (RTSS '85), December 3-6, 1985, San Diego, California, USA, pages 112-122, December 1985.

Ning Jia, Ye-Qiong Song, and Françoise Simonot-Lion.Task Handler Based on (m,k)-firm Constraint Model for Managing a Set of Real-Time Controllers. In Nicolas Navet, Françoise Simonot-Lion, and Isabelle Puaut, editors, 15th International Conference on Real-Time and Network Systems - RTNS 2007, pages 183-194, Nancy, France, 2007. URL: http://hal.inria.fr/inria-00189899.

Florian Kluge.tms-sim - timing models scheduling simulation framework - release 2014-12. Technical Report 2014-07, University of Augsburg, December 2014. URL: http://dx.doi.org/10.13140/2.1.1251.2321

Florian Kluge. Notes on the generation of spin-values for fixed (m,k)-patterns. Technical Report 2016-01, University of Augsburg, January 2016.

Florian Kluge, Mike Gerdes, Florian Haas, and Theo Ungerer. A generic timing model for cyber-physical systems. In Workshop Reconciling Performance and Predictability (RePP'14), Grenoble, France, April 2014. URL: http://dx.doi.org/10.13140/2.1.1820.4165

Florian Kluge, Florian Haas, Mike Gerdes, and Theo Ungerer. History-cognisant time-utility-functions for scheduling overloaded real-time control systems. In Proceedings of 7th Junior Researcher Workshop on Real-Time Computing (JRWRTC 2013), Sophia Antipolis, France, October 2013.

Florian Kluge, Markus Neuerburg, and Theo Ungerer. Utility-based scheduling of (m, k) -firm real-time task sets. In Luís Miguel Pinho, Wolfgang Karl, Albert Cohen, and Uwe Brinkschulte, editors, Architecture of Computing Systems - ARCS 2015 - 28th International Conference, Porto, Portugal, March 24-27, 2015, Proceedings, volume 9017 of Lecture Notes in Computer Science, pages 201-211. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-16086-3_16

Gilad Koren and Dennis E. Shasha. D^over; an optimal on-line scheduling algorithm for overloaded real-time systems. In Proceedings of the Real-Time Systems Symposium - 1992, Phoenix, Arizona, USA, December 1992, pages 290-299. IEEE Computer Society, 1992. URL: http://dx.doi.org/10.1109/REAL.1992.242650

Gilad Koren and Dennis E. Shasha. An approach to handling overloaded systems that allow skips. In 16th IEEE Real-Time Systems Symposium, Palazzo dei Congressi, Via Matteotti, 1, Pisa, Italy, December 4-7, 1995, Proceedings, pages 110-119. IEEE Computer Society, 1995. URL: http://dx.doi.org/10.1109/REAL.1995.495201

Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmark for free. In 6th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2015), July 7, 2015, Lund, Sweden, July 2015.

John P. Lehoczky, Lui Sha, and Y. Ding. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of the Real-Time Systems Symposium - 1989, Santa Monica, California, USA, December 1989, pages 166-171. IEEE Computer Society, 1989. URL: http://dx.doi.org/10.1109/REAL.1989.63567

Peng Li and Binoy Ravindran. Fast, best-effort real-time scheduling algorithms.IEEE Trans. Computers, 53(9):1159-1175, 2004. URL: http://dx.doi.org/10.1109/TC.2004.61

Peng Li, Haisang Wu, Binoy Ravindran, and E. Douglas Jensen. A utility accrual scheduling algorithm for real-time activities with mutual exclusion resource constraints.IEEE Trans. Computers, 55(4):454-469, 2006. URL: http://dx.doi.org/10.1109/TC.2006.47

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

Carey Douglass Locke. Best-effort decision-making for real-time scheduling. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, 1986. URL: http://douglocke.com/Downloads/BE.pdf.

Pedro Mejía-Alvarez, Rami G. Melhem, and Daniel Mossé. An incremental approach to scheduling during overloads in real-time systems. In Proceedings of the 21st IEEE Real-Time Systems Symposium (RTSS 2000), Orlando, Florida, USA, 27-30 November 2000, pages 283-294. IEEE Computer Society, 2000. URL: http://dx.doi.org/10.1109/REAL.2000.896017

Daniel Mossé, Martha E. Pollack, and Yagíl Ronén. Value-density algorithms to handle transient overloads in scheduling. In 11th Euromicro Conference on Real-Time Systems (ECRTS 1999), 9-11 June 1999, York, England, UK, Proceedings, pages 278-286. IEEE Computer Society, 1999. URL: http://dx.doi.org/10.1109/EMRTS.1999.777475

Enrico Poggi, Yeqiong Song, Anis Koubaa, and Zhi Wang. Matrix-dbp for (m, k)-firm real-time guarantee. In Real-Time Systems Conference RTS'2003, Paris (France), pages 457-482, 2003.

Gang Quan and Xiaobo Sharon Hu. Enhanced fixed-priority scheduling with (m, k)-firm guarantee. In Proceedings of the 21st IEEE Real-Time Systems Symposium (RTSS 2000), Orlando, Florida, USA, 27-30 November 2000, pages 79-88. IEEE Computer Society, 2000. URL: http://dx.doi.org/10.1109/REAL.2000.895998

Parameswaran Ramanathan. Overload management in real-time control applications using (m, k)-firm guarantee.IEEE Trans. Parallel Distrib. Syst., 10(6):549-559, 1999. URL: http://dx.doi.org/10.1109/71.774906

J.-H. Rhu, J.-H. Sun, K. Kim, H. Cho, and J.K. Park. Utility accrual real-time scheduling for (m, k)-firm deadline-constrained streams on multiprocessors. Electronics Letters, 47(5):316-317, 2011. URL: http://dx.doi.org/10.1049/el.2010.7980

Tiago Semprebom, Carlos Montez, and Francisco Vasques. (m, k)-firm pattern spinning to improve the GTS allocation of periodic messages in IEEE 802.15.4 networks.EURASIP J. Wireless Comm. and Networking, 2013:222, 2013. URL: http://dx.doi.org/10.1186/1687-1499-2013-222

Sivakumar Swaminathan and Govindarasu Manimaran.A Reliability-Aware Value-Based Scheduler for Dynamic Multiprocessor Real-Time Systems. In Proceedings of the 16th International Parallel and Distributed Processing Symposium, IPDPS '02, pages 39-, Washington, DC, USA, 2002. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=645610.661233.

Terry Tidwell, Robert Glaubius, Christopher D. Gill, and William D. Smart. Optimizing expected time utility in cyber-physical systems schedulers. In Proceedings of the 31st IEEE Real-Time Systems Symposium, RTSS 2010, San Diego, California, USA, November 30 - December 3, 2010, pages 193-201. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/RTSS.2010.28

Jinggang Wang and Binoy Ravindran. Time-utility function-driven switched ethernet: Packet scheduling algorithm, implementation, and feasibility analysis.IEEE Trans. Parallel Distrib. Syst., 15(2):119-133, 2004. URL: http://dx.doi.org/10.1109/TPDS.2004.1264796

Richard West and Karsten Schwan. Dynamic window-constrained scheduling for multimedia applications. In IEEE International Conference on Multimedia Computing and Systems, ICMCS 1999, Florence, Italy, June 7-11, 1999. Volume II, pages 87-91. IEEE Computer Society, 1999. URL: http://dx.doi.org/10.1109/MMCS.1999.778145

Haisang Wu, Binoy Ravindran, E. Douglas Jensen, and Umut Balli. Utility accrual scheduling under arbitrary time/utility functions and multiunit resource constraints. In in IEEE Real-Time and Embedded Computing Systems and Applications, pages 80-98, 2004.

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

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

Copyright (c) 2016 Florian Kluge

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.