Planificación de tareas considerando particiones: una aproximación basada en ventanas temporales para sistemas de tiempo real mononúcleo y multinúcleo
Enviado: 30-01-2026
|Aceptado: 29-06-2026
|Publicado: 03-07-2026
Derechos de autor 2026 Luis Ortiz, Marc Fontalba, Ana Guasque, Patricia Balbastre, Jose Simó
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Descargas
Palabras clave:
Planificación de tareas, Tiempo real, Cambios de contexto, Sistemas críticos, ARINC 653, Sistemas multinúcleo, Interferencias
Agencias de apoyo:
Resumen:
Los sistemas de tiempo real crítico que ejecutan aplicaciones particionadas conforme estándares como DO-178C o ISO 26262 enfrentan cambios de contexto entre particiones (PCS) que pueden resultar varios órdenes de magnitud más costosos que cambios convencionales, comprometiendo el cumplimiento de los requisitos temporales. En este trabajo se propone RPCS (Reduced Partition Context-Switch), un planificador de tipo offline que minimiza el número de PCS mediante la planificación basada en ventanas temporales definidas a partir del máximo común divisor de los períodos de las tareas, junto con un esquema de clasificación jerárquica de tres niveles. Los resultados experimentales en sistemas mononúcleo demuestran que RPCS supera a EDF en el 95.62 % de los casos, con una reducción media de entre el 27.99 % y el 31.62 % en el número de cambios de contexto de partición. En sistemas multinúcleo, RPCS muestra ventaja en el 17.50 % de los casos comparables, concentrándose en configuraciones de 2-4 núcleos. El enfoque propuesto facilita el análisis temporal y los procesos de certificación en sistemas críticos de los dominios aeroespacial y automotriz.
Citas:
Aceituno, J. M., Guasque, A., Balbastre, P., Sim´o, J., Crespo, A., 2021. Hardware resources contention-aware scheduling of hard real-time multiprocessor systems. Journal of Systems Architecture 118, 102223.
Akesson, B., Nasri, M., Nelissen, G., Altmeyer, S., Davis, R. I., 2022. A comprehensive survey of industry practice in real-time systems. Real-Time Systems 58 (3), 358–398.
ARINC, 2006. Avionics application software standard interface (arinc-653). part 1—required services. Annapolis, MD, USA.
Brocal, V., Balbastre, P., Ballester, R., Ripoll, I., 2011. Task period selection to minimize hyperperiod. In: ETFA2011. pp. 1–4.
Burns, A., Davis, R., 2026. Mixed criticality systems-(a review: 14th and final edition, february 2026).
Cerrolaza, J. P., Obermaisser, R., Abella, J., Cazorla, F. J., Gr¨uttner, K., Agirre, I., Ahmadian, H., Allende, I., 2020. Multi-core devices for safety-critical systems: A survey. ACM Computing Surveys (CSUR) 53 (4), 1–38.
Chen, J., Du, C., Xie, F., Lin, B., 2016. Allocation and scheduling of strictly periodic tasks in multi-core real-time systems. In: 2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). pp. 130–138.
Coffman, E. G., Garey, M. R., Johnson, D. S., 1996. Approximation Algorithms for Bin Packing: A Survey. PWS Publishing Co.
Dasari, D., Akesson, B., N´elis, V., Awan, M. A., Petters, S. M., 2013. Identifying the sources of unpredictability in cots-based multicore systems. In: 2013 8th IEEE International Symposium on Industrial Embedded Systems (SIES).
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.
Davis, R. I., Burns, A., oct 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. 43 (4).
Guasque, A., Tohidi, H., Balbastre, P., Aceituno, J. M., Sim´o, J., Crespo, A., 2020. Integer programming techniques for static scheduling of hard real-time systems. IEEE Access 8, 170389–170403.
Han, P., Hu,W., Zhai, Z., Huang, M., 2024. A model-based optimization method of arinc 653 multicore partition scheduling. Aerospace 11 (11).
Hanen, C., Munier, A., 1995. Cyclic scheduling on parallel processors: An overview. In: Chretienne, P., Coffman, E., Lenstra, J., Liu, Z. (Eds.), Scheduling Theory and Its Applications. John Wiley & Sons Ltd, New York, Ch. 9.
Isstaif, A. A. T., Kalyvianaki, E., Mortier, R., 2025. Mitigating context switching in densely packed linux clusters with latency-aware group scheduling.
Johnson, D. S., 1973. Near-optimal bin packing algorithms. Ph.D. thesis, Massachusetts Institute of Technology.
Kermia, O., Sorel, Y., 2008. Schedulability analysis for non-preemptive tasks under strict periodicity constraints. In: 2008 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications.
L. Ortiz, A. G., Balbastre, P., Sim´o, J., 2024. Allocation algorithms for multicore partitioned mixed-criticality real-time systems. PeerJ Computer Science 10.
Ladeira, M., Grolleau, E., Bonneval, F., Hattenberger, G., Ouhammou, Y., H´erouard, Y., 2022. Scheduling offset-free systems under FIFO priority protocol. In: Maggio, M. (Ed.), 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik.
Lehoczky, J., Sha, L., Ding, Y., 1989. The rate monotonic scheduling algorithm: exact characterization and average case behavior. In: [1989] Proceedings. Real-Time Systems Symposium. pp. 166–171.
Liu, C. L., Layland, J. W., jan 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20 (1), 46–61.
Locke, C. D., mar 1992. Software architecture for hard real-time applications: Cyclic executives vs. fixed priority executives. Real-Time Systems 4.
Martins, J., Pinto, S., 2023. Shedding light on static partitioning hypervisors for arm-based mixed-criticality systems. In: 2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS).
Masmano, M., Ripoll, I., Crespo, A., Jean-Jacques, M., 09 2009. Xtratum: a hypervisor for safety critical embedded systems.
Mikucionis, M., Larsen, K. G., Rasmussen, J. I., Nielsen, B., Skou, A., Palm, S. U., Pedersen, J. S., Hougaard, P., 2010. Schedulability analysis using uppaal: Herschel-planck case study. In: Margaria, T., Steffen, B. (Eds.), Leveraging Applications of Formal Methods, Verification, and Validation.Springer, Berlin, Heidelberg.
Oh, Y., Son, S. H., Nov. 1995. Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Syst. 9 (3), 207–239.
Paul, A. A., Pillai, B. A. S., 2011. Reducing the number of context switches in real time systems. In: 2011 International Conference on Process Automation, Control and Computing. IEEE, pp. 1–6.
Rivas, J. M., Guti´errez, J. J., Guasque, A., Balbastre, P., 2024. Gradient descent algorithm for the optimization of fixed priorities in real-time systems. Journal of Systems Architecture 153, 103198.
Rushby, J., 1999. Partitioning for safety and security: Requirements, mechanisms, and assurance. NASA Contractor Report 209347, 3–9.
Senoussaoui, I., Zahaf, H.-E., Benhaoua, M. K., Lipari, G., Olejnik, R., 2020. Allocation of real-time tasks onto identical core platforms under deferred fixed preemption-point model. In: Proceedings of the 28th International Conference on RTNS.
Zeng, H., Di Natale, M., 2013. An efficient formulation of the real-time feasibility region for design optimization. IEEE Trans. on Computers 62 (4).
Zhang, Y.-W., Ma, J.-P., Gu, Z., 01 2024. Partitioned scheduling with shared resources on imprecise mixed-criticality multiprocessor systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
