zbMATH — the first resource for mathematics

Priority-free conditionally-preemptive scheduling of modular sporadic real-time systems. (English) Zbl 1388.93015
Summary: For a Real-Time System (RTS) processing both sporadic and (multiple-period) periodic tasks, this study presents a novel modular modeling framework to describe the parameters of tasks, conforming to the pertinent concepts and techniques of Discrete-Event Systems (DES). A task is represented by an automaton synchronized by the modular models corresponding to its parameters. As a consequence, a DES model depicting the RTS is synchronized by the DES representing these tasks. Based on supervisory control theory, Priority-Free Conditionally-Preemptive (PFCP) real-time scheduling is solved by finding all the safe execution sequences. Finally, the PFCP scheduling is illustrated by real-world examples.

93A30 Mathematical modelling of systems (MSC2010)
90B36 Stochastic scheduling theory in operations research
93C65 Discrete event control/observation systems
Cheddar; Kronos
Full Text: DOI
[1] Alareqi, S.; Gorges, D.; Liu, S., Event-based networked control and scheduling codesign with guaranteed performance, Automatica, 57, 128-134, (2015) · Zbl 1330.93154
[2] Baruah, S. (2005). The limited-preemption uniprocessor scheduling of sporadic task systems. In Proceedings of 17th euromicro conference on real-time systems (pp. 137-144).
[3] Chen, P. C.Y.; Wonham, W. M., Real-time supervisory control of a processor for non-preemptive execution of periodic tasks, Real-Time Systems, 23, 183-208, (2002) · Zbl 1012.68019
[4] Cury, J. E.; De Queiroz, M. H.; Bouzon, G.; Teixeira, M., Supervisory control of discrete event systems with distinguishers, Automatica, 56, 93-104, (2015) · Zbl 1323.93049
[5] Fontanelli, D.; Greco, L.; Palopoli, L., Soft real-time scheduling for embedded control systems, Automatica, 49, 2330-2338, (2013) · Zbl 1364.93499
[6] Janarthanan, V.; Gohari, P.; Saffar, A., Formalizing real-time scheduling using priority-based supervisory control of discrete-event systems, IEEE Transactions on Automatic Control, 51, 6, 1053-1058, (2006) · Zbl 1366.93349
[7] Kronos, Yovine S., A verification tool for real-time systems, International Journal of Software Tools and Technology Transfer, 1, 1, 123-133, (1997) · Zbl 1060.68606
[8] Liu, C. L.; Layland, J. W., Scheduling algorithms for multiprogramming in a hard real time environment, Journal of the ACM, 20, 1, 46-61, (1973) · Zbl 0265.68013
[9] Nassor, E., & Bres, G. (1991). Hard real-time sporadic task scheduling for fixed priority schedulers. In Proceedings of international workshop on responsive systems (pp. 44-47).
[10] Park, S.-J.; Cho, K.-H., Real-time preemptive scheduling of sporadic tasks based on supervisory control of discrete event systems, Information Sciences, 178, 17, 3393-3401, (2008) · Zbl 1142.90409
[11] Ramadge, P. J.; Wonham, W. M., Supervisory control of a class of discrete event processes, SIAM Journal on Control and Optimization, 25, 1, 206-230, (1987) · Zbl 0618.93033
[12] Singhoff, F., Legrand, J., Nana, L., & Marce, L. (2004). Cheddar: A flexible real time scheduling framework. In Proceedings of international ACM SIGAda conference (pp. 1-8).
[13] Su, R.; Wonham, W. M., Supervisor reduction for discrete-event systems, Discrete Event Dynamic Systems, 14, 1, 31-53, (2004) · Zbl 1035.93048
[14] Veenman, J.; Scherer, C., A synthesis framework for robust gain-scheduling controllers, Automatica, 50, 2799-2812, (2014) · Zbl 1300.93062
[15] Wang, X.; Khemaissia, I.; Khalgui, M.; Li, Z. W.; Mosbahi, O.; Zhou, M. C., Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks, IEEE Transactions on Automation Science and Engineering, 12, 1, 258-271, (2015)
[16] Wang, X.; Li, Z. W.; Wonham, W. M., Dynamic multiple-period reconfiguration of real-time scheduling based on timed DES supervisory control, IEEE Transactions on Industrial Informatics, 12, 1, 101-111, (2016)
[17] Wang, X.; Li, Z. W.; Wonham, W. M., Optimal priority-free conditionally-preemptive real-time scheduling of periodic tasks based on DES supervisory control, IEEE Transitions on Systems, Man and Cybernetics: Systems, 47, 7, 1082-1098, (2017)
[18] Wang, Y.; Saksena, M., Scheduling fixed-priority tasks with preemption threshold, Proceedings of the Real-Time Computing Systems and Applications, 328-335, (1999)
[19] Wonham, W. M.; Cai, K., Supervisory control of discrete-event systems, (2017), Department of Electrical and Computer Engineering, University of Toronto, Available at http://www.control.utoronto.ca/DES
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.