Hello Friends of Hive, Happy New Year 2022.
Hola Amigos de Hive, Feliz Año 2022.
I give continuity to the series concerning Real-Time Systems (RTS), in the framework of topics related to science, research, technology, and innovation.
Doy continuidad a la serie concerniente a los Sistemas de Tiempo Real (STR), en el marco de temas relacionados a la ciencia, investigación, tecnología e innovación.
In previous posts, I presented the context of offline and online real-time scheduling in Real-Time Systems: Scheduling - Context and Cyclic Executive. As well as Real-Time Scheduling Based on Static Priorities
En publicaciones anteriores, presenté el contexto de la planificación de tiempo real fuera de línea y en línea en Sistemas de Tiempo Real: Planificación – Contexto y Ejecutivo Cíclico. Así como también, la Planificación de Tiempo Real Basados en Prioridades Estáticas.
This post I will dedicate to the EDF (Earliest Deadline First) Dynamic Priority Scheduling Algorithm.
Este post lo dedicaré al Algoritmo de Planificación de Prioridades Dinámicas EDF (Earliest Deadline First).
EDF Dynamic Priority Scheduling Algorithm
Algoritmo de Planificación de Prioridades Dinámicas EDF
The main dynamic prioritization algorithm was introduced by Horn in 1974, called Earliest Deadline First (EDF), which allows scheduling a set of n independent tasks on a processor when the tasks have dynamic arrival time and preemption is allowed. This result can be expressed by the following theorem.
El principal algoritmo de asignación de prioridades dinámico fue introducido por Horn en 1974, llamado Earliest Deadline First (EDF), el cual permite planificar un conjunto de n tareas independientes sobre un procesador, cuando las tareas tienen tiempo de llegada dinámica y el adelanto es permitido. Este resultado puede ser expresado por el siguiente teorema.
Given a set of n independent tasks with arbitrary arrival time, an algorithm that at some instant executes the task with the smallest absolute deadline among all ready tasks is optimal for minimizing the maximum delay.
Dado un conjunto de n tareas independientes con tiempo de llegada arbitrario, un algoritmo que en algún instante ejecute la tarea con plazo absoluto más pequeño entre todas las tareas listas, es óptimo con respecto a la minimización del máximo retraso.
To ensure the feasibility of the scheduler produced by the EDF algorithm, it must be verified that all tasks must be completed before their completion deadline (Di), which is given by the following n conditions:
Para garantizar la factibilidad del planificador producido por el algoritmo EDF, se debe verificar que todas las tareas deben ser completadas antes de su plazo de finalización (Di), lo cual está dado por las siguientes n condiciones:
Where Ci is the remaining execution time in the worst case of the task Ti, note that it has an initial value equal to Ci and must be updated when the task is evicted.
donde Ci es el tiempo restante de ejecución en el peor caso de la tarea Ti, note que tiene un valor inicial igual a Ci y debe ser actualizado cuando la misma es desalojada.
EDF is a dynamic scheduler that selects tasks according to their absolute deadline, uses advance, and can be used for periodic as well as aperiodic task scheduling since it does not make use of task periodicity for task scheduling.
EDF es un planificador dinámico que selecciona las tareas de acuerdo a su plazo absoluto, utiliza adelanto y puede ser usado para planificación de tareas periódicas como aperiódicas ya que no hace uso de la periodicidad de las tareas para la planificación de las mismas.
For this case the lowest bound for the processor utilization factor is 1, therefore tasks can use 100% of the processor and still be schedulable. In particular, the following theorem of Liu and Lailand (1973) holds:
Para este caso la menor cota para el factor de utilización del procesador es 1, por lo tanto las tareas pueden utilizar el 100% del procesador y aún ser planificable. En particular el siguiente teorema de Liu y Lailand (1973) se mantiene:
A set of tasks is schedulable with EDF if and only if: / Un conjunto de tareas es planificable con EDF si y sólo si
EDF Method
El Método EDF
The EDF scheduling method consists of assigning the highest priority at each instant to the task whose absolute completion time is closest. The absolute completion time of Ti at instant t is:
El método de planificación EDF consiste en asignar en cada instante la prioridad más alta a la tarea cuyo plazo de finalización absoluto está más próximo. El plazo de finalización absoluto de Ti en un instante t es:
where Pi,k is the instant k at which the last activation of Ti not yet satisfied at t has occurred. If Ti has no activation pending at t, it is assumed that Li,k=∞. Therefore, the task running at instant t is the one whose value of Li,k is minimum.
donde Pi,k es el instante k en que se ha producido la última activación de Ti aún no satisfecha en t. Si Ti no tiene ninguna activación pendiente en t, se supone que Li,k=∞. Por tanto, la tarea que se ejecuta en el instante t es aquel cuyo valor de Li,k es mínimo.
Example
Ejemplo
To illustrate the above, I take the temporal characteristics of three tasks outlined in Table 1.
Para ilustrar lo anterior, tomo las características temporales de tres tareas señaladas en la Tabla 1.
Table 1. Temporal characteristics of three tasks.
Tabla 1. Características temporales de tres tareas.
Doing the schedulability analysis based on Liu and Lailand's (1973) System Utilization shows:
Al hacer el análisis de planificabilidad basado en la Utilización del Sistema de Liu y Lailand (1973) se demuestra:
Whose scheduling with EDF is shown in Figure 1.
Cuya planificación con EDF se muestra en la Figura 1.
Figure 1. Three-task scheduling diagram with EDF.
Figura 1. Diagrama de planificación de tres tareas con EDF.
By way of closing
A manera de cierre
In this post, I explained the EDF dynamic scheduler algorithm for RTSs. I accompanied it with an example for better understanding, where the preceding relationship between the Schedulability Analysis and the respective dynamic execution is highlighted.
En este post expliqué el algoritmo de planificador dinámico EDF para los STR. Lo acompañé con un ejemplo para una mejor comprensión, donde se pone de manifiesto la relación precedente entre el Análisis de Planificabilidad y la ejecución dinámica respectiva.
It is worth mentioning that this scheduler is available in texts and publications about RTSs. Therefore, below I leave references where you can find them. Also, most of the Real-Time Operating Systems host it.
Vale la pena mencionar, que este planificador está disponibles en los textos y publicaciones acerca de los STR. Por tanto, abajo dejo referencias donde los podrán encontrar. También, la mayoría de los Sistemas Operativos de Tiempo Real lo alojan.
See you soon, I hope the reading has been enriching.
Nos vemos pronto, espero que la lectura haya sido enriquecedora.
I invite you to visit and follow me at @alfonsoalfonsi.
Los invito a visitarme y seguirme en @alfonsoalfonsi.
Thank you for your time and comments.
Gracias por su tiempo y comentarios.
References
Referencias
Alfonsi, A. (2021). Unidad II: Restricciones de los Sistemas Empotrados. [Material educativo para la asignatura Proyecto de Digitales Avanzados, Semestre 1-2020]. (Disponible: Grupo de Investigación de Arquitecturas de Sistemas de Control, Departamento de Computación y Sistemas, EICA, Universidad de Oriente, Barcelona, Venezuela).
Butazzo, G. (2011). Hard Real-Time Computing Systems: Predictable Scheduling Algoritms and Applications (3rd ed.). Springer Science/Business Media.
Horn, W. (1974). Some simple scheduling algorithms. Naval Research Logistics Quarterly, 21 (1), 177-185. https://doi.org/10.1002/nav.3800210113
Liu, C. & Layland, J. (1973). Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM, 201, 46-61. https://doi.org/10.1145/321738.321743
Shirvaikar, M. & Elbert, T. (2018). Fundamentals of Real Time Systems. Cognella, Inc.
Figures and Images
Figuras e Imágenes
The Home or Title image was made by @alfonsoalfonsi using CANVAS.
La imagen de Inicio o Título fue realizado por @alfonsoalfonsi usando CANVAS.
The separator used is my own and is made using CANVAS and an image from klipartz.
El separador es de mi propiedad y está realizado usando CANVAS e imagen de klipartz.
The banner and the photographs on it are my property. Made with Paint and the Linerock Investment LTD ToonMe App.
El banner y las fotografías son de mi propiedad. Realizado con Paint y Linerock Investment LTD Aplicación ToonMe.