Hello Friends of Hive we continue the series concerning Real Time Systems (RTS), in the framework of topics related to science, research, technology, and innovation.
Hola Amigos de Hive damos 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.
We are developing the Schedulability Analysis and consequently, in the previous post, the System Utilization Based was presented, leaving for this publication the second analysis considered which is the Response Time Based.
Estamos desarrollando el Análisis de Planificabilidad y en consecuencia en el post anterior se presentó el Basado en la Utilización del Sistema, dejando para esta publicación el segundo análisis considerado, que es el Basado en el Tiempo de Respuesta.
As usual, some examples are provided for a better understanding of the content.
Como es costumbre, se entrega un ejemplo para una mejor comprensión del contenido.
2. Analysis based on Response Time.
2. Análisis basado en el Tiempo de Respuesta.
The above test is based on the concept of utilization, where it is verified that the processor demand by the tasks does not exceed a certain threshold.
La prueba anterior está basada en el concepto de utilización, donde se comprueba que la demanda de procesador por parte de las tareas no supera un determinado umbral.
In this section, I will refer to the Response Time Analysis formulated by Joseph and Pandya in 1986, as it is the basis of many algorithms that have succeeded it.
En esta sección, voy a referirme al Análisis basado en el Tiempo de Respuesta formulado por Joseph y Pandya en 1986, por ser base de muchos algoritmos que le han sucedido.
The objective of this analysis is to calculate how much time it costs for a Ti task to be executed in the worst case, taking into account its own Ci and that of other, higher-priority Ti that can be executed at the same time.
El objetivo de este análisis es calcular cuánto tiempo le cuesta a una tarea Ti ejecutarse en el peor caso, teniendo en cuenta su propio Ci y el de otras Ti más prioritarias que puedan ejecutarse al mismo tiempo.
This time is called Ti Response Time and is represented as Ri. Once Ri has been calculated, it will suffice to check that the Response Time remains below the task deadline, i.e., Ri ≤ Di.
A este tiempo se le llama Tiempo de Respuesta de Ti, y se representa como Ri. Una vez calculado Ri, bastará con comprobar que el Tiempo de Respuesta se mantiene por debajo del plazo de la tarea, es decir, Ri ≤ Di.
The above is solved iteratively, by:
Lo anterior se resuelve de forma iterativa, mediante:
The method consists of estimating new Ri values from the values obtained in the previous interaction. The monotonic dependence of the equation on the Ri term guarantees the convergence of the algorithm, as long as the utilization is 100%.
El método consiste en estimar nuevos valores de Ri de los valores obtenidos en la interacción anterior. La dependencia monótona de la ecuación respecto del término Ri garantiza la convergencia del algoritmo, siempre y cuando la utilización sea del 100%.
It starts by assigning an initial value to the response time:
Se inicia al asignar un valor inicial al tiempo de respuesta:
It ends when two consecutive equal values are obtained:
Y finaliza cuando se obtienen dos valores consecutivos iguales:
The Response Time-Based Analysis has properties that make it very interesting:
El Análisis Basado en el Tiempo de Respuesta tiene propiedades que lo hacen muy interesante:
First, it is a Exact Test, i.e., necessary and sufficient.
It does not answer with a yes or no but gives information about which tasks may miss their deadlines and to what extent.
It is valid for any priority assignment algorithm: the set hp(i) collects all tasks of higher priority than Ti, regardless of their ordering.It works the same when Di = Ti and when Di < Ti.
It is very easy to incorporate sporadic tasks, just assuming that the period is the minimum separation between two consecutive activation events.
Finally, it is relatively simple to implement and has a reasonable cost, especially compared to exact utilization-based analysis.
En primer lugar, se trata de una Prueba Exacta, es decir, necesario y suficiente.
No responde con un sí o un no, sino que da información acerca de cuáles son las tareas que pueden perder sus plazos y en qué medida.
Es válido para cualquier algoritmo de asignación de prioridades: el conjunto hp(i) recoge todas las tareas de mayor prioridad que Ti, independientemente de su ordenación.
Funciona exactamente igual cuando Di = Ti y cuando Di < Ti.
Resulta muy sencillo incorporar las tareas esporádicas, sólo asumiendo que el periodo es en realidad la mínima separación entre dos eventos de activación consecutivos.
Por último, su aplicación es relativamente sencilla y tiene un coste razonable, especialmente en comparación con el análisis exacto basado en la utilización.
Let us exemplify the above.
Ejemplifiquemos lo anterior.
Example 1
Ejemplo 1
Let's take the Ti values indicated in Table 1 and perform the Response Time Analysis.
Tomemos los valores de las Ti indicadas en la Tabla 1 y realicemos el Análisis basado en el Tiempo de Respuesta.
Table 1. Temporal characteristics of 3 tasks of Example 1.
Tabla 1. Características temporales de 3 tareas del Ejemplo 1.
First, we do the System Utilization Based Analysis, which we know is a sufficient but not necessary condition of schedulability.
Primero hacemos el Análisis basado en la Utilización del Sistema, el cual sabemos que es una condición suficiente pero no necesaria de planificabilidad.
The result indicates that the processing capacity requested by the Ti can be supplied by the processor, because it meets the condition.
El resultado indica que la capacidad de proceso solicitada por las Ti puede ser suministrada por el procesador, porque cumple la condición.
However, when applying a Cyclic Executive Scheduler we can see from its scheduling diagram (which you can see in Figure 1 of the previous post) that the T3 in its third instance, was about to complete the execution of the missing millisecond when it misses its deadline or period.
Sin embargo, al aplicar un Planificador Ejecutivo Cíclico podemos constatar de su diagrama de planificación (el cual pueden apreciar en la Figura 1 del post anterior) donde se evidencia que la T3 en su tercera instancia, se disponía a completar la ejecución del milisegundo faltante, cuando pierde su plazo o período.
Also, Liu and Layland's condition (Liu and Layland, 1973) is not met. Then, it could be thought that these tasks are not schedulable, not even for the RM Scheduler. Not being able to predict their schedulability, we resort to Response Time Analysis.
Así como también, la condición de Liu y Layland (Liu y Layland, 1973) no se cumple. Entonces, se pudiera pensar que esas tareas no son planificables, ni siquiera para el Planificador RM. Al no poder predecir su planificabilidad, recurrimos al Análisis del Tiempo de Respuesta.
We started to calculate:
Empezamos a calcular:
The above proves that the Ti in Table 1 can be schedulable using other scheduling algorithms, both static and dynamic because their response times are shorter than their completion times.
Lo anterior, es una prueba exacta que las Ti de la Tabla 1 pueden ser planificadas usando otros algoritmos de planificación, como los dinámicos, porque sus tiempos de respuestas son menores que sus plazos de finalización.
Among these dynamic algorithms is the Earliest Deadline First (EDF). The priorities of the tasks are modified, giving higher priority to the tasks that are closer to their Di. A sample of this is presented in the Scheduling Diagram using EDF for the Ti of the Example.
Dentro de estos algoritmos dinámicos está el Earliest Deadline First (EDF). Las prioridades de las tareas van modificándose, proporcionando mayor prioridad a las tareas que tienen más cercano su Di. Muestra de ello se presenta en el Diagrama de Planificación usando EDF para las Ti del Ejemplo.
Figure 1. Diagrama de programación con EDF utilizando las 3 tareas del Ejemplo 1.
Figura 1. Diagrama de Planificación con EDF usando las 3 tareas del Ejemplo 1.
By way of closing
A manera de cierre
In this post, I explained the Schedulability Analysis based on Response Time for RTS.
En este post expliqué el Análisis de Planificabilidad basado en el Tiempo de Respuesta para los STR.
I accompanied it with an example for a better understanding, where the exact nature of the analysis, which places it in a necessary and sufficient test, is made clear. It is worth noting that the critical moment is also applied to this analysis.
Lo acompañé con un ejemplo para una mejor comprensión, donde se pone de manifiesto el carácter exacto del análisis, que lo ubica en una prueba necesaria y suficiente. Vale la pena destacar, que a este análisis también se le aplica el instante crítico.
With the two approaches explained above, you will be able to analyze whether the tasks involved in a system can be scheduled in real-time.
Con los dos enfoques explicados ya podrán analizar si las tareas involucradas en un sistema pueden ser planificadas en tiempo real.
Therefore, in the next post, I will formally address the RM and DM Static Schedulers, respectively.
Por tanto, en el próximo post abordaré formalmente los Planificadores Estáticos RM y DM, respectivamente.
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 8). [Eng-Spa] Real-Time Systems - Scheduling - Schedulability Analysis Based on System Utilization . The HiVE Blog. [POST]. @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. The HiVE Blog. [POST]. @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. The HiVE Blog. [POST]. @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. HiVE Blog. [POST]. @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., 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].
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. & 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.