El algoritmo de programación de prioridad dinámica que se utiliza en los sistemas operativos en tiempo real para colocar procesos en una cola de prioridad es el de fecha límite más temprana ( EDF , por sus siglas en inglés ) o el de menor tiempo restante . Siempre que se produce un evento de programación (finalización de una tarea, lanzamiento de una nueva tarea, etc.), se buscará en la cola el proceso más cercano a su fecha límite. Este proceso es el siguiente en programarse para su ejecución.
EDF es un algoritmo de programación óptima en uniprocesadores preemptivos, en el siguiente sentido: si una colección de trabajos independientes, cada uno caracterizado por un tiempo de llegada, un requisito de ejecución y una fecha límite, se puede programar (mediante cualquier algoritmo) de manera que se garantice que todos los trabajos se completen en su fecha límite, el EDF programará esta colección de trabajos para que todos se completen en su fecha límite.
Al programar procesos periódicos con fechas límite iguales a sus períodos, EDF tiene un límite de utilización del 100 %. Por lo tanto, la prueba de programabilidad [1] para EDF es:
donde son los tiempos de cálculo del peor caso de los procesos y son sus respectivos períodos entre llegadas (que se supone que son iguales a los plazos relativos). [2]
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 programación de prioridad fija, como la programación monotónica de velocidad , EDF puede garantizar todos los plazos del sistema con una carga mayor.
Tenga en cuenta que se utiliza 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 con la utilización no 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 Falla de programación de EDF para obtener más detalles.
EDF también es un algoritmo de programación óptimo en procesadores monoprocesadores no preemptivos, pero sólo entre la clase de algoritmos de programación que no permiten insertar tiempo de inactividad. Al programar procesos periódicos que tienen plazos de entrega iguales a sus períodos, una prueba de capacidad de programación suficiente (pero no necesaria) para EDF se convierte en: [3]
Donde p representa la penalización por no preemisión, dada por max / min . Si este factor se puede mantener bajo, la EDF no preemisión puede ser beneficiosa ya que tiene una baja sobrecarga de implementación.
Sin embargo, cuando el sistema está sobrecargado, el conjunto de procesos que no cumplirán con los plazos es en gran medida impredecible (será una función de los plazos exactos y del momento en que se produzca la sobrecarga). Esto supone 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 complicado a la hora de representar los plazos en diferentes rangos (los plazos no pueden ser más precisos que la granularidad del reloj utilizado para la programación). Si se utiliza una aritmética modular para calcular los plazos futuros en relación con el presente, el campo que almacena un plazo relativo futuro debe acomodar al menos el valor de (("duración" {del tiempo más largo esperado hasta la finalización} * 2) + "ahora"). Por lo tanto, EDF no se encuentra comúnmente 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 (normalmente, una programación monotónica de velocidad ). Con prioridades fijas, es fácil predecir que las condiciones de sobrecarga harán que los procesos de baja prioridad no cumplan los plazos, mientras que el proceso de mayor prioridad cumplirá con su plazo.
Existe un importante cuerpo de investigación que aborda la programación EDF en computación en tiempo real ; es posible calcular los tiempos de respuesta en el peor de los casos de los procesos en EDF, abordar otros tipos de procesos que no sean procesos periódicos y utilizar servidores para regular las sobrecargas.
Consideremos tres procesos periódicos programados en un monoprocesador preemptivo. Los tiempos y períodos de ejecución se muestran en la siguiente tabla:
En este ejemplo, las unidades de tiempo pueden considerarse como franjas de tiempo programables . Los plazos son los que cada proceso periódico debe completar dentro de su período.
En el diagrama de tiempo, las columnas representan porciones de tiempo en las que el tiempo aumenta hacia la derecha y todos los procesos comienzan sus períodos en la porción de tiempo 0. El sombreado azul y blanco alternado del diagrama de tiempo indica los períodos de cada proceso, con fechas límite en los cambios de color.
El primer proceso programado por EDF es el P2, porque su período es el más corto y, por lo tanto, tiene el plazo más cercano. Asimismo, cuando finaliza el P2, se programa el P1 y, a continuación, el 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 ellos.
La utilización será:
Como el mínimo común múltiplo de los períodos es 40, el patrón de programación puede repetirse cada 40 intervalos de tiempo. Sin embargo, solo 37 de esos 40 intervalos de tiempo son utilizados por P1, P2 o P3. Como la utilización, 92,5 %, no es mayor que 100 %, el sistema se puede programar con EDF.
Con la programación de EDF pueden producirse intercambios de fechas límite no deseados. Un proceso puede utilizar un recurso compartido dentro de una sección crítica para evitar que se desprograme de manera preventiva en favor de otro proceso con una fecha límite anterior. Si es así, resulta importante que el programador asigne al proceso en ejecución la fecha límite más temprana entre los demás procesos que esperan el recurso. De lo contrario, los procesos con fechas límite anteriores podrían perderlas.
Esto es especialmente importante si el proceso que ejecuta la sección crítica tiene un tiempo mucho más largo para completar y salir de su sección crítica, lo que retrasará la liberación del recurso compartido. Pero el proceso aún podría verse precedido en favor de otros que tienen plazos anteriores pero no comparten el recurso crítico. Este riesgo de intercambio de plazos es análogo a la inversión de prioridad cuando se utiliza la programación preferente de prioridad fija .
Para acelerar la búsqueda de fechas límite en la cola de procesos listos, las entradas de la cola se pueden ordenar según sus fechas límite. Cuando se asigna una nueva fecha límite a un proceso nuevo o a un proceso periódico, se inserta antes del primer proceso con una fecha límite posterior. De esta manera, los procesos con las fechas límite más tempranas siempre están 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 programación de fecha límite más temprana con incumplimiento, [4] los procesos tienen fechas límite y se atienden solo hasta que vencen sus fechas límite. La fracción de "trabajo incumplido", definida como el trabajo residual no atendido debido al vencimiento de las fechas límite, es una medida de rendimiento importante.
Se acepta comúnmente que una implementación de programación preemptiva 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 programación óptima bajo prioridad fija (con la prioridad de cada hilo dada por la programación monotónica de tasa ), el EDF puede alcanzar el 100% mientras que el valor máximo teórico para la programación monotónica de tasa es de alrededor del 69%. Además, la sobrecarga en el peor de los casos de una implementación de EDF (totalmente preemptiva o limitada/no preemptiva) para tareas periódicas y/o esporádicas se puede hacer 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. [5] En casos prácticos, como sistemas integrados que utilizan una representación fija de tiempo de 32 bits, las decisiones de programación se pueden tomar utilizando esta implementación en un pequeño tiempo fijo constante que es independiente del número de tareas del sistema. En tales situaciones, los experimentos han encontrado pocas diferencias perceptibles en la sobrecarga entre EDF y FPS, incluso para conjuntos de tareas de cardinalidad (comparativamente) grande. [5]
Tenga en cuenta que EDF no hace ninguna suposición específica sobre la periodicidad de las tareas; por lo tanto, se puede utilizar para programar tareas periódicas y aperiódicas. [2]
Aunque las implementaciones de EDF no son comunes en los núcleos comerciales en tiempo real, aquí hay algunos enlaces de núcleos de código abierto y en tiempo real que implementan EDF:
SCHED DEADLINE
que está disponible desde el lanzamiento 3.14.