La fecha límite más temprana primero ( EDF ) o el tiempo que queda menos es un algoritmo de programación de prioridad dinámica que se utiliza en los sistemas operativos en tiempo real para colocar los procesos en una cola de prioridad . Siempre que se produzca un evento de programación (finalización de la tarea, liberación 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 que se programará para su ejecución.
EDF es un algoritmo de programación óptimo en monoprocesadores preventivos, en el siguiente sentido: si una colección de trabajos independientes , cada uno caracterizado por una hora de llegada, un requisito de ejecución y una fecha límite, se puede programar (mediante cualquier algoritmo) de una manera que garantice todos los trabajos se completen antes de su fecha límite, el EDF programará esta colección de trabajos para que todos se completen antes de su fecha límite.
Con la programación de procesos periódicos que tienen plazos iguales a sus períodos, EDF tiene un límite de utilización del 100%. Por lo tanto, la prueba de capacidad de programación para EDF es:
donde el son los tiempos de cálculo del peor caso de la procesos y el son sus respectivos períodos entre llegadas (se supone que son iguales a los plazos relativos). [1]
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 de velocidad monótona , EDF puede garantizar todos los plazos en el sistema con una carga más alta.
EDF también es un algoritmo de programación óptimo en monoprocesadores no preventivos, pero solo entre la clase de algoritmos de programación que no permiten el tiempo de inactividad insertado. Cuando se programan procesos periódicos que tienen plazos iguales a sus períodos, una prueba de capacidad de programación suficiente (pero no necesaria) para EDF se convierte en: [2]
Donde p representa la penalización por no apropiación, dada por max / min . Si este factor se puede mantener pequeño, el EDF no preventivo puede ser beneficioso, ya que tiene un bajo costo 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 el momento en el que se produce la sobrecarga). Esta es 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 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 (("duration" {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 (generalmente programación de velocidad monótona ). Con prioridades fijas, es fácil predecir que las condiciones de sobrecarga harán que los procesos de baja prioridad no cumplan con los plazos, mientras que el proceso de mayor prioridad seguirá cumpliendo su plazo.
Existe un importante cuerpo de investigación que se ocupa de la programación del FED en la computación en tiempo real ; es posible calcular los peores tiempos de respuesta de los procesos en EDF , para hacer frente a otros tipos de procesos que los procesos periódicos y utilizar servidores para regular las sobrecargas.
Ejemplo
Considere 3 procesos periódicos programados en un monoprocesador preventivo. Los tiempos y períodos de ejecución se muestran en la siguiente tabla:
Proceso | Tiempo de ejecución | Período |
---|---|---|
P1 | 1 | 8 |
P2 | 2 | 5 |
P3 | 4 | 10 |
En este ejemplo, las unidades de tiempo pueden considerarse como segmentos de tiempo programables . Los plazos son que cada proceso periódico debe completarse dentro de su período.
Diagrama de tiempo
En el diagrama de tiempo, las columnas representan porciones de tiempo con el tiempo aumentando hacia la derecha, y todos los procesos comienzan sus períodos en el intervalo de tiempo 0. El sombreado alterno de azul y blanco 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 P2, porque su período es más corto y, por lo tanto, tiene el plazo más temprano. Asimismo, cuando se completa P2, 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 ellos.
Utilización
La utilización será:
Dado que 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. Pero, P1, P2 o P3 solo utilizan 37 de esos 40 intervalos de tiempo. Dado que la utilización, 92,5%, no es superior al 100%, el sistema es programable con EDF.
Intercambio de fechas límite
Pueden producirse intercambios de plazos no deseados con la programación de EDF. Un proceso puede utilizar un recurso compartido dentro de una sección crítica , para evitar que se desprograme de manera preventiva a 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 de entre los otros procesos que esperan el recurso. De lo contrario, los procesos con fechas límite anteriores podrían perderlos.
Esto es especialmente importante si el proceso que ejecuta la sección crítica tiene mucho más tiempo para completarse y salir de su sección crítica, lo que retrasará la liberación del recurso compartido. Sin embargo, el proceso aún podría adelantarse en favor de otros que tienen fechas límite más tempranas pero que no comparten el recurso crítico. Este riesgo de intercambio de fechas límite es análogo a la inversión de prioridad cuando se utiliza la programación preventiva de prioridad fija .
Para acelerar la búsqueda de fechas límite dentro de la cola lista, las entradas de la cola se ordenan según sus fechas límite. Cuando un nuevo proceso o un proceso periódico recibe una nueva fecha límite, se inserta antes del primer proceso con una fecha límite posterior. De esta forma, los procesos con los plazos más tempranos están siempre al principio de la cola.
Análisis de tráfico pesado para colas 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 Early-Deadline-First (EDF) con incumplimiento , los procesos tienen fechas límite y se sirven solo hasta que venzan sus fechas límite. La fracción de "trabajo incumplido", definido como el trabajo residual sin servicio debido a los plazos transcurridos, es una medida de rendimiento importante.
Comparación con los programadores de prioridad fija
Se acepta comúnmente que la implementación de una programación preventiva de prioridad fija (FPS) es más simple que un programador de prioridad dinámica, como el EDF. Sin embargo, al comparar el uso máximo de una programación óptima con prioridad fija (con la prioridad de cada hilo dada por la programación de tarifa monótona ), el EDF puede alcanzar el 100% mientras que el valor máximo teórico para la programación de tarifa monótona es de alrededor del 69% .
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. [3]
Kernels que implementan la programación EDF
Aunque las implementaciones de EDF no son comunes en los kernels comerciales en tiempo real, aquí hay algunos enlaces de kernels de código abierto y en tiempo real que implementan EDF:
- SHARK El SHaRK RTOS, implementando varias versiones de programación EDF y algoritmos de programación de reserva de recursos
- ERIKA Enterprise ERIKA Enterprise, que proporciona una implementación de EDF optimizada para pequeños microcontroladores con una API similar a la API OSEK .
- Everyman Kernel El Everyman Kernel implementa la programación EDF o Deadline Monotonic dependiendo de la configuración del usuario.
- MaRTE OS MaRTE OS actúa como un tiempo de ejecución para las aplicaciones Ada e implementa una amplia gama de algoritmos de programación, incluido EDF.
- El proyecto AQuoSA constituye una modificación del kernel de Linux que enriquece el programador de procesos con capacidades de programación EDF. La sincronización de la programación no puede ser tan precisa como en el caso de los sistemas operativos en tiempo real duro anteriores, pero es lo suficientemente precisa como para mejorar en gran medida la previsibilidad y, por lo tanto, cumplir con los requisitos en tiempo real de las aplicaciones multimedia. AQuoSA es uno de los pocos proyectos que proporciona capacidades de programación en tiempo real a usuarios sin privilegios en un sistema de forma controlada, mediante un modelo de control de acceso diseñado adecuadamente. [4]
- El kernel de Linux tiene una primera implementación de fecha límite más temprana llamada SCHED DEADLINE que está disponible desde la versión 3.14.
- El programador en tiempo real desarrollado en el contexto del Proyecto Europeo IRMOS es un programador en tiempo real multiprocesador para el kernel de Linux, particularmente adecuado para el aislamiento temporal y el aprovisionamiento de garantías de QoS para componentes de software complejos de múltiples subprocesos y también 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 presenta un planificador jerárquico combinado EDF / FP . En el nivel externo hay un programador EDF particionado en las CPU disponibles. Sin embargo, las reservas son multiprocesador y la FP global sobre multiprocesadores se utiliza 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 tiene un programador EDF desde hace algún tiempo. La página de manual contiene una breve descripción.
- El sistema operativo Plan 9 de Bell Labs incorpora EDFI, un "protocolo ligero de programación en tiempo real que combina EDF con herencia de fecha límite sobre recursos compartidos". [5]
- RTEMS : El programador EDF estará disponible en la versión 4.11. RTEMS SuperCore
- Litmus-RT es una extensión en tiempo real del kernel de Linux con un enfoque en la programación y sincronización multiprocesador en tiempo real. Su conjunto de algoritmos en tiempo real incluye programadores Partitioned-EDF, Global-EDF y Clustered-EDF.
Ver también
Referencias
- ^ Buttazzo, Giorgio (2011), Sistemas informáticos duros en tiempo real: Aplicaciones y algoritmos de programación predecibles (Tercera ed.), Nueva York, NY: Springer, p. 100, ISBN 9781461406761
- ^ Corto, Michael (2011). "Análisis de capacidad de programación mejorado de tareas de fecha límite implícitas bajo programación EDF de preferencia limitada". 2011 IEEE International Conference on Emerging Technology and Factory Automation . págs. 1–8. doi : 10.1109 / ETFA.2011.6059008 . ISBN 978-1-4577-0017-0. S2CID 7656331 .
- ^ Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Tercera ed.), Nueva York, NY: Springer, p. 100, ISBN 9781461406761
- ^ Cucinotta, Tommaso (2008). "Control de acceso para reservas adaptables en sistemas multiusuario". 2008 Simposio de aplicaciones y tecnologías integradas y en tiempo real de IEEE . págs. 387–396. doi : 10.1109 / RTAS.2008.16 . ISBN 978-0-7695-3146-5. S2CID 1008365 .
- ^ Pierre G. Jansen, Sape J. Mullender, Paul JM Takinga, Hans Scholten. Programación ligera de EDF con herencia de fecha límite