La importancia del tiempo



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

Sistemas monoprocesadores sin recursos compartidos y T>D

Cuando los plazos de finalización son menores que los periodos, los test anteriores dejan de ser válidos. Además la asignación de prioridades en función de los periodos, ya no es la óptima. En estos sistemas la asignación óptima es aquella basada en los plazos de ejecución (deadline monotonic, DM), de forma que corresponda la mayor prioridad del sistema a aquella tarea con el deadline más pequeño. Esta asignación de prioridades fue demostrada como óptima en el año 82 por Leung y Whitehead [LEU82].


El primer test de planficabilidad para estos sistemas fue elaborado por Audsley [AUS91A]. Este test no era exacto, sino que sólo suficiente y también basado en las utilizaciones. La mayor interferencia que una tarea i puede sufrir ocurre en el instante crítico, estando ésta limitada por la expresión:
(3.5)

en donde:

hp(i) es el conjunto de tareas con mayor o igual prioridad que la tarea i, exceptuando la propia tarea i

El sistema será planificable si cumple para cada tarea la inecuación :


(3.6)
Este test no es exacto, ya que supone que las tareas de mayor prioridad hp(i) pueden interrumpir a la tarea i en cualquier instante dentro de su plazo, sin tener en cuenta que la ejecución dei puede haber finalizado antes de que la expulsión se hay producido
El análisis exacto se obtiene por extensión del análisis de Lehocky, Sha y Ding dado en la expresión (3.4) y aplicado a la planificación deadline monotonic. De esta forma un sistema será planificable si y sólo si para cada tarea del sistema se cumple:

Aunque al igual que en el test en el test original, podemos limitar la desigualdad en un número limitado de puntos Qi que cumplan:


(3.7)
Con lo que el test se reduce a :
(3.8)

  1. Sistemas monoprocesadores con cursos compartidos

Consideremos ahora un sistema con tareas que comparten recursos, que supondremos que la compartición de recursos se lleva a cabo mediante alguna de las técnicas vistas en el apartado 2.3. Identificaremos el término de bloqueo de la tarea i debido a las tarea de prioridad inferior como Bi. En el caso de planificadores no expulsores, podemos hacerlo equivalente a un planificador expulsor con un bloqueo para cada tarea Bi = donde lp(i) son las tareas con menor prioridad a i.


Si conocemos los diferentes bloqueos de las tareas, podemos generalizar el test de utilización de Liu y Layland. Así un sistema compuesto por N tareas planifiaads con Rate Monotonic y bloqueo Bi para cada tarea será planificable si verifica [SHA90A]:
(3.9)

La extensión del análisis para sistemas con tareas con plazos iguales o inferiores al periodo, con bloqueos, y con asignación arbitraria de prioridades es un test más complicado y no exacto. Así un sistema con N tareas con bloqueo Bi para cada tarea i y con una asignación arbitraria de prioridades{S} es planificable si cumple para cada tarea:


(3.10)


  1. Sistemas monoprocesadores con plazos superiores al periodo

Los sistemas con plazos superiores a los periodos, tienen la complicación añadida de que en la respuesta de una tarea puede interferir alguna activación anterior de ella misma..


Otro problema añadido al cálculo de los tiempos de respuesta es el de asignación de prioridades, ya que ninguna de las asignaciones vistas anteriormente en función del periodo o del deadline es óptima. Esta asignación debe realizarse mediante el algoritmo heurístico visto en el apartado 2.2.3[AUD91B] .
La asignación del instante crítico sigue siendo válida, pero mientras que antes se extendía a comprobar una única activación, ahora debe extenderse el análisis sobre todas las activaciones que ocurran dentro de lo que se llamará periodo de ocupación de peor caso[LEH90]. El periodo de ocupación para una tarea i es un intervalo de tiempo durante el cual el procesador se encuentra ocupado en la ejecución de tareas e mayor o igual prioridad que i .
El test utilizado es generalización del método utilizado anteriormente para plazos menores o iguales al periodo. Definamos Wi(m,t) como el máximo tiempo de ejecución requerido por las tareas de mayor o igual prioridad que i junto con m activaciones de ella misma en un intervalo de duración t desde el instante crítico. Este tiempo vendrá definido como:
(3.11)
La utilización máxima en ese intervalo vendrá definida como:
(3.12)

El conjunto de tareas será planificable si para todas cada activación dentro del periodo de ocupación, existe un instante anterior a su plazo de finalización con utilización menor que 1. Como la activación m-ésima se produce en el instante (m-1)Ti+Di, los plazos de finalización serán en el instante (m-1)Ti+Di, por lo tanto deberá cumplirse:


(3.13)
Donde Ni es el número de activaciones de cada tarea i dentro de su periodo de ocupación. Este número se puede calcular teniendo en cuenta que corresponden a la primera activación cuya ejecución finaliza antes de que se produzca la siguiente:
(3.14)3.2.2 Análisis por tiempo de respuesta
El método de análisis por tiempo de respuesta, es más potente que el de utilidades, pues además de ser exacto nos permite saber la distancia de la peor respuesta a su plazo máximo de ejecución.


  1. Sistemas monoprocesadores con DT sin bloqueos y sin Jitter

Se considera sólo los plazos inferiores o igual al periodo, pues cuando el deadline es superior al periodo, pueden interferir en una activación de la tarea anteriores activaciones de la misma, con lo que se complica el análisis.


Si Ri es el tiempo de respuesta de peor caso de de cada tarea i la máxima interferencia que producen el resto de tareas de mayor prioridad a partir del instante crítico vendrá dada por el término:
(3.15)
Con lo que el tiempo de repuesta de peor caso, Ri, de la tarea i vendrá dado por la suma de los términos de interferencia y de ejecución de peor caso:
Ri=Ci + Ii (3.16)

De forma que el sistema será planificable si todas sus tareas cumplen ejecutarse antes de sus plazos, es decir:


R i Di  i=1..N (3.17)

Cuando analizamos las 3 ecuaciones anteriores, nos damos cuenta de un problema, el cálculo de la interferencia requiere el conocimiento del tiempo de respuesta, y el cálculo del tiempo de respuesta a su vez requiere el de la interferencia. La solución a esto es resolverlo de forma iterativa, mediante las siguientes expresión:


(3.18)

De esta forma estimamos los valores de Ri a partir de los valores obtenidos en la anterior iteración. El valor inicial del tiempo de repuesta será el tiempo de ejecución de la tarea ,Ri0=Ci. La dependencia monótona de la ecuación respecto Ri garantiza la convergencia de este algoritmo siempre que la utilización sea inferior al 100% [JOS86], de forma que la iteración finaliza cuando Ri(n+1)=Ri(n). Si bien si en una iteración anterior es mayor el tiempo de respuesta que el deadline, no es necesario iterar hasta la convergencia, pues ya sabremos que dicha tarea no cumple sus plazos.





  1. Sistemas monoprocesadores con DT con bloqueos y Jitter

Para calcular el tiempo de respuesta en este tipo de sistemas, tendremos que redefinir cuando comienza el instante crítico.


Teorema 3.2[Aud93] El instante crítico para este tipo de sistemas se produce cuando la tarea se activa después de sufrir el máximo, recién bloqueado el recurso compartido con mayor sección crítica y coincidiendo con la activación, también retrasado, de las tareas con mayor prioridad. El resto de activaciones posteriores se producirán sin retraso, con el fin de acercar lo máximo las activaciones al instante crítico.
A partir de este instante crítico, el tiempo de respuesta de peor caso de una tarea i será igual a:

Ri= Bi + Ci + Ii + Ji (3.19)
Siendo:

Ii la interferencia debida a las tareas de mayor o igual prioridad que i

Ji el jitter o máximo retraso de la tarea i

Bi el bloque máximo sufrido por la tarea i

El bloque y el retraso de la tarea se consideran conocidos, luego la complicación surge en el calculo de la interferencia. A diferencia que en el apartado anterior esta no será producida por la duración Ri, sino desde el instante crítico. Este tiempo se denominará tiempo de finalización, wi, que representa el tiempo transcurrido desde el instante crítico hasta que finaliza la ejecución de la tarea i. A partir de esta definicón, y teniendo en cuenta que la tareas de mayor priorida se han activado Jj antes la interferencia vendrá dada por la siguiente expresión:
(3.20)

Donde el valor del tiempo de finalización vendrá dada por la suma de las contribuciones desde el instante crítico:


(3.21)
El tiempo de respuesta vendrá dado por la suma de tiempo de finalización mas el retraso de la propia tarea:
Ri= wi + Ji (3.22)

Una vez calculado el tiempo de respuesta, e sistema será planificable si para todas las tareas se cumple que su ejecución es anterior a su plazo:



Ri Di i=1..N (3.23)
De igual forma que en el apartado anterior, tenemos que aplicar un método iterativo ya que wi e Ii está relacionados entre si. De esta forma combinado las ecuaciones anteriores tenemos la expresión iterativa:
(3.24)
La asignación comienza asignando el valor del tiempo de ejecución al tiempo de finalización: wi(0)=Ci, y finaliza cuando se obtienen dos iteraciones consecutivas iguales wi(n+1)= wi(n) . El tiempo de respuesta de peor caso de la tarea i será
Ri=wi+Ji. (3.25)



  1. Sistemas monoprocesadores con plazos superiores al periodo

Existe una técnica exacta para el cálculo de tiempos de respuesta de peor caso en sistemas con plazos superiores al periodo. Esta fue desarrollada por Tindell, y además incorpora efectos debidos a la compartición de recursos y al retraso [TIN92B][TIN94F]. La notación empleada por Tindell difiere de la empleada por Lehoczky; mientras que el primero a la primera activación la denota como q=0, Lehoczky la da el valor m=1.


El tiempo de respuesta de peor caso de la tarea q-ésima sigue la expresión dad por :

(3.26)
Donde la ecuación se resuelve de forma iterativa con el valor inicial dado por wi(0)(q)=(q+1)Ci, que es la contribución de la propia tarea. Para obtener el tiempo de respuesta tendremos que aplicar que la activación q-ésima comienza a ejecutar en t=qTi-Ji, con lo cual debemos restárselo al tiempo de finalización.
(3.27)
El numero de activaciones que debemos comprobar (qmax) es la primera que cumple la desigualdad:
Wi(q)(q+1)Ti (3.28)

La q que obtenemos puede ser menor que la última activación dentro del periodo de ocupación, que es la primera que cumple Wi(q)(q+1)Ti-Ji. La validez de la expresión (3.28) se demuestra en [PAL99].


El sistema será planificable si se cumple que el tiempo de respuesta de peor caso es menor que su plazo de ejcución:
RiDi (3.29)

3.3. Planificación EDF en sistemas monoprocesadores
3.3.1 Análisis por utilización

La planificación con prioridades fijas es un tema de reciente actualidad en los sistemas de tiempo real. Se comprueba que para sistema monoprocesadores expulsores sin recursos compartidos ni retrasos la planificación EDF es óptimo. Así muchos sistemas que no son planificables bajo prioridades fijas si lo son con prioridades fijas.


Cuando tenemos un sistema con las propiedades descritas anteriormente, existe una forma sencilla de saber si dicho sistema es planificable. Podemos garantizar que el sistema cumple los plazos de respuesta si cumple:
(3.30)
Luego es optima con una cota de utilización del 100%.
Veamos un ejemplo que no cumple los plazos planificándose con RMA y si lo hace con EDF:

Ejemplo:


Planificado por RMA


No cumple el plazo


Planificado con EDF

3.3.2 Análisis por cálculo el tiempo de respuesta
El test de planificación por utilización es muy sencillo, pero el sistema al que es aplicable tiene muchas restricciones, tales como que no poder sufrir bloqueos o no tener retaso. El cálculo de respuesta de peor caso nos permite eliminar las restricciones anteriores pudiéndose aplicar a todos los sistemas de tiempo real. Si bien la complicación de cálculo es mayor, como veremos en este apartado.
El cálculo de tiempos de respuesta fue desarrollado por Spuri en el año 1996 [SPR96A] y [SPR96B] aunque en este apartado vamos a utilizar la notación empleada por Palencia y Glez Harbour [PAL2002].
El análisis de tiempo de respuesta de peor caso está basdo en la creación del mayor periodo de ocupación. El periodo de ocupación se define en EDF como el tiempo durante el cual el procesador se encuentra ocupado procesando alguna ejecución pendiente de alguna tarea. En RMA el instante crítico ocurría cuando comenzaba el periodo de ocupación, en EDF estoa propiedad no es cierta aunque le concepto de periodo de ocupación es utilizado. Para encontrar el instante crítico definiremos el siguiente teorema:


Teorema 3.3[SPURI]:El tiempo de peor caso de una tarea a ocurre cuando se activa con máximo retraso dentro del periodo de ocupación, donde todas las tareas se relajan simultáneamente con sus máximos retraso al comienzo de dicho periodo de ocupación. Además de forma que su deadline coincida con alguno de las otras tareas o cuando comienza con el inicio del periodo de ocupación.

Para calcular dicho tiempo de respuesta de peor caso de la tarea a, tendremos que ver la contribución de cada tarea i en un periodo de ocupación de longitud t, y con el deadline de a ocurrido en D.


El número de activaciones de la tarea a en el periodo de ocupación las denotaremos como pt siendo la solución a la expresión:
(3.31)

Por otro lado el número de activaciones que interfieren a la tarea con deadline D serán debidas por aquellas cuyo deadline es menor que D, que serán dadas por la expresión :


(3.32)
El número de activaciones que interfieren a la tarea a será el menor de ambos, ya que deben cumplir, tanto que se encuentre dentro del periodo de ocupación, como que el deadline sea menor que D, con lo que la interferencia será:
(3.33)

Los posibles valores del deadline, según se vio en el teorema 3.3 son los que coinciden con algún otro deadline o los creados por la propia tarea activándose en el comienzo del periodo de ocupación, estos vendrán dados por la expresión:


(3.34)
donde L corresponde a la longitud del periodo de ocupación, creado cuando todas las tareas se activan en el mismo instante tras sufrir el máximo retraso, que se calcula de forma iterativa:

(3.35)

Es importante en el análisis saber ver cuales de los deadlines son los que pueden coincidir con la activación p-ésima de la tarea. Denotaremos a estos instantes como :


(3.36)
Para cada elemento de, el valor de inicio de la activación de la tarea de análisis a respecto al comienzo del periodo de oaupación, se denotará como A y vendrá dado por la expresión:
(3.37)
Todo deadline se podrá poner en función de la activación A y de la activación a la que corresponda:
(3.38)
Cuando la primera activación de la tarea a ocurre en el tiempo A después del comienzo del periodo de ocupación el tiempo de completación de su activación p-ésima vendrá dada por:
(3.39)
Con lo que el tiempo de repuesta para esa activación viene dado por:
(3.40)
Y por último, el tiempo de respuesta de peor caso de la tarea a se puede determinar como el tiempo de respuesta de mayor duración:
(3.41)

3.4. Planificación en sistemas distribuidos. Modelo transaccional.
3.4.1 Introducción
Hasta ahora solo hemos analizado sistemas monoprocesadores, en este apartado veremos las diferentes técnicas de análisis en sistemas multiprocesadores o distribuidos. La importancia de los sistemas distribuidos es grande, ya que esta es la configuración de muchos de los sistemas de tiempo real, ya que la potencia de éstos es mucho mayor que los monoprocesadores.
La planificación es sistemas distribuidos se complica bastante respecto a la de sistemas monoprocesadores. Además de la asignación prioridades que debe de realizarse de forma heurística [TIN92A], surgen problemas con la sincronización.
En el análisis de sistemas distribuidos ha de analizarse al igual que el procesador el sistema de comunicaciones entre los diferentes procesadores. Como comentamos en el primer apartado consideraremos tanto el tiempo de ejecución de las tareas como el tiempo de transmisión de los mensajes como acciones.
El proceso esquematizado que ocurrirá en un sistema distribuido puede resumirse de la forma siguiente: llegada de un evento periódico externo ei, éste desencadena una serie de acciones aij tanto en el procesador como en las redes de comunicación, donde el subíndice j indica la posición de la acción respecto a la llegada del evento. Cada acción aij se la considera un tiempo de ejecución Cij y hereda el periodo del evento externo Tj.
Podemos distinguir los siguientes requisitos temporales a las diferentes acciones:


  • Plazos Globales: plazos relativos a las llegadas del evento externo




  • Plazos locales: plazos considerados desde el instante real en que se activó la acción en la repuesta al evento.




  • Plazos de principio-a-fin: plazos asignados a las secuencias de respuesta completa del evento.

La notación para los plazos será la siguiente: llamaremos Dj al plazo global de la acción aij, dj al plazo local y EDi al plazo principio-a-fin para la respuesta al evento ei, que coincide con el plazo global de la última acción de la cadena de respuestas. En la siguiente figura se pueden ver ejemplos de la notación y de estos plazos.




a11

a12

a13

Una de las mayores problemáticas de los sistemas distribuidos es la precedencia en la activación de las tareas y mensajes de una misma secuencia de respuesta. Así la acción aij se activa en el instante que finaliza la acción precedente aij-1 en la secuencia, a excepción de la primera que se activa a la llegada del evento externo y se produce de forma perfectamente periódica.


Podemos resolver la problemática de la precedencia a partir de la asignación a las acciones un retraso. La primera acción tendrá retraso nulo, Ji1 =0, sin embargo las subsiguientes acciones pueden sufrir un retraso igual a la diferencia de tiempo entre el tiempo de respuesta de peor caso y el mejor de la acción precedente.


(3.42)
donde Rij-1 es el tiempo de respuesta global de peor caso de la acción previa de aij y

el tiempo de mejor caso.
En un principio Tidell y Clark [TIN94F] consideraban como primera aproximación (pesimista) =0, con lo que los retrasos serán . En la actualidad hay métodos para el cálculo exacto de este tiempo de mejor caso, elaborado por Redell [RED2002].


3.4.1 Análisis en RMA bajo la aproximación de tareas independientes.
Tindell y Clark aplicaron la notación elaborada por ellos mismo para sistemas monoprocesadores [TIN92B] con el concepto correspondiente a los retrasos visto en la introducción, considerando cada acción como si se trataran de tareas independientes entre si. Ahora las tareas que pueden interferir en cada acción son las que se encuentran en el mismo recurso(procesador o red de comunicaciones) con mayor prioridad a dicha acción.
El instante crítico de cada acción se consideran como si fueran independientes, lo cual no hace no empeorar la ejecución de la tarea analizada, pues la procedencia hace que sea imposible hacer coincidir sólo los instantes críticos. El tiempo de finalización de la activación p-ésima (consideraremos p=1 la primera activación) de la acción aij se obtiene de forma semejante que en tarea monoprocesadores mediante el método iterativo como:
(3.43)
donde ahora hp(i,j) es el conjunto de acciones de mayor o igual prioridad que la asignada a la acción aij ejecutando en el mismo procesador.
El tiempo de respuesta global se obtiene considerando el instante en el que se activó y vendrá dado por la expresión:
(3.44)
La iteración sobre p finaliza con el primer valor de p que cumple:
(3.45)

Esta forma de calcular el tiempo de respuesta tiene un problema añadido con respecto al cálculo a sistemas monoprocesadores, los tiempos de respuesta (3.43) requieren el conocimiento previo de los términos de retraso, que a su vez requiere el conocimiento previo de los tiempos de respuesta (3.42).





Para solucionar el problema Tindell y Clark diseñaron un método iterativo que permite calcular los tiempos de respuesta de peor caso de las tareas. El método consite en estimar los valores de los términos de retraso y en función de los cuales se calculan los tiempos de respuesta, que a su vez se pueden usar para volver a calcular los tiempos de retraso. El proceso continua hasta que se obtengan los mismos tiempos de repuesta en dos iteraciones consecutivas. La convergencia se asegura por el comportamiento monótono tanto del cálculo de los tiempos de respuesta como en los términos de retraso.



3.4.2 Análisis en RMA para tareas con offsets estáticos y dinámicos
En los sistemas distribuidos basados en tareas independientes, las técnicas de análisis producen un pesimismo muy grande, lo que hace que sólo se pueda garantizar sistemas con niveles de utilización muy pobres.
En el año 1994 Tindell desarrolló una técnica para calcular los tiempos de respuesta de peor caso (o cota superior de los mismos) para un conjuntos de tareas con offsets estáticos. El sistema está compuesto de transacciones periódicas, cada una de ellas con varias tareas. Cada tarea se libera después de transcurrido cierto tiempo) offset) desde la legada del evento que dispara la transacción. Tindell limitó los offsets a ser menores que el periodo de dicha transacción. Este análisis es útil en los sistemas donde la activación de las tareas se hacen de forma precisa para evitar efectos negativos de la activación retrasada.
Palencia[PAL99] desarrolla una nueva técnica basada en análisis de Tindell pero donde el jitter no está limitado a ser menor que el periodo y los offsets no son estáticos, de forma que pueden cambiar de una a otra activación. Por ejemplo, en sistemas distribuidos una tarea se activa cuando la precedente finaliza, siendo diferente el instante de activación en los diferentes periodos. Además en sistemas distribuidos es usual que el plazo sea mayor que el periodo, de aquí la importancia de no limitar el retraso a ser inferior al periodo.
En este capítulo desarrollaremos la técnica empleada por Palencia, comenzando con el análisis para offset estáticos y extendiéndolo luego para offset dinámicos y su aplicabilidad a sistemas distribuidos.



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