Asignación y diagramabilidad de sistemas distribuidos de tiempo real duro

Abstract

Los sistemas de computación de tiempo real son componentes críticos de la infraestructura tecnológica de cualquier país industrializado. Son de aplicación imprescindible en robótica, aviónica, manufactura automatizada, sistemas de control, etc. Constituyen, como consecuencia, una de las áreas de más rápido crecimiento dentro de la disciplina. Existen diferen-tes componentes (sistemas operativos, lenguajes de progra-mación, arquitecturas) que caracterizan a dichos sistemas. Pero la diagramabilidad, entendida como el cumplimiento de to-das las restricciones temporales del sistema y la asignación de un conjunto de tareas a un conjunto de procesadores cum-pliendo cada una de ellas con las restricciones de recursos, de asignación, de comunicaciones y de precedencia aparece en-tre las más importantes. Cada día más y mejores sistemas de tiempo real, dependen de sistemas basados en multiprocesa-dores. Desdichadamente se conoce poco acerca de la asigna-ción y la diagramación basada en múltiples procesadores. Esto se debe por un lado a que la complejidad de los resultados muestra que la mayoría de estos sistemas son NP-duros y por otro a que la experiencia adquirida en el manejo de estos sis-temas no es mucha. Como consecuencia hay un número redu-cido de heurísticas que emergen como una de las pocas herra-mientas disponibles para resolver el problema. Este consiste en asignar un conjunto de tareas de tiempo real duro, apropia-bles, sobre un conjunto de procesadores heterogéneos, cum-pliendo restricciones de tiempo, ubicación, memoria, comunica-ciones y precedencia. Esta tesis tiene como base trabajos pu-blicados en revistas y actas de congresos de arbitraje riguro-so. El primero de ellos es publicado en el Real Time Systems Journal y se denomina A Heuristic Approach to the Multitask-Multiprocessor Assignment Problem Using The Empty-Slots method and Rate Monotonic Scheduling, el cual usando como premisa esencial todas la restricciones antes enumeradas,des-cribe y compara con otros métodos la heurística de asignación implementada. En esta heurística fue utilizado por razones de velocidad y de mantenimiento en memoria de información útil, el cálculo de las ranuras libres disponibles en un determinado intervalo de tiempo. Estos resultados fueron publicados en el Journal Información Tecnológica bajo el titulo de Sincroniza-ción de tareas en Tiempo Real Duro utilizando el método de las Ranuras Vacías. Sobre la base de estos resultados prelimi-nares obtenidos, se refinaron los métodos heurísticos incorpo-rando parámetros sintonizables que guían el proceso de asig-nación para obtener distintos tipos de soluciones (e.g. con red de comunicación interprocesadores más descargada). El diseño de parámetros que relacionen las restricciones de comunicaciones, tiempo y recursos que vayan sintonizándose durante el proceso heurístico de asignación permiten obtener soluciones orientadas. En el método sintonizado las asignacio-nes de tareas a procesadores se hacen desde una pila de ta-reas a una pila de procesadores, cada una ordenada de acuer-do a un cierto criterio. En lugar de usar criterios únicos, se pueden constituir varias pilas de acuerdo a distintos criterios. A partir de las mismas se forman polinomios cuyos coeficien-tes son los parámetros diseñados y cuyas variables son los ordinales asociados a la posición en cada una de las pilas. El valor de esos polinomios permite construir pilas de tareas y de procesadores, con criterios combinados que posibilitan optimi-zar el proceso de asignación. Está mejora a la heurística base fue publicada en Proc 8th IEEE Euromicro Workshop on Real Time Systems: Tuning Parameters to improve a Heuristic Method, More and Better Solutions to an NP-Hard Real Time Problem. Principalmente se confrontan los resultados obteni-dos con los alcanzados por autores que utilizan Recocido Si-mulado (Simulated Annealing) o bien otro tipo de heurísticas para obtener una solución subóptima al problema de asigna-ción. Como soporte a los algoritmos se diseñó y construyó un generador aleatorio de problemas. El mismo permitió probar y comparar los métodos desarrollados. El generador produce aleatoriamente grafos acíclicos, orientados y con propiedad de clausura transitiva, que representan subconjuntos de tareas con relaciones de precedencia. Obtenido un grafo base, es posible generar aleatoriamente (dentro de cotas preestable-cidas) períodos, tiempos de ejecución, requerimientos de re-cursos y longitud de mensajes intercambiados entre las distin-tas tareas que componen el grafo. La instanciación de diver-sos grafos, cada uno de los cuales se usa como base para la generación de problemas con distintos períodos, factores de utilización, memoria, etc., conduce al planteo de problemas en el orden de miles para poder validar conclusiones estadísticas experimentales. Con los datos obtenidos experimentalmente se construyeron curvas que caracterizan la relación de éxito obtenida por cada método para la resolución del problema ata-cado, utilizando al efecto los problemas generados mediante el dispositivo mencionado anteriormente. La comparación con otros métodos se ve dificultada por el hecho de que no hay una norma de ensayo y cada autor elige la especificación del problema al cual aplica su método. Sin embargo pequeñas va-riaciones en la especificación pueden producir grandes varia-ciones en el resultado. Debe hacerse notar que el grupo de investigación en STR nucleado en el laboratorio de Sistemas Digitales de la Universidad Nacional del Sur, es relativamente reducido y de mucha interacción entre sus integrantes. Debi-do a esto último, los trabajos tienen, la mayoría de las veces, varios autores. Como regla, sin embargo, cada trabajo puede ser usado como apoyo de sólo una tesis y corresponde a algu-no de los dos primeros autores. La tesis esta presentada de la siguiente forma: un capítulo inicial en el que se realiza una introducción a los sistemas distribuidos de tiempo real, plan-teando el problema de asignación de un conjunto de tareas a procesadores distribuidos en un entorno de tiempo real duro y las técnicas de solución mas comúnmente usadas. En el se-gundo capítulo se describe el modelo utilizado y las restriccio-nes a satisfacer para obtener una asignación. En el tercero se describe las heurísticas desarrolladas y el generador de proble-mas utilizado para los ensayos, comparando los algoritmos implementados, con otros existentes (eg: Recocido Simulado) a partir de lo cual se extraen conclusiones.