Algoritmo de planificación para la fecha de finalización más cercana

El algoritmo de programación de fecha de vencimiento más cercana ( EDF ) es un algoritmo de programación dinámico. Se utiliza en sistemas operativos en tiempo real para colocar procesos en una cola de prioridad . Cuando ocurre un evento de programación (se completa una tarea, aparece una nueva tarea, etc.), se busca en la cola el proceso más cercano a su fecha límite. Este proceso se programará para ejecutarse a continuación.

La programación de finalización más cercana es óptima para los sistemas preventivos de un solo procesador en el siguiente sentido: si es posible garantizar que se puede garantizar un conjunto de tareas independientes, cada una caracterizada por una hora de llegada, un requisito de finalización y una fecha límite de finalización, para la fecha límite. para completar, entonces el algoritmo EDF también podrá hacer esto.

Al programar procesos periódicos que tienen plazos iguales a sus períodos, el algoritmo de programación más cercano a la finalización utiliza la carga completa. Por lo tanto, la prueba de programación para este algoritmo será [1] :

donde  es el tiempo de ejecución del peor de los casos para los procesos y  es el período correspondiente entre sus fechas de llegada (asumiendo que es igual a los plazos respectivos).

Es decir, la asignación por la fecha de finalización más cercana garantiza que se cumplan todos los plazos, siempre que el uso total de la CPU no supere el 100 %. En comparación con el uso de prioridades fijas, la programación para la fecha de finalización más cercana garantiza que se cumplan todos los plazos cuando la carga de trabajo es mayor.

Sin embargo, si el sistema está sobrecargado, entonces el conjunto de procesos para los que se perderá la fecha límite será muy impredecible (dependerá del momento exacto y el momento de la sobrecarga). Este es un inconveniente notable para los diseñadores de sistemas en tiempo real. . Además, el algoritmo es difícil de implementar en hardware y existen dificultades para representar los plazos en diferentes rangos (los plazos no se pueden asignar con mayor precisión que los ciclos de reloj utilizados para la programación). Si se utiliza aritmética modular para calcular plazos futuros , los campos que almacenan plazos futuros deben contener al menos el valor "el doble de la duración del tiempo de ejecución esperado más largo" + "ahora". Por lo tanto, la programación para la fecha de finalización más cercana no es común en los sistemas informáticos industriales en tiempo real.

En cambio, la mayoría de los sistemas informáticos en tiempo real utilizan una programación de prioridad fija. Con una prioridad fija, es más fácil asegurarse de que, cuando se sobrecargan, los procesos de baja prioridad no cumplirán con los plazos, mientras que los procesos de alta prioridad aún se completarán a tiempo.

Se han realizado muchas investigaciones sobre la planificación de la finalización a corto plazo ; es posible calcular el tiempo de respuesta de los procesos en el peor de los casos con este algoritmo, trabajar con otros tipos de procesos que no sean procesos por lotes y utilizar servidores para la gestión de la congestión.

Véase también

• SCHED DEADLINE  : implementación del programador de tareas para el tiempo de finalización más cercano en el kernel de Linux

Notas

1. ↑ Jia Xu, David Parnás. Procesos de programación con tiempos de publicación, plazos, precedencia y relaciones de exclusión. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 16 NÚM. 3 de marzo de 1990

Literatura

• Pierre G. Jansen, Sape J. Mullender, Paul JM Havea, Hans Scholten. Programación ligera de EDF con herencia de fecha límite
• Stankovic, JA Programación de plazos para sistemas en tiempo real: Edf y algoritmos relacionados. - Springer EE. UU., 1998. - 273 p. — ISBN 9780792382690 .
• Leung, JYT Manual de programación: algoritmos, modelos y análisis de rendimiento. - Prensa CRC, 2004. - 1224 p. — ISBN 9780203489802 .