Hello Friends of Hive and appreciated readers of topics that I publish, without them it would not be possible to enjoy the technologies and applications that we usually use and applaud. Particularly, the one I am going to develop is still listed as open research.
Hola Amigos de Hive y apreciados lectores de los temas que publico, que sin ellos no sería posible disfrutar de las tecnologías y aplicaciones que habitualmente utilizamos y aplaudimos. Particularmente, la que voy a desarrollar sigue catalogada como una investigación abierta.
I dedicate this post to an important and impactful topic in the world of Real-Time Systems such as Slack Time (ST).
Dedico este post a un tema importante y de impacto en el mundo de los Sistemas de Tiempo Real como es el Tiempo Ocioso (ST: Slack Time).
Introduction / Introducción
The world of RTS has borne fruit as a result of formal studies and findings in public and private research centers, where open research topics are addressed in a transdisciplinary manner. So much so, and as expected, one of them is the management of the time in which a processor is active, either executing programming units (set of codes that are related for a purpose) or when it is not. Recall that:
El mundo de los STR ha dado frutos producto de los estudios y hallazgos formales que se han dado en centros de investigación, públicos y privados, donde se abordan transdisciplinariamente temas abiertos de investigación. Tanto es así, y como es de esperarse, una de ellas es el manejo del tiempo en el cual está activo un procesador, ya sea ejecutando unidades de programación (conjunto de códigos que se relacionan para un fin) o cuando no lo está. Recordemos que:
In Real-Time Systems (RTS), it is not enough that the actions of the system are logically correct, but they must also occur within a time interval. This is because the system is connected to an external process from which it receives stimuli that appear in unpredictable instants of time, to which it must respond quickly enough to prevent it from evolving to an undesirable state.
En los Sistemas de Tiempo Real (STR), no es suficiente que las acciones del sistema sean correctas lógicamente, sino, que además, deben producirse dentro de un intervalo de tiempo, esto se debe a que el sistema está conectado a un proceso externo del cual recibe estímulos, que aparecen en instantes de tiempo no predecibles, a los cuales debe responder con suficiente rapidez, para evitar que evolucione a un estado indeseable.
The above definition, still in force, was established by Young (1982) and Stankovic (1988) and has been paraphrased by many authors, including myself.
La anterior definición, aun en vigencia, fue establecida por Young (1982) y Stankovic (1988) parafraseada por muchos autores, al cual me incluyo.
These programming units in an RTS are formed by a set of tasks Ti where i is the identification of the task and its definition:
Estas unidades de programación en un STR están formadas por un conjunto de tareas Ti donde i es la identificación de la misma, y su definición:
It is an executable entity Ti, consisting of a set of instances τi,k.
Es una entidad ejecutable Ti, formada por un conjunto de instancias τi,k.
These instances are executed by the processor in a determined time, and between one and another instance of the same or different tasks, there are gaps of time where the processor is still active but does not execute instances. Well, this characteristic of the RTS is called Slack Time (ST).
Estas instancias son ejecutadas por el procesador en un lapso determinado, y entre una y otra instancias de la misma tarea o diferentes, se presentan espacios de tiempo donde el procesador sigue activo, pero no ejecuta instancias. Pues bien, esta característica de los STR se le llama Tiempo Ocioso (ST: Slack Time).
Definition / Definición
Some studies have observed and verified that the Ci,k of Ti in computational applications can vary up to 87% with respect to their measured WCET (reference data).
Algunos estudios han observado y comprobado que los Ci,k de Ti en las aplicaciones computacionales pueden variar hasta 87% con respecto a sus WCET medidos (dato de referencia).
In addition, the time from the completion of an instance of Ti until its completion deadline Di the processor may not be not executing another task.
Además, el tiempo desde la finalización de una instancia de Ti hasta su plazo de finalización Di el procesador puede, no estar no ejecutando otra tarea.
Figure 1. ST due to WCET (STWCET) and, D (STD)
Figura 1. ST debido al WCET (STWCET) y D (STD)
Then, the ST, (Shirvaikar & Elbert, 2018; Butazzo, 2011; Hwang, et al. 2011; Chantem et al., 2009; Dertouzoz & Mok, 1989), is oriented to satisfy slack when an instance τi,k, does not consume its WCETi, given by:
Entonces, el ST, (Shirvaikar & Elbert, 2018; Butazzo, 2011; Hwang, et al. 2011; Chantem et al., 2009; Dertouzoz & Mok, 1989), está orientado a satisfacer la holgura cuando una instancia τi,k, no consume su WCETi, dado por:
For the purposes of the paper this ST will be called ST due to the WCET (STWCET), it is presented in Figure 1 and explained below.
Para efectos del trabajo éste ST será llamado ST debido al WCET (STWCET), se presenta en la Figura 1 y se explica a continuación.
And the ST due to Di is given by:
Y el ST debido al Di está dado por:
It is worth mentioning, looking at Figure 1, the temporal parameters of Ti, such as C, D, P and r were explained in a previous post, I invite you to refer to it for more information.
Vale la pena mencionar, observando la Figura 1, los parámetros temporales de Ti, como C, D, P y r fueron explicados en un post anterior, les invito a acudir a él para más información.
The parameter α is a factor representing the speed of the processor. When it is equal to one it means that it works at maximum speed.
El parámetro α es un factor que representa la velocidad del procesador. Cuando es igual a uno significa que trabaja a máxima velocidad.
Use of the ST / Utilización del ST
Scheduling Real-Time Tasks
Planificar Tareas de Tiempo Real
There are real-time schedulers that have functionalities capable of improving system performance by using the ST generated by the Ti to attend others, which are already planned and waiting to be executed, and minimize their waiting time, without violating their temporal restrictions.
Hay planificadores de tiempo real que tienen funcionalidades capaces de mejorar el desempeño del sistema al utilizar los ST generados por las Ti para atender otras, que ya planificadas están esperando ser ejecutada y minimizan su tiempo de espera, sin violar sus restricciones temporales.
Also, these schedulers cater for Aperiodic or Sporadic Tasks, accompanying the Periodic Tasks, without violating their temporal constraints. These are called ST Servers.
También, estos planificadores atienden a las Tareas Aperiódicas o Esporádicas, acompañando a las Tareas Periódicas, sin violar sus restricciones temporales. A estos se les denomina Servidores de ST.
Many algorithms for this purpose attempt to predict the duration of the current instance of Ti-based on the characteristics of the average Cimedio. This decision typically depends on the behavior of previous instances of Ti.
Muchos algoritmos, para este propósito, intentan predecir la duración de la instancia actual de la Ti basándose en las características del Cimedio. Esta decisión depende típicamente del comportamiento de las instancias anteriores de Ti.
The prediction mechanism can be very simple (such as storing the Ciaverage of each Ti, or more complex such as exploiting probabilistic information and using feedback algorithms. The success of this kind of methods relies on deciding correctly the behavior of the Ti.
El mecanismo de predicción puede ser muy simple, como guardar el Ci medio de cada Ti, o más complejo como explotar la información probabilística y uso de reguladores realimentados. El éxito de esta clase de métodos confía en decidir correctamente el comportamiento de la Ti.
Then distributing and serving the ST is an operation of real-time schedulers such as the well-known Least Laxity Firts (LLF) of Dertouzoz & Mok (1989), or the Least Slack Time first (LST) of Alsheikhy et al. (2016). Currently, Alsheikhy (2021) manages the dynamic approach to minimize the overhead and response time in scheduling real-time periodic tasks.
Entonces distribuir y servir el ST es una operación de planificadores de tiempo real como el conocido Least Laxity Firts (LLF) de Dertouzoz & Mok (1989), o el Least Slack Time first (LST) de Alsheikhy et al. (2016). Actualmente, Alsheikhy (2021) maneja el enfoque dinámico para minimizar la sobrecarga y el tiempo de respuesta en la programación tareas periódicas de tiempo real.
By way of closing
A manera de cierre
In this post I presented a characteristic of the systems in full execution such as the times in which the processors do not execute tasks, since they are waiting lapses between the execution of one instance and another.
En este post presenté a una característica de los sistemas en plena ejecución como lo son los tiempos en los cuales los procesadores no ejecutan tareas, ya que son lapsos de espera entre la ejecución de una instancia y otra.
I defined Idle Time by covering WCET and completion deadlines and how they are used by real-time schedulers to improve system performance. In addition, to be able to schedule Aperiodic or Sporadic Tasks, along with Periodic.
Definí al Tiempo Ocioso cubriendo lo referente al WCET y los plazos de finalización y cómo son utilizados por planificadores de tiempo real para mejorar el desempeño del sistema. Además, de poder planificar las Tareas Aperiódicas o Esporádicas, junto a la Periódicas.
Today, this issue is important because of the concurrent and distributed nature to which computing systems have to respond in a range of multiprocessor and mobile computing.
Hoy en día, este tema es importante, debido a la naturaleza concurrente y distribuida a la cual los sistemas de computación tienen que dar respuestas en una gama de multiprocesadores y computación móvil.
See you soon, I hope the reading has been enriching.
Nos vemos pronto, espero que la lectura haya sido enriquecedora.
Thank you for your time and comments.
Gracias por su tiempo y comentarios.
References / Referencias
Alsheikhy, A. (2021). Dynamic approach to minimize overhead and response time in scheduling
periodic real-time tasks. International Journal of Advanced and Applied Sciences, 8(4), 75-8.
https://doi.org/10.21833/ijaas.2021.04.009
Alsheikhy, A., Elfouly, R., Alharthi, M., Ammar, R. & Alshegaifi, A. (2016). An effective real-time dynamic scheduling approach for periodic tasks. International Journal of Computing, Communications and Instrumentation Engineering, 3(2): 279-383. https://doi.org/10.21833/ijaas.2021.04.009
Butazzo, G. (2011). Hard Real-Time Computing Systems: Predictable Scheduling Algoritms and Applications (3rd ed.). Springer Science/Business Media.
https://link.springer.com/book/10.1007%2F978-1-4614-0676-1
Chantem, T. T., Hu, X. S. & Lemmon, M. D. (2009). Generalized Elastic Scheduling for Real-Time Tasks. IEEE Transactions on Computers, 58(4), 480-495.
Dertouzoz, M. L. & Mok, A. K. (1989). Multiprocessor On-Line Scheduling of Hard-Real-Time Task. IEEE Trans. Software Engineering, 15(12), 1497-1506.
https://doi.org/10.1109/32.58762
Hwang, M., Choi, D. & Kim, P. (2011). Least slack time rate first: An efficient scheduling algorithm for pervasive computing environment. Journal of Universal Computer Science, 17(6), 912–925.
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.666.4779&rep=rep1&type=pdf
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
Young, S. J. (1982). Real Time Languages Desing and Developments. Ellis Horwood Limited.
https://dl.acm.org/doi/abs/10.5555/69567
Figures and Images / Figuras e Imágenes
The Title image was made by 
La imagen del Título fue realizado por
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.