Algoritmo de programación de CPU con fecha límite más temprana (EDF)

La fecha límite más temprana primero (EDF) es un algoritmo de programación de prioridad dinámico óptimo utilizado en sistemas en tiempo real.
Se puede utilizar para la programación estática y dinámica en tiempo real.

EDF utiliza prioridades para los trabajos para la programación. Asigna prioridades a la tarea según el plazo absoluto. La tarea cuya fecha límite es más cercana obtiene la prioridad más alta. Las prioridades se asignan y cambian de forma dinámica. EDF es muy eficiente en comparación con otros algoritmos de programación en sistemas en tiempo real. Puede hacer que la utilización de la CPU sea aproximadamente del 100 % y, al mismo tiempo, garantizar los plazos de todas las tareas.

EDF incluye la sobrecarga del núcleo. En EDF, si el uso de la CPU es inferior al 100 %, significa que todas las tareas han cumplido el plazo. EDF encuentra un programa factible óptimo. El cronograma factible es aquel en el que todas las tareas del sistema se ejecutan dentro del plazo. Si EDF no puede encontrar un cronograma factible para todas las tareas en el sistema en tiempo real, significa que ningún otro algoritmo de programación de tareas en los sistemas en tiempo real puede brindar un cronograma factible. Todas las tareas que están listas para su ejecución deben anunciar su fecha límite a EDF cuando la tarea sea ejecutable.

El algoritmo de programación de EDF no necesita que las tareas o procesos sean periódicos y también las tareas o procesos requieren un tiempo de ráfaga de CPU fijo. En EDF, cualquier tarea en ejecución puede adelantarse si cualquier otra instancia periódica con una fecha límite anterior está lista para su ejecución y se activa. La preferencia está permitida en el algoritmo de programación La primera fecha límite más temprana.

Ejemplo:
Considere dos procesos P1 y P2.

Sea el período de P1 p ₁ = 50
Sea el tiempo de procesamiento de P1 t ₁ = 25

Sea el período de P2 el período ₂ = 75
Sea el tiempo de procesamiento de P2 t ₂ = 30

Pasos para la solución:

1. La fecha límite para P1 es anterior, por lo que la prioridad de P1>P2.
2. Inicialmente, P1 se ejecuta y completa su ejecución de 25 veces.
3. Después de 25 veces, P2 comienza a ejecutar hasta 50 veces, cuando P1 puede ejecutar.
4. Ahora, comparando la fecha límite de (P1, P2) = (100, 75), P2 continúa ejecutándose.
5. P2 completa su procesamiento en el tiempo 55.
6. P1 comienza a ejecutarse hasta el tiempo 75, cuando P2 puede ejecutarse.
7. Ahora, comparando nuevamente la fecha límite de (P1, P2) = (100, 150), P1 continúa ejecutándose.
8. Repita los pasos anteriores…
9. Finalmente, en el tiempo 150, tanto P1 como P2 tienen el mismo plazo, por lo que P2 continuará ejecutándose hasta su tiempo de procesamiento, luego de lo cual P1 comenzará a ejecutarse.

Limitaciones del algoritmo de programación EDF:

• Problema de sobrecarga transitoria
• Problema de recursos compartidos
• Problema de implementación eficiente