Fecha límite más temprana, primera programación

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:

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

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] $\izquierda\{C_{i}\derecha\}$ ${\estilo de visualización n}$ $\izquierda\{T_{i}\derecha\}$

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.

Fallo de programación de EDF

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]

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

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. $\left\{C_{i}\right\}$ $\left\{T_{i}\right\}$

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.

Ejemplo

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 horarias programables . Los plazos son los que cada proceso periódico debe completar dentro de su período.

Diagrama de tiempos

Diagrama de tiempo que muestra parte de un posible cronograma para el ejemplo.

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.

Utilización

La utilización será:

$\left({\frac {1}{8}}+{\frac {2}{5}}+{\frac {4}{10}}\right)=\left({\frac {37}{40}}\right)=0.925={\mathbf {92.5\%} }$

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.

Intercambio de fechas límite

Con la programación 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í, es 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 mucho más tiempo 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.

Análisis de tráfico pesado para colas de EDF con incumplimiento

En un análisis de tráfico pesado 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.

Comparación con los programadores de prioridad fija

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]

Núcleos que implementan la programación EDF

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:

SHARK El RTOS SHaRK, que implementa varias versiones de algoritmos de programación de reserva de recursos y programación EDF
ERIKA Enterprise ERIKA Enterprise, que proporciona una implementación de EDF optimizada para pequeños microcontroladores con una API similar a la API OSEK .
El núcleo Everyman El núcleo Everyman implementa la programación EDF o Deadline Monotonic dependiendo de la configuración del usuario.
MaRTE OS MaRTE OS actúa como un entorno de ejecución para aplicaciones Ada e implementa una amplia gama de algoritmos de programación, incluido EDF.
El proyecto AQuoSA constituye una modificación del núcleo Linux que enriquece el planificador de procesos con capacidades de planificación EDF. La sincronización de la planificación no puede ser tan precisa como en el caso de los sistemas operativos de tiempo real estrictos antes mencionados, pero es lo suficientemente precisa como para mejorar en gran medida la predictibilidad 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 sin privilegios en un sistema de forma controlada, mediante un modelo de control de acceso diseñado adecuadamente. ^[6]
El kernel de Linux tiene una fecha límite más temprana para su primera implementación, SCHED DEADLINEque está disponible desde el lanzamiento 3.14.
El planificador en tiempo real desarrollado en el contexto del proyecto europeo IRMOS es un planificador en tiempo real multiprocesador para el núcleo Linux, especialmente adecuado para el aislamiento temporal y el aprovisionamiento de garantías de QoS para componentes de software multiproceso complejos y también para máquinas virtuales completas . Por ejemplo, cuando se utiliza Linux como sistema operativo host y KVM como hipervisor, IRMOS se puede utilizar para proporcionar garantías de programació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 programar los subprocesos (y/o procesos) adjuntos a cada reserva EDF externa. Consulte también este artículo en lwn.net para obtener una descripción general y un breve tutorial sobre el tema.
Xen cuenta con un programador EDF desde hace algún tiempo. La página del manual contiene una breve descripción.
El sistema operativo Plan 9 de Bell Labs incorpora EDFI, un "protocolo de programación ligero en tiempo real que combina EDF con herencia de plazos sobre recursos compartidos". ^[7]
RTEMS: El planificador EDF estará disponible en la versión 4.11. RTEMS SuperCore
Litmus-RT es una extensión en tiempo real del núcleo Linux que se centra en la programación y sincronización en tiempo real de múltiples procesadores. Su conjunto de algoritmos en tiempo real incluye programadores Partitioned-EDF, Global-EDF y Clustered-EDF.
A partir de 2018, el kernel XNU de Apple implementa el algoritmo EDF en su Clutch Scheduler con el objetivo de mejorar la capacidad de respuesta.

Véase también

Referencias

^ Xu, J.; Parnas, DL (1990). "Programación de procesos con tiempos de lanzamiento, fechas límite, relaciones de precedencia y exclusión". IEEE Transactions on Software Engineering . 16 (3): 360–369. doi :10.1109/32.48943.
^ ab Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (tercera edición), Nueva York, NY: Springer, pág. 100, ISBN 9781461406761
^ Short, Michael (2011). "Análisis mejorado de la capacidad de programación de tareas con plazos implícitos en el marco de una programación EDF con prelación limitada". Conferencia internacional IEEE de 2011 sobre tecnología emergente y automatización de fábricas. págs. 1–8. doi :10.1109/ETFA.2011.6059008. ISBN 978-1-4577-0017-0.S2CID 7656331 .
^ Kruk, Łukasz; Lehoczky, John; Ramanan, Kavita; Shreve, Steven (2011). "Análisis de tráfico pesado para colas EDF con incumplimiento" (PDF) . Anales de probabilidad aplicada . 21 (2). doi :10.1214/10-AAP681. S2CID 12268649.
^ ab Short, Michael (abril de 2010). "Técnicas de gestión de tareas mejoradas para aplicar la programación EDF en tareas recurrentes". 16.º Simposio sobre tecnología y aplicaciones integradas y en tiempo real del IEEE de 2010. págs. 56-65. doi :10.1109/RTAS.2010.22. ISBN 978-1-4244-6690-0. Número de identificación del sujeto 13940378.
^ Cucinotta, Tommaso (2008). "Control de acceso para reservas adaptativas en sistemas multiusuario". Simposio sobre tecnología y aplicaciones integradas y en tiempo real del IEEE de 2008. págs. 387–396. doi :10.1109/RTAS.2008.16. ISBN 978-0-7695-3146-5.S2CID1008365 .
^ Pierre G. Jansen, Sape J. Mullender, Paul JM Havea, Hans Scholten. Programación EDF ligera con herencia de fecha límite