La importancia del tiempo



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

3. Técnicas de análisis de tiempo real existentes.



3.1 Introducción
En el apartado anterior hemos contado de forma genérica los diferentes tipos de planificaciones de tiempo real, sin desarrollar sus técnicas de análisis. El objetivo de este apartado será introducir las técnicas de análisis existentes, tanto en RMA como en EDF ya que en esta técnica se desarrollan nuevas técnicas de análisis para tareas aperiódicas en ambas teorías.
El objetivo que persiguen estas técnicas es verificar el cumplimiento de los requisitos temporales de las diferentes tareas. La verificación de si el sistema es planificable se lleva a cabo a priori. Los test de planificación pueden ser más o menos pesimistas, según la exactitud de sus soluciones temporales de peor caso del sistema. Los primeros test no eran exactos siendo bastante pesimistas, de forma que aunque muchas veces no nos aseguraban que el sistema fuera planificable si lo era. En la actualidad el pesimismo de los análisis se va perdiendo, y en especial en sistemas monoprocesadores donde la mayoría del análisis actual es exacto. No ocurre lo mismo en sistemas distribuidos, donde la complicación del sistema es mayor.
En la sección 3.2 vamos a ver las técnicas de análisis para sistemas en RMA, desde las primeras basadas en utilidades hasta la técnica exacta. En la sección 3.3 vamos a ver la técnica exacta de la teoría EDF. Por último en 3.4 vamos a ver en sistemas distribuidos las técnicas basadas en transacciones, tanto en RMA como en EDF.

3.2. Planificación RMA en sistemas monoprocesadores
Antes de ver las diferentes técnicas de análisis de los sistemas monoprocesadores planificados bajo RMA definiremos los parámetros con los que vamos a tratar. Supondremos un conjunto de N tareas periódicas ejecutándose en un único procesador. Cada tarea i estará especificada mediante su periodo de activación identificado por Ti, su tiempo de ejecución de peor caso, Ci, su plazo máximo de ejecución (deadline), Di, su prioridad ,Pi, y por último su retraso máximo de ejecución (jitter), Ji.
Principalmente en RMA distinguios entre dos tipos de tests, basado en conceptos diferentes, estos son:


  • Límite de utilización: es el porcentaje de ocupación del procesador. Cada tarea periódica i tiene una utilización sobre el procesador dada por la expresión: Ui=. A partir de la utilización de todas las tareas podremos ver si el sistema es planificable, si bien estos métodos no son exactos, sino pesimistas.

  • Tiempo de respuesta de peor caso: se centra en el cálculo de los tiempos de ejecución de peor caso de todas las tareas del sistema, para compara luego con sus plazos respectivos.

Las dos técnicas están basadas en el concepto de instante crítico para una tarea i., que corresponde al instante donde al producirse la activación de dicha tarea tiene como tiempo de respuesta el de peor caso, es decir la peor situación para la ejecución de cada tarea.


En RMA existe un teorema demostrado en [LIU73] que demuestra la posición del instante crítico para cada tarea.:
Teorema 3-1 (Liu y Layland). El instante crítico de una tarea se produce cuando esta se activa de forma simultanea a las demás tareas con prioridad igual o superior a la suya.
El teorema esta definido sin considerar retraso de las tareas. En caso de que exista jitter, el instante crítico ocurre cuando la tarea se activa después de sufrir el máximo retaso en el mismo instante en el que se activan las tareas con mayor prioridad, tras sufrir estas su máximo retraso.

3.2.1 Análisis por utilización


  1. Sistemas monoprocesadores sin recursos compartidos y T=D

El primer test de planficabilidad dentro de la teoría RMA fue deducido por Liu y Layland en el año 1973 [LIU73]. Este test se aplica cuando tenemos n tareas independientes, sin recursos compartidos y con plazos de finalización iguales a sus periodos Ti=Di.


Por otro lado los mismos autores demostraron que la asignación de prioridades óptimas cuando asignamos la prioridad conforme al periodo de activación, de forma que asignemos a la tarea con menor periodo la prioridad más alta. Si un sistema no es planificable con esta asignación entonces no es planificable en cualquier otra asignación, ya que esta es óptima.
Un sistema con estas propiedades y con asignación óptima de prioridades será planificable si cumple la siguiente relación:
(3.1)
donde U es la utilización total del procesador, e igual a la suma de las utilizaciones del conjunto de tareas en el sistema y U(N) es el límite de utilización máximo del procesador para N tareas.
Según el valor del número de tareas, N, el criterio nos limita la utilización del procesador entre el 69% y el 83%. Esto nos condiciona que el test nos limita la planficabilidad de sistemas para utilizaciones relativamente bajas.
Debido a que el test no es exacto, sino sólo suficiente existen sistemas que sobrepasando el límite de utilización marcado por el test son planificables.
Lehoczky, Sha y Ding[LEH89] propusieron 16 años después un test exacto para el mismo problema. Definen así una utilización máxima de peor caso para cada tarea i para cada tiempo t. Esta utilización de peor caso para la tarea i en el tiempo t viene definida como:
(3.2)
siendo la función matemática función techo, definida como el entero mayor o igual que x.
El sistema será planificable si se verifica :
(3.3)

De esta forma si para cada tarea i si existe un instante t entre t=0 y el periodo Ti cuya utilización de peor caso sea inferior o igual a la unidad entonces dicho sistema es planificable. Para comprobar la inecuación no es necesario comprobarlo en todo tiempo t, sino sólo chequear los instantes en las que se activa una tarea de mayor prioridad a ella( menor periodo), ya que es en estos instantes donde varía el término en la ecuación 3.2. Aplicando ésta condición el test se reduce a la expresión:


(3.4)




  1. 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