La importancia del tiempo



Descargar 237.93 Kb.
Página7/7
Fecha de conversión14.11.2017
Tamaño237.93 Kb.
1   2   3   4   5   6   7

A) Análisis de offsets estáticos

Consideremos un único procesador donde ejecutan un conjunto de tareas agrupadas en entidades con mismo periodo llamadas transacciones, y que denotaremos como i. Cada tarea de la transacción se activa cuando ha transcurrido un intervalo arbitrario y fijado llamado offset.


Notación:

i Transacción

ijTarea, donde el índice i fija la transacción a la que pertenece, i, y el índice j nos indica la posición que ocupa dentro del conjunto de tareas en dicha transacción. Denotaremos por ab a la tarea de análisis.

ij fase de activación de la tarea ij (puede ser mayor que el periodo)

Cij tiempo de ejecución de peor caso de la tarea ij

Jij retraso de la tarea ij.

Ti periodo de la transacción i

RijTiempo de respuesta de peor caso de la tarea ij

DijPlazo global de ejcución de la tarea ij

Bab término de bloqueo de la tarea ab

Con estas consideraciones, si el evento externo llega en un instante t0, la tarea se activa en un intervalo [t0+ij, t0+ij+Jij].
Calcularemos la expresión analítica de los tiempos de respuesta de peor caso de las diferentes tareas. En un principio estudiaremos el cálculo exacto aunque como se verá este es inabordable sistemas grandes con muchas tareas, con lo que aproximaremos

con un análisis pesimista.


A diferencia de las tareas independientes la existencia de offset nos limita el número de activaciones que interfieren a una tarea dada. De esta manera a la hora de construir el escenario de peor caso para la tarea ab, debemos tener en cuenta que en el instante criticó de dicha tarea no pueden coincidir todas las tareas con mayor prioridad a dicha tarea, como ocurría cuando eran consideradas independientes. La existencia de los offset hace imposible la activación simultanea de todas las tareas de mayor prioridad.

A la hora de analizar una determinada tarea, la variación del offset de las tareas con prioridad superior sumando o restando periodos completos no causa ningún efecto sobre su tiempo de respuesta. Por sencillez en el análisis consideraremos el offset reducido ij, que es un valor positivo menor que el periodo y definido como:


ij=ij mod Ti.
A.1.Análisis exacto
La forma de proceder el análisis será la siguiente:


  1. Contribución de cada tarea al tiempo de respuesta de peor caso de ab suponiendo conocido el instante crítico.

  2. Cálculo del instante crítico.



1.Contribución de cada tarea fijado tc
Sea i la fase relativa entre la última activación de la transacción i antes del instante crítico y el propio instante crítico. Se cumple que 0ii.
Para calcular la contribución de ij al tiempo de respuesta de tareas de menor prioridad distinguiremos entre tres tipos conjuntos de las activaciones de la tarea ij:


  • Conjunto 0 : Activaciones ocurridas antes del instante crítico y que no pueden ocurrir después del instante crítico, aunque se produzca el máximo retraso Jij.




  • Conjunto 1: Activaciones que se producen en el instante crítico o se pueden retrasar para comenzar en el.




  • Conjunto2: Activaciones producidas después del instante crítico.

Según sea la relación entre i y ij podemos distinguir entre dos tipos de escenarios. La figura siguiente muestra estos escenarios. El “escenario 1” corresponde al caso en el que iij . Por el contrario el “escenario 2” ocurre cuando i<ij. En la figura se muestra también el conjunto de tareas que pueden retrasarse hasta el instante crítico (conjunto 1), donde las líneas punteadas representa el retraso. En ambos escenarios el instante t0 corresponde a la primera tarea de la transacción que pertenece al conjunto 1 y que puede retrasarse hasta el instante crítico. Las activaciones de la tarea ij comprendidas entre t0 y tc también pertenecen al conjunto 1 y se pueden retrasar hasta tc.


En el “escenario 1” el conjunto de tareas pertenecientes a conjunto 1 son los correspondientes a los instantes t0, t1, t2, siendo las activaciones anteriores a t0 del conjunto 0 y las posteriores a t2 al conjunto 2. En el “escenario2” la activación correspondiente al evento que llega en t2 pertenece al conjunto 2, ya que la tarea ij se produce después de tc.

Una vez clasificadas las activaciones de la tarea ij en los tres conjuntos, el cálculo de los retrasos que producen las contribuciones de peor caso sobre tareas de menor prioridad son las que siguen el siguiente teorema.


Teorema 3.3 [PALENCIA]: Sea tc un instante crítico para la activación de una tarea ab y i el desfase entre el patrón de activaciones de la transacción i y dicho instante crítico. La contribución de peor caso de la tarea ij al tiempo de repuesta de la tarea ab ocurre cuando las activaciones de ij pertenecientes al Conjunto 1 sufren un retraso tal que coinciden en el instante crítico, y las activaciones del Conjunto 2 ocurren con retraso nulo.
A partir del teorema anterior calcularemos el número de activaciones de la tarea ij incluidas en el conjunto 1 y que se comienzan a ejecutar en tc. A este número lo denotaremos como nij (en el ejemplo gráfico nij=3 en el “escenario 1” y nij=2 en el “escenario2”). Para calcular este número de tareas definiremos dos nuevas magnitudes:
(3.46)
(3.47)
i es la diferencia temporal entre el instante crítico y el instante en el que se hubiera producido la última activación del Conjunto 1 sino hubiera sufrido ningún retraso. La diferencia entre el periodo y i es la magnitud i.
Con estas nuevas magnitudes tenemos que el número de activaciones de activaciones del conjunto 0, nij son:
(3.48)

A partir de l teorema 3.3 la máxima interferencia de la tarea ij al tiempo de respuesta de ab desde el instante crítico hasta un instante t se determina a partir de la expresión:


(3.49)

La interferencia de todas las tareas de la transacción i sobre la ejecución de ab se calculará sumando todas las contribuciones de las tareas de la transacción con mayor prioridad a ab.


(3.50)
donde,
hpi(ab) es el conjunto de tareas de la transacción i con mayor o igual prioridad que ab.


2. Cálculo del instante crítico.
Hasta ahora nos hemos centrado en el cálculo de la interferencia conocido el instante crítico, ahora nos centraremos en el cálculo de dicho instante crítico, que nos determinará el valor i de las diferentes transacciones y que nos determinará la interferencia de sus tareas sobre ab. Para obtener el valor del instante crítico, taplicaremos el siguiente teorema:
Teorema 3.4[PALENCIA]: La máxima interferencia de una transacción i sobre la ejecución de una tarea ab se obtiene cuando la primera activación, dentro del periodo de ocupación, de alguna tarea ik del conjunto hpi(ab) coincide con el instante crítico después de haber experimentado el máximo retraso Jik.
Aplicando el teorema anterior, supongamos que ik es la tarea que origina el instante crítico, podemos determinar el desfase entre la activación de la transacción y el instante crítico como:
(3.51)
Sustituyendo este expresión en la ecuación (3.46) y (3.47) podemos obtener la fase ijk de una tarea ij cuando el instante crítico es creado por ik:
(3.52)
la cual aplicando las propiedades de la función módulo conduce a la expresión más sencilla:
(3.53)
Utilizando este valor podemos obtener la expresión que nos da la contribución al peor caso de la transacción i cuando la tarea ik es la que genera el instante crítico en dicha transacción.
(3.54)

De esta forma el tiempo de respeta de peor caso de la tarea de estudio, ab requiere la aplicación de esta notación a cada una de las transacciones del sistema.


El problema que se nos presenta Ahora es encontrar para cada transacción la acción que genera el instante crítico. Si queremos chequear un análisis exacto debemos chequear todas las posibles variaciones en la tarea elegida para cada transacción, y elegir entre todas ellas la que genere el mayor tiempo de respuesta.
El número de variaciones, y por tanto el número posible de instantes críticos diferentes que necesitamos chequear, viene determinado por el número de tareas de mayor o igual prioridad a la tarea analizada en cada transacción. Del sistema. La propia tarea de análisis puede originar el instante crítico para su transacción, por lo que tenemos que considerarla en las variaciones. El número total de variaciones es pués:
(3.55)

Por el índice  entenderemos cada una de éstas variaciones que generan el instante crítico. En cada una de éstas podemos calcular el tiempo de finalización correspondiente a cada una de las activaciones de la tarea ab. Este tiempo se obtiene considerando la ejecución de ab junto con la interferencia debida al resto de tareas del sistema:


(3.56)
donde p0,abv es la primera activación de la tarea ab considerada en el periodo de ocupación y calculada como:
(3.57)
La solución a la ecuación (3.56) se realiza de forma iterativa, comenzando con un valor wabv(p)=0. El tiempo de respuesta global se obtiene restando, del tiempo de finalización el instante en el que se produjo la llegada del evento que activó la transacción. El instante de activación de la transacción correspondiente vendrá dada por abv(a)+(p-1)Ta-ab (donde ab es el término de retraso real y no el reducido). De esta forma el tiempo de repuesta global para la activación p-ésima generada por el instante crítico  vendrá dado por:
(3.58)
El análisis se repite para cada variación  desde hasta que es la última activación que se ejecuta dentro del periodo de ocupación. Este valor se puede calcular mediante de dos diferentes formas:


  1. A partir de la longitud del periodo de ocupación:



y donde L se puede calcular a partir de la expresión :
(3.59)



  1. Podemos también calcular como el primer valor de p que cumpla la siguiente inecuación:


(3.60)

Para calcular el tiempo de respuesta de peor caso de la tarea ab debemos determinar el máximo de todas las posibles instantes críticos y de todas las activaciones en dichos instantes críticos.


(3.61)
Esta técnica es exacta pero el número de casos a chequear crece exponencialmente con el número de tareas (algoritmo NP-completo). Esto significa que este algoritmo será intratable para la mayoría de casos prácticos.


A.2.Análisis aproximado
Para los casos donde el método exacto es inabordable Tidell [TIN94B] desarrolló un método de obtener cotas superiores y reducir el análisis. Si los tiempos de respuesta de peor caso con este método son menores que el deadline podremos garantizar la planficabilidad del sistema, si bien si no los cumple no podremos decir que no sea planificable.
Para evitar estudiar todos los posibles instante críticos se obtiene una cota superior de la interferencia debida a tareas de la misma transacción. Así la interferencia total sobre la tarea ab será la suma de todas las cotas superiores de todas las transacciones.
La cota superior de la interferencia a la tarea ab por las tareas de la transacción i en un periodo de ocupación w, vendrá dada por la expresión:
(3.62)

Para introducir menor pesimismo en análisis no usaremos la cota superior para la propia transacción de la tarea de estudio a. De esta manera, para el análisis debemos considerar todos los instantes críticos creadas por cada una de las tareas pertenecientes a la transacción con prioridad mayor o igual a ab. El tiempo de respuesta de peor caso vendrá determinado por la expresión:


(3.63)

Esta ecuación se resolverá de forma iterativa al igual que en el método exacto visto anteriormente.
El valor del tiempo de respuesta de peor caso se obtiene restando del tiempo de finalización el instante donde se produjo la llegada del evento externo asociado, y tomando el peor de los tiempos de respuesta obtenido:
(3.64)
(3.65)




Compartir con tus amigos:
1   2   3   4   5   6   7


La base de datos está protegida por derechos de autor ©composi.info 2017
enviar mensaje

    Página principal