No description available.

Esta tesis afronta el problema de la planificación de sistemas de tiempo real utilizando sistemas multiprocesador con memoria compartida. Según laliteratura este problema es NP-Hard. En las aplicaciones de sistemas de tiempo real se imponen unos plazos temporales para la realización de las tareas. Así, lo importante es obtener los resultados a tiempo y no lo es tanto el obtener un rendimiento alto en promedio. La solución al problematradicionalmente ha consistido en repartir las tareas en tiempo de diseño y tratar a losprocesadores como monoprocesadores aislados. La solución alternativa, la planificación global del multiprocesador, tiene una teoría poco desarrollada. Los límites de utilización del sistema con garantías para losplazos son muy bajos, del orden del 50%, y la capacidad sobrante difícilmente se puede usar para dar servicio a las tareas aperiódicas. Así, el objetivoprincipal de la tesis es la planificación global con garantías de los plazos y con buen servicio a las tareas aperiódicas, llegando a usar el 100% de la capacidad de proceso. Primero se estudiaron cuatro posibilidades de distribución: estática o dinámica según las tareas, periódicas o aperiódicas. Para ello se trató el servicioa las tareas aperiódicas con dos métodos distintos: con servidores y sin servidores. En las distribuciones dinámicas, con el método de los servidoresse encontraron dificultades en su dimensionado y en las garantías de los plazos. Los métodos sin servidores probados fueron los planificadores Slack Stealing y Total Bandwidth. Ambos solo se pudieron adaptar para la planificación estática de las tareas periódicas. Las simulaciones mostraron que laplanificación local con Slack Stealing y un distribuidor de las tareas aperiódicas tipo Next-Fit proporcionan los mejores tiempos de respuesta medios para las tareas aperiódicas. Sin embargo, cuando las cargas son muy altas su tiempo de respuesta se dispara. Todos los métodos ensayados hasta elmomento quedaron desestimados para la planificación global. En segundo lugar se adaptó a la planificación global el algoritmo Dual Priority. Primero se analizaron sus características en monoprocesadores y se realizaron diversas mejoras. El algoritmo depende del cálculo off-line del peor tiempo de respuesta de las tareas periódicas y la fórmula paracalcularlos en monoprocesadores no es válida para multiprocesadores. Así, se analizaron tres métodos para su cálculo: un método analítico, unmétodo con simulación y un método con un algoritmo. El primero obtiene valores demasiado pesimistas; el segundo obtiene valores más ajustados pero en ocasiones son demasiado optimistas; el tercero es un método aproximado y obtiene valores tanto optimistas como pesimistas. Así, estemétodo no garantiza los plazos y no se puede usar en sistemas de tiempo real estrictos. En sistemas laxos, con una monitorización on-liney un ajuste dinámico de las promociones, el número de plazos incumplidos es muy bajo y el tiempo de repuesta de las tareas aperiódicas es excelente. Finalmente, se presenta una solución híbrida entre el repartimiento estático de las tareas periódicas y la planificación global. En tiempo de diseño, sereparten las tareas periódicas entre los procesadores y se calculan las promociones para la planificación local. En tiempo de ejecución las tareasperiódicas se pueden ejecutar en cualquier procesador hasta el instante de su promoción, instante en el que deben migrar a su procesador. Así segarantizan los plazos y se permite un cierto grado de balanceo dinámico de la carga. La flexibilidad conferida por las promociones de las tareas y el balanceo de la carga se utiliza para (i) admitir tareas periódicas que de otra forma no serian planificables, (ii) servir tareas aperiódicas y (iii) servirtareas aperiódicas con plazo o esporádicas. Para los tres casos se diseñaron y analizaron distintos métodos de distribución de las tareas periódicas en tiempo de diseño. También se diseño un método para reducir el número de migraciones. Las simulaciones mostraron que con este método se puedenconseguir cargas con solo tareas periódicas muy cercanas al 100%, lejos del 50% de la teoría de la planificación global. Las simulaciones con tareasaperiódicas mostraron que su tiempo de repuesta medio es muy bueno. Se diseño un test de aceptación de las tareas esporádicas, de forma que si una tarea es aceptada entonces su plazo queda garantizado. El porcentaje de aceptación obtenido en los experimentos fue superior al 80%.Finalmente, se diseñó un método de distribución de las tareas periódicas pre-rutime capaz de facilitar en tiempo de ejecución la aceptación de un alto porcentaje de tareas esporádicas y mantener un buen nivel de servicio medio para las tareas aperiódicas. / This thesis takes into consideration the problem of real-time systems scheduling using shared memory multiprocessor systems. According to the literature, this problem is NP-Hard. In real-time systems applications some time limits are imposed to tasks termination. Therefore, the really important thing is to get results on time and it is not so important to achieve high average performances. The solution to the problem traditionally has been to partition the tasks at design time and treat processors as isolated uniprocessors. The alternative solution, the global scheduling, has an undeveloped theory. The limit on the system utilization with deadlines guarantees is very low, around 50%, and spare capacity can hardly be used to service aperiodic tasks. Thus, the main goal of this thesis is to develop global scheduling techniques providing deadlines guarantees and achieving good service for aperiodic tasks, being able to use 100% of the processing capacity.First of all, we explored four possibilities of distribution: static or dynamic depending on the tasks, periodic or aperiodic. We tried to schedule aperiodic tasks with two different methods: with servers and without servers. In dynamic distributions, with the method of servers were found difficulties in its size and guarantees for deadlines. The methods without servers were The Slack Stealing and The Total Bandwidth. Both were adapted only for scheduling the static case. The simulations showed that the local scheduling with Slack Stealing and an allocation of aperiodic tasks kind Next-Fit provides the best mean average response time for the aperiodic tasks. However, when the load is very high response time increases. All methods tested so far were dismissed for the global scheduling.Secondly the Dual Priority algorithm was adapted to global scheduling. First we discussed its characteristics in uniprocessors and various improvements were made. The algorithm depends on the off-line calculation of the worst case response time for the task and the formula to compute them in uniprocessors is not valid for multiprocessors. We have analyzed three methods for its calculation: an analytical method, a simulation method and an algorithmic method. The former gets too pessimistic values, the second gets adjusted values but are sometimes too optimistic, and the third is a method that obtains approximate values. Thus, this method does not guarantee deadlines and may not be used in hard real-time systems. However, it is very suitable for soft real-time systems. In these systems, using an on-line monitoring and dynamic adjustment of promotions, the number of missed deadlines is very low and the response time of aperiodic tasks is excellent.Finally, we present a hybrid solution between static task allocation and global scheduling. At design time, is performed the distribution of periodic tasks among processors and their promotions are calculated for local scheduling. At runtime, the task can be run on any processor until the moment of its promotion, when it has to migrate to its processor. This will ensure deadlines and allowing a certain degree of dynamic load balancing. The flexibility provided by task promotions and load balancing is used (i) to admit task that would otherwise not be scheduled, (ii) to serve aperiodic tasks and (iii) to serve aperiodic tasks with deadlines or sporadic tasks. For the three cases were designed and analyzed various methods of task distribution at design time. We also designed a method to reduce the number of migrations. The simulations showed that this method can achieve with only periodic task loads very close to 100%, far from the 50% of the global scheduling theory. The simulations showed that aperiodic tasks average response time is very good. We designed an acceptance test for sporadic tasks, hence, if a task is accepted then its deadline is guaranteed. The acceptance rate obtained in the experiments was over 80%. Finally, we devised a pre-rutime distribution method of periodic tasks that is able to provide at run time a high acceptance ratio for sporadic tasks and maintain a good level of service for aperiodic tasks

La evolución de los procesadores siempre ha consistido en ir aumentando el rendimiento de estos, fijando como medida de este aumento de rendimiento la velocidad de proceso en la ejecución de las distintas aplicaciones. Sin embargo esta mayor velocidad implica también un mayor consumo energético. En la era de la informática móvil, un mayor consumo energético comporta el uso de mayores baterías y una disminución del tiempo útil de trabajo de estas. A su vez, el usuario común de esta informática móvil, puede que no necesita una mayor velocidad de proceso, puesto que la limitación de velocidad de las aplicaciones más comunes que usará, aplicaciones multimedia, procesadores de texto, viene impuesta por cualidades físicas (velocidad de mecanografía, frecuencia de visualización en pantalla, frecuencia de emisión del sonido,..). En estos casos, por más rápido que sea el procesador, la aplicación no puede ejecutarse a mayor velocidad, resultando en un mayor consumo energético pero sin la obtención de mejores resultados. En los sistemas de tiempo real, estas restricciones en la velocidad del procesador también vienen impuestas por las características físicas del medio, por ejemplo, la frecuencia de muestreo de un sensor de temperatura, debe ser la necesaria, de nada sirve que se tomen medidas al doble de su frecuencia, puesto que la temperatura no cambiará tan rápidamente. Para evitar el problema de sobredimensionado de la velocidad del procesador que requiere a su vez, de un mayor consumo energético, en la última década, el estudio del rendimiento de los procesadores (velocidad del procesador) se ha unido al estudio del consumo energético y de la disipación del calor. De manera que ya no puede haber evolución únicamente a nivel de velocidad del procesador sin tener en cuenta el consumo de este y la disipación de energía. En el campo de la reducción energética se ha observado que la técnica de DVS (reducción dinámica de la velocidad del procesador junto con la reducción del voltaje suministrado) permite al algoritmo de planificación de las tareas ahorrar energía. Si observamos atentamente los algoritmos de planificación que se han usado en los entornos de tiempo real, observaremos la siguiente evolución temporal:· Algoritmos de planificación cíclicos.· Algoritmos de planificación en-línea para conjuntos de tareas periódicas independientes.· Algoritmos de planificación en-línea para conjuntos de tareas periódicas independientes y para tareas aperiódicas y/o esporádicas· Algoritmos de planificación en-línea para conjuntos de tareas no independientes entre si, es decir tareas con recursos compartidos y/o precedencias entre tareas.· Algoritmos de planificación para arquitecturas multiprocesadores.Una evolución parecida se ha producido en el estudio de los planificadores con ahorro energético, iniciando el estudio con la planificación estática y finalizando con los algoritmos de planificación dinámica, que ofrecen mayor flexibilidad a los programadores de las aplicaciones.En la tesis, se sigue esta misma evolución, estudiando y proponiendo un algoritmo de planificación con ahorro energético para un sistema monoprocesador con tareas independientes. Suponiendo, inicialmente, correctos todos los parámetros de diseño del sistema (algoritmo PLMDP) para finalmente aplicar de manera automática una corrección a un posible sobredimensionado del WCET (algoritmo EPLDP). Estudiando las diferencias de ahorro energético que se obtienen con estos dos algoritmos, se ha constatado que a nivel energético es siempre favorable ejecutar a una velocidad de proceso intermedia en lugar de ejecutar a velocidades extremas (primero a muy poca velocidad, para después tener que ejecutar a velocidades más altas).A continuación, añadimos a los planificadores anteriores la posibilidad de que las tareas puedan acceder a recursos compartidos entre estas. Implementando en los planificadores el protocolo de techo de prioridad. A pesar del uso de este protocolo, se puede observar que nuestros algoritmos continúan aportando ahorro energético, garantizando la planificabilidad de las tareas.Para finalizar con los cambios en los planificadores, se ha añadido a todos los planificadores implementados, la posibilidad de tener precedencias entre las tareas y plazos globales entre una cadena de precedencias. En este punto se ha visto que la dificultad principal del algoritmo de planificación es el hecho de no saber con exactitud el instante de llegada de estas tareas, disminuyendo de esta manera la utilización del procesador que se puede planificar de una manera garantizada. A pesar de todo, observamos que los algoritmos de planificación PLMDP y EPLDP tienen un buen comportamiento en términos de planificación de tareas.Para completar el estudio de la planificación, se ha realizado el estudio del tiempo de respuesta de las tareas aperiódicas junto al estudio del ahorro energético. En principio ambos conceptos están enfrentados, puesto que para obtener un tiempo de respuesta menor, debemos ejecutar la tarea a máxima velocidad, asegurando que en el procesador esté disponible a la llegada de las tareas. Y por el contrario, para tener ahorro energético debemos ejecutar a una velocidad reducida la mayor parte del tiempo.Realizando un análisis global, se ha visto que los planificadores PLMDP y EPLDP, obtienen un buen rendimiento, siendo de fácil implementación y requiriendo al mismo tiempo poca cantidad de memoria para su funcionamiento. Sin embargo, todos los resultados obtenidos se han realizado bajo simulaciones con conjuntos de tareas reales y conjuntos de tareas sintéticos.Las técnicas DVS y las modificaciones que se han realizado en los algoritmos de planificación para ahorro energético, son fácilmente aplicables a otros algoritmos de planificación, en concreto se podrían aplicar sin demasiada complicación a sistemas multiprocesadores con una planificación global de las tareas. Los resultados obtenidos con el algoritmo EPLDP demuestran que en las aplicaciones de tiempo real es energéticamente económico ejecutar a una velocidad media el máximo tiempo posible en lugar de ejecutar a mayor velocidad para después tener el procesador parado. Este resultado, junto con los resultados que reducen la corriente de fuga a base de agrupar los espacios libres del procesador, es fácilmente aplicable a los algoritmos de planificación, en los que las tareas pueden ejecutarse en cualquier procesador. De manera que las tareas se deben ejecutar a una velocidad lo más uniformemente posible para tener al procesador ocupado el máximo tiempo posible.