Planificación de sistemas de tiempo real crítico mediante técnicas no convencionales
DOI:
https://doi.org/10.4995/riai.2022.17148Palabras clave:
Sistemas de control de tiempo real, Sistemas de control embebidos o empotrados, Planificación y planificabilidad de sistemas de control, Sistemas ciber-físicos en controlResumen
En la planificación de sistemas de tiempo real crítico es clave encontrar un plan temporal en el que las tareas pueden ejecutarse antes de que venza el plazo establecido. Para lograr este objetivo se pueden utilizar diferentes tipos de algoritmos de planificación. Además de encontrar un plan factible, muchas veces es beneficioso, de todos los planes factibles existentes, encontrar aquel que minimiza algún parámetro temporal del sistema. Existen muchos algoritmos de planificación que son capaces de encontrar una planificación correcta del conjunto de tareas. Pero no es tan común encontrar algoritmos que optimicen otros parámetros para mejorar el funcionamiento del sistemas en términos de estabilidad, consumo de potencia, etc. Los heurísticos existentes puede mejorar el comportamiento pero sin asegurar un resultado óptimo. En este trabajo exploramos las técnicas de planificación no convencionales basadas en programación lineal entera para resolver la planificación en sistemas mono procesador con el objetivo de minimizar el peor tiempo de respuesta y el cambio de contexto de las tareas del sistema y la asignación de tareas a procesadores en sistemas multiprocesador con el objetivo de minimizar la interferencia producida por el acceso a recursos hardware comunes.
Descargas
Citas
Baker, T. P., Shaw, A., Dec 1988. The cyclic executive model and ada. En:Proceedings. Real-Time Systems Symposium. pp. 120-129.DOI: 10.1109/REAL.1988.51108 https://doi.org/10.1109/REAL.1988.51108
Baruah, S., 2004. Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platforms. En: 25th IEEE International Real-Time Systems Symposium. pp. 37-46.
Baruah, S., Mar. 2022. An ILP representation of a DAG scheduling problem. Real-Time Systems 58 (1), 85-102. https://doi.org/10.1007/s11241-021-09370-7
Crespo, A., Ripoll, I., Albertos, P., 1999. Reducing delays in rt control: The control action interval. IFAC Proceedings Volumes 32 (2), 8527 - 8532, 14th IFAC World Congress 1999, Beijing, Chia, 5-9 July. https://doi.org/10.1016/S1474-6670(17)57454-6
Dasari, D., Andersson, B., Nelis, V., Petters, S. M., Easwaran, A., Lee, J., 2011. Response time analysis of cots-based multicores considering the contention on the shared memory bus. In: 2011IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications. pp. 1068-1075. https://doi.org/10.1109/TrustCom.2011.146
Davis, R. I., Burns, A., Dec 2009. Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In: 2009 30th IEEE Real-Time Systems Symposium. pp. 398-409. https://doi.org/10.1109/RTSS.2009.31
Davis, R. I., Burns, A., Oct. 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. 43 (4). https://doi.org/10.1145/1978802.1978814
Davis, R. I., Griffin, D., Bate, I., 2021. Schedulability analysis for multi-core systems accounting for resource stress and sensitivity. In: 33rd Euromicro Conference on Real-Time Systems, ECRTS 2021. https://doi.org/10.1007/s11241-022-09377-8
Di Natale, M., Zeng, H., 04 2013. An efficient formulation of the real-time feasibility region for design optimization. IEEE Transactions on Computers 62, 644-661. https://doi.org/10.1109/TC.2012.21
Fernandez, G., Abella, J., Quiñones, E., Rochange, C., Vardanega, T., Cazorla,F., 2014. Contention in multicore hardware shared resources: Understanding of the state of the art. En: WCET.
Fleming, T., Burns, A., 2015. Investigating mixed criticality cyclic executive schedule generation. En: Proc. Workshop on Mixed Criticality (WMC).
Guasque, A., Tohidi, H., Balbastre, P., Aceituno, J. M., Simo, J., Crespo, A., 2020. Integer programming techniques for static scheduling of hard realtime systems. IEEE Access 8, 170389-170403. https://doi.org/10.1109/ACCESS.2020.3024698
Gurobi, 2019. Gurobi optimizer reference manual. Inc. Gurobi Optimization.
Harter, Jr., P. K., Aug. 1987. Response times in level-structured systems. ACM Trans. Comput. Syst. 5 (3), 232-248. DOI: 10.1145/24068.24069 https://doi.org/10.1145/24068.24069
Hong, I., Kirovski, D., Gang Qu, Potkonjak, M., Srivastava, M. B., 1999. Power optimization of variable-voltage core-based systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 18 (12), 1702-1714. https://doi.org/10.1109/43.811318
Joseph, M., Pandya, P., 1986. Finding response times in a real-time system. The Computer Journal 29 (5), 390-395. DOI: 10.1093/comjnl/29.5.390 https://doi.org/10.1093/comjnl/29.5.390
Kim, H., de Niz, D., Andersson, B., Klein, M., Mutlu, O., Rajkumar, R., 2014. Bounding memory interference delay in cots-based multi-core systems. In: 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS). pp. 145-154. https://doi.org/10.1109/RTAS.2014.6925998
Lampka, K., Giannopoulou, G., Pellizzoni, R., Wu, Z., Stoimenov, N., 11 2014. A formal approach to the wcrt analysis of multicore systems with memory contention under phase-structured task sets. Real-Time Systems 50, 736-773. https://doi.org/10.1007/s11241-014-9211-y
Leung, J., Whitehead, J., 1982. On the complexity of fixed-priority schedulings of periodic, real-time tasks. Performance Evaluation 2 (4), 237-250. https://doi.org/10.1016/0166-5316(82)90024-4
Lisper, B., Mellgren, P., 10 2001. Response-time calculation and priority assignment with integer programming methods.
Liu, C. L., Layland, J. W., Jan. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20 (1), 46-61. https://doi.org/10.1145/321738.321743
Locke, C. D., Mar. 1992. Software architecture for hard real-time applications: Cyclic executives vs. fixed priority executives. Real-Time Syst. 4 (1), 37-53. DOI: 10.1007/BF00365463 https://doi.org/10.1007/BF00365463
Maiza, C., Rihani, H., Rivas, J. M., Goossens, J., Altmeyer, S., Davis, R. I., jun 2019. A survey of timing verification techniques for multi-core real-time systems. ACM Comput. Surv. 52 (3). https://doi.org/10.1145/3323212
Mangeruca, L., Baleani, M., Ferrari, A., Sangiovanni-Vincentelli, A., Dec. 2007. Uniprocessor scheduling under precedence constraints for embedded systems design. ACM Trans. Embed. Comput. Syst. 7 (1). https://doi.org/10.1145/1324969.1324975
Nguyen, V. A., Hardy, D., Puaut, I., 2019. Cache-conscious off-line real-time scheduling for multi-core platforms: algorithms and implementation. Real-Time Systems 55 (4), 810-849.DOI: 10.1007/s11241-019-09333-z https://doi.org/10.1007/s11241-019-09333-z
Sun, Y., Natale, M. D., Sep. 2017. Weakly hard schedulability analysis for fixed priority scheduling of periodic real-time tasks. ACM Trans. Embed. Comput. Syst. 16 (5s). DOI: 10.1145/3126497 https://doi.org/10.1145/3126497
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2022 Revista Iberoamericana de Automática e Informática industrial
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Esta revista se publica bajo una Licencia Creative Commons Attribution-NonCommercial-CompartirIgual 4.0 International (CC BY-NC-SA 4.0)
Datos de los fondos
-
Ministerio de Ciencia e Innovación
Números de la subvención proyecto de I+D+i PLEC2021-007609 -
Agencia Estatal de Investigación
Números de la subvención 10.13039/501100011033