Mejora de los Test de Planificabilidad para Asignación Incremental de Tareas en Sistemas Multiprocesadores de Tiempo Real

Sergio Sáez, Alfons Crespo

Resumen

Durante la etapa de diseño de un sistema multiprocesador de tiempo real, los test de planificabilidad son una parte clave de los algoritmos de asignación de tareas. El uso de test de planificabilidad exactos permite aumentar la eficiencia de los algoritmos de asignación a costa de un incremento en el tiempo de computo necesario para validar una partición. Aunque existen varios estudios que mejoran el rendimiento de dichos test de planificabilidad, ninguno se ha centrado en el contexto en que dichos test se utilizan. Este trabajo presenta diversas mejoras en los test de planificabilidad exactos basándose en la naturaleza incremental del proceso de asignación.

Palabras clave

Sistema Multiprocesadores; Análisis de Planificabilidad; Sistema de Tiempo Real

Texto completo:

PDF

Referencias

Audsley, N., 1993. Flexible scheduling of hard real-time systems. Ph.D. thesis, Dept. of Computer Science, Univ. of York.

Baruah, S. K., Howell, R. R., Rosier, L. E., September 1993. Feasibility problems for recurring tasks on one processor. Theoretical Computer Science 118, 3–20. URL: http://portal.acm.org/citation.cfm?id=162622.162629 DOI: 10.1016/0304-3975(93)90360-6

Baruah, S. K., Mok, A. K., Rosier, L. E., 1990. Preemptively scheduling hardreal-time sporadic tasks on one processor. In: In Proceedings of the 11th Real-Time Systems Symposium. IEEE Computer Society Press, pp. 182– 190.

Burchard, A., Liebeherr, J., Oh, Y., Son, S. H., 1995. New strategies for assigning realtime tasks to multiprocessor systems. IEEE Transactions On Computers 44 (12), 1429–1442.

Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J., Baruah, S., 2004. A categorization of real-time multiprocessor scheduling problems and algorithms. In: Handbook on Scheduling Algorithms, Methods, and Models. Chapman Hall/CRC, Boca.

Davis, R., Zabos, A., Burns, A., 2008. Efficient exact schedulability tests for fixed priority real-time systems. Computers, IEEE Transactions on 57 (9), 1261 –1276. DOI: 10.1109/TC.2008.66

Davis, R. I., Burns, A., Oct. 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv. 43 (4), 35:1–35:44. URL: http://doi.acm.org/10.1145/1978802.1978814 DOI: 10.1145/1978802.1978814

IEEE, 2001. IEEE Std 1003.1-2001 Standard for Information Technology — Portable Operating System Interface (POSIX) System Interfaces, Issue 6.

ISO/IEC JTC 1, S., 2012. Ada 2012 Reference Manual: Language and Standard Libraries. ISO/IEC 8652:201z(E) (Submission Draft [Draft 18]).

Joseph, M., Pandya, P. K., 1986. Finding response times in a real-time system. Comput. J. 29 (5), 390–395.

Leung, J.-T., Whitehead, J., 1982. On the complexity of fixed-priority scheduling of periodic real-time tasks. Performance Evaluation 2, 237–250.

Liu, C., Layland, J., 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM 20 (1), 40–61.

Ripoll, I., Crespo, A., Mok, A. K., 1996. Improvement in feasibility testing for real-time tasks. Real-Time Systems 11 (1), 19–39.

Ruiz, J. F., May 2010. Towards a ravenscar extension for multi-processor systems. Ada Lett. 30, 86–90. URL: http://doi.acm.org/10.1145/1806546.1806556 DOI: http://doi.acm.org/10.1145/1806546.1806556

Sáez, S., Vila, J., Crespo, A., Jun. 1998. Using exact feasibility tests for allocating real-time tasks in multiprocessor systems. In: Proceedings of 10th Euromicro Workshop on Real-Time Systems. pp. 53 –60. DOI: 10.1109/EMWRTS.1998.685068

Sjödin, M., Hansson, H., 1998. Improved response-time analysis calculations. In: Proceedings of the IEEE Real-Time Systems Symposium. RTSS ’98. IEEE Computer Society, Washington, DC, USA, pp. 399–. URL: http://portal.acm.org/citation.cfm?id=827270.829035

Tindell, K. W., Burns, A., Wellings, A. J., May 1992. Allocating hard real-time tasks: an NP-hard problem made easy. Real-Time Systems 4, 145–165. URL: http://portal.acm.org/citation.cfm?id=139740.139751 DOI: 10.1007/BF00365407

Zhang, F., Burns, A., 2009. Schedulability analysis for real-time systems with EDF scheduling. Computers, IEEE Transactions on 58 (9), 1250 –1258. DOI: 10.1109/TC.2009.58

Abstract Views

591
Metrics Loading ...

Metrics powered by PLOS ALM


 

Citado por (artículos incluidos en Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Herramienta Web Ligera para La Programación en C-Concurrente
Pablo Basanta-Val, Marisol García-Valls, Pablo López-Anastasio
Revista Iberoamericana de Automática e Informática Industrial RIAI  vol: 10  num.: 4  primera página: 465  año: 2013  
doi: 10.1016/j.riai.2013.05.010



Creative Commons License

Esta revista se publica bajo una Licencia Creative Commons Attribution-NonCommercial-CompartirIgual 4.0 International (CC BY-NC-SA 4.0)

Universitat Politècnica de València     https://doi.org/10.4995/riai

e-ISSN: 1697-7920     ISSN: 1697-7912