Recientemente las arquitecturas multiprocesador se han ido popularizando, pues el uso de un sólo procesador no es suficiente para cubrir las demandas computacionales de las aplicaciones modernas. Además, con los límites actuales del hardware, es más fácil y barato incrementar la capacidad de cálculo con un multiprocesador que realizarlo con sistemas uniprocesadores de equivalente capacidad. En los sistemas multiprocesador de tiempo real, es crucial verificar el cumplimiento de los plazos de las tareas, y de esto se ocupa la planificación. La planificación uniprocesador ha sido ampliamente estudiada, pero existen muchos problemas abiertos en la planificación multiprocesador, la cual ha sido abordada principalmente con algoritmos aproximados eficientes.
En este trabajo de tesis, se trató el problema de planificar fuera de línea un conjunto de tareas periódicas sin restricciones de dependencia y que no comparten recursos en m procesadores homogéneos usando el algoritmo de planificación EDF (Earliest Deadline First) y bajo un esquema particionado. El problema de asignar las tareas a los procesadores se modelo como un problema de programación lineal entera binaria, y luego se resolvió aplicando la versión del algoritmo de Balas dada por Geoffrion, optimizada para el problema de la planificación de tiempo real usando conocimiento previo del problema. Se evaluó, con resultados experimentales, la factibilidad de la aplicación de este algoritmo exacto de optimización entera para hallar la solución óptima al problema de la planificación multiprocesador, para varios sistemas de tareas en sistemas multiprocesador de tamaño típico. Para algunos de los experimentos, se mostró que es perfectamente posible utilizar este algoritmo fuera de línea para hallar la planificación óptima. Además, a partir de los experimentos realizados es posible hacer conjeturas acerca de las cotas de utilización para la planificabilidad de un conjunto de tareas que cumpla con los requisitos del modelo de tareas propuesto, bajo EDF usando esquema particionado en un sistema multiprocesador.
Abstract
Recently, multiprocessor systems have become popular, since the use of only one processor is not sufficient to satisfy the computational demands of modern applications. Besides, with the actual hardware limitations, it is easier and cheaper to increase the computational capacity with a multiprocessor than to make it with uniprocessors systems of equivalent capacity. In real time multiprocessor systems, it is crucial to verify the fulfillment of the task deadlines, and this is what scheduling is all about. Uniprocessor scheduling has been widely studied, but there are still open problems in multiprocessor scheduling, which has been faced mainly with efficient approximate algorithms. In this work, we dealt with the off-line scheduling of a set of periodic tasks with no dependence relations that do not share any resources, using EDF (Earliest Deadline First) scheduling algorithm under a partitioned scheme. The allocation problem was modeled as a binary integer linear programming problem, and it was solved by applying Geoffrion's version of Balas algorithm, optimized for the real-time scheduling problem, by using previous knowledge of the problem. The feasibility of applying this integer optimization exact algorithm to find the optimal solution to the multiprocessor scheduling problem, was evaluated, with experimental results, for several task systems in multiprocessor systems of typical size. For some experiments, it was shown that it is perfectly possible to use this algorithm off-line to find the optimal scheduling. In addition, from the experiments that were made, it is possible to make conjectures about the worst case utilization bounds for the schedulability in a multiprocessor system under EDF using the partitioned scheme, for any task set that fulfills the requirements of the proposed task model
