Planificación de sistemas de tiempo real crí­tico mediante técnicas no convencionales

Autores/as

  • Patricia Balbastre Universitat Politècnica de València https://orcid.org/0000-0001-9458-4083
  • José María Aceituno Universitat Politècnica de València
  • Ana Guasque Universitat Politècnica de València
  • Juan Francisco Blanes Universitat Politècnica de València
  • Alfons Crespo Universitat Politècnica de València
  • José Luis Poza

DOI:

https://doi.org/10.4995/riai.2022.17148

Palabras 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 control

Resumen

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

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

Patricia Balbastre, Universitat Politècnica de València

Instituto de Automática e Informática Industrial

José María Aceituno, Universitat Politècnica de València

Instituto de Automática e Informática Industrial

Ana Guasque, Universitat Politècnica de València

Instituto de Automática e Informática Industrial

Juan Francisco Blanes, Universitat Politècnica de València

Instituto de Automática e Informática Industrial

Alfons Crespo, Universitat Politècnica de València

Instituto de Automática e Informática Industrial

José Luis Poza

Instituto de Automática e Informática Industrial

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

22-03-2022

Cómo citar

Balbastre, P., Aceituno, J. M., Guasque, A., Blanes, J. F., Crespo, A. y Poza, J. L. (2022) «Planificación de sistemas de tiempo real crí­tico mediante técnicas no convencionales», Revista Iberoamericana de Automática e Informática industrial, 19(4), pp. 369–379. doi: 10.4995/riai.2022.17148.

Número

Sección

Artículos

Datos de los fondos