José Carlos Palencia Gutiérrez


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "José Carlos Palencia Gutiérrez"

Transcripción

1 UNIVERSIDAD DE CANTABRIA FACULTAD DE CIENCIAS DEPARTAMENTO DE ELECTRÓNICA Y COMPUTADORES ANÁLISIS DE PLANIFICABILIDAD DE SISTEMAS DISTRIBUIDOS DE TIEMPO REAL BASADOS EN PRIORIDADES FIJAS TESIS DOCTORAL José Carlos Palencia Gutiérrez Santander 1999

2

3 UNIVERSIDAD DE CANTABRIA FACULTAD DE CIENCIAS DEPARTAMENTO DE ELECTRÓNICA Y COMPUTADORES ANÁLISIS DE PLANIFICABILIDAD DE SISTEMAS DISTRIBUIDOS DE TIEMPO REAL BASADOS EN PRIORIDADES FIJAS MEMORIA presentada para optar al grado de DOCTOR EN CIENCIAS FÍSICAS por José Carlos Palencia Gutiérrez Licenciado en Ciencias, Sección Físicas Especialidad de Electrónica Universidad de Cantabria i

4 Análisis de planificabilidad de sistemas distribuidos de tiempo real ii Grupo de Computadores y Tiempo Real

5 UNIVERSIDAD DE CANTABRIA FACULTAD DE CIENCIAS DEPARTAMENTO DE ELECTRÓNICA Y COMPUTADORES ANÁLISIS DE PLANIFICABILIDAD DE SISTEMAS DISTRIBUIDOS DE TIEMPO REAL BASADOS EN PRIORIDADES FIJAS MEMORIA presentada para optar al grado de Doctor en Ciencias Físicas por el Licenciado en Ciencias José Carlos Palencia Gutiérrez El Director, Dr. Michael González Harbour Profesor Titular de Universidad DECLARO: Que el presente trabajo ha sido realizado en el Departamento de Electrónica y Computadores de la Universidad de Cantabria, bajo mi dirección y reúne las condiciones exigidas a los trabajos de Doctorado. Santander, Abril de 1999 Fdo. José Carlos Palencia Gutiérrez Fdo. Michael González Harbour Universidad de Cantabria iii

6 Análisis de planificabilidad de sistemas distribuidos de tiempo real iv Grupo de Computadores y Tiempo Real

7 A Tino y Margarita, a Judith y Jezabel, y a Luis Alberto. Universidad de Cantabria v

8 Análisis de planificabilidad de sistemas distribuidos de tiempo real vi Grupo de Computadores y Tiempo Real

9 Es curioso como algunas situaciones, aparentemente intrascendentes, pueden cambiar el rumbo de tu vida. Supongo que mi inicial admiración por José María Drake despertó mi interés por trabajar en este grupo. A él quiero dirigir en primer lugar mi agradecimiento más sincero. También quiero agradecer conjuntamente a José María y a Michael su empeño en que esta tesis haya llegado a término. Especialmente por su interés y esfuerzo personales para conseguir mi sostenimiento económico, en varias situaciones ciertamente difíciles para mí. Quisiera mostrar públicamente mi agradecimiento a todas aquellas personas que han contribuido a crear a mi alrededor un ambiente agradable. Sin ellos seguramente no hubiera encontrado la inspiración suficiente para superar los momentos difíciles, tanto desde el punto de vista emocional como intelectual. Afortunadamente para mí, debería citar aquí a mucha gente, pero lógicamente no es posible. En primer lugar a mis padres, por enseñarme lo que es realmente importante en la vida, y a mis hermanos. En segundo lugar, a mis amigos y compañeros de trabajo, especialmente a Gustavo y Mercedes, Felipe y Sol, Vicente, Borja, Carmen, Javi, Kakel, Rafa, Romero, Julio, Jorge,... y un montón de gente más. También quiero citar expresamente a mis amigos y compañeros de carrera, con los que compartí tantas horas de estudio y risas: Pedro, Jose, Manolo, César y Alex. No sería justo si no agradeciera especialmente a Luis Alberto su amistad, interés y sentido común. En último, pero más importante lugar, a Jezabel y a mi hija, Judith, que llenan mi vida de felicidad. También quisiera expresar mi agradecimiento y admiración hacia aquellos que me han hecho disfrutar con sus trabajos, especialmente a Michael González Harbour, Neil Audsley, Ken Tindell y John Lehoczky. Por cierto, no se me deberían olvidar Beethoven y Solti. Los tres hemos compartido muchas noches en vela rodeados de ecuaciones. Gracias a todos. Universidad de Cantabria vii

10 Análisis de planificabilidad de sistemas distribuidos de tiempo real viii Grupo de Computadores y Tiempo Real

11 La presente Tesis Doctoral, ha sido desarrollada en el marco de los siguientes proyectos de investigación: "Extensión de la teoría RMA al diseño y análisis de sistemas de tiempo real gobernados por eventos". Proyecto del Plan Nacional de Investigación en Automatización Avanzada y Robótica, , Ref. ROB "Herramientas para el análisis de tiempo real de sistemas distribuidos para automatización industrial". Proyecto del Plan Nacional de Investigación en Tecnologías Avanzadas de la Producción, , Ref. TAP "Metodología para el análisis y diseño orientado a objetos de sistemas distribuidos de tiempo real estricto". Proyecto del Plan Nacional de Investigación en Tecnologías Avanzadas de la Producción, Universidad de Cantabria ix

12 Análisis de planificabilidad de sistemas distribuidos de tiempo real x Grupo de Computadores y Tiempo Real

13 Indice de contenidos Indice de contenidos Resumen... xv Sistemas distribuidos de tiempo real Introducción Modelo del sistema Caracterización de eventos Respuesta a un evento Sistemas multiprocesadores y distribuidos Red de comunicación Modelo general para transacciones de tiempo real Planificación de sistemas de tiempo real Planificación estática Planificación dinámica por prioridades fijas Planificación dinámica por prioridades dinámicas Exclusión mutua e inversión de prioridad Planificación de eventos aperiódicos Planificación en el modelo transaccional Problemática de los sistemas distribuidos Objetivos planteados en el trabajo Optimización de la técnica existente Desarrollo de nuevas técnicas de análisis Organización de la memoria de tesis doctoral Técnicas existentes de análisis temporal Introducción Sistemas monoprocesadores Tareas independientes Tareas con recursos compartidos Plazos superiores a los periodos Universidad de Cantabria xi

14 Análisis de planificabilidad de sistemas distribuidos de tiempo real 2.3. Sistemas multiprocesadores y distribuidos Análisis de las redes de comunicación Modelo general para el análisis La problemática del jitter Análisis bajo la aproximación de tareas independientes Mejoras sobre el análisis en sistemas distribuidos Introducción Validación de la técnica existente Explorando la reducción del número de casos a comprobar en el test de planificabilidad Cálculo de los tiempos de respuesta locales de peor caso Análisis de mejor caso para mejorar el análisis de peor caso Estimación trivial del mejor caso Estimación iterativa del mejor caso Resultados de simulación Análisis de planificabilidad para tareas con offsets estáticos y dinámicos Introducción Análisis para tareas con offsets estáticos Modelo computacional Análisis exacto de los tiempos de respuesta Análisis aproximado de los tiempos de respuesta Tareas esporádicas con offset Análisis para tareas con offsets dinámicos Análisis para sistemas multiprocesadores y distribuidos Comparación con las técnicas existentes Mejoras al análisis de tareas con offsets y relaciones de precedencia Introducción Relaciones de precedencia en la transacción analizada Resultados de simulación Perfil de prioridades y precedencia en transacciones xii Grupo de Computadores y Tiempo Real

15 Indice de contenidos Prioridades y conflictos de activación Aplicación a la transacción analizada Comparación de resultados Tareas con prioridades variantes Conclusiones 6.1. Revisión de objetivos Contribuciones de este trabajo Trabajo futuro Bibliografía... B Universidad de Cantabria xiii

16 Análisis de planificabilidad de sistemas distribuidos de tiempo real xiv Grupo de Computadores y Tiempo Real

17 Indice de contenidos Resumen Palabras clave: Tiempo real, sistemas distribuidos, análisis de planificabilidad, tiempo de respuesta, planificación por prioridades. En la tesis doctoral presentada en esta memoria se estudia el análisis de sistemas de tiempo real en los que se debe verificar el cumplimiento de ciertos requerimientos temporales, principalmente referidos a plazos máximos de ejecución. Esta verificación se realiza mediante el análisis de planificabilidad basado en el cálculo de tiempos de respuesta de peor. El estudio se centra en los sistemas multiprocesadores y distribuidos gobernados por eventos y planificados mediante políticas basadas en asignación de prioridades fijas. Dentro de este ámbito no se conocen técnicas exactas de análisis, de manera que parte de la investigación se ha orientado a la búsqueda de técnicas analíticas aproximadas que verifiquen suficientemente el cumplimiento de los requisitos temporales. El trabajo presentado en esta tesis se dirige básicamente a esa búsqueda. Por un lado, se centra en la formalización y optimización de las técnicas de análisis previamente desarrolladas por otros autores, mediante modelos que aproximan el comportamiento real de los sistemas distribuidos de forma que sean analizables, aunque introduciendo con ello cierto pesimismo, que hace que el análisis no resulte exacto, pero sí suficiente. Por otro lado, la tesis se centra en la búsqueda de un nuevo modelo que permita reducir el pesimismo en el análisis. El modelo que se propone es el basado en tareas con offsets dinámicos, mediante el que se consiguen mejoras sustanciales frente a los modelos anteriormente utilizados. También se optimiza el análisis al considerar las relaciones de precedencia en la ejecución de tareas dentro del sistema distribuido. La inclusión de estas relaciones de precedencia cuando deducimos las expresiones analíticas que conducen a la obtención de los tiempos de respuesta hace que se reduzca fuertemente el pesimismo. Este modelo se ha encontrado también adecuado para el análisis de tareas que se suspenden o para el análisis de tareas con prioridades variantes, dentro de sistemas multiprocesadores y distribuidos. Universidad de Cantabria xv

18 Análisis de planificabilidad de sistemas distribuidos de tiempo real xvi Grupo de Computadores y Tiempo Real

19 Sistemas distribuidos de tiempo real 1. Sistemas distribuidos de tiempo real Introducción Tradicionalmente se ha considerado que un sistema computacional funciona correctamente cuando la solución que obtiene es correcta desde el punto de vista lógico. Esta definición, si bien es válida para sistemas de cálculo convencional, no es suficiente cuando estamos considerando sistemas que interactúan fuertemente con el entorno. Este tipo de sistemas, normalmente dedicados a tareas de monitorización o control, suelen estar formados por un conjunto de recursos tales como sensores, unidades de cómputo y actuadores que deben trabajar de forma coordinada para realizar la labor encomendada. La cooperación entre diferentes recursos obliga, no sólo a que cada operación sea correcta, sino a que se realice en los instantes oportunos. Este tipo de sistemas a los que es preciso imponer restricciones temporales se denominan sistemas de tiempo real [STA88]. Desde el punto de vista de los requerimientos temporales impuestos, un sistema se pueden clasificar en tres categorías diferentes: Sistemas de tiempo real estricto: el incumplimiento de alguno de los requerimientos puede tener efectos catastróficos sobre el sistema que controla, por lo que es imprescindible evitar esta situación. El sistema debe cumplir todos los requerimientos especificados. Sistemas de tiempo real no estricto: el sistema puede incumplir ocasionalmente alguno de los requerimientos impuestos. Ese incumplimiento produce una disminución en las prestaciones o calidad de la respuesta pero el funcionamiento se puede considerar todavía correcto. Universidad de Cantabria 1-1

20 Análisis de planificabilidad de sistemas distribuidos de tiempo real Sistemas sin requerimientos de tiempo real: no importa el tiempo que se tarda en obtener una respuesta. La rapidez en la respuesta sería deseable simplemente a efectos de mejorar el tiempo de respuesta promedio o la capacidad media de procesado. Evidentemente pueden considerarse sistemas en los que existan simultáneamente requerimientos temporales estrictos y no estrictos junto con tareas de cálculo convencional. Normalmente los requerimientos temporales que se imponen a un sistema se refieren al tiempo de respuesta de cada una de las tareas que lo componen. El más usual, y sobre el que se centra gran parte del análisis de tiempo real, es el concepto de plazo de una tarea, considerado como el máximo tiempo necesario para obtener una respuesta. Otros tipos de requerimientos se refieren a la separación entre dos respuestas consecutivas, a la capacidad mínima de procesado, etc. En esta tesis nos centraremos exclusivamente en los plazos de respuesta en sistemas de tiempo real estricto. Las técnicas utilizadas comúnmente para verificar el cumplimiento de esos requerimientos temporales se pueden clasificar en dos tipos diferentes: Técnicas off-line: antes de que el sistema de tiempo real esté operando se preveen y analizan los posibles comportamientos, de forma que estimando cotas superiores de los tiempos de respuesta se puede verificar el cumplimiento de los plazos de respuesta o, en caso de que pudiera 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 existente. Si el nuevo sistema formado siguiera siendo planificable, entonces se acepta la tarea para ejecutar; en caso contrario, se rechaza. Estas técnicas presentan el inconveniente de que pueden rechazar tareas de gran importancia, sin que este hecho se pueda detectar hasta el momento de la ejecución. El análisis desarrollado en esta tesis se enmarca en el primer tipo de técnicas. El hecho de tener que garantizar a priori plazos en la respuesta de un sistema hace necesario imponer ciertos requisitos sobre la especificación e implementación del mismo. En particular, es 1-2 Grupo de Computadores y Tiempo Real

21 Sistemas distribuidos de tiempo real preciso que el comportamiento temporal del sistema de tiempo real sea predecible. Esto quiere decir que todos los componentes (tanto hardware como software) del sistema de tiempo real deben ser conocidos y estar perfectamente especificados a priori Modelo del sistema La mayoría de los sistemas de control están basados en uno o varios procesadores conectados entre sí a través de un bus o una red de comunicación y que interactúan con el entorno. Esta interacción se realiza mediante sensores que dan información del estado actual del sistema a controlar y mediante actuadores que pueden modificar o actuar sobre algún aspecto del mismo. La implementación del sistema de control determinará como interactuarán los diferentes elementos que lo forman, clasificándose en: Sistemas gobernados por eventos: las acciones encargadas del control del sistema se activan con la ocurrencia de eventos, de forma que la llegada de esos eventos es la que caracteriza el flujo del programa de control. Sistemas gobernados por tiempo: las acciones de control son activadas por el sistema ejecutivo en instantes de tiempo predeterminados. Estos instantes de activación se producen normalmente a intervalos de tiempo regulares, de forma que el sistema está formado por acciones activadas periódicamente. Sistemas gobernados por el paso de mensajes: la activación de las acciones se produce como consecuencia de la llegada de algún mensaje a través del sistema de comunicación. Esta es la forma usual de activación de acciones cooperantes en sistemas distribuidos, en los que una tarea comienza a ejecutar cuando otra tarea (normalmente ejecutando en otro procesador) ha finalizado previamente. Normalmente, la activación de la primera tarea cooperante está gobernada por un evento o por tiempo y la activación de las siguientes mediante paso de mensajes entre los procesadores involucrados. Universidad de Cantabria 1-3

22 Análisis de planificabilidad de sistemas distribuidos de tiempo real En esta tesis modelaremos los sistemas de tiempo real suponiendo que su funcionamiento se basa en esta última política de control, ya que las dos primeras serían un caso particular de ese modelo general Caracterización de eventos La sensorización de un sistema físico se identifica con el concepto de evento, que dispara el proceso de control. Desde el punto de vista de cada elemento que forma el sistema de control (en particular los procesadores donde se ejecutan las acciones oportunas) debemos caracterizar la ocurrencia de eventos y la detección de esa ocurrencia. En cuanto a quién es la fuente que origina el evento, clasificaremos los eventos en tres tipos diferentes: Eventos temporizados: producidos por temporizadores o relojes propios del sistema de control, de forma que el sistema ejecutivo es el encargado de hacer notar la ocurrencia de esos eventos. Eventos externos: son los eventos originados en el sistema físico que se está controlando y que significan el desencadenamiento de una serie de acciones dentro del sistema de control como respuesta a ese evento. Eventos internos: son los eventos producidos dentro del propio sistema de control como consecuencia de la necesaria sincronización entre la ejecución de acciones en diferentes procesadores en respuesta, normalmente, a un mismo evento externo. En nuestro modelo identificaremos estos eventos internos con los mensajes entre procesadores. La sensorización de cada evento, ya sea interno o externo, caracteriza la activación de la correspondiente acción asociada, de forma que ésta se puede producir: A requerimiento del sensor: El sensor genera asíncronamente un requerimiento de interrupción a algún procesador del sistema, de manera que éste invoca un manejador de excepciones con el código oportuno para el procesado de ese evento. Es un 1-4 Grupo de Computadores y Tiempo Real

23 Sistemas distribuidos de tiempo real mecanismo de sensorización muy eficiente, pero hay que tener en cuenta la dificultad de su programación. A requerimiento del procesador: Hay sensores que no son capaces de generar una interrupción o que ni siquiera lo necesitan. En ese caso, el procesador debe requerir, normalmente de forma periódica, el estado del sensor o dispositivo correspondiente. Este método es más sencillo de implementar pero en algunos casos es menos eficiente que el método anterior, ya que debe tenerse en cuenta la incertidumbre introducida por el periodo de muestreo y la capacidad del dispositivo de dar medidas de forma continua o discreta. Independientemente de cómo se genera, la llegada de un evento dispara la ejecución de un conjunto de actividades en el sistema procesador. Esto significa que debemos caracterizar el patrón de llegadas u ocurrencia de todos los eventos producidos en el sistema. Este patrón de llegadas puede ser de los tipos siguientes: Periódico: los eventos se generan a intervalos de tiempo regulares. La duración de ese intervalo se denomina periodo de activación, T, y es suficiente para caracterizar la llegada de eventos. Esporádico: los eventos se generan a intervalos no regulares de tiempo, pero con tiempo mínimo entre la llegada de dos eventos consecutivos. Dado que verificaremos el plazo máximo de respuesta al evento, nos interesa conocer cuál es ese tiempo mínimo, al que identificaremos como T. Limitado: los eventos se generan a intervalos no regulares de tiempo, pero tienen garantizada una densidad máxima de ocurrencia, generalmente expresada como máximo número de eventos n max en un intervalo determinado de tiempo T. Desde el punto de vista del análisis de peor caso, podemos modelar este patrón de generación en base a eventos esporádicos (cada uno equivalente a n max eventos) con tiempo mínimo entre llegadas equivalente a T. Universidad de Cantabria 1-5

24 Análisis de planificabilidad de sistemas distribuidos de tiempo real Ilimitado: los eventos se generan a intervalos no regulares de tiempo, pero no existe un tiempo mínimo entre llegadas ni una densidad máxima de ocurrencia. Virtualmente podrían llegar infinitos eventos simultáneamente, por lo que no se puede garantizar un tiempo de respuesta limitado. Evidentemente ningún sistema es capaz de seguir instantáneamente un numero infinito de eventos, así que realmente se trataría de un patrón limitado de llegadas, aunque con un límite efectivamente muy grande Respuesta a un evento Cada evento que llega al sistema de control desencadena una serie de acciones en respuesta. Esas acciones normalmente se asocian a tareas cuyo código se activa a instancias de la llegada de eventos (externos, internos o temporizados). Para poder garantizar off-line un tiempo finito de respuesta es preciso que cada tarea del sistema tenga definido un tiempo máximo de ejecución, C, también llamado tiempo de ejecución de peor caso, entendido como el tiempo máximo que tarda en ejecutar el código correspondiente suponiendo que no hay ningún tipo de interferencia (por ejemplo de otras tareas) en dicha ejecución. Aunque no es tarea fácil en absoluto, en esta tesis supondremos que se conocen los tiempos de ejecución de peor caso de todas las acciones que ejecutan en el sistema. Este es un requisito general en todos los sistemas de tiempo real estricto, sea cual sea su método de planificación. Técnicas que estudian la obtención de estos tiempos de ejecución de peor caso se pueden encontrar en [CHA93] [CHA94] [JOU95] [LIM95]. En sistemas de control complejos se suele asociar la respuesta a un evento a la ejecución de varias tareas, incluso en varios procesadores, que coordinan su ejecución para obtener la respuesta total del sistema. Esta asociación de tareas se conoce como cadena de respuesta al evento y debe ser totalmente conocida en sistemas en los que sea preciso obtener una garantía de tiempos de respuesta de peor caso en tiempo de compilación. En esta tesis consideraremos una cadena de respuesta fija para cada posible evento del sistema, tanto desde el punto de vista de las tareas que lo componen como del procesador en que ejecuta cada tarea. Asimismo, consideraremos un modelo lineal de la cadena de respuesta: esto significa que cada tarea se activa por un único evento (ya sea interno, externo o temporizado) y puede 1-6 Grupo de Computadores y Tiempo Real

25 Sistemas distribuidos de tiempo real generar un único evento interno a su finalización. En [GUT95D] se muestran modelos no lineales, más flexibles para los sistemas de tiempo real; sin embargo, nosotros mantendremos el modelo lineal, ya que el análisis para esos modelos no lineales se puede descomponer en análisis de varios modelos lineales [GUT95D]. Un efecto que también debemos considerar a la hora de caracterizar la generación de eventos es el retraso en la activación de una tarea (release jitter). Entre el instante en que ocurre el evento y el instante en que el sistema se da por enterado de esa ocurrencia puede haber cierto desfase, especialmente si la sensorización del evento se realiza a requerimiento del procesador. También puede haber cierto error en la generación o en la anotación de ese instante debido a la imprecisión del reloj, especialmente en eventos temporizados. Al igual que antes, en técnicas off-line debemos garantizar un valor máximo para esa magnitud, que identificaremos como J. Sin embargo, tal como veremos posteriormente, existe otra fuente importante de retraso en sistemas cuyas tareas tengan relaciones de precedencia, esto es, sistemas en los que cada tarea se activa mediante un evento interno generado a la finalización de una tarea previa en la cadena de respuesta. En este caso, el instante en que se produce la activación de una tarea respecto de la llegada del evento externo puede retrasarse dependiendo de cuál sea el tiempo de respuesta de la tarea precedente. El cálculo del máximo retraso originado por ese motivo es bastante más complicado, y de hecho, es lo que dificulta el análisis para sistemas distribuidos con relaciones de precedencia, respecto al análisis realizado en sistemas en los que no existan restricciones de ese tipo. Esto hace que el término correspondiente a este retraso no lo consideraremos como parte de la especificación del sistema, sino como parte del cálculo de los tiempos de respuesta, tal como veremos en capítulos posteriores de esta tesis Sistemas multiprocesadores y distribuidos Red de comunicación Cuando la respuesta a un evento externo se ejecuta en varios procesadores debemos considerar los mecanismos mediante los que se coordina la ejecución de las diferentes tareas involucradas en esa respuesta. Normalmente este mecanismo es el de paso de mensajes: Universidad de Cantabria 1-7

26 Análisis de planificabilidad de sistemas distribuidos de tiempo real cuando una tarea finaliza su ejecución envía un mensaje que activa a la tarea siguiente en la cadena de respuesta. En general, un sistema distribuido está compuesto por múltiples recursos procesadores conectados entre sí por uno o varios recursos de comunicación (buses, redes locales, líneas serie, etc). En sistemas de tiempo real en los que hay que garantizar un plazo máximo de respuesta es preciso que la comunicación se realice de forma fiable y en un tiempo máximo acotado, por lo que la planificación de los mensajes a transmitir debe estar bien establecida. Aunque la mayoría de las redes de comunicación no se adaptan bien a las comunicaciones de tiempo real y no soportan una planificación de los mensajes basada en prioridades, sí existen algunas redes de comunicación estándares que se han utilizado para llevar a cabo comunicaciones de tiempo real estricto, tales como el token-bus [STR88], FDDI [AGR91], el bus CAN [TIN94E], etc. También se han desarrollado algunas redes de comunicación no estándares para hacer una planificación expulsora basada en prioridades. En [GUT95D] se implementan sistemas de comunicación de tiempo real mediante líneas serie (RS-232 y RS-485) multipunto y buses VME basados en la interfaz de colas de mensajes definidas en el estándar POSIX.1b [POS93]. Evidentemente, debemos incluir el impacto que tiene el envío de esos mensajes en la respuesta total del sistema. La cadena de respuesta a un evento se modela entonces como una sucesión de tareas y mensajes que se ejecutan o envían secuencialmente. El sistema de comunicaciones debe ser también predecible, asegurando un tiempo acotado en la transmisión de cada mensaje. Cada mensaje tendrá asociada, por tanto, una longitud máxima identificada también como l m. Adicionalmente supondremos que cada mensaje a transmitir se puede partir en paquetes de tamaño fijo, de forma que la comunicación entre dos tareas involucra la transmisión de un cierto número de paquetes. Este proceso de comunicación entre tareas se realiza en las siguientes etapas: Generación y encolado del mensaje. La tarea que envía el mensaje debe componer el mensaje a transmitir y, en caso necesario, partirlo en paquetes de tamaño fijo. 1-8 Grupo de Computadores y Tiempo Real

27 Sistemas distribuidos de tiempo real Además, cada paquete transmitido por la red necesitará información adicional para el encaminamiento del mensaje hasta el destino. Finalmente, cada paquete debe ser puesto en la cola de transmisión. Acceso al dispositivo de comunicación. Una vez encolado cada paquete, deberá esperar a que el dispositivo de comunicación quede libre y listo para realizar la transmisión del paquete. Transmisión del mensaje por el enlace físico. Desde el recurso procesador origen al recurso procesador donde esté alojada la tarea destino. El tiempo de transmisión de cada paquete vendrá determinado por su longitud y por la velocidad de transmisión del dispositivo. Recepción y composición del mensaje. Finalmente, y una vez que se hayan recibido todos los paquetes correspondientes deberá componerse el mensaje original y notificarse a la tarea destino. A la hora de analizar el sistema de tiempo real deberá considerarse el efecto de cada una de estas etapas en la respuesta completa. En muchos sistemas se pueden considerar los tiempos de generación y encolado del mensaje como parte de la ejecución de la tarea emisora, de forma que se deberán sumar estos dos tiempos al tiempo de ejecución de peor caso de la tarea origen. En otros sistemas, sin embargo, parte de las operaciones de generación y encolado las ejecuta alguna otra tarea, de prioridad generalmente más alta, de forma que habría que considerar esa tarea adicional en el análisis. De igual forma, el tiempo de recepción y composición del mensaje se añadirán al tiempo de ejecución de peor caso de la tarea destino o, en caso necesario, se considerará otra tarea, si realiza parte de esas operaciones. El impacto del acceso al dispositivo y de la propia transmisión del mensaje es más complejo, ya que debe tenerse en cuenta la influencia de otros mensajes que quieran transmitirse por el mismo medio de comunicación. La sección de esta tesis muestra en detalle el cálculo de ese impacto. Cuando se dispone de una red de comunicación apta para tiempo real, el acceso y la transmisión de un mensaje por una red de comunicación se puede analizar de una forma muy Universidad de Cantabria 1-9

28 Análisis de planificabilidad de sistemas distribuidos de tiempo real parecida a como se analiza el acceso y ejecución de una tarea en un procesador. Esto hace que, desde el punto de vista del análisis, no distingamos entre la ejecución de una tarea en un procesador o la transmisión de un mensaje por un dispositivo de comunicación. Por ese motivo, especificaremos cada mensaje mediante su longitud máxima l m o indistintamente, mediante su tiempo de transmisión de peor caso C m, calculado suponiendo que tuviera el uso exclusivo del dispositivo de comunicación. A efectos de uniformizar el modelo, nos referiremos a las tareas que se ejecutan en un procesador o a los mensajes transmitidos por una red de comunicación como acciones a realizar dentro del sistema de tiempo real. Asociaremos con un evento interno la generación de un mensaje, de forma que ese evento dispara la ejecución de una acción en el recurso correspondiente (transmisión del mensaje por el dispositivo de comunicación). De igual forma, asociaremos la recepción del mensaje con otro evento interno que dispara la ejecución de la tarea receptora del mensaje. El modelo de sistema gobernado por paso de mensajes consistirá por tanto en una secuencia de acciones (tareas en procesadores o mensajes en redes de comunicación) conectados entre sí (activados) mediante eventos internos y requiriendo cada una de ellas un tiempo de cómputo C, correspondiente al tiempo de ejecución de peor caso (o al tiempo de transmisión de peor caso, si la acción es un mensaje). Por extensión, se considera como acción periódica aquella que se activa por un patrón periódico de eventos externos y como acción esporádica aquella activada por un patrón esporádico de eventos. Cada acción a i se especifica, en resumen, mediante los parámetros: C i : tiempo de ejecución de peor caso si se trata de una tarea en un procesador o tiempo de transmisión de peor caso si es un mensaje en una red de comunicación. T i : periodo de activación (o tiempo mínimo entre llegadas) del evento externo cuya llegada originó la cadena de respuesta a la cual pertenece la acción. J i : retraso máximo en la activación de la acción Grupo de Computadores y Tiempo Real

29 1.3.2 Modelo general para transacciones de tiempo real Sistemas distribuidos de tiempo real Un modelo que nos será muy útil en el análisis de los sistemas distribuidos de tiempo real es el de transacciones de tiempo real [TIN94B]. Una transacción es una entidad que agrupa tareas activadas con igual periodo y que deben satisfacer ciertas restricciones en cuanto a sus instantes de activación. Cada transacción Γ i es activada por una secuencia periódica de eventos externos con periodo T i y se compone de un conjunto de m i tareas o mensajes. Cada ocurrencia del evento periódico externo originará una instancia (job) dela transacción asociada. Cada tarea 1 se puede activar a partir del momento en que haya transcurrido un intervalo de tiempo (llamado offset) desde la llegada del evento externo. La activación se produce desde ese instante con un retraso aleatorio, que puede estar comprendido entre 0yelretraso máximo, J i. τ i1 T i τ i2 R i1 R i2 Γ i Φ i1 Φi2 Figura 1-1. Transacción de tiempo real La Figura 1-1 muestra un ejemplo de transacción, donde el eje horizontal representa el tiempo, y donde suponemos que los retrasos máximos son nulos (J i =0). Las flechas descendentes representan la llegada de un evento externo asociado a la transacción mientras que las flechas ascendentes representan la activación de las tareas y los rectángulos sombreados la ejecución de las mismas. Nótese que en este modelo no hay relaciones de precedencia explícitas entre las tareas; cada tarea se activa en un instante igual a la llegada del evento externo más el offset, independientemente de que las tareas de su misma transacción y menor offset hayan finalizado o no. Identificaremos cada tarea mediante dos subíndices: el primero identifica la transacción a la que pertenece, y el segundo la posición que ocupa dentro del conjunto de tareas de su 1 A partir de aquí, siempre que hablemos de una tarea nos estaremos refiriendo a una tarea en un procesador o a un mensaje en una red de comunicación Universidad de Cantabria 1-11

30 Análisis de planificabilidad de sistemas distribuidos de tiempo real transacción, al ordenarlas en orden creciente de offset. De esta forma, con τ ij denotaremos la j-ésima tarea perteneciente a la transacción Γ i, con una fase de activación Φ ij y un tiempo de ejecución de peor caso C ij. Permitiremos además que cada tarea puede sufrir un retraso máximo denotado por J ij. Esto quiere decir que la activación de la tarea puede producirse en cualquier instante dentro del intervalo determinado por los instantes t 0 +Φ ij y t 0 +Φ ij +J ij, donde t 0 es el instante en que llegó el evento externo. Para cada tarea τ ij definiremos su tiempo de respuesta como la diferencia entre su tiempo de finalización y el instante en que ocurrió el evento externo asociado. El tiempo de respuesta de peor caso será R ij. Si la fase de activación Φ ij de cada tarea es fija, estaremos hablando de transacciones con offsets estáticos. Por el contrario, si la fase de una tarea puede variar en un intervalo Φ ij,min y Φ ij,max estaremos hablando de transacciones con offsets dinámicos. Tal como se verá en el capítulo 4 de esta tesis, la inclusión en el modelo de offsets dinámicos permite modelar y analizar sistemas de tiempo real con relaciones de precedencia, tales como los gobernados por paso de mensajes. En sistemas multiprocesadores y distribuidos es usual que el sistema pueda ser modelado mediante "transacciones" compuestas por varias tareas, al estilo del modelo computacional descrito anteriormente. Por ejemplo, en un sistema que siga la arquitectura cliente-servidor, una tarea cliente se activa por la llegada de un evento externo y requiere servicios de uno o varios servidores, quizás en diferentes procesadores. Esta tarea cliente puede modelarse mediante una transacción. Cada sección de código entre requerimientos de servicio se modela como una tarea de la transacción y cada porción de ejecución de un servidor en otro procesador se modela también como otra tarea de la misma transacción. Exactamente igual se modelan los mensajes transmitidos entre distintos procesadores. En este modelo, cada tarea τ ij se activa con la finalización de la tarea previa perteneciente a la misma transacción, τ ij-1. También podemos modelar mediante transacciones con offsets dinámicos, sistemas con tareas que se suspenden a sí mismas. Por ejemplo, una tarea puede ejecutar durante algún tiempo, y entonces suspender su ejecución para leer datos de un disco. Supongamos que la duración de la suspensión está comprendida entre S min y S max. Podríamos modelar entonces esa tarea como una transacción compuesta por dos tareas: tarea τ i1 correspondiente al código 1-12 Grupo de Computadores y Tiempo Real

31 Sistemas distribuidos de tiempo real anterior a la suspensión, y tarea τ i2 para el código posterior a la suspensión. El instante de activación para la segunda tarea depende del instante de finalización de la primera tarea más el tiempo que dure la suspensión. Consecuentemente, modelaremos las actividades que se desarrollan en un sistema distribuido como transacciones, considerada cada una de ellas compuesta por una cadena de acciones, al modo de las tareas en las transacciones originales. Cada acción de una transacción representa una tarea o una sección de una tarea ejecutando en un procesador, o un mensaje transmitido por un canal de comunicación, y se activa cuando se completa la ejecución de la acción previa en la transacción. Esto nos permite modelar la activación de una tarea por la llegada de un mensaje o la transmisión de un mensaje por la finalización de la ejecución de una sección de código 1.4. Planificación de sistemas de tiempo real Un aspecto fundamental a tratar en el desarrollo de sistemas de tiempo real es el de la compartición de recursos. Dado que la generación de diferentes eventos externos se produce de forma independiente, pueden existir en el sistema de control varias cadenas de respuesta ejecutándose simultáneamente. Esto quiere decir que simultáneamente varias tareas pueden necesitar hacer uso del mismo recurso. Si el recurso permite varios usuarios, tal como las memorias multipuerta, no hay ningún problema; sin embargo, la situación normal es que solamente una de las tareas pueda hacer uso del recurso. Un claro ejemplo de este tipo de recursos de uso exclusivo es el procesador. La planificación del sistema de tiempo real consiste en la definición de las reglas de uso de cada uno de los recursos disponibles. Un sistema de tiempo real se considera planificable si, en función de la política de planificación elegida, es capaz de satisfacer todos los requisitos temporales impuestos. Las políticas de planificación deben además considerar los siguientes aspectos: Universidad de Cantabria 1-13

32 Análisis de planificabilidad de sistemas distribuidos de tiempo real Ser predecible, con objeto de asegurar tiempos de ejecución finitos. Para ello, debe ser posible analizar los efectos de las interferencias que el propio planificador tendrá sobre el sistema. Tales efectos deberán ser mensurables. Ser capaz de gestionar el uso de diferentes recursos compartidos. Diferentes recursos pueden requerir diferentes políticas de planificación, incluso formando parte del mismo sistema de tiempo real. Debe garantizar el tratamiento de eventos tanto periódicos como no periódicos, incluso con patrones de llegada ilimitados. Garantizar también la ejecución de tareas sin requerimientos temporales, procurando además que los tiempos de respuesta sean reducidos. Alcanzar utilizaciones de recursos altas, sobre todo del procesador. Que sea sencillo de implementar en aplicaciones reales. Preferiblemente que esté disponible comercialmente. El único mecanismo fiable para determinar si la política o políticas de planificación elegidas aseguran el cumplimiento de los plazos consiste en la realización a priori de un test de planificabilidad, ya que la simulación no garantiza que se haya comprobado el comportamiento en cualquier situación [DIJ72] [XU93]. Un posible test de planificabilidad para sistemas de tiempo real consiste en el cálculo de los tiempos de respuesta de peor caso para cada una de las tareas que conforman el sistema. Si los tiempos de respuesta de peor caso de las tareas son siempre menores que los plazos de ejecución asociados a las mismas quiere decir que el sistema verificará en cualquier condición los requerimientos impuestos. Dicho test de planificabilidad debe ser cuanto menos suficiente, esto es, si el test dice que el sistema cumple los requerimientos temporales, entonces inexorablemente los cumple bajo cualquier situación. Un posible test de planificabilidad suficiente pasa por el cálculo de cotas superiores de los tiempos de respuesta de las tareas, mediante los cuales se puede garantizar el correcto funcionamiento del sistema. Un test suficiente puede ser pesimista, en el sentido de que puede considerar como no planificable un sistema que realmente si lo es, como 1-14 Grupo de Computadores y Tiempo Real

33 Sistemas distribuidos de tiempo real consecuencia de que los tiempos de respuesta de peor caso se hayan estimado por exceso. Hay tests de planificabilidad exactos para sistemas monoprocesadores; sin embargo, para sistemas multiprocesadores o distribuidos sólo existen tests exactos en ciertos casos, y a menudo resultan impracticables. Para los sistemas distribuidos gobernados por eventos no existen tests de planificabilidad exactos conocidos y todos los test aplicables a ellos son tests suficientes. Evidentemente, los recursos más importantes y sobre los que se centra la mayor parte del esfuerzo investigador son el procesador y la red de comunicación. Dado que ambos recursos se pueden considerar con un comportamiento similar (tal como hemos señalado en la sección 1.3.1), centraremos el estudio en el procesador, esto es: bajo qué condiciones el procesador es asignado a una tarea (o una red de comunicación a un mensaje) Planificación estática El mecanismo más sencillo es la planificación estática, también conocida como ejecutivo cíclico [BAK88]. Esta planificación, para tareas periódicas, se realiza en tiempo de compilación, esto es, una vez conocido el sistema y antes de su ejecución. A cada tarea del sistema se le asignan rodajas temporales durante las cuales puede ejecutar, según una tabla (plan estático) que indica los instantes en los que cada tarea debe ponerse en ejecución y cuando debe finalizar, de forma que se vayan garantizando los plazos de ejecución de todas las tareas. Esta tabla se va siguiendo cíclicamente durante la ejecución del sistema [LOC92] [BUR90]. El funcionamiento del planificador es muy sencillo, ya que sólo tiene que ir leyendo las entradas correspondientes en el plan de ejecución. Desde este punto de vista es además muy eficiente en tiempo de ejecución, ya que la carga que supone sobre la ejecución de las tareas es mínima. El principal inconveniente de este mecanismo es que el software debe partirse en secciones de código tales que puedan ser ejecutadas en una rodaja. Este proceso puede ser bastante costoso y de difícil mantenimiento y no siempre es posible [BUR90]. Universidad de Cantabria 1-15

34 Análisis de planificabilidad de sistemas distribuidos de tiempo real Otra desventaja es el hecho de que necesitamos elaborar el plan de ejecución, lo que supone construir una tabla en la que figuren todos los posibles estados de ejecución de las tareas. Esto significa que debe hacerse ese plan para un intervalo temporal igual al mínimo común múltiplo de los periodos de todas las tareas, lo cual puede dar como resultado una tabla de tamaño intratable. Esto se puede resolver reduciendo convenientemente los periodos de activación de las tareas, aunque tendría la desventaja de cargar el procesador más de lo que realmente necesita. Además, cualquier cambio en una tarea requiere tener que volver a construir nuevamente toda la tabla y, lo que es peor, a tener que partir las tareas de una forma diferente a como se hizo previamente. No se sigue el principio de independencia entre la estructura lógica del programa y su planificación Planificación dinámica por prioridades fijas Una posibilidad bastante más adecuada es la planificación en tiempo de ejecución o planificación dinámica. En ella, los posibles problemas de contención de recursos se resuelven en el instante en que aparecen, por lo que se elimina la necesidad de establecer un plan de ejecución previo. Evidentemente, esto hace más complejo el funcionamiento del planificador, aunque el sistema resulta más fácilmente mantenible y entendible, al no tener que hacer la partición del código y mantener, por tanto, la independencia entre la estructura lógica del programa y su planificación. En esta política de planificación se sigue el concepto de tarea como thread de ejecución. A cada tarea se le asigna una prioridad y, en función de ella, se resuelven los conflictos de utilización del procesador. Cuando hay varias tareas que quieren ejecutar, el planificador elige de entre todas ellas aquella con prioridad más alta y le asigna el uso del procesador. Si la prioridad de una tarea no cambia una vez asignada, hablaremos de prioridades fijas. Por contra, si la prioridad puede variar en tiempo de ejecución, en función del estado de operación del sistema, hablaremos de prioridades dinámicas. La asignación dinámica es más eficiente que la asignación estática, desde el punto de vista de que consigue mayor utilización de los recursos. Sin embargo, la implementación del planificador es mucho más 1-16 Grupo de Computadores y Tiempo Real

35 Sistemas distribuidos de tiempo real sencilla cuando se utiliza la asignación estática y es el que incorporan la mayoría de los planificadores comerciales existentes. Dentro de las políticas de planificación por prioridades se puede elegir 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 ésta ha finalizado. En cambio, en un planificador expulsor una tarea cede el uso del procesador (es expulsada) si se activa una tarea de prioridad superior 2. El planificador no expulsor es más sencillo de implementar, si bien puede producir un retraso significativo para las tareas de mayor prioridad, que es posible evitar con el planificador expulsor. Aunque recientemente ha resurgido el interés de algunos autores [AUD96] [BAT97] [BAT98] por los planificadores no expulsores, la elección más natural es la de un planificador expulsor y así, el análisis desarrollado en esta tesis se refiere a sistemas con planificadores de este tipo, al menos para el procesador. En todo caso, los efectos de no expulsión son fácilmente modelables en el análisis de una tarea, mediante un término de bloqueo correspondiente al mayor tiempo de ejecución de peor caso de las tareas que tengan asignadas menor prioridad que la tarea bajo análisis (ver sección 2.2.2). La asignación de prioridades a tareas de forma que se garantice la planificabilidad es todavía un tema abierto, en el que se han hecho muchas aportaciones significativas. La principal aportación vino dada por Liu y Layland [LIU73] y significó el principio de la teoría RMA (Rate Monotonic Analysis). En este artículo discuten ambos tipos de asignación: la asignación de prioridades estática en función de los periodos de las tareas (Rate Monotonic, RM, a menor periodo mayor prioridad) o la asignación dinámica en función del tiempo restante hasta los plazos de ejecución de las tareas (Earliest Deadline First, EDF, el plazo más cercano conlleva la mayor prioridad). Posteriormente el esquema de asignación estática fue mejorado por Leung y Whitehead [LEU82] para tareas con plazos menores al periodo. Esta asignación (Deadline Monotonic, DM) asigna mayor prioridad a la tarea que tiene menor plazo. Audsley desarrolló un algoritmo de asignación heurístico para el caso de plazos 2 Realmente una tarea sólo puede ser expulsada por otras tareas de mayor prioridad. Sin embargo, a efectos de análisis de peor caso consideraremos que sí se puede dar este efecto de expulsión entre diferentes tareas con igual prioridad. Universidad de Cantabria 1-17

36 Análisis de planificabilidad de sistemas distribuidos de tiempo real superiores al periodo [AUD91B] que obtiene una asignación de prioridades planificable, si acaso existe. Si bien estos esquemas son óptimos para sistemas con tareas periódicas en un sistema monoprocesador no lo son para sistemas con varios procesadores. Esto hace que se hayan desarrollado algunos algoritmos heurísticos para la asignación de prioridades de forma que ésta garantice los requerimientos temporales, como son el templado simulado [TIN92A] o el algoritmo HOPA [GUT95A], que obtiene generalmente mejores resultados, si la asignación de tareas a procesadores es conocida Planificación dinámica por prioridades dinámicas Estas políticas de planificación, al igual que las anteriores, se refieren a la asignación de prioridades para la utilización del procesador. Sin embargo, al contrario que en la asignación estática, la prioridad de cada tarea no permanece fija una vez establecida, sino que puede variar en tiempo de ejecución, dependiendo del estado de ejecución de las tareas que requieren el uso del procesador. El principal algoritmo de este tipo es el EDF (Earliest Deadline First) [LIU73], que asigna prioridades en función de los instantes en que se cumplen los plazos de las tareas. Se le asigna la mayor prioridad a la tarea que tiene el plazo más cercano al instante actual. Nótese que la asignación es en función del tiempo restante hasta que cumpla el plazo, que disminuye según el tiempo va transcurriendo. Otro algoritmo utilizado es el LLF (Least Laxity First) [AUD90], que asigna prioridades en función de las holguras, entendiendo como holgura la longitud del intervalo entre el instante actual hasta el instante en que se cumple el plazo, menos la cantidad de tiempo de cómputo pendiente de ejecución. Un algoritmo más eficiente es el de asignación al "Mejor Esfuerzo" (Best-Effort) [LOC85], que se basa en la asignación a priori de un valor fijo a cada tarea en función de su "utilidad". En tiempo de ejecución se asigna mayor prioridad, y por tanto de elige para ejecutar aquella tarea que tenga una relación menor valor_asignado/tiempo_ejecución_restante. Estos algoritmos son óptimos en sistemas monoprocesadores, pero dejan de serlo en multiprocesadores [AUD90] [RIP96]. Evidentemente, los planificadores por prioridades dinámicas son bastante más complicados de implementar y analizar que los basados en prioridades estáticas, aunque 1-18 Grupo de Computadores y Tiempo Real

SitemapChilling Adventures of Sabrina | Township | lone.wolf.and.cub.baby.cart.in.the.land.of.demons.1973.bluray.x264-usury.calorifix.srt