Hello, Friends of Hive, it is a pleasure to be with you again presenting topics of interest in science, research, technology, and innovation, continuing the series on Real-Time Systems.
Hola Amigos de Hive un gusto estar nuevamente con ustedes presentándoles temas de interés de la ciencia, investigación, tecnología e innovación, dando continuidad a la serie referente a los Sistemas de Tiempo Real.
In our second post, I explained the characteristics of the Tasks where I stated the need to eliminate the indeterminism produced by the concurrent execution of them, in order to know exactly their temporal behavior.
En nuestro segundo post, expliqué las características de las Tareas donde manifesté la necesidad de eliminar el indeterminismo que produce la ejecución concurrente de ellas, para poder conocer con exactitud su comportamiento temporal.
Well, in this third installment, I will share what makes the above expressed possible, explaining the Real-Time Scheduling and one of the schedulers, the Cyclical Executive.
Pues bien, en esta tercera entrega, compartiré lo que hace posible lo anterior expresado, explicando la Planificación de Tiempo Real y uno de los planificadores, el Ejecutivo Cíclico.
What is Real-Time Scheduling?
¿Qué es la Planificación de Tiempo Real?
Let's start from the assumption that we have a processor where several tasks will be executed and assigned at given times. Moreover, beforehand, it should be clear that the set of tasks will comply with the time constraints of the system. This defines the Real-Time Scheduling.
Vamos a partir que tenemos un procesador donde se ejecutarán varias tareas que serán asignadas en tiempos determinados. Además de antemano, se debería estar claro que el conjunto de tareas cumplirán con las restricciones temporales del sistema. Lo anterior define la Planificación de Tiempo Real.
So, in this context the scheduling tasks are highlighted:
Entonces, en este contexto de la planificación de tareas se ponen de manifiesto:
1. The Scheduler supplies an algorithm or policy for ordering the execution of the set of activities according to a predefined criterion.
1. El Planificador que suministra un algoritmo o política para la ordenación de la ejecución del conjunto de actividades de acuerdo a un criterio predefinido.
2. The Schedulability Analysis, a method for predicting the worst-case behavior of the system when the scheduling algorithm is applied to it. That is, it allows to know if the imposed restrictions are going to be fulfilled in any situation.
2. El Análisis de Planificabilidad, método para predecir el comportamiento del sistema en el peor caso cuando se le aplica el algoritmo de planificación. Es decir, permite conocer si las restricciones impuestas van a cumplirse en cualquier situación.
Real-Time Scheduling Algorithms
Algoritmos de Planificación de Tiempo Real
The problem is to find, for a given RTS, an allocation of processor time to each process that is consistent with the timing specifications and with the synchronization constraints.
El problema es encontrar, para un STR dado, una asignación de tiempo de procesador a cada proceso que sea consistente con las especificaciones temporales y con las restricciones de sincronización.
Such an allocation will be called admissible scheduling (as there may be several) and if it exists, the system will be executable in real-time. Any algorithm that allows obtaining admissible scheduling for an RTS will be called Real-Time Scheduler.
Tal asignación se denominará planificación admisible (ya que pueden existir varias) y en caso de existir, el sistema será ejecutable en tiempo real. Cualquier algoritmo que permita obtener una planificación admisible para un STR se denominará Planificador de Tiempo Real.
There are two types of scheduling algorithms and they are presented in Figure 1.
Existen dos tipos de algoritmos de planificación y se presentan en la Figura 1.
Figure 1. Real-Time Scheduling Algorithms
Figura 1. Algoritmos de Planificación de Tiempo Real Base
The algorithms shown in Figure 1 are the most widely used for different applications of different types and their codes are available in different programming languages and even form part of the resources of Real-Time Operating Systems. They have been tested and validated for years, building a solid reputation.
Los algoritmos señalados en la Figura 1 son los más utilizados para las diferentes aplicaciones de distintas índoles y sus códigos estás disponibles en distintos lenguajes de programación e inclusive forman parte de los recursos de los Sistemas Operativos de Tiempo Real. Han sido sometidos a diversas pruebas y validaciones por años, levantando una sólida reputación.
Nevertheless, there is a range of algorithmic possibilities, incorporating resources from Artificial Intelligence, Emergent Computing, etc. Coming to be used to conform energy adjustment schemes in computational systems (Alfonsi et al., 2017).
No obstante, existe un abanico de posibilidades algorítmicas, incorporándoles recursos de la Inteligencia Artificial, Computación Emergente, etc. Llegando a utilizarse para conformar esquemas de ajustes de energía en los sistemas computacionales (Alfonsi et al., 2017).
It is worth noting that the temporal characteristics of each task are necessary and the developer must classify them into periodic, aperiodic, or sporadic. As well as to visualize them according to how they would be manipulated, whether they would be expulsive or non-expulsive. Topic discussed in previous post.
Vale la pena destacar, que son necesarias las características temporales de cada tarea y el desarrollador debe clasificarlas en periódicas, aperiódicas o esporádicas. Así como también, visualizarlas según cómo se comportarían en ejecución, sean expulsivas o no-expulsivas. Asunto tratado en el post anterior.
Figure 1 on the left side shows the Cyclic Executives where an analysis of the execution of the tasks is considered a priori static and is done at design time. With the above, the Schedulability Analysis is conceived by construction. In the next section of this post we will discuss this type of scheduling.
En la Figura 1 del lado izquierdo se encuentran los Ejecutivos Cíclicos donde se considera un análisis de la ejecución de las tareas de forma estática a priori y se hace en tiempo de diseño. Con lo anterior, el Análisis de planificabilidad se concibe por construcción. En la siguiente sección de este post trataremos este tipo de planificación.
Right side of Figure 1, we find the Priority Based, which selects the task to be executed within a set, according to a criterion, which is translated into priority.
Del lado derecho de la Figura 1 nos encontramos con los Basados en Prioridades que seleccionan la tarea a ejecutar dentro de un conjunto, atendiendo a un criterio, que se traduce en prioridad.
These priorities have a static form, which is set by the developer following some semantic criteria, periods, or deadlines for completion; or, dynamic as determined by the system at runtime, for example, the one that considers the most urgent task.
Estas prioridades tienen una forma estática, la cual fija el desarrollador siguiendo algún criterio semántico, períodos o plazos de finalización; o, dinámica determinada por el sistema en tiempo de ejecución, como por ejemplo, la que considera la tarea más urgente.
I point within Statics:
Señalo dentro de las Estáticas:
The one that uses the period (Pi) of the tasks to decide their priority. It assigns the highest priority to the one with the lowest Pi. Known as Rate Monotonic (RM).
La que utiliza el período (Pi) de las tareas para decidir la prioridad e ellas. Le asigna la prioridad más alta a la que tenga el menor Pi. Conocida por Rate Monotonic) (RM).
The one that uses the period (Di) of the tasks to decide their priority. It assigns the highest priority to the one with the lowest Di. Known as Deadline Monotonic (DM).
Y, otra que se vale del plazo de finalización (Di) de las tareas para decidir la prioridad de ellas. Le asigna la prioridad más alta a la que tenga el menor Di. Conocida por Deadline Monotonic) (DM).
Among the Dynamics is the one that gives more priority to the most urgent task, or Early Deadline First (EDF). This algorithm is optimal among others of the same nature. The basis for assigning the priority is taken from the dynamic calculation that is produced in the execution of the next completions of each task, variable by the task that takes the name of Dynamic Completion Deadline.
Dentro de las Dinámicas se encuentra el que da más prioridad a la tarea más urgente, o Early Deadline First (EDF). Este algoritmo es óptimo entre otros de su misma naturaleza. El fundamento para asignar la prioridad es tomada del cálculo dinámico que se va produciendo en ejecución de las próximas finalizaciones de cada tarea, variable por tarea que toma el nombre de Plazo de Finalización Dinámico.
In the following, I will present the Cyclical Executive Scheduler, leaving the Priority Driven ones to later publications.
A continuación, presentaré el Planificador Ejecutivo Cíclico, dejando a posteriores publicaciones los Guiados por Prioridades.
Cyclical Executive Scheduler
Planificación con Ejecutivo Cíclico
On the right side of Figure 1 is the Cyclical Executive, which consists of manually ordering the tasks and having the processor execute them always in the same order, the length of the main cycle is given by the hyperperiod, which is defined as the least common multiple of the periods of the tasks.
Del lado derecho de la Figura 1 se destaca el Ejecutivo Cíclico, que consiste en ordenar manualmente las tareas y hacer que el procesador las ejecute siempre en el mismo orden, la duración del ciclo principal viene dada por el hiperperiodo, que se define como el mínimo común múltiplo de los periodos de las tareas.
This scheduling scheme results when the system under consideration has equal periods or multiples of each other. But, there are also complex cases where it is required to decide on a plan within several options in sub-periods. This problem is computationally complex (NP-Hard) (Baker & Shaw, 1989; Butazzo, 2011).
Este esquema de planificación resulta cuando el sistema considerado tiene periodos iguales o múltiplos entre sí. Pero, también hay casos complejos donde se requiere decidir por un plan dentro de varias opciones en subperíodos. Este problema es computacionalmente complejo (NP-Hard) (Baker y Shaw, 1989; Butazzo, 2011).
The algorithm is available in different bibliographic sources, one of them being Baker and Shaw (1989), which explains and details its structure, both Expulsive and Non-Expulsive.
El algoritmo está disponible en diferentes fuentes bibliográficas, siendo una de ellas Baker y Shaw (1989), donde explica y detalla su estructura, tanto Expulsivo como No-Expulsivo.
Also, in Alianga et al. (2015) prepare a simulator for task scheduling in Non-Expulsive Cyclic Executive, as well as RM and EDF algorithms.
También, en Alianga et al. (2015) preparan un simulador para la planificación de tareas en Ejecutivo Cíclico No-Expulsivo, así como también los algoritmos RM y EDF.
Examples of a Scheduler with Cyclical Executive
Ejemplos de una Planificación con Ejecutivo Cíclico
Example 1: Scheduler with Non-Expulsive Cyclical Executive.
Ejemplo 1: Planificación con Ejecutivo Cíclico No-Expulsivo.
It is desired to schedule 3 tasks using the Cyclic Executive, allowing to execute each Ti without interruption by the other tasks until it finishes, after which another task is executed. Its temporal characteristics are shown in Table 1.
Se desea planificar 3 tareas usando el Ejecutivo Cíclico, permitiendo ejecutar cada Ti sin interrupción por parte de las otras tareas hasta que finalice, tras lo cual se ejecuta otra tarea. Sus características temporales se muestran en la Tabla 1.
Table 1. Temporal characteristics of 3 tasks taken as examples.
Tabla 1. Características temporales de 3 tareas tomadas como ejemplo.
The first calculations are made with the least common multiple (LCM) for the Hyperperiod and the greatest common divisor (GCD) for the subperiod, leaving:
Se hacen los primeros cálculos con el mínimo común múltiplo (m.c.m.) para el Hiperperíodo y el máximo común divisor (m.c.d.) para el subperíodo, quedando:
Hyperperiod=m.c.m. (P1,P2,P3)= m.c.m. (25,50,100)= 100 ms
Subperiod=m.c.d. (P1,P2,P3)= m.c.d. (25,50,100)= 25 ms
That is, the number of subperiods is equal to 4.
Hiperperíodo=m.c.m. (P1,P2,P3)= m.c.m. (25,50,100)= 100 ms
Subperíodo=m.c.d. (P1,P2,P3)= m.c.d. (25,50,100)= 25 ms
Es decir, que el número de subperíodos es igual a 4
Then, the execution is ordered taking into consideration the Pi, i.e., the task with the shorter period will be executed before those with longer periods. It is always necessary to observe the Subperiod and the Ci of the Ti.
Luego, se ordena la ejecución tomando en consideración al Pi, es decir, la tarea que tenga el periodo menor se ejecutará antes que las que tengan periodos mayores. Siempre hay que observar el Subperíodo y los Ci de las Ti.
It is shown that they will be executed in the Hyperperiod: T1 4 times; T2 2 times and, T3 one time.
Se pone de manifiesto que se ejecutarán en el Hiperperiodo, T1 4 veces; T2 2 veces y, T3 una vez.
It is worth noting that there can be several scheduling schemes. It is up to the developer to decide which one is the most suitable for his system.
Vale la pena destacar, que pueden existir varios esquemas de planificación. El desarrollador le tocará decidir cuál es el idóneo para su sistema.
A schedule for the example 1 and discussion of the result is shown in Figure 2 below.
A continuación, en la Figura 2 se muestra una planificación para el ejemplo 1 y la discusión del resultado.
Figure 2. Example of the scheduling of 3 tasks with Cyclic Executive.
Figura 2. Ejemplo de la planificación de 3 tareas con Ejecutivo Cíclico.
At t=0 starts the 1st Hyperperiod. Then, in the 1st Subperiod are executed T1 (10 ms), T2 (8 ms) and, T3 (6 ms). With a total of 24 ms. This is one of the scheduling options.
En t=0 inicia el 1er Hiperperiodo. Entonces, en el 1er Subperíodo se ejecutan T1 (10 ms), T2 (8 ms) y T3 (6 ms). Con un total de 24 ms. Siendo esta una de las opciones de planificación.
For the 2nd Subperiod, only T1 (10 ms) is executed.
Para el 2do Subperíodo se ejecuta solo T1 (10 ms).
In the 3rd subperiod, T1 (10 ms) and, T2 (8 ms) are executed. With a total of 18 ms.
En el 3er Subperíodo se ejecutan T1 (10 ms) y T2 (8 ms). Con un total de 18 ms.
Now, following the arrangement of the tasks, I ask you how would the planning of the 4th Subperiod look like? Cheer up, the answer is at the end of the post.
Ahora, siguiendo el acomodo de las tareas, les pregunto ¿cómo quedaría la planificación del 4to Subperíodo? Anímense, la respuesta al final del post.
Example 2: Scheduler with Expulsive Cyclical Executive.
Ejemplo 2: Planificación con Ejecutivo Cíclico Expulsivo.
It is desired to plan 3 tasks using the Cyclic Executive, allowing Ti (Expulsive) segmentation to meet the temporal requirements. Their temporal characteristics are shown in Table 2, I only varied the C2 to apply the segmentation.
Se desea planificar 3 tareas usando el Ejecutivo Cíclico, permitiendo la segmentación de Ti (Expulsiva) para cumplir con los requerimientos temporales. Sus características temporales se muestran en la Tabla 2, solo varío el C2 para aplicar la segmentación.
Table 2. Temporal characteristics of 3 tasks taken as examples.
Tabla 2. Características temporales de 3 tareas tomadas como ejemplo.
Since Pi was not changed, the Hyperperiod and Subperiod remain 100 and 25 ms, respectively.
Como los Pi no se variaron, el Hiperperíodo y el Subperíodo siguen siendo 100 y 25 ms, respectivamente.
Then, the execution is ordered taking into consideration the Pi, as previously established. The Ci of the Ti continues to be observed in the Subperiod.
Luego, se ordena la ejecución tomando en consideración al Pi, como se estableció anteriormente. Se sigue observando en el Subperíodo los Ci de las Ti.
It is shown that they will be executed in the Hyperperiod: T1 4 times; T2 2 times and, T3 one time.
Se pone de manifiesto que se ejecutarán en el Hiperperiodo, T1 4 veces; T2 2 veces y, T3 una vez.
It is worth noting that the tasks in this example cannot be planned with the Cyclic Executive of the first example. The segmentation or partitioning of tasks has to be applied, to then accommodate them in the Subperiods for execution.
Vale la pena destacar, que las tareas de este ejemplo no son planificables con el Ejecutivo Cíclico del primer ejemplo. Se tiene que aplicar la segmentación o partición de tareas, para entonces acomodarlas en los Subperíodos para su ejecución.
This segmentation will depend on the structure of the programming code of the system under consideration. Several scheduling options may appear, as well as the possibility of not being able to schedule under this type of algorithm. It is up to the system developer to decide.
Esta segmentación dependerá de la estructura del código de programación del sistema considerado. Pueden aparecer varias opciones de planificación, así como también la posibilidad de no poderse planificar bajo este tipo de algoritmo. Quien decide es el desarrollador des sistema.
Here T2 is partitioned into four (4) segments for each Subperiod. That is, T2,k with k=1,2,3,4.
Aquí la T2 se particiona en cuatro (4) segmentos para cada Subperíodo. Es decir, T2,k con k=1,2,3,4.
A schedule for the example 2 and discussion of the result is shown in Figure 3 below.
A continuación, en la Figura 3 se muestra una planificación para el ejemplo 2 y la discusión del resultado.
Figure 3. Example of the scheduling of 3 tasks with Cyclic Executive.
Figura 3. Ejemplo de la planificación de 3 tareas con Ejecutivo Cíclico.
At t=0 the 1st Hyperperiod starts. Then, in the 1st Subperiod, T1 (10 ms), T2,1 (9 ms, with 11 ms remaining to be executed), and T3 (6 ms) are executed. With a total of 25 ms. This being one of the scheduling options.
En t=0 inicia el 1er Hiperperiodo. Entonces, en el 1er Subperíodo se ejecutan T1 (10 ms), T2,1 (9 ms y quedan 11 ms por ejecutar) y T3 (6 ms). Con un total de 25 ms. Siendo esta una de las opciones de planificación.
For the 2nd Subperiod, T1 (10 ms), T2,2 (11 ms, completing its execution) are executed. Totaling 21 ms.
Para el 2do Subperíodo se ejecutan, T1 (10 ms), T2,2 (11 ms, completándose su ejecución). Totalizando 21 ms.
In the 3rd subperiod, T1 (10 ms) and, T2,3 (15 ms, with 5 ms remaining to be executed). Totaling 25 ms.
En el 3er Subperíodo se ejecutan, T1 (10 ms) y T2,3 (15 ms, quedando 5 ms por ejecutar). Totalizando 25 ms.
Now, following the arrangement of the tasks, I ask you again how would the planning of the 4th subperiod look like? Cheer up, the answer is at the end of the post.
Ahora, siguiendo el acomodo de las tareas, nuevamente les pregunto ¿cómo quedaría la planificación de los subperíodo 4to? Anímense, la respuesta al final del post.
By way of closing
A manera de cierre
In this post I explained that in order to guarantee the compliance with the time constraints it is necessary to appeal to Scheduling, where a Schedulability Analysis and a Scheduler must be performed.
En este post expuse que para garantizar el cumplimiento de las restricciones temporales es necesario apelar a la Planificación, donde deben realizarse un Análisis de Planificabilidad y un Planificador.
In addition, the types of Real-Time Schedulers, Cyclic Executive (offline), and Priority-Based, static and dynamic, both online, were presented.
Además, se presentaron los tipos de Planificadores de Tiempo Real, los Ejecutivos Cíclicos (fuera de línea) y los Basados en Prioridades, estáticos y dinámicos, ambos en línea.
I continued with the Cyclic Executive Scheduler providing its features, highlighting its expulsion and non-explosive functionality utilizing 2 examples. In addition, some references in case you want to go deeper into this topic.
Seguí con el Planificador Ejecutivo Cíclico proporcionando sus características, poniendo de manifiesto su funcionalidad tanto expulsiva como no explusiva mediante 2 ejemplos. Además, unas referencias en caso de querer profundizar acerca de este tema.
This scheduler is one of the most used in computer systems, which could be embedded or embedded, where the temporal characteristics of the system are well known. It has several drawbacks, one of them is that it does not handle sporadic tasks well.
Este planificador es uno de los más utilizados en sistemas computacionales, que pudieran ser empotrados o embebidos, donde se conocen muy bien las características temporales del sistema. Tiene varios detalles, uno de ellos es que no maneja bien las tareas esporádicas.
En el próximo post de esta serie estaré abordando los Planificadores Estáticos Basados en Prioridades y aprovecharé para explicar el Análisis de Planificabilidad.
En el próximo post de esta serie estaré abordando los Planificadores Estáticos Basados en Prioridades. y aprovecharé para explicar el Análisis de Planificabilidad.
Answers to questions
Respuestas a las preguntas
See you soon, I hope the reading has been enriching.
Nos vemos pronto, espero que la lectura haya sido enriquecedora.
Be sure to visit my other posts and follow me @alfonsoalfonsi.
No dejes de visitar mis otros posts y de seguirme en @alfonsoalfonsi.
Thank you for your time and comments.
Gracias por su tiempo y comentarios.
Real-Time Systems Post Series by @alfonsoalfonsi
Serie de Post Sistemas de Tiempo Real por @alfonsoalfonsi
Alfonsi, A. [@alfonsoalfonsi] (2021, August 16). [Eng-Spa] Real-Time System: Concept and Context // Sistema de Tiempo Real: Concepto y Contexto. HiVE Blog. [POST]. @alfonsoalfonsi/eng-spa-real-time-system-concept-and-context-sistema-de-tiempo-real-concepto-y-contexto
Alfonsi, A. [@alfonsoalfonsi] (2021, August 28). [Eng-Spa] Real-Time System: Real-time Task. The HiVE Blog. [POST]. @alfonsoalfonsi/eng-spa-real-time-system-real-time-task
References from @alfonsoalfonsi as a Basis for this Content
Referencias de @alfonsoalfonsi como Base de este Contenido
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).
Alfonsi A., Yánez R. y Pérez J. (2017). Distribución del Tiempo Ocioso Orientado al Ahorro de Energía en Tareas de Control de Tiempo Real. Revista Ciencia e Ingeniería, 38(2), pp. 159-166. https://www.redalyc.org/journal/5075/507555007008/html/
Alfonsi, A., Yánez, R., Alfonsi, A. R. (2015). Proceso del Diseño del Software en Sistemas de Control Empotrado de Tiempo Real Orientado al Ahorro de Energía. [Informe Final Proyecto de Investigación CI-020402-1739-11. Consejo de Investigación Universidad de Oriente, Venezuela].
Alfonsi, A., Pérez, J. y Dunia, E. (2013). Arquitectura de Control Multifrecuencia para el Ajuste Dinámico del Consumo de Energía en Tareas de Tiempo Real. Revista Multidisciplinaria del Consejo de Investigación de la Universidad de Oriente SABER, 25(2), 202-209. https://www.redalyc.org/articulo.oa?id=427739462010
References
Referencias
Aliaga García, F. J., Aliaga García, I. M., Olivares Bueno, J., Gámez Granados, J. C., Palomares Muñoz, J. M. (2015). Simuladores de Planificadores de Sistemas en Tiempo Real. Enseñanza y Aprendizaje de Ingeniería de Computadores, 5, 105-114.
Baker, T. P. y Shaw, A. (1989). The Cyclic Executive Model and Ada. Real Time Systems, 1, 120-129. https://doi.org/10.1007/BF02341919
Butazzo, G. (2011). Hard Real-Time Computing Systems: Predictable Scheduling Algoritms and Applications (3rd ed.). Springer Science/Business Media.
Shirvaikar, M. y Elbert, T. (2018). Fundamentals of Real Time Systems. Cognella, Inc.
Stankovic, J. A. (1988). Misconceptions About Real-Time Computing: A Serius Problem for Next-Generations Systems. Computer, 21 (10), 10-19. https://doi.org/10.1109/2.7053
Images
Imágenes
The Home or Title image was made by @alfonsoalfonsi using CANVAS with a Pixabay images
La imagen de Inicio o Título fue realizado por @alfonsoalfonsi usando CANVAS con imagen Pixabay
The separator used is my own and is made using CANVAS and an image from PxHere
El separador son de mi propiedad y está realizado usando CANVAS e imagen de PxHere.
The banner and the photographs on it are my property. Made with Power Point, Paint and the Linerock Investment LTD ToonMe App.
El banner y las fotografías son de mi propiedad. Realizado con Power Point, Paint y Linerock Investment LTD Aplicación ToonMe.