Resumen de Planificación global en sistemas multiprocesador de tiempo real
Josep María Banús Alsina
Esta tesis afronta el problema de la planificación de sistemas de tiempo real utilizando sistemas multiprocesador con memoria compartida, Según la literatura 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 problema tradicionalmente ha consistido en repartir las tareas en tiempo de diseño y tratar a los procesadores 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 los plazos 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 objetivo principal 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. Para ello se trató el servicio a 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 servidores se encontraron dificultades en su dimensionado y en las garantías de los plazos. Los métodos sin servidores probados fueron los planificadotes Slack Stealing y Total Brandwidth. Ambos solo se pudieron adaptar para la planificación estática de las tareas periódicas. Las simulaciones mostraron que la planificació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 on muy altas su tiempo de respuesta se dispara. Todos los métodos ensayados hasta el momento 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 para calcularlos en monoprocesadores no es válida para multiprocesadores. Así, se analizaron tres métodos para su cálculo: un método analítico, un mé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í, este mé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 respuesta 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, se reparten las tareas periódicas entre los procesadores y se calculan las promociones para la planificación local. En tiempo de ejecución las tareas periódicas se pueden ejecutar en cualquier procesador hasta el instante de su promoción, instante en el que deben migrar a su procesador. Así se garantizan 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) servir tareas aperiódicas con plazo o esporádicas.
