PDF de programación - Implementación de un Método de Slack Stealing en el Kernel de MaRTE OS

Implementación de un Método de Slack Stealing en el

Kernel de MaRTE OS

Luis A. Díaz1, Francisco E. Páez1,3, José M. Urriza1, Javier D. Orozco2,3,

Ricardo Cayssials2,3

1Universidad Nacional de la Patagonia San Juan Bosco, Puerto Madryn, Argentina,

2Universidad Nacional del Sur, 3CONICET

[email protected]

Resumen. Este trabajo presenta la implementación de un método Slack Stealing
dentro del kernel del sistema operativo de tiempo real MaRTE OS. Existe en la
actualidad, una necesidad de ampliar la funcionalidad de los sistemas operativos
de tiempo real, para ofrecer la planificación de nuevos requerimientos
heterogéneos, conservando la predictibilidad que deben poseer las tareas de
tiempo real.

Palabras Claves: Sistemas de Tiempo Real, Slack Stealing, MaRTE OS,
Planificabilidad.

1.

Introducción

En la disciplina de los Sistemas de Tiempo Real (STR), la administración del tiempo
ocioso es de vital importancia para lograr que un sistema pueda ser heterogéneo en el
tipo de tareas de tiempo real o no a ejecutar. Este tipo de administración se logra
implementando algún tipo de método o técnica que permita lograrlo. El método Slack
Stealing (SS) es uno de estos, tal vez el mejor de ellos. Consecuentemente, numerosos
sistemas informáticos industriales requieren de un sistema operativo de tiempo real
(SOTR) como MaRTE OS y contar con métodos que permitan ejecutar tareas de no
tiempo real, sin afectar al STR. En muchos casos, tareas como alarmas, ahorro de
energía en dispositivos móviles, robustez en la ejecución de las tareas, tolerancia a los
fallos mediante re-ejecución de tareas, etc., son modeladas de esta forma. Sin
embargo, este tipo de tarea puede requerir de algún tipo de calidad de servicio (QoS)
distinto, como puede ser una atención prioritaria. Este trabajo permite aportar una
herramienta tangible para que los diseñadores de informática industrial puedan
utilizarla en el diseño de sus sistemas.

En las últimas décadas los lenguajes de programación y los sistemas operativos
(SO) han evolucionado a fin de poder desarrollar aplicaciones con características de
Tiempo Real (TR). El lenguaje de programación ADA y las extensiones para TR del
estándar POSIX, pueden tomarse como referencias en esta tendencia. Poco a poco, la

3º Simposio Argentino de Informatica Industrial, SII 201443 JAIIO - SII 2014 - ISSN: 2313-9102 - Página 13 industria ha ido incorporando estos avances sin que los usuarios finales lo perciban,
en por ejemplo PLCs, controladores industriales, etc.

Sin embargo, diversos aspectos del problema aún no han sido explorados
profundamente y uno de estos, es la de conseguir niveles óptimos en el desempeño de
la planificación de sistemas heterogéneos en termino de recursos físicos y lógicos. En
lo que sigue, se denominará Sistema de Tiempo Real Heterogéneo (STRH) a un
sistema compuesto por un subsistema de TR (sTR) y otro de no TR (sNTR). En
particular, debido a que el sTR posee restricciones temporales que resultan
insoslayables para que el funcionamiento global del sistema resulte aceptable, se
asume que un sistema de este tipo es un es un STR compuesto por un sTR y un sNTR.
Hoy en día, se utilizan diversos métodos específicos para tratar STRH en algunos
SOTR. Entre los más comunes se encuentran los Métodos Servidores (MS) [1, 2, 3, 4,
5], Slack Stealing (SS) [6, 7, 8, 9], Dual Priority (DP) [10]. Sin embargo, algunos de
estos métodos, no resultan eficientes a
implementación y
consecuentemente no siempre pueden ser utilizados debido a restricciones de costo,
escala y disponibilidad, entre otras.

la hora de su

La principal ventaja que poseen los métodos basados en SS frente a otros métodos,
es que son los únicos que permiten detectar y aprovechar el tiempo ocioso del sistema
en su totalidad. A pesar de ello, muchos de estos poseen un elevado Costo
Computacional (CC) y consecuentemente no pueden ser utilizados en algunas
aplicaciones reales. No obstante, en los últimos años se ha logrado una reducción en
el CC de su implementación y existen diversos trabajos de investigación que están
enfocados en ese sentido [11, 12].

En este trabajo se ha implementado un método SS en el kernel del SOTR
MaRTE OS, más precisamente en el planificador de tareas, como una política más de
planificación, dando soporte a la atención del sNTR.

El presente trabajo se organiza de la siguiente manera. A continuación se realiza
una breve introducción a los STR y a la planificación heterogénea. En la sección 2 se
selecciona un SOTR. En la sección 3, se presenta el algoritmo SS a utilizar. En la
sección 4 se presenta la implementación efectuada. En la sección 5 se realiza el
análisis de eficiencia. Finalmente, en la sección 6 se presentan las conclusiones y
trabajos futuros.

Introducción a los Sistemas de Tiempo Real

1.1.
La definición de STR más aceptada, es la realizada por Stankovic [13]: “En los STR
los resultados no sólo deben ser correctos aritmética y lógicamente sino que, además,
deben producirse antes de un determinado tiempo, denominado vencimiento.”

La ejecución de una tarea por fuera de sus constricciones puede ser inaceptable y
dicha inaceptabilidad puede ser local a la tarea o global. Esta consideración permite
clasificar los STR en tres tipos:

 Duros: No admiten que ninguna tarea pierda su vencimiento. Esta condición es

local y global.

 Blandos: Permiten que se pierdan algunos vencimientos. En este contexto la

inaceptabilidad local puede no ser global.

3º Simposio Argentino de Informatica Industrial, SII 201443 JAIIO - SII 2014 - ISSN: 2313-9102 - Página 14  Firmes: Sólo permiten una cantidad acotada de pérdidas. Como en el caso pre-

vio, la inaceptabilidad local puede no ser global.

En los STR duros, la pérdida de un vencimiento en una tarea es inaceptable y en
general puede tener consecuencias adversas sobre todo el funcionamiento del sistema.
Por ello se debe garantizar que todas las tareas finalicen antes de su vencimiento. Para
ello es necesario analizar, en tiempo de diseño, la planificabilidad del sistema
mediante procedimientos analíticos denominados, tests de planificabilidad. Si el test
es exitoso, a estos sistemas se los denomina planificables y se dice que han cumplido
con todas sus constricciones de tiempo. Las primeras contribuciones en este sentido
fueron realizadas por Liu y Layland [14] y han sido mejoradas en trabajos posteriores.
Un algoritmo de planificación es un conjunto de reglas que determinan qué tarea
va a ser ejecutada en un instante determinado. Los algoritmos de planificación pueden
ser clasificados en estáticos y dinámicos [15]. Los planificadores dinámicos, son los
más utilizados y están basados en asignar una prioridad a cada tarea. Si la prioridad
cambia en tiempo de ejecución, es dinámica; caso contrario, es fija.

En la planificación por prioridades fijas, las reglas más utilizadas son Rate
Monotonic (RM) y Deadline Monotonic (DM). En prioridades dinámicas, las más
utilizadas son Earliest Deadline First (EDF) y Least Laxity First (LLF). Además,
existe un método de planificación que combina prioridades fijas y dinámicas,
denominado Dual Priority (DP). Este trabajo se centra exclusivamente en las
disciplinas de prioridades fijas y en STR de tipo duro.

Planificadores de Tiempo Real Heterogéneos Apropiativos

1.2.
Generalmente, un planificador heterogéneo, debe garantizar las restricciones del sTR
y proveer algún nivel en la QoS para el sNTR. Ello requiere una administración
eficiente de los recursos del sistema con el objeto de no sobredimensionar
innecesariamente la plataforma de ejecución con la intención de mejorar el
desempeño del sNTR sin afectar al sTR. A fin de trabajar con un modelo restrictivo, se
considerará en adelante que el sTR es del tipo duro. Consecuentemente, debe contarse
con alguna técnica o servicio en tiempo de ejecución, que maximice la utilización de
los recursos, maximizando el aprovechamiento de los tiempos ociosos que deja el sTR
duro. A continuación se realiza una breve introducción a los métodos desarrollados
para planificadores heterogéneos:
 Servicio en Segundo Plano (Background Service - BS): Su principio de
funcionamiento es ejecutar el sNTR cuando las tareas del sTR no se están
ejecutando. Su mayor desventaja es no poder garantizar ningún tipo de QoS para
las tareas del sNTR.

 Servidores: Consiste en implantar en el sTR, una tarea servidora, con una
determinada prioridad y utilizar el tiempo de ejecución de la misma para procesar
el sNTR. Este tipo de método, no logra utilizar todo el tiempo ocioso, por lo cual
también debe utilizar un BS y aguardar a que se instancie nuevamente la tarea
servidora, para proseguir con las tareas del sNTR. Entre los Métodos Servidores
clásicos para planificación de sNTR, se pueden mencionar: Polling Server [5],

3º Simposio Argentino de Informatica Industrial, SII 201443 JAIIO - SII 2014 - ISSN: 2313-9102 - Página 15 Deferred Server [5], Priority Exchange Server [3], Sporadic Server [4] y Total
Bandwidth Server [2].

 Slack Stealing: Consiste en adelantar una fracción del tiempo ocioso, de manera tal
que se pueda ejecutar el sNTR, retrasando las ejecuciones de las tareas del sTR al
límite de su planificabilidad. En la actualidad existen diversos métodos que aplican
esta técnica, algunos lo hacen en tiempo de ejecución (on-line), otros lo pre-
calculan en el tiempo de inicialización (off-line); algunos lo rea