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

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.

Abstract

In this paper a new task model with periods defined as ranges is proposed with the main goal of drastically reducing the hyperperiod of the task set. The model is focused to be applied in cyclic scheduling, where the length of the major cycle of the plan is determined by the hyperperiod. But it also can be applied in synthetic task sets generation, where having a small hyperperiod reduces complexity and simulation time. As the hyperperiod grows exponentially with the number of tasks and their periods, system analysis may become unaffordable if the hyperperiod exceeds reasonable bounds.

A new algorithm, which allow us to calculate the minimum hyperperiod of such a set of tasks, is presented. This algorithm calculates the minimum value even with a large number of tasks, where exhaustive search becomes intractable.

Referencias no citadas

Baruah et al., 1990a, Baruah et al., 1990b, Brocal et al., 2010, Buttazzo et al., 1998, Cervin and Eker, 2000, Crandall and Pomerance, 2005, Kermia et al., 2006, Leung and Merrill, 1980, Liu and Layland., 1973, Macq and Goossens, 2001, Martí et al., 2001, Ripoll et al., 1996, Shih et al., 2003 and Xu, 2010.