La fecha límite más temprana se programará primero.

El algoritmo de planificación de prioridad dinámica ( EDF , por sus siglas en inglés ) es un algoritmo que se utiliza en sistemas operativos en tiempo real para colocar procesos en una cola de prioridad . Cada vez que ocurre un evento de planificación (una tarea finaliza, se libera una nueva tarea, etc.), se busca en la cola el proceso más próximo a su fecha límite. Este proceso es el siguiente en ser programado para su ejecución.

EDF es un algoritmo de planificación óptimo para uniprocesadores con desalojo, en el siguiente sentido: si un conjunto de trabajos independientes , cada uno caracterizado por un tiempo de llegada, un requisito de ejecución y una fecha límite, puede planificarse (mediante cualquier algoritmo) de manera que garantice que todos los trabajos se completen antes de su fecha límite, EDF planificará este conjunto de trabajos de forma que todos se completen antes de su fecha límite.

Al programar procesos periódicos con plazos de entrega iguales a sus períodos, EDF tiene un límite de utilización del 100%. Por lo tanto, la prueba de programabilidad ^{[ 1 ] [ 2 ]} para EDF es:

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq 1,}$

donde el${\displaystyle \left\{C_{i}\right\}}$son los tiempos de cálculo del peor caso de la${\displaystyle n}$los procesos y el${\displaystyle \left\{T_{i}\right\}}$son sus respectivos períodos entre llegadas (se supone que son iguales a los plazos relativos). ^{[ 3 ]}

Es decir, EDF puede garantizar que se cumplan todos los plazos siempre que la utilización total de la CPU no supere el 100 %. En comparación con las técnicas de planificación de prioridad fija, como la planificación de tasa monótona , EDF puede garantizar el cumplimiento de todos los plazos en el sistema incluso con cargas más elevadas.

Tenga en cuenta que use la fórmula de prueba de programabilidad con fecha límite como período. Cuando la fecha límite es menor que el período, las cosas son diferentes. Aquí hay un ejemplo: Las cuatro tareas periódicas necesitan programación, donde cada tarea se representa como TaskNo(tiempo de cálculo, fecha límite relativa, período). Son T0(5,13,20), T1(3,7,11), T2(4,6,10) y T3(1,1,20). Este grupo de tareas cumple que la utilización no es mayor que 1.0, donde la utilización se calcula como 5/20+3/11+4/10+1/20 = 0.97 (dos dígitos redondeados), pero aún no es programable, consulte la figura de EDF Scheduling Failure para obtener más detalles.

EDF también es un algoritmo de planificación óptimo en uniprocesadores no preemptivos, pero solo dentro de la clase de algoritmos de planificación que no permiten tiempo de inactividad insertado. Al planificar procesos periódicos que tienen plazos de entrega iguales a sus períodos, una prueba de planificabilidad suficiente (pero no necesaria) para EDF se convierte en: ^{[ 4 ]}

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq {1-p},}$

Donde p representa la penalización por no preferencia, dada por max${\displaystyle \left\{C_{i}\right\}}$/ min${\displaystyle \left\{T_{i}\right\}}$Si este factor se puede mantener pequeño, EDF no preemptivo puede ser beneficioso ya que tiene una baja sobrecarga de implementación.

Sin embargo, cuando el sistema se sobrecarga, el conjunto de procesos que no cumplirán con los plazos es en gran medida impredecible (dependerá de los plazos exactos y del momento en que se produzca la sobrecarga). Esto representa una desventaja considerable para un diseñador de sistemas en tiempo real. El algoritmo también es difícil de implementar en hardware y existe un problema complejo al representar los plazos en diferentes rangos (los plazos no pueden ser más precisos que la granularidad del reloj utilizado para la planificación). Si se utiliza una aritmética modular para calcular plazos futuros en relación con el presente, el campo que almacena un plazo futuro relativo debe contener al menos el valor de (("duración" {del tiempo esperado más largo para la finalización} * 2) + "ahora"). Por lo tanto, EDF no se encuentra comúnmente en sistemas informáticos industriales en tiempo real.

En cambio, la mayoría de los sistemas informáticos en tiempo real utilizan una planificación de prioridad fija (generalmente una planificación de tasa monótona ). Con prioridades fijas, es fácil predecir que las condiciones de sobrecarga provocarán que los procesos de baja prioridad no cumplan con los plazos, mientras que el proceso de mayor prioridad sí lo hará.

Existe un importante conjunto de investigaciones sobre la planificación de EDF en la computación en tiempo real ; es posible calcular los tiempos de respuesta en el peor de los casos de los procesos en EDF, tratar con otros tipos de procesos además de los periódicos y utilizar servidores para regular las sobrecargas.

Consideremos 3 procesos periódicos programados en un uniprocesador con desalojo. Los tiempos y periodos de ejecución se muestran en la siguiente tabla:

En este ejemplo, las unidades de tiempo pueden considerarse segmentos de tiempo programables . Los plazos son que cada proceso periódico debe completarse dentro de su período.

Diagrama de tiempos

En el diagrama de tiempos, las columnas representan intervalos de tiempo que aumentan hacia la derecha, y todos los procesos comienzan sus períodos en el intervalo de tiempo 0. El sombreado azul y blanco alterno del diagrama indica los períodos de cada proceso, con fechas límite en los cambios de color.

El primer proceso programado por EDF es P2, ya que su duración es la más corta y, por lo tanto, tiene la fecha límite más temprana. Asimismo, cuando P2 finaliza, se programa P1, seguido de P3.

En el intervalo de tiempo 5, tanto P2 como P3 tienen la misma fecha límite, y deben completarse antes del intervalo de tiempo 10, por lo que EDF puede programar cualquiera de los dos.

En la planificación de EDF pueden producirse intercambios de plazos indeseables. Un proceso puede utilizar un recurso compartido dentro de una sección crítica para evitar que se cancele de forma preventiva en favor de otro proceso con un plazo anterior. En ese caso, es importante que el planificador asigne al proceso en ejecución el plazo más temprano entre los demás procesos que esperan el recurso. De lo contrario, los procesos con plazos anteriores podrían perderlos.

Esto es especialmente importante si el proceso que ejecuta la sección crítica tiene un tiempo mucho mayor para completarse y salir de dicha sección, lo que retrasará la liberación del recurso compartido. Sin embargo, el proceso aún podría ser interrumpido en favor de otros que tengan plazos de entrega más cortos pero que no compartan el recurso crítico. Este riesgo de intercambio de plazos es análogo a la inversión de prioridad cuando se utiliza la planificación con prioridad fija y con interrupción .

Para agilizar la búsqueda de plazos en la cola de procesos listos, las entradas se ordenan según sus fechas límite. Cuando a un proceso nuevo o periódico se le asigna un nuevo plazo, se inserta antes del primer proceso con un plazo posterior. De esta forma, los procesos con los plazos más próximos siempre se encuentran al principio de la cola.

En un análisis de tráfico intenso del comportamiento de una cola de un solo servidor bajo una política de planificación de plazo más temprano con incumplimiento de plazos, ^{[ 5 ]} los procesos tienen plazos y se atienden solo hasta que vencen dichos plazos. La fracción de "trabajo incumplido", definida como el trabajo residual no atendido debido a plazos vencidos, es una medida de rendimiento importante.

Se acepta comúnmente que una implementación de planificación preventiva de prioridad fija (FPS) es más simple que un planificador de prioridad dinámica, como el EDF. Sin embargo, al comparar el uso máximo de una planificación óptima bajo prioridad fija (con la prioridad de cada hilo dada por la planificación de tasa monótona ), el EDF puede alcanzar el 100%, mientras que el valor máximo teórico para la planificación de tasa monótona es de alrededor del 69%. Además, la sobrecarga en el peor de los casos de una implementación de EDF (totalmente preventiva o limitada/no preventiva) para tareas periódicas y/o esporádicas puede hacerse proporcional al logaritmo de la representación de tiempo más grande requerida por un sistema dado (para codificar plazos y períodos) utilizando árboles de búsqueda digital. ^{[ 6 ]} En casos prácticos, como sistemas embebidos que utilizan una representación fija de tiempo de 32 bits, las decisiones de planificación pueden tomarse utilizando esta implementación en un tiempo fijo constante pequeño que es independiente del número de tareas del sistema. En tales situaciones, los experimentos han encontrado poca diferencia discernible en la sobrecarga entre EDF y FPS, incluso para conjuntos de tareas de cardinalidad (comparativamente) grande. ^{[ 6 ]}

Cabe señalar que EDF no hace ninguna suposición específica sobre la periodicidad de las tareas; por lo tanto, puede utilizarse para programar tareas periódicas y aperiódicas. ^{[ 3 ]}

Aunque las implementaciones de EDF no son comunes en los kernels comerciales en tiempo real, aquí hay algunos enlaces a kernels de código abierto y en tiempo real que implementan EDF:

• SHARK : ^{[ 14 ]} El RTOS SHARK, que implementa varias versiones de algoritmos de planificación de EDF y de reserva de recursos.
• ERIKA Enterprise : ^{[ 15 ]} ERIKA Enterprise, que proporciona una implementación de EDF optimizada para microcontroladores pequeños con una API similar a la API de OSEK .
• El núcleo Everyman : ^{[ 16 ]} El núcleo Everyman implementa la planificación EDF o Deadline Monotonic dependiendo de la configuración del usuario.
• MaRTE OS : ^{[ 17 ]} MaRTE OS actúa como un entorno de ejecución para aplicaciones Ada e implementa una amplia gama de algoritmos de planificación, incluido EDF.
• El proyecto AQuoSA constituye una modificación del núcleo de Linux que enriquece el planificador de procesos con capacidades de planificación EDF. La temporización de la planificación no puede ser tan precisa como en el caso de los sistemas operativos de tiempo real estricto mencionados anteriormente, pero es suficientemente precisa como para mejorar considerablemente la previsibilidad y, por lo tanto, cumplir con los requisitos de tiempo real de las aplicaciones multimedia. AQuoSA es uno de los pocos proyectos que proporciona capacidades de planificación en tiempo real a usuarios no privilegiados en un sistema de forma controlada, mediante un modelo de control de acceso diseñado adecuadamente. ^{[ 18 ]}
• El kernel de Linux tiene una implementación de fecha límite más temprana llamada SCHED DEADLINEque está disponible desde la versión 3.14.
• El planificador en tiempo real ^{[ 19 ]} desarrollado en el contexto del proyecto europeo IRMOS ^{[ 20 ]} es un planificador en tiempo real multiprocesador para el kernel de Linux, particularmente adecuado para el aislamiento temporal y el aprovisionamiento de garantías de QoS a componentes de software complejos multihilo y también a máquinas virtuales completas . Por ejemplo, cuando se utiliza Linux como sistema operativo anfitrión y KVM como hipervisor, IRMOS puede utilizarse para proporcionar garantías de planificación a máquinas virtuales individuales y, al mismo tiempo, aislar su rendimiento para evitar interferencias temporales no deseadas. IRMOS cuenta con un planificador jerárquico combinado EDF/FP . En el nivel externo hay un planificador EDF particionado en las CPU disponibles. Sin embargo, las reservas son multi-CPU, y se utiliza FP global sobre multiprocesadores en el nivel interno para planificar los hilos (y/o procesos) asociados a cada reserva EDF externa. ^{[ 21 ]}
• Xen lleva un tiempo utilizando un planificador EDF. ^{[ 22 ]}
• El sistema operativo Plan 9 de Bell Labs incorpora EDFI, ^{[ 23 ]} un "protocolo de planificación en tiempo real ligero que combina EDF con herencia de plazos sobre recursos compartidos". ^{[ 24 ]}
• RTEMS : ^{[ 25 ]} El planificador EDF estará disponible en la versión 4.11. ^{[ 26 ]}
• Litmus-RT : ^{[ 27 ]} Una extensión en tiempo real del núcleo Linux centrada en la planificación y sincronización en tiempo real de multiprocesadores. Su conjunto de algoritmos en tiempo real incluye planificadores Partitioned-EDF, Global-EDF y Clustered-EDF.
• Planificador Clutch de XNU : ^{[ 28 ]} A partir de 2018, el kernel XNU de Apple implementa el algoritmo EDF en su planificador Clutch con el objetivo de mejorar la capacidad de respuesta.
• SuperTinyKernel RTOS : ^{[ 29 ]} Un RTOS ligero y de alto rendimiento diseñado para sistemas embebidos con MCU ARM Cortex-M o RISC-V. Desde la versión 1.1.2, STK proporciona un planificador EDF para aplicaciones de tiempo real estricto , lo que permite una sincronización predecible en dispositivos con recursos limitados.

• Planificación de prioridades dinámicas
• Fecha límite virtual más temprana elegible, primera programación
• Política de recursos de pila