[Eng-Spa] Real-Time Systems - Scheduling - Schedulability Analysis Based on System Utilization
Hello, Friends of Hive a pleasure to be with you presenting topics of interest in science, research, technology, and innovation, with the series referred to the Real Time Systems (RTS).
Hola Amigos de Hive un gusto estar con ustedes presentándoles temas de interés de la ciencia, investigación, tecnología e innovación, con la serie referida a los Sistemas de Tiempo Real (STR).
In the previous post we had gone into the subject with Scheduling, where I highlighted an important element, which allows knowing if the tasks comply with the time constraints of the system under development in any situation.
En el post anterior habíamos entrado en materia con la Planificación, donde destaqué un elemento importante, que permite conocer si las tareas cumplen con las restricciones temporales del sistema en desarrollo en cualquier situación.
The concept belongs to the Schedulability Analysis. Therefore, I will develop two approaches that are widely known in RTS, and their explanation will be accompanied by examples to facilitate their understanding. These are:
Concepto que pertenece al Análisis de Planificabilidad. Por tanto, desarrollaré dos enfoques ampliamente conocida en los STR y su explicación irá acompañada de ejemplos que faciliten su comprensión. Estos son:
1. Analysis based on System Utilization.
2. Analysis based on Response Time.
1. Análisis basado en la Utilización del Sistema.
2. Análisis basado en el Tiempo de Respuesta.
Next, I will develop Analysis based on System Utilization. And, in the subsequent publication, I will dedicate it to the Analysis based on Response Time.
A continuación desarrollaré Análisis basado en la Utilización del Sistema. Y, en la siguiente publicación la dedicaré al Análisis basado en el Tiempo de Respuesta.
1. Analysis based on System Utilization.
1. Análisis basado en la Utilización del Sistema.
In principle, it could be thought that the condition for a system with N tasks to be schedulable is that all tasks meet their deadlines, i.e., that they do not require more computation time than is available.
En principio, podría pensarse que la condición para que un sistema con N tareas sea planificable, es que todas las tareas cumplan sus plazos, es decir, que éstas no requieran más tiempo de cómputo del disponible.
Then at first, there is the Utilization Factor of Ti, which represents the fraction of processor time used by Ti, given by:
Entonces en un primer momento está el Factor de Utilización de Ti, que representa la fracción tiempo del procesador utilizada por Ti., dado por:
The sum of the Ti utilization factors is known as the System or Processor Utilization Factor (U), given by:
La suma de los factores de utilización de las Ti es conocida como el Factor de Utilización del Sistema o Procesador (U), dado por:
Then, U is the maximum fraction of processor time possibly demanded by the set of tasks in an interval. That is, if U is 100%, then the processing capacity requested by all Ti per unit time cannot exceed that 100% of the time, represented by:
Entonces, U es la máxima fracción de tiempo de procesador posiblemente demandada por el conjunto de tareas en un intervalo. Es decir, si U es el 100%, entonces la capacidad de proceso solicitada por todas las Ti por unidad de tiempo no puede superar ese 100% del tiempo, representado por:
However, this U limit can only be reached in some cases, when the execution of all tasks fits perfectly into all possible phases, i.e. the periods of the tasks are uniformly harmonic.
Sin embargo, este límite de U sólo se puede alcanzar en algunos casos, cuando la ejecución de todas las tareas encaja perfectamente en todas las posibles fases, esto es, los periodos de las tareas son uniformemente armónicos.
A system is uniformly harmonic if the period of each task is an exact divisor of the larger periods. Even partial harmonicity (only in some tasks) can significantly increase the utilization of the system.
Un sistema es uniformemente armónico si el periodo de cada tarea es un divisor exacto de los periodos más grandes. Incluso la armonicidad parcial (sólo en algunas tareas) permite incrementar notablemente la utilización del sistema.
Example 1
Ejemplo 1
Let's consider the data in Table 1 and let's calculate the System Utilization.
Consideremos los datos de la Tabla 1 y vamos a calcular la Utilización del Sistema.
Table 1. Temporal characteristics of 3 tasks of Example 1.
Tabla 1. Características temporales de 3 tareas del Ejemplo 1.
Applying the previous inequation we are left with:
Aplicando la inecuación anterior nos queda:
This indicates that the processing capacity requested by the Ti can be supplied by the processor. And, as developed in previous post a Cyclic Executive Scheduler could be applied.
Lo que indica que la capacidad de proceso solicitada por las Ti puede ser suministrada por el procesador. Y, como se desarrolló en el post anterior, se podría aplicar un Planificador Ejecutivo Cíclico.
Example 2
Ejemplo 2
Now, let's calculate the System Utilization by taking the data from Table 2 and plot a scheduling diagram.
Ahora, calculemos la Utilización del Sistema tomando los datos de la Tabla 2 y graficamos un diagrama de planificación.
Table 2. Temporal characteristics of 3 tasks of Example 2.
Tabla 2. Características temporales de 3 tareas del Ejemplo 2.
We calculate U:
Calculamos U:
The result indicates that the processing capacity requested by the Ti can be supplied by the processor.
El resultado indica que la capacidad de proceso solicitada por las Ti puede ser suministrada por el procesador.
Let's see what happens when applying the scheduler we know so far. Figure 1 shows that T3, its third instance was about to execute the millisecond to complete, but loses its deadline or period.
Veamos que sucede al aplicar la planificación que hasta ahora conocemos. En la Figura 1 se manifiesta que la T3, su tercera instancia se disponía a ejecutar el milisegundo para completarse, pero pierde su plazo o período.
Figure 1. Scheduling Diagram with the Cyclic Executive to the tasks of Example 2.
Figura 1. Diagrama de Planificación con el Ejecutivo Cíclico a las tareas del Ejemplo 2.
Thus, checking that U is less than 100% is not a sufficient guarantee that the system will meet all its deadlines. It is important to note, that the Cyclic Executive was applied, but there are priority-based algorithms that can provide admissible scheduling.
Así pues, comprobar que U sea inferior al 100% no es garantía suficiente de que el sistema vaya a cumplir todos sus plazos. Es importante señalar, que se aplicó el Ejecutivo Cíclico, pero están los algoritmos basados en prioridades que posiblemente puedan ofrecer una planificación admisible.
Schedulability Analysis for Rate Monotonic Scheduler
Análisis de Planificabilidad para el Planificador Rate Monotonic
In 1973, Liu and Layland formulated the sufficient schedulability condition of an RTS with the constraints for the Rate Monotonic (RM) Static Scheduler, i.e.: expulsive scheduler, with higher priority assignment to more frequent tasks, periodic and independent tasks, and deadlines equal to periods.
En 1973, Liu y Layland formularon la condición suficiente de planificabilidad de un STR con las restricciones para el Planificador Estático Rate Monotonic (RM), es decir: planificador expulsivo, con asignación de mayor prioridad a las tareas más frecuentes, tareas periódicas e independientes y plazos iguales a los periodos.
For a system with i tasks, numbered from 1 to N, this condition is as follows:
Para un sistema con i tareas, numeradas de 1 to N, esta condición es la siguiente:
U(N) represents the maximum utilization so that the schedulability of a system of N tasks is guaranteed. This function is decreasing as N increases. It is easy to check that U(1)=1, which represents that a single task is schedulable as long as it does not require more than 100% of U. For arbitrarily large values of N, U(N) tends to ln(2) , approximately 69%.
U(N) representa la utilización máxima para que la planificabilidad de un sistema de N tareas esté garantizada. Esta función es decreciente según aumenta N. Es fácil comprobar que U(1)=1, lo que representa que una sola tarea es planificable mientras no requiera más del 100% de U. Para valores arbitrariamente grandes de N, U(N) tiende a ln(2), aproximadamente 69%.
Example 3
Ejemplo 3
Going back to the tasks in Table 1, let's do the Schedulability Analysis based on Liu and Layland's System Utilization.
Volviendo a las tareas de la Tabla 1, hagamos el Análisis de Planificabilidad basado en la Utilización del Sistema de Liu and Layland.
Thus, the following is true:
Entonces, se cumple:
And it can be schedulability with RM.
Y puede ser planificable con RM.
But this does not mean that if a system has a higher utilization it cannot be schedulable. This is a sufficient but not necessary condition for schedulability.
Pero ello no significa que si un sistema tiene una mayor utilización no pueda ser planificable. Esta representa una condición suficiente pero no necesaria de planificabilidad.
It is worth noting that if the task periods are uniformly harmonic the system can be schedulable. The pointed out is presented in Example 2 of previous post where U=0.86, however, is schedulable.
Vale la pena destacar, que si los periodos de las tareas son uniformemente armónicos el sistema puede ser planificable. Lo señalado se presenta en el Ejemplo 2 del post anterior donde U=0,86, sin embargo, es planificable.
To conclude, this Schedulability Analysis is based on the concept of the Critical Instant for a Ti, which corresponds to the moment that the activation occurs with a worst-case response time, also defined by Liu and Layland:
Para terminar, este Análisis de Planificabilidad se basan en el concepto del Instante Crítico para una Ti, que corresponde al momento que se produce la activación que tiene como tiempo de respuesta el de peor caso, también definido por Liu y Layland:
El Instante Crítico para una tarea se produce cuando se activa simultáneamente a la activación de todas las tareas de prioridad superior.
El Instante Crítico para una tarea se produce cuando se activa simultáneamente a la activación de todas las tareas de prioridad superior.
By way of closing
A manera de cierre
In this post I developed what is related to the Schedulability Analysis of Real-Time Systems, emphasizing the Analysis based on System Utilization.
En este post desarrollé lo relacionado con el Análisis de Planificabilidad de los Sistemas de Tiempo Real, haciendo énfasis el Análisis basado en la Utilización del Sistema.
I accompanied it with examples for a better understanding, where the outstanding cases of this type of analysis were highlighted.
Lo acompañé de ejemplos para una mejor comprensión, donde se destacaron los casos resaltantes de este tipo de análisis.
Because of its maturity within the area of RTS, Liu and Layland's schedulability test was explained emphasizing the sufficient but not necessary condition of schedulability, as well as, the concept of the Critical Instant.
Por su madurez dentro del área de los STR, se explicó la prueba de planificabilidad de Liu y Layland enfatizando la condición suficiente pero no necesaria de planificabilidad, así como también, el concepto del Instante Crítico.
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]. https://hive.blog/hive-196387/@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]. https://hive.blog/hive-196387/@alfonsoalfonsi/eng-spa-real-time-system-real-time-task
Alfonsi, A. [@alfonsoalfonsi] (2021, September 30). [Eng-Spa] Real-Time Systems: Scheduling - Context and Cyclic Executive. The HiVE Blog. [POST]. https://hive.blog/hive-196387/@alfonsoalfonsi/eng-spa-real-time-systems-scheduling-context-and-cyclic-executive
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 Jornoal (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 Home or Title image was made by @alfonsoalfonsi using CANVAS with a PxHere images
La imagen de Inicio o Título fue realizado por @alfonsoalfonsi usando CANVAS con imagen de PxHere
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.
https://twitter.com/lfonsi3/status/1446582802699407360?s=20
It is a lot to take at once, but It was informative. !discovery 20
Hi, @juecoree thanks for reading my post and your comment. We are in communication.
This post was shared and voted inside the discord by the curators team of discovery-it
Join our community! hive-193212
Discovery-it is also a Witness, vote for us here
Delegate to us for passive income. Check our 80% fee-back Program
Thank you @discovery-it for your support.
Your content has been voted as a part of Encouragement program. Keep up the good work!
Use Ecency daily to boost your growth on platform!
Support Ecency
Vote for Proposal
Delegate HP and earn more
Thank you @ecency for supporting this post. We are moving forward.
Thanks for your contribution to the STEMsocial community. Feel free to join us on discord to get to know the rest of us!
Please consider supporting our funding proposal, approving our witness (@stem.witness) or delegating to the @stemsocial account (for some ROI).
Please consider using the STEMsocial app app and including @stemsocial as a beneficiary to get a stronger support.
Hi, @steemstem thanks for the support. We continue to publish content, thank you
Has sido votado por
PROYECTO ENLACE
'Conectando Ideas y Comunidades'
PROYECTO ENLACE es un proyecto de curación de habla hispana enfocado en recompensar contenido de calidad y apoyar autores en su proceso de crecimiento en HIVE.
Creemos y apostamos por el futuro de esta gran plataforma, y estamos muy emocionados de poder hacerla crecer junto a esta comunidad. Así que te invitamos a usar nuestra etiqueta ENLACE y estar atento a todas las actividades que tenemos preparadas y que estaremos publicando en breve.
¿QUIERES AUTOMATIZAR TUS GANANCIAS DE CURACIÓN? SE PARTE DEL PROYECTO ENLACE APOYANDO A NUESTRO TRAIL EN HIVE.VOTE INGRESA AQUÍ PARA CONCOCER LOS DETALLES.
¿QUIERES INVERTIR ENLACE? DESCUBRE COMO HACERLO Y GENERAR INGRESOS DE FORMA SEMANAL MEDIANTE TU DELEGACIÓN DE HP AQUÍ TE EXPLICAMOS COMO.
Te invitamos a participar en nuestro servidor de Discord: https://discord.gg/3S9y7BbWfS
Atentamente
EQUIPO ENLACE 2021
Hola @enlace gracias por apoyar este post.
Congratulations @alfonsoalfonsi! You have completed the following achievement on the Hive blockchain and have been rewarded with new badge(s) :
Your next target is to reach 9000 upvotes.
You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOPHi @hivebuzz thank you.
De nada @alfonsoalfonsi 😊👍
Apóyenos también y vote por nuestro testigo.
Recibirá una insignia adicional y un voto más fuerte de nuestra parte cuando le notifiquemos.