Hello Friends of Hive we continue with the series concerning Real Time Systems (RTS), in the framework of topics related to science, research, technology and innovation.
Hola Amigos de Hive seguimos con 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.
Scheduling is a primary point to be handled by an RTS developer. In a previous post the Cyclic Executive Scheduling Algorithm was explained and, brush strokes have been given to the Priority Based Statics.
La planificación es un punto primordial que debe manejar un desarrollador de STR. En un post anterior se explicó el Algoritmo de Planificación Ejecutivo Cíclico y, se han dado pinceladas a los Basados en Prioridades Estáticas .
Therefore, this post will be dedicated to the Algorithms Based on Static Priorities, the |Rate Monotonic (RM), and the Deadline Monotonic (DM).
Por tanto, este post lo dedicaré a los Algoritmos Basados en Prioridades Estáticas, el que da más prioridad a la tarea más frecuente (RM: Rate Monotonic) y, al que da más prioridad a la tarea más urgente (DM: Deadline Monotonic).
They will be accompanied by examples for a better understanding.
Serán acompañados de ejemplos para una mejor comprensión.
RATE MONOTONIC (RM)
Liu and Layland (1973) presented an optimal algorithm based on fixed priorities for task execution with Pi=Di, where a fixed priority assignment increasing with task frequencies is considered, called Rate Monotonic (RM).
Liu y Layland (1973) presentaron un algoritmo óptimo basado en prioridades fijas para la ejecución de tareas con Pi=Di, donde se considera una asignación de prioridades fijas creciente con las frecuencias de las tareas, llamado Rate Monotonic (RM).
In addition, the possibility of being able to determine whether a set of tasks was schedulability or not was demonstrated. Where the sufficient but not necessary condition of schedulability based on System Utilization appears.
Además, se demostraba la posibilidad de poder determinar si un conjunto de tareas era planificable o no. Donde aparece la condición suficiente pero no necesaria de planificabilidad basada en la Utilización del Sistema
The work of Liu and Layland laid the foundations of scheduling theory as we know it today.
El trabajo de Liu y Layland sentó las bases de la teoría de programación tal como la conocemos hoy en día.
The RM scheduler has the following features:
El planificador RM tiene las siguientes características:
- All tasks are periodic and independent of each other.
- Di = Pi.
- Priority assignment will be done in inverse Pi, i.e., a task of lower period than another will have higher priority.
- It is expulsive.
- The context switching time is considered negligible.
- Si un sistema es uniformemente armónico las Ti son planificables bajo RM si la condición. U≤1.
- Todas las tareas son periódicas e independientes unas de otras.
- El Di = Pi.
- La asignación de prioridades se hará de forma inversa Pi, es decir, una tarea de menor periodo que otra tendrá mayor prioridad.
- Es expulsivo.
- El tiempo de cambio de contexto se considera despreciable.
- Si un sistema es uniformemente armónico las Ti son planificables bajo RM si la condición U≤1.
Example 1
Ejemplo 1
Let's consider the data in Table 1 and let's schedule the tasks with RM.
Consideremos los datos de la Tabla 1 y vamos a planificar las tareas con RM.
Table 1. Temporal characteristics of 3 tasks of Example 1.
Tabla 1. Características temporales de 3 tareas del Ejemplo 1.
Going back to the tasks in Table 1, let's do the Schedulability Analysis based on Liu and Layland's System Utilization.
Hacemos el Análisis de Planificabilidad basado en la Utilización del Sistema de Liu y Layland.
Then, the condition is fulfilled and can be schedulable in RM. So, we proceed to establish the priorities to the Ti, indicated in Table 2 and its scheduling diagram in Figure 1.
Entonces, se cumple la condición y puede planificarse en RM. Así, que se procede a establecer las prioridades a las Ti, indicadas en la Tabla 2 y su diagrama de planificación en la Figura 1.
Table 2. Time characteristics and priorities of 3 tasks in Example 1.
Tabla 2. Características temporales y prioridades de 3 tareas del Ejemplo 1.
Figure 1. Three Ti scheduling diagrams under RM.
Figura 1. Diagrama de Planificación de tres Ti bajo RM.
From this example, we will highlight the necessary concepts that we have already mentioned.
De este ejemplo vamos a destacar conceptos necesarios que hemos manifestado hasta ahora.
- It is clear that the Ti is schedulable in RM (objective of this post).
- The system is uniformly harmonic due to its Pi. Therefore, at each Hyperperiod=100 ms, the same scheduling scheme is executed.
- When a Hyperperiod starts, the Critical Instant occurs.
More information about points 1 and 2 can be found in the post Eng-Spa-Real-Time Systems - Scheduling - Schedulability Analysis Based on System Utilization
- Se pone de manifiesto que las Ti son planificadas en RM (objetivo de este post).
- El sistema es uniformemente armónico. Por tanto, en cada Hiperperíodo=100 ms se ejecuta el mismo esquema de planificación.
- Cuando da inicio a un Hiperperíodo se produce el Instante Crítico.
Más información acerca de los puntos 1 y 2 los consigue en el post Eng-Spn- Real-Time Systems - Scheduling - Schedulability Analysis Based on System Utilization
DEADLINE MONOTONIC (DM)
Scheduling that monotonically assigns priorities with Deadline Monotonic (DM) was proposed by Audsley et al. (1993) where Di can be different from Pi (less than or equal to).
La planificación que asigna monotónicamente prioridades con el Plazo de Finalización Di o Deadline Monotonic (DM) fue prouesto por Audsley et al. (1993) donde los Di pueden ser distintos a los Pi (menores o iguales).
In this case, priorities are assigned in reverse order to Di, so that the task with the shortest completion time has the highest priority.
La asignación de prioridades se hace en este caso en orden inverso al Di, de forma que la tarea con plazo de finalización menor tenga mayor prioridad.
As a guarantee test for the DM scheduling policy we can take the result when applying Response Time Analysis, but comparing with Di instead of its Pi.
Como test de garantía para la política de planificación DM podemos tomar el resultado al aplicar Análisis del Tiempo de Respuesta, pero comparando con el Di en lugar de su Pi.
The DM scheduler, like the RM, is not optimal in the most general case, but it is optimal among schedulers with fixed priorities.
El planificador DM, al igual que el RM, no es óptimo en el caso más general, pero si que es óptimo de entre los planificadores con prioridades fijas.
Example 2
Ejemplo 2
Let's consider the data in Table 3 and let's schedule the tasks with DM.
Consideremos los datos de la Tabla 3 y vamos a planificar las tareas con DM.
Table 3. Temporal characteristics of 3 tasks of Example 1.
Tabla 3. Características temporales de 3 tareas del Ejemplo 1.
Going back to the tasks in Table 1, let's do the Schedulability Analysis based on System Utilization.
Hacemos el Análisis de Planificabilidad basado en la Utilización del Sistema.
Now we apply the Response Time Analysis.
Ahora aplicamos el Análisis de Tiempo de Respuesta.
As can be observed the respective Response Times are less than their Di, therefore they can be schedulability with DM. In the following, the priority assignment according to DM is presented in Table 4 and Figure 2 the respective Scheduling Diagram.
Como puede observarse los respectivos Tiempos de Respuestas son menores a sus Di, por tanto pueden ser planificados con DM. A continuación, se presenta en la Tabla 4 la asignación de prioridades según DM y en la Figura 2 el Diagrama de Planificación respectivo.
Table 4. Time characteristics and priorities of 3 Ti in Example 2.
Tabla 4. Características temporales y prioridades de 3 Ti del Ejemplo 2.
Figure 2. Three Ti scheduling diagrams under DM.
Figura 2. Diagrama de Planificación de tres Ti bajo DM.
This example shows that the scheduling with DM is executed for each Hyperperiod=200 ms. Moreover, in the Critical Instant, the Ti are schedulability.
Este ejemplo, pone de manifiesto que la planificación con DM se ejecuta por cada Hiperperiodo=200 ms. Además, en el Instante Crítico las Ti son planificadas.
By way of closing
A manera de cierre
In this post, I explained the RM and DM Static Schedulers for RTS. I accompanied it with examples for a better understanding, where the preceding relationship between the Schedulability Analysis and the respective scheduling algorithms is highlighted.
En este post expliqué los Planificadores Estáticos RM y DM para los STR. Lo acompañé con ejemplos para una mejor comprensión, donde se pone de manifiesto la relación precedente entre el Análisis de Planificabilidad y los respectivos algoritmos de planificación.
It is worth mentioning that these schedules are available in the texts and publications about RTS. Therefore, below I leave references where you can find them. Also, most of the Real-Time Operating Systems host them.
Vale la pena mencionar, que estos planificadores están 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 los alojan.
Now, my distinguished readers, you have the fundamental bases for the Schedulability Analysis and Static Schedulers, as well as to do the same with the Cyclic Executive, once we have the tasks defined.
Ahora, mis distinguidos lectores, tienen las bases fundamentales para el Análisis de Planificabilidad y Planificadores Estáticos, así como también hacer lo propio con el Ejecutivo Cíclico, una vez que tenemos las tareas definidas.
However, it is necessary to arrive at the tasks and define them in the context of the system and its relationships, to then develop the Real-Time System. This previous and subsequent stage manifests itself in the Realization.
Sin embargo, hay que llegar a las tareas y definirlas en el contexto del sistema y sus relaciones, para luego desarrollar el Sistema de Tiempo Real. Esta etapa previa y posterior, se manifiesta en la Realización.
In later posts, I will address the Real Time Systems Performance. With the understanding, that the dynamic scheduling algorithm, which gives higher priority to the most urgent task, Earliest Deadline First (EDF), is pending.
En post posteriores abordaré la Realización de Sistemas de Tiempo Real. En el entendido, que el algortimo dinámico de planificación, que da más prioridad a la tarea más urgente, Earliest Deadline First (EDF), queda pendiente.
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, October 15). [Eng-Spa] Real-Time Systems - Scheduling - Schedulability Analysis Based on Response Time [POST]. The HiVE Blog. @alfonsoalfonsi/eng-spa-real-time-systems-scheduling-schedulability-analysis-based-on-response-time
Alfonsi, A. [@alfonsoalfonsi] (2021, October 8). [Eng-Spa] Real-Time Systems - Scheduling - Schedulability Analysis Based on System Utilization [POST]. The HiVE Blog. @alfonsoalfonsi/eng-spa-real-time-systems-scheduling-schedulability-analysis-based-on-system-utilization
Alfonsi, A. [@alfonsoalfonsi] (2021, September 30). [Eng-Spa] Real-Time Systems: Scheduling - Context and Cyclic Executive [POST]. The HiVE Blog. @alfonsoalfonsi/eng-spa-real-time-systems-scheduling-context-and-cyclic-executive
Alfonsi, A. [@alfonsoalfonsi] (2021, August 28). [Eng-Spa] Real-Time System: Real-time Task [POST]. The HiVE Blog. @alfonsoalfonsi/eng-spa-real-time-system-real-time-task
Alfonsi, A. [@alfonsoalfonsi] (2021, August 16). [Eng-Spa] Real-Time System: Concept and Context // Sistema de Tiempo Real: Concepto y Contexto [POST]. HiVE Blog. @alfonsoalfonsi/eng-spa-real-time-system-concept-and-context-sistema-de-tiempo-real-concepto-y-contexto
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., Pescina, J., Alfonsi, A. R. y Yánez, R. (2020). Capítulo 2: Micronúcleo de Tiempo Real con Ahorro Energía para el Sistema Sensor Inteligente. En Sensores y Actores Inteligentes Autónomos con Enfoques No Convencionales para la Agricultura de Precisión [Informe Final del Proyecto de Investigación Nº CI-03-020400-1982-17) (pp. 43-83). Consejo de Investigación de la Universidad de Oriente, Venezuela].
References
Referencias
Audsley, N., Burns, A., Richardson, M., Tindell, K., and Wellings, A. (1993). Applying New Scheduling Theory to Static Preemptive Scheduling. Software Engineering Journal, 8(5), 285-292.
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. & 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.
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
Joseph, M. and Pandya, P. (1896). Finding Response Times in Real-Time Systems. The Computer Jornual (British Computing Society), 29(5), 390-395.
https://www.semanticscholar.org/paper/Finding-Response-Times-in-a-Real-Time-System-Joseph-Pandya/f4de2179e263c3ad242ea6521a54fea20d877aa0#:~:text=DOI%3A10.1093/comjnl/29.5.390
Shirvaikar, M. & 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
Figures and Images
Figuras e Imágenes
The image of Home or Title was made by @alfonsoalfonsi using CANVAS with picture by mohamed Hassan on Pixabay
La imagen de Inicio o Título fue realizado por @alfonsoalfonsi usando CANVAS con imagen de
de mohamed Hassan en Pixabay
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 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.