×

Optimal resource allocation for stochastic systems performance optimisation of control tasks undergoing stochastic execution times. (English) Zbl 1482.93701

Summary: The problem addressed in this paper is the optimal allocation of a CPU to a number of software control tasks. Each task is used to implement a feedback controller for a linear and time invariant system and is activated with a fixed period. On every periodic activation, the task executes a job, which collects the output of the system, and produces the control values after executing for a random computation time. If a job’s duration exceeds a deadline, then the job is cancelled and the control values are not updated. The systems to be controlled are affected by process noise. Therefore the performance of each control loop can be evaluated through the steady-state covariance of the system’s state, which depends on the probability with which the task implementing the controller drops its jobs. We show that by making a proper choice for the scheduling algorithm, this probability can be straightforwardly computed as a function of the scheduling parameters. This observation enables the construction of a very efficient procedure for finding the scheduling parameters that attain the optimal tradeoff between the performance of the different control loops.

MSC:

93E20 Optimal stochastic control
93C30 Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems)
93B52 Feedback control
93C83 Control/observation systems involving computers (process control, etc.)
68Q99 Theory of computing

Software:

PROSIT
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abeni, L., & Buttazzo, G. (1998, December). Integrating multimedia applications in hard real-time systems. Proceedings 19th IEEE real-time systems symposium (pp. 4-13). IEEE.
[2] Aminifar, A.; Bini, E.; Eles, P.; Peng, Z., Analysis and design of real-time servers for control applications, IEEE Transactions on Computers, 65, 3, 834-846 (2016) · Zbl 1360.93411 · doi:10.1109/TC.2015.2435789
[3] Aminifar, A., Tabuada, P., Eles, P., & Peng, Z. (2016, March). Self-triggered controllers and hard real-time guarantees. 2016 design, automation test in Europe conference exhibition (date) (pp. 636-641). IEEE.
[4] Bernstein, D. S., Matrix mathematics: Theory, facts, and formulas (2009), Princeton University Press · Zbl 1183.15001
[5] Borgers, D.; Postoyan, R.; Anta, A.; Tabuada, P.; Nešić, D.; Heemels, W., Periodic event-triggered control of nonlinear systems using overapproximation techniques, Automatica, 94, 81-87 (2018) · Zbl 1400.93186 · doi:10.1016/j.automatica.2018.04.019
[6] Cervin, A., & Eker, J. (2003). The control server: A computational model for real-time control tasks. In ECRTS (pp. 113-120). IEEE Computer Society.
[7] Costa, O.; Fragoso, M.; Marques, R., Discrete-time Markov jump linear systems (2006), Springer · Zbl 1081.93001
[8] The Economist (2016, May 25). The long, winding road for driverless cars.
[9] Elsner, L.; Szulc, T., Convex sets of Schur stable and stable matrices, Linear and Multilinear Algebra, 48, 1, 1-19 (2000) · Zbl 0970.15009 · doi:10.1080/03081080008818656
[10] Fontanelli, D.; Greco, L.; Palopoli, L., Soft real-time scheduling for embedded control systems, Automatica, 49, 8, 2330-2338 (2013) · Zbl 1364.93499 · doi:10.1016/j.automatica.2013.04.036
[11] Fontanelli, D., & Palopoli, L. (2018, June). On soft real-time implementation of LQG controllers. IEEE international symposium on industrial embedded systems (SIES) (pp. 1-8). IEEE.
[12] Fontanelli, D., Palopoli, L., & Greco, L. (2013, April). Optimal CPU allocation to a set of control tasks with soft real-time execution constraints. Hybrid systems: Computation and control (HSCC) (pp. 233-242). ACM. · Zbl 1361.68020
[13] Frías, B. V.; Palopoli, L.; Abeni, L.; Fontanelli, D., The PROSIT tool: Towards the optimal design of probabilistic soft real-time systems, Journal of Software: Practice and Experience, 48, 11, 1940-1967 (2018) · doi:10.1002/spe.2604
[14] Fürst, S. (2010, March). Challenges in the design of automotive software. 2010 design, automation test in Europe conference exhibition (pp. 256-258). IEEE.
[15] Greco, L.; Fontanelli, D.; Bicchi, A., Design and stability analysis for anytime control via stochastic scheduling, IEEE Transactions on Automatic Control, 56, 3, 571-585 (2011) · Zbl 1368.90082 · doi:10.1109/TAC.2010.2058497
[16] Kao, C.; Rantzer, A., Stability analysis of systems with uncertain time-varying delays, Automatica, 43, 6, 959-970 (2007) · Zbl 1282.93203 · doi:10.1016/j.automatica.2006.12.006
[17] Kopetz, H.; Bauer, G., The time-triggered architecture, Proceedings of the IEEE, 91, 1, 112-126 (2003) · doi:10.1109/JPROC.2002.805821
[18] Ling, Q., & Lemmon, M. (2002, December). Robust performance of soft real-time networked control systems with data dropouts. Proceedings of the 41st IEEE conference on decision and control (Vol. 2, pp. 1225-1230). IEEE.
[19] Liu, C. L.; Layland, J., Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the ACM, 20, 1, 46-61 (1973) · Zbl 0265.68013 · doi:10.1145/321738.321743
[20] Marti, P., Fuertes, J., Fohler, G., & Ramamritham, K. (2001, December). Jitter compensation for real-time control systems. Proceedings 22nd IEEE real-time systems symposium (pp. 39-48). IEEE.
[21] Mohamed, S., Awan, A. U., Goswami, D., & Basten, T. (2019). Designing image-based control systems considering workload variations. Proceeding of 58th conference on decision and control. IEEE.
[22] Nilsson, J., & Bernhardsson, B. (1996, December). Analysis of real-time control systems with time delays. Proceedings of 35th IEEE conference on decision and control (Vol. 3, pp. 3173-3178). IEEE.
[23] Palopoli, L.; Pinello, C.; Bicchi, A.; Sangiovanni-Vincentelli, A., Maximizing the stability radius of a set of systems under real-time scheduling constraints, IEEE Transactions on Automatic Control, 50, 11, 1790-1795 (2005) · Zbl 1365.90144 · doi:10.1109/TAC.2005.858639
[24] Roberts, J., A survey on statistical bandwidth sharing, Computer Networks, 45, 3, 319-332 (2004) · Zbl 1070.68504 · doi:10.1016/j.comnet.2004.03.010
[25] Seto, D., Lehoczky, J., Sha, L., & Shin, K. (1996). On task schedulability in real-time control systems. IEEE real-time systems symposium (pp. 13-21). IEEE.
[26] Velasco, M., Martí, P., & Bini, E. (2008). Control-driven tasks: Modeling and analysis. IEEE real-time systems symposium (pp. 280-290). IEEE Computer Society.
[27] Wang, X.; Lemmon, M. D., Event-triggering in distributed networked control systems, IEEE Transactions on Automatic Control, 56, 3, 586-601 (2011) · Zbl 1368.93211 · doi:10.1109/TAC.2010.2057951
[28] Xu, Y., Cervin, A., & Årzén, K. (2018, June). Jitter-robust LQG control and real-time scheduling co-design. 2018 annual American control conference (ACC) (pp. 3189-3196). IEEE.
[29] Xu, Y., Cervin, A., & Årzén, K. E. (2016, August). Harmonic scheduling and control co-design. 2016 IEEE 22nd international conference on embedded and real-time computing systems and applications (RTCSA) (pp. 182-187). IEEE.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.