La importancia del tiempo



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

1. Introducción


    1. Sistemas de tiempo real

El problema del tiempo ha tenido presencia en toda la historia de la filosofía, ya desde sus inicios. Las diversas soluciones dadas al problema, desde un punto de vista exclusivamente especulativo han sido muchas y variadas a lo largo de la historia, además claramente decepcionares a la hora de su demostración práctica. Toda la mentalidad filosófica del tiempo cambió al ser tratado un problema desde un análisis científico.


El tiempo ha estado y está presente en toda la física, solamente hay que pararse a pensar el número de fórmulas físicas donde aparece el tiempo. El concepto del tiempo sufre un cambio drástico de mentalidad con el concepto relativista que surge en comienzos del siglo anterior con Einstein.
En los sistemas computacionales, tradicionalemte se ha considerado que un sistema computacional funcionaba correctamente cuando obtenía solución correcta desde el punto de vista lógico, independiente del tiempo de procesado. Esta definición no será válido par los sistemas que interactúan fuertemente con el entorno, son los denominados Sistemas de procesamiento en Tiempo Real (STR). Este tipos de sistemas, generalmente dedicados a tareas de control, suelen estar formados por recursos tales como sensores, para detectar el estado del sistema, unidad o unidades de cómputo, para procesar la entrada y generar la salida y los actuadores que ejecuta la información generada por el procesador. La cooperación y coordinación entre los diversos recursos obliga a que además de obtener una operación correcta, esta se realice con una temporalidad determinada.


tarea

tarea

tarea

Software de Tiempo-Real

sensores

Entorno

externo


Reloj

Actuadores

Sistema operativo



Figura 1.1 Sistemas de tiempo Real

El ejemplo clásico de STR es el sistema electrónico de los automóviles, que deben controlar la velocidad del coche, control de la tracción del coche, del ABS, etc. Según que requerimientos no sólo deseamos que se realice una determinada tarea, por ejemplo que active el ABS, sino que esto se realice en un tiempo mínimo. Desde luego, es deseable que todos los procesos se ejecuten en el menor tiempo, pero las limitaciones del entorno y del sistema de procesado impiden que así sea. Tendremos que priorizar unas tareas sobre otras, estableciendo un tiempo máximo de respuesta de cada una de las tareas, y acorde esta información establecer un plan de ejecución. Así desde el punto de vista de requerimientos temporales impuestos podemos distinguir entre tres diferentes categorías:

  • Sistemas de tiempo real estricto: el incumplimiento de alguno de sus requerimientos puede tener efectos catastróficos sobre el sistema que controla, por lo que imprescindible evitar estas situaciones, (ABS,Airbag)

  • Sistemas de tiempo real no estricto: el sistema puede incumplir ocasionalmente alguno de los requerimientos impuestos, tal que este incumplimiento produce una disminución en la calidad o prestaciones de la respuesta, pero se puede considerar aun así correcto el funcionamiento si no cumple alguno de los requisitos (monitorización de la velocidad, de la gasolina,etc).

  • Sistemas sin requerimientos de tiempo real: no importas el tiempo que se tarda en obtenerse una respuesta, si bien es deseable que se realice en el menor tiempo posible.

Además de su requerimiento temporal es importante saber como es el patron de llegadas o requerimientos de los eventos producidos en el sistema. Podemos distinguir según este patrón entre tres tipos de tareas:



  • Tareas periódicas: los eventos se generan a intervalos temporales regulares. La duración de este intervalo se conoce como periodo de activación, T, y es suficiente para caracterizar la llegada de eventos.

  • Tareas esporádicas: los eventos se generan a intervalos temporales no regulares, pero conocemos un tiempo mínimo entre llegada de dos eventos consecutivos. A este tiempo lo identificaremos de igual forma con el periodo de la tarea, T (en las situaciones de peor caso, coincidirá con la periódica de periodo T).

  • Limitado: los eventos se ejecutan a intervalos irregulares, pero se tiene garantizada una densidad máxima entre llegadas, expresada como un número máximo de eventos nmax en un intervalo de tiempo T.

  • Ilimitado: los eventos se generan a intervalos no regulares de tiempo, pero no existe un tiempo mínimo entre llegadas ni densidad máxima de ocurrencia. Virtualmente podría ocurrir la llegada de infinitos requerimientos de forma simultanea, por lo que no se puede garantizar un tiempo de respuesta limitado. Evidentemente ningún sistema es capaz de seguir instantáneamente un número infinito de eventos, así que realmente se trataría de un patrón limitado de llegadas, aunque con un límite efectivamente muy grande.



1.2 Técnicas de modelado de sistemas
Para verificar el cumplimiento de los requerimientos temporales de las distintas tareas, tendremos que diseñar la ejecución de los eventos, y estudiar matemáticamente los resultados que se obtienen. Las técnicas utilizadas comúnmente son:

  • Técnicas off-line: antes de que el sistema de tiempo real esté operando se prevé y analizan los posibles comportamientos, de manera que se pueda verificar el cumplimiento de los plazos de respuesta a partir de cotas superiores de los tiempos de respuesta o, en caso de incumplir alguno, cuantificar el grado de incumplimiento.




  • Técnicas on-line: en el instante en que una nueva tarea está lista para ejecutar, se realiza el análisis de planificabilidad considerando la nueva tarea junto con el conjunto de tareas ya existentes. Si el nuevo sistema formado siguiera siendo planificable se acepta, en caso contrario se rechaza. Estas técnicas presentan el inconveniente de que se puede rechazar tareas de gran importancia.

Las técnicas que se van a desarrollar en la tesina son del primer tipo de técnicas, mediante la cual se garantiza a priori plazos en la respuesta del sistema. Para poder realizar estas técnicas es necesario conocer los requisitos de las tareas, así como sus características. De forma que es necesario que todos los componentes del sistema, tanto software como hardware deben de ser conocidos a priori.



1.3. Sistemas monoprocesadores y multiprocesadores.
A la hora de planificar el sistema de tiempo real podemos distinguir, según los recurso de procesado de la información en sistemas monoprocesadores, un único procesador, y multiprocesadores , dos o más procesadores.

Cuando la planificación se realiza en un entorno multiprocesador tenemos mayor potencia de resolución, pero tenemos que considerar los mecanismos mediante los cuales se coordinan la ejecución de las diferentes tareas relacionadas en diferentes procesadores. Por lo general este mecanismo se realice mediante el paso de mensajes, de manera que cuando una tarea termina envía un mensaje que activa a la tarea siguiente.

Los sistemas multiprocesadores y distribuidos de tiempo real tiene una importancia creciente en los sistemas de control de hoy en día, sobre todo, debido a que el bajo coste de las redes de comunicación permite la intercomunicación de múltiples dispositivos y de sus controladores en un gran sistema.

Por lo general un sistema distribuido esta compuesto por múltiples procesadores conectados entre sí por recursos de comunicación. Es preciso que dichos sistemas de comunicación sean, al igual que todo el sistema, de tiempo real, es decir que realice la comunicación en un tiempo máximo acotado, y conocido a priori. De esta forma en la planificación del sistema, han de considerarse las tareas de comunicación como otras más del sistema de tiempo real.

Procesador 1

Procesador 2

Redes de comunicación
Entorno Externo

sensores


actuadores




Figura 1.2 Sistema Multiproceasador




Ejemplo de sistema multiprocesador con 2 procesadores


La mayoría de las redes de comunicación no se adaptan bien a las requerimientos de tiempo real, no soportando una planificación de los mensajes soportados bajo prioridades. Redes de comunicación de tiempo real son el token-bus [STR88], el bus CAN [TIN94E], FDI [AGR91], etc.
Los mensajes de comunicación de estas redes se modelan como tareas con distintas prioridades que se ejecutan en la red de comunicación, de manera que tenemos que planificar también las “tareas” de la red de comunicación. Cada mensaje tendrá asociada, por tanto una longitud máxima de envió identificada como lm.
El proceso de comunicación entre tareas en diferentes procesadores se realiza en las siguientes etapas:

  • Generación y encolado del mensaje: la tarea que envíe el mensaje debe componer el mensaje a trasmitir, y en el caso necesario, segmentarlo en paquetes de tamaño fijo. Además cada paquete transmitido por la red necesitará información adicional para el encadenamiento del mensaje hasta el destino, par finalmente ser puesto en la cola de transmisión.

  • Acceso al dispositivo de comunicación. Una vez que el paquete es encolado, deberá esperar a que el dispositivo de comunicación quede libre y listo para la transmisión del paquete.

  • Transmisión del mensaje por enlace físico desde el procesador de la tarea emisora origen hasta el procesador donde se encuentra la tarea receptora. El tiempo de transmisión vendrá definido por la longitud y por la velocidad de la red comunicaciones.

  • Recepción y composición del mensaje. Una vez recibido todos los paquetes correspondientes deberá componerse el mensaje original y notificarse a la tarea de destino.

En la mayoría de los sistemas se suelen considerar los tiempos de generación y de encolado del mensaje como parte de ejecución de la tarea emisora, así como la recepción y composición del mensaje a la tarea receptora. Estos tiempos han de sumarse a los tiempos de ejecución de peor caso propias de las tareas. Otros sistemas, sin embargo parte de las operaciones de generación y encolado las ejecuta alguna otra tarea, de prioridad generalmente superior, de forma que es necesario considerar esta tarea adicional en el análisis.


La similitud en una red de comunicación apta para tiempo real del acceso y la transmisión del mensaje con el tiempo de ejecución de una tarea de un procesador, hace que desde un punto de vista analítico, no distingamos entre la ejecución de una tarea en un procesador y la transmisión de un mensaje por un dispositivo de comunicación. De esta forma identificaremos cada mensaje por su tiempo de transmisión de peor caso Cm, siendo calculado suponiendo que tuviera el uso exclusivo del sistema de transmisión.
Es por esto que nos referiremos a las tareas que se ejecutan en un procesador o a los mensajes transmitidos por una red de comunicación como “acciones” del sistema del tiempo real. Así el modelo de sistemas distribuidos de paso con mensajes consistirá desde un punto de vista analítico como una secuencia de acciones (tareas en los procesadores y mensajes en las redes de comunicación) conectados entre sí mediante eventos internos, y con tiempo de computo o transmisión de peor caso Ci, siendo i la tarea.

1.4 Características de las acciones

Como hemos visto en el anterior apartado, consideraremos a partir de ahora “acciones” entendiendo estas como tareas en los procesadores o mensajes en las redes de comunicación. En las técnicas de análisis off-line, debemos conocer los parámetros propios de las acciones, de manera que seamos capaces mediante algoritmos matemáticos (planificación del sistema de tiempo real). Identificaremos cada acción con el subíndice i. Cada acción ai queda definida, en un principio por los parámetros siguientes:




  • Ci: tiempo de ejecución de peor caso de la tarea ai en un procesador sin otras tareas o el tiempo de transmisión de peor caso si es un mensaje en una red de comunicación.




  • Ti: periodo de activación (o tiempo mínimo entre llegadas) del evento externo que origina la cadena de respuesta a la cual pertenece la acción.




  • Ji: retraso máximo en la activación de la acción.




  • Di: deadline, es el tiempo máximo que ha de transcurrir entre la llegada del evento externo (no la activación que puede ocurrir hasta Ji instantes después) hasta la finalización de la ejecución. A veces también es necesario cumplir unos requisitos temporales en cada tarea particular que se ejecute en un tiempo máximo di. Cuando cada evento externo tiene un única tarea asociada D y d coinciden.

Conociendo estas características de las tareas, tendremos que ser capaces de hacer que el sistema cumpla todos los requisitos temporales, finalizando cada proceso antes de sus deadline. Para esto tendremos que buscar técnicas de planificación apropiadas, y encontrar los algoritmos matemáticos que nos calculen los tiempos de respuesta de peor caso comprobando que es inferior al deadline. Otras técnicas de análisis no nos calculan el tiempo de ejecución de peor caso, pero nos aseguran que si cumple una series de requisitos dicho sistema es planificables, es decir, cumple los requisitos temporales.


Nota: por comodidad denotaremos las acciones como tareas, aun siendo mensajes. También denotaremos Ci como el tiempo de ejecución de peor caso, incluso cuando sea tiempo de envío.

1.5 Modelo general para transacciones de tiempo real.
En sistemas distribuidos de tiempo real, el modelo mas utilizado es modelo transacional [Tin94B]. Una transacción es una entidad que agrupa tareas activadas todas con igual periodo y con ciertas restricciones en cuanto a sus instantes de activación.
Identificaremos cada transacción como i , ésta es activada por un evento externo con periodicidad Ti, y que se compone de un conjunto de mi tareas o mensajes. La llegada de un evento activa la secuencia de tareas de la misma transacción. Cada tarea de la transacción i se denotará como ij, donde el subíndice j denota la posición en la secuencia de la transacción. Cada tarea se puede activar a partir de un tiempo relativo a la llegada del evento de la transacción (offset, ij). La activación se puede producir desde este momento hasta Jij instantes posteriores, de forma que se produce en el intervalo temporal [t0+ij, t0+ij+Jij], donde t0 es el instante de llegada del evento externo. Para cada tarea identificaremos su tiempo de ejecución de peor caso como Cij.
Dependiendo de cómo sea la fase de activación de la tarea distinguimos entre dos tipos de transacciones:

  • Con offset estáticos, cuando la fase de activación es fija, y conocida a priori.

  • Con offset dinámicos, cuando la fase de activación depende de los tiempos de respuesta de las tareas anteriores. Este modelo permite modelar y analizar sistemas de tiempo real con relaciones de procedencia, tales como las gobernadas por el paso de mensajes.

En los sistemas multiprocesadores y distribuidos es usual que el sistema pueda ser modelado por transacciones compuestas por varias tareas, al estilo del modelo computacional descrito anteriormente. En sistemas que siga la arquitectura cliente-servidor una tarea cliente se activa por la llegada de un evento externo y requiere el servicio de uno o varios procesadores. Estas tareas cliente pueden modelarse mediante una transacción . En este modelo cada tarea ij se activa con la finalización de la tarea previa perteneciente a la misma transacción(ij-1).

El tiempo de respuesta de la tarea ij será el tiempo transcurrido desde la llegada del evento externo hasta la finalización de su ejecución y se denota Rij.
De esta forma, cada acción de una transacción representa una tarea ejecutando en un procesador o un mensaje trasmitido por el canal de comunicación, que se activan cuando se completan la ejecución de la tarea anterior. Como veremos, la fase ij será el tiempo de mejor caso de la tarea anterior, y el retraso será la diferencia entre la peor y mejor respuesta de la anterior tarea.

Figura 1.3. Transacción de Tiempo Real


2. PLANIFICACIÓN DE SISTEMAS DE TIEMPO REAL
2.1 Características fundamentales.
Como comentábamos en el apartado 1.2 las técnicas que desarrollaremos en esta tesina serán del tipo off-line. Para poder conocer con exactitud el comportamiento temporal de las tareas de un sistema en tiempo real es necesario eliminar el indeterminismo que produce la ejecución concurrente. Ello es posible por medio de la planificación.

La planificación del sistema de tiempo real consiste en:



  • Definición de las reglas de uso de cada uno de los recurso disponibles, procesadores y recursos compartidos. Es lo que llamaremos algoritmo o política de planificación.

  • Un método para predecir el comportamiento del sistema en el peor caso cuando se le aplica el algoritmo de planificación. Ello permitirá cumple o no las restricciones temporales que se le imponen. Esto es lo que se llama análisis de planificabilidad.

En esta tesina sólo estudiaremos los tiempos de respuesta de peor caso, por muy poco probables que sea éste. Existen también estudios estadísticos, que se centran en los tiempos de respuesta en función de la probabilidad de que ocurran los sucesos correspondientes.


Las técnicas de análisis de planificabilidad, muchas veces no son técnicas exactas, y lo que obtenemos son cotas superiores de los tiempos de respuestas, se dicen que estas técnicas son pesimistas, de forma que se pueden encontrar sistemas que desde el punto de vista del análisis no son planificables, pero si lo son realmente. Cada vez se buscan técnicas menos pesimistas, que se acerque al algoritmo de planificabilidad que nos da el tiempo de respuesta exacto, o con las cuales obtengamos el valor exacto de los tiempos de respuesta.
Los test de planificabilidad que obtienen el resultado exacto o bien cotas superiores se llaman test de planificabilidad suficientes. En el caso de que el test sea exacto, además de suficiente se denomina test de planificabilidad exacto. Desde el punto de vista del estudio de los tiempos de peor caso, que es el que trataremos, necesitamos obtener test suficientes. Para sistemas monoprocesadores hay múltiples test de planificabilidad exactos, sin embargo la complicación de los sistemas distribuidos sólo existen test exactos en ciertos casos sencillos, resultando inabordables en la mayoría.
Las políticas de planificación deben cumplir además las siguientes características:

  • Ser predecible, con objeto de asegurar tiempos de ejecución finitos. Para ello deben ser predecibles las propias interferencias que el algoritmo tendrá sobre el calculo del tiempo de respuesta del sistema. Estos efectos deben ser mensurables.

  • Capaz de gestionar diferentes recursos compartidos. Diferentes recursos pueden requerir diferentes políticas de planificación, incluso formando parte del mismo sistema de tiempo real.

  • Debe de ser capaz de garantizar el tratamiento tanto de eventos periódicos como aperiódicos, incluso con patrones de llegada ilimitados.

  • Verificar su planificabilidad para utilizaciones altas.

  • Que sea sencillo de implementar en aplicaciones reales.



2.2 Clasificación de las políticas de planificación sistemas monoprocesadores

En la clasificación vamos a ver las políticas de planificación, suponiendo además de ser monoprocesadores las siguientes propiedades:



  • Las tareas son independientes, es decir los tiempos de respuesta no dependen de los tiempos de respuesta de las otras tareas.

  • No existen compartición de recursos de las distintas tareas.

  • Todas las tareas son periódicas.

  • Los tiempos de cambio de contexto(tiempo que se emplea entre el paso de la ejecución de una tarea a otra) son despreciables, o están incluidos en los tiempos de ejecución de peor caso de las tareas.

Estas imposiciones se irán eliminando añadiendo variantes a las diferentes políticas de planificación, de forma que puedan soportar tareas que no cumplan los requisitos expuestos anteriormente.


Conforme a lo expuesto anteriormente las políticas de planificación se pueden clasificar como:

  1. Ejecutivo cíclico o planificación estática.

  2. Por prioridades:

    1. Estáticas

      1. Rate monotonic (RMA)

      2. Deadline monotonic (DMA)

    2. Dinámicas

      1. Prioridad al más urgente. Earliest Deadline first (EDF).

      2. Prioridad al menos holgado. Least Laxity First (LLF)



2.2.1 Planificación estática o cíclica
Es el mecanismos de planificación más sencilla es la planificación estática o ejecutivo cíclico. Es válida únicamente para tareas periódicas. La planificación se realiza antes de la ejecución, una vez conocido el sistema. Se organiza la ejecución de las tareas en un hiperperiodo, que es el mínimo común múltiplo de los periodos de las tareas. Se construye una tabla con la secuencia de llamadas(activación de tareas) a realizar en el hiperperiodo. Puesto que a patir del primer hiperperiodo se repite el comportamiento del sistema, la tabla sólo necesita almacenar las acciones de un hiperperiodo.
Según como sean las tareas a realizar, se pueden fraccionar en rodajas o deben ejecutarse completas. A la hora de realizar la tabla de ejecución, es deseable que las tareas puedan ser fraccionadas, si bien muchas veces este proceso necesita un tiempo adicional al de ejecución. Si se puede construir el plan, entonces el sistema es correcto.
El funcionamiento del planificador, una vez realizada la planificación es muy sencilla, ya que sólo debe ir leyendo las entradas correspondientes en el plan de ejecución.
El ejecutivo cíclico tiene s inconvenientes muy grandes, que le hace que sólo sea usado para planificaciones muy sencillas, estos problemas son:


  • Es difícil de construir el plan, sobre todo si los periodos generan un hiperperiodo muy grande, lo que generaría una tabla de activación de gran tamaño, prácticamente intratable. Esto puede resolverse reduciendo convenientemente los periodos de las tareas(nunca ampliando, pues debemos de ser pesimistas).

  • Es muy difícil de mantener, pequeñas modificaciones del sistema pueden hacer que tengamos que rehacer de nuevo el plan de ejecución. No siguiendo el principio de independencia entre la estructura lógica del programa y su planificación.

  • Es muy poco flexible, no pudiendo tratarse en esta planificador eventos asíncronos, o con retraso.


Ejemplo:

Actividades a controlar

Tiempo ejecución(C)

Periodo(T)

Plazo de finalización(D)

Medida velocidad

4ms

20ms

5ms

Control de Inyección

40ms

80ms

80ms

Control frenos ABS

10ms

40ms

40ms

H=hipermeriodo=mcm(20,80,40)=80ms


En un hiperperiodo hay 4 ejecuciones de la medida de la velocidad, 2 del control de frenos y una del control de inyección. El tiempo de ejecución del sistema es de 44ms+40ms+102ms=76ms. Será planificable siempre que pueda ser las tareas seccionables, en especial el control de inyección, ya que si este no es seccionable perderían el plazo las otras dos tareas, ya que su ejecución es mayor o igual que los plazos de finalización.

Una posibles solución cíclica de este sistema podría ser la siguiente:



76

4

0



64

14

Fuel-4

Veloc




ABS



Otras tareas sin requisitos temporales

Veloc

Fuel-1



60

20




Fuel-3

Veloc




ABS

Veloc

Fuel-2



54

24



40

44

Pseudocódigo de ejecución del sistema de control:


Begin

loop

Veloc; ABS; Fuel_1;Veloc;Fuel_2;Veloc;ABS;Fuel_3;Veloc;Fuel_4;

Sleep(4ms);

end loop;

end;

2.2.2 Planificación mediante prioridades.
Un planificador basado en prioridades decide que tarea es la que se ejecuta de la q ue estén pendientes de ejecución en virtud de un único atributo de la tarea: su prioridad. Las tareas planificadas pueden encontrarse en tres posibles estados:

  • Preparada: El evento de la activación de la tarea ha ocurrido, y la tarea está lista para poder ser ejecutada pero el procesador se encuentra ejecutando otra de mayor prioridad.

  • Suspendida: Una tarea se suspende cuando termina su ejecución y se encuentra a la espera de la llegada de la siguiente activación.

  • Ejecutando: La tarea es la más prioritaria de las tareas preparadas y esta siendo atendida por el procesador.

Cuando las tareas se comunican entre si, entonces aparecen estados adicionales que reflejan la situación de una tarea que está esperando a sincronizarse con otra.


Un planificador basado en prioridades puede entenderse como una cola de tareas, ordenadas por prioridad, de la que se extrae el primer elemento de la cola(con mayor prioridad). Los procesos realizados por el procesador son las siguientes:


  • Despacho. Una tarea i lista para ejecutar será despachada cuando no haya otra tarea en ejecución de mayor o igual prioridad que ella

  • Suspensión. Cada vez que una tarea termina de ejcutar, se suspende hasta la siguiente activación

  • Activación. Cuando es una tarea periódica se produce de forma periódica, para las esporádicas cuando se produce un proceso interno o externo que debe atender.

  • Expulsión. Una tarea i es expulsada del procesador, cuando esta ejecutando y se produce una activación de una tarea con mayor prioridad, pasando a estar en estado preparada en al cola de prioridad.


Figura 2.1 Modelo de planificador expulsivo por prioridades


2.2.3 Planificación dinámica mediante prioridades fijas.
Una posibilidad bastante más potente y versátil a la planificación estática es la planificación dinámica. En ella los problemas de contención de recursos se resuelven en el instante que aparecen, por lo que no es necesario realizar un plan ejecutivo previo. Esto hace más complejo el funcionamiento del planificador, aunque el sistema resulta mas sostenible y general, además de ser independiente de la estructura del código, al no tener que hacer partición del mismo.
La elección de la ejecución de una otra tarea a la hora de ejecutar en el procesador o en algún otro recurso compartido se realiza según la prioridad de las tareas, prioridad que se conocen a priori (prioridades fijas). De esta forma la tarea con mayor prioridad de las que desean ejecutar en un recurso es la que toma dicho recurso.
Dentro de las políticas de planificación de prioridades hay que diferenciar entre un planificador expulsor o un planificador no expulsor. En un planificador no expulsor, cuando una tarea toma el control del procesador no detiene su ejecución hasta que ha finalizado el proceso. Por el contrario en un planificador expulsor una tarea cede el uso del procesador (es expulsada) si se activa una tarea de mayor prioridad, aunque desde el punto de vista del análisis de peor caso consideraremos que es expulsable también por tareas de igual prioridad)
Según la asignación de prioridades a las diferentes tareas tendremos distintos planificadores. Las más importantes son la Rate Monotonic (RM) y la deadline Monotonic (DM).


Teoría RMA (Rate Monotonic Análisis)
La teoría RMA (Rate Monotonic Análisis) es una técnica de análisis de sistemas con prioridades fijas, cuyo objetivo es determinar que el sistema sea planificable. Esta teoría surge a partir de un trabajo llevado a cabo por Liu y Layland en 1973 [Liu73] en el que introdujeron el algoritmo RMS (Rate Monotonic Scheduling). Demostrando que la asignación era óptima cuando se le daba mayor prioridad a las tareas con menor periodo. El trabajo de Liu y Layland era demasiado restrictivo, siendo aplicable a pocos sistemas, pero sentaría las bases de trabajos posteriores donde se eliminan las restricciones impuestas.
Cuando los plazos de finalización son iguales al periodo esta asignación es óptima. De esta forma si un sistema con asignación estática de prioridades y con deadline igual al periodo no es planificable con asignación RM no es planificable con cualquier otra asignación estática.
Teoría DMA (Deadline Monotonic Análisis)
La teoría DMA (Deadline Monotonic Análisis) es una técnica de análisis de sistemas con prioridades fijas, que asigna prioridades según el deadline. Así la mayor prioridad corresponde a la tarea que tenga menor plazo de ejecución. Leung y Whithehead probaron que, en el caso en el que el deadline sea menor que el periodo la asignación óptima es la basada en esta teoría [LEU82].

En el apartado 2 de esta tesina veremos los diferentes test de planificabilidad, tanto para los análisis RMA como DMA.





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