Selección del periodo para la minimización del hiperperiodo

Vicent Brocal, Patricia Balbastre

Resumen

En este artículo presentamos un nuevo modelo de tareas donde el periodo de una tarea no es un valor fijo sino que, de acuerdo con un interpretación más amplia, el periodo puede ser elegido dentro de un intervalo de periodos aceptables. El objetivo principal es dotar al modelo de flexibilidad suficiente para que sea posible una reducción drástica del hiperperiodo del conjunto de tareas. El modelo está enfocado a sistemas de planificación cíclica, donde el ciclo del plan está determinado por el hiperperiodo. Sin embargo, la propuesta también es aplicable a la generación de cargas sintéticas para simulaciones, donde la reducción del hiperperiodo tiene beneficios en términos de complejidad y duración de la simulación. Debido a que el hiperperiodo crece exponencialmente con el número de tareas y con el valor de sus periodos, el análisis de los sistemas se vuelve intratable si el hiperperiodo excede unos límites razonables.

A su vez, se propone un algoritmo que permite el cálculo del hiperperiodo de acuerdo con el modelo de tareas presentado. Este algoritmo es capaz de calcular el hiperperiodo mínimo incluso para conjuntos de tareas grandes, donde la enumeración exhaustiva no es factible.


Palabras clave

Tiempo-real; Modelo; Algoritmos de planificación

Texto completo:

PDF

Referencias

Baruah, S., Mok, A., Rosier, L., 1990a. Preemptively scheduling hard real-time sporadic tasks on one processor. In: IEEE Real-Time Systems Symposium. pp. 182–190.

Baruah, S., Rosier, L., Howell, R., 1990b. Algorithms and complexity concerning the preemptive scheduling of periodic real-time tasks on one processor. Journal of Real-Time Systems 2.

Brocal, V., Masmano, M., Ripoll, I., Crespo, A., Balbastre, P., 2010. Xoncrete: a scheduling tool for partitioned real-time systems. In: Embedded Real-Time Software and Systems.

Buttazzo, G., Lipari, G., Abeni, L., December 1998. Elastic task model for adaptive rate control. In: IEEE Real-Time Systems Symposium. pp. 286– 295.

Cervin, A., Eker, J., 2000. Feedback scheduling of control tasks. In: Proceedings of the 39th IEEE Conference on Decision and Control.

Crandall, R., Pomerance, C. B., 2005. Prime numbers: a computational perspective. Springer.

Kermia, O., Cucu, L., Sorel, Y., 2006. Non-preemptive multiprocessor static scheduling for systems with precedence and strict periodicity constraints. In: Proceedings of the 10th International Workshop On Project Management and Scheduling.

Leung, J., Merrill, R., 1980. A note on the preemptive scheduling of periodic, real-time tasks. Information Processing Letters 18, 115–118.

Liu, C., J.W.Layland., 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. JACM 23, 46–68.

Macq, C., Goossens, J., 2001. Limitation of the hyper-period in real-time periodic task set generation. In: Proceedings of the 9th international conference on real-time systems. pp. 133–148, iSBN 2-87717-078-0.

Martí, P., Fuertes, J. M., Fohler, G., 2001. Jitter compensation for real-time control systems. In: IEEE Real-Time Systems Symposium.

Ripoll, I., Crespo, A., Mok, A., 1996. Improvement in feasibility testing for real-time tasks. Journal of Real-Time Systems 11, 19–40.

Shih, C.-S., Gopalakrishnan, S., Ganti, P., Caccamo, M., Sha, L., dec. 2003. Scheduling real-time dwells using tasks with synthetic periods. pp. 210 – 219.

Xu, J., july 2010. A method for adjusting the periods of periodic processes to reduce the least common multiple of the period lengths in real-time embedded systems. In: Mechatronics and Embedded Systems and Applications (MESA), 2010 IEEE/ASME International Conference on. pp. 288 –294.

Abstract Views

655
Metrics Loading ...

Metrics powered by PLOS ALM




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