Definiciones de atributos temporales
5
10
15
0
Modelo de tareas simple
Dado un programa arbitrariamente complejo, no es tarea fácil analizarlo para poder predecir su comportamiento en el peor caso.
Por tanto, resulta imprescindible imponer algunas restricciones en la estructura de los programas concurrentes de tiempo real.
Se presenta un modelo muy simple que permitirá describir algunos esquemas de planificación estándar. La idea es expandirlo posteriormente.
Modelo de tareas simple
Se supone que la aplicación está compuesta por un conjunto fijo de tareas y se conoce en tiempo de ejecución (estático)
Todas las tareas son periódicas, con periodos conocidos
Las tareas son completamente independientes unas de otras (e interrumpibles en cualquier punto del código). No se comunican ni sincronizan entre ellas.
Los plazos de respuesta de todas las tareas son iguales a sus periodos (o sea, cada tarea debe acabar antes de ser ejecutada nuevamente)
El tiempo de ejecución máximo (en un único procesador) de cada tarea es conocido y fijo
Todas las sobrecargas del sistema (tales como cambio de contexto) son ignoradas
Modelo de tareas simple
Este conjunto de suposiciones puede ser realista en algunos casos de sistemas de tiempo real. Ej.:una aplicación de control simple con un conjunto fijo de sensores y actuadores, un entorno bien definido al igual que los requisitos de procesamiento (Stankovic et al.).
Parámetros de planificación
N Número de tareas en el sistema
T Período de activación de una tarea
C Tiempo de ejecución máximo de una tarea
D Plazo de respuesta de una tarea
R Tiempo de respuesta máximo de una tarea
P Prioridad
En el modelo de tareas simple, para cada tarea ?i:
Se trata de asegurar
Hiperperíodo
En el modelo de tarea simple se denomina hiperperíodo del sistema a
El comportamiento temporal se repite cada hiperperíodo
Planificación con ejecutivos cíclicos
Es el algoritmo de planificación más utilizado para construir el esqueleto de sistemas de control embebidos (no existe un sistema operativo propiamente dicho)
La aplicación se divide en una serie de procedimientos, el ejecutivo es una tabla de llamada a los mismos, donde cada procedimiento representa parte del código de un proceso.
La complejidad de las aplicaciones embebidas ha ido aumentando y en la actualidad es normal que requieran servicios como multitarea avanzada o comunicaciones (provistos típicamente por un sistema operativos en tiempo real). Sin embargo se siguen usando en aplicaciones sencillas o con restricciones temporales muy estrictas
Planificación con ejecutivo cíclico
Planificación con ejecutivos cíclicos
Si todas las tareas son periódicas, puede confeccionarse un plan de ejecución fijo (offline), almacenado en una tabla. El despacho de las mismas es una simple búsqueda en la tabla
Se trata de un esquema que se repite cada ciclo principal
Cada ciclo principal se divide en ciclos secundarios, con periodos
En cada ciclo secundario se ejecutan las actividades correspondientes a determinadas tareas
Ejemplo
Ejemplo
Propiedades
No hay concurrencia en la ejecución
Cada ciclo secundario es una secuencia de llamadas a procedimientos
Los procedimientos comparten un espacio de direcciones, por lo que pueden pasar datos entre ellos
No hace falta usar mecanismos de exclusión mutua porque es imposible el acceso concurrente
Todos los periodos de las tareas deben ser múltiplos del periodo de los ciclos secundarios
Puede ser necesario usar períodos mas cortos de lo necesario
No hace falta analizar el comportamiento temporal
El sistema es correcto por construcción
Problemas
Dificultad para incorporar tareas esporádicas
Dificultad en la construcción del plan cíclico
Si los períodos son de diferentes órdenes de magnitud el número de ciclos secundarios se hace muy grande
Puede ser necesario partir una tarea (alto tiempo de ejecución) en varios procedimientos
En el caso más general, es un problema NP duro
Poco flexible y difícil de mantener
Cada vez que se cambia una tarea hay que rehacer toda la planificación
Programación basada en procesos
Un enfoque alternativo es soportar la ejecución de procesos de forma directa (como es norma en los sistemas operativos de propósito general) y,
Determinar cuál es el proceso que deberá ejecutarse en cada instante de tiempo, mediante uno o más atributos de planificación.
Programación basada en procesos
Un proceso puede estar en varios estados (suponiendo que no exista comunicación entre ellos)
Programación basada en procesos
Los procesos ejecutables se despachan para su ejecución de acuerdo con un esquema de planificación
Prioridades fijas (FPS, por Fixed-Priority Scheduling)
Primero el más urgente (EDS, por Earliest Deadline First)
Primero el más valioso (VBS, por Value-Based Scheduling)
Alternativas de planificación
Un esquema de planificación puede ser
Estático: el análisis se realiza antes de la ejecución
Dinámico: se toman decisiones en tiempo de ejecución
Un método estático muy usado es el de planificación con prioridades fijas y desalojo
La prioridad es un parámetro relacionado con la urgencia o importancia de la tarea
En todo momento se ejecuta la tarea con mayor prioridad de todas las ejecutables
Alternativas de planificación
Planificación con prioridades fijas
Es el método más corriente en los sistemas operativos de tiempo real
Cada tarea tiene un prioridad fija, estática, que se calcula antes de su ejecución
Las tareas ejecutables se despachan para su ejecución en orden de prioridad
El despacho puede hacerse
Con desalojo
Sin desalojo
Con desalojo limitado (apropiación diferida o de distribución cooperativa)
En general, se supondrá prioridad fija con desalojo
Se mejora la reacción de los procesos de alta prioridad
Primero el más urgente
Las tareas ejecutables se despachan por orden de los respectivos tiempos límites (absolutos)
La primer tarea que se ejecuta es la más urgente (aquélla cuyo plazo vence antes)
Los tiempos límites absolutos se calculan en tiempo de ejecución (esquema dinámico)
Primero el más valioso
Si el sistema puede sobrecargarse no será suficiente el simple uso de los métodos anteriores
Se precisa un esquema más adaptable
Se asigna un valor (utilidad) a cada tarea, y se emplea un algoritmo de planificación en línea basado en ellos para decidir cuál es la siguiente tarea a ejecutar
Utilidad: Si un servicio se completa dará algún beneficio intrínseco al entorno del sistema de cómputo
Valor
La utilidad de un servicio (Burns et al.) depende de:
La calidad de la salida que produce
El tiempo dentro del cual se ejecuta el servicio (Ej.:demasiado temprano, aceptablemente temprano, entrega óptima, aceptablemente tarde, demasiado tarde)
La historia de las previas invocaciones del servicio
Las condiciones del entorno
Valor
El estado del sistema de cómputo (ej.:que otros servicios se están proveyendo)
La importancia del servicio (fundamentales/ no fundamentales)
La probabilidad de completar el servicio
Prioridades de tasa monotónica
Se asigna mayor prioridad a las tareas de menor período (rate monotonic scheduling), es óptimo para el modelo de tareas simple:
Si pueden garantizarse los plazos de un conjunto de tareas con otra asignación de prioridades, podrán garantizarse con el esquema de asignación de prioridades con tasa monotónica.
Prioridades de tasa monotónica
O, los procesos pueden no alcanzar sus tiempos límites con este esquema sólo si ningún otro esquema de asignación de prioridades puede hacerlo
Instante crítico
Uno de los conceptos más importantes para el análisis de planificabilidad en un sistema con un procesador, es el instante crítico.
Instante crítico
Una consecuencia de la independencia entre tareas es que se puede suponer que en algún instante de tiempo todos los procesos son requeridos simultáneamente para ejecutarse
Esto representará la carga máxima para el procesador, y se conoce como instante critico
Instante inicial para el modelo de tareas simple
Corresponde al tiempo de respuesta máximo de una tarea (Teorema de Liu y Layland)
Si una tarea puede ser planificada en su instante crítico entonces cumplirá con sus requisitos temporales (D)
Instante crítico
Factor de utilización
Es una medida de la carga del procesador para un conjunto de tareas
En un sistema con un único procesador
Liu y Layland (1973) demostraron que usando este factor puede obtenerse un test de planificabilidad para RM
Análisis basado en la utilización
Para el modelo simple, con D=T, con prioridades de tasa monotónica, los plazos están garantizados si:
N Utilización mínima garantizada U0(N)
1 100.0%
2 82.8%
3 78.0%
4 75.7%
5 74.3%
10 71.8%
Mientras que la utilización de la CPU sea menor a 0.69, todas las tareas alcanzarán sus tiempos límites
Ejemplo 1
La utilización combinada es del 0.82 (>0.78) por tanto este conjunto de tareas no pasa el test de utilización. En el instante t=50 la tarea a incumple su primer límite temporal
Tarea T C P U
a 50 12 1 0.24
b 40 10 2 0.25
c 30 10 3 0.33
Ejemplo 1
Ejemplo 1 – Diagrama de Gantt
c
b
a
c
b
0
10
20
30
40
50
Tiempo
Instante crítico
Las líneas temporales pueden utilizarse para probar la planificabilidad
Para conjunto de tareas que comparten un tiempo de activación común (instante crítico) es suficiente dibujar una línea temporal igual al tamaño del periodo más largo (Liu y Layland, 1973)
Si todas las tareas cumplen su primer límite temporal, entonces cumplirán todos sus límites futuros
Ejemplo 2
Este sistema está garantizado (U< 0.78)
Tarea T C P U
a 80 32 1 0.400
b 40 5 2 0.125
c 16 4 3 0.250
Ejemplo 3
Este sistema no pasa la prueba de utilización (U=1>0.78) pero, se cumplen los plazos
Tarea T C P U
a 80 40 1 0.50
b 40 10 2 0.25
c 20 5 3 0.25
Ejemplo 3
(Gp:) 0
(Gp:) 10
(Gp:) 20
(Gp:) 30
(Gp:) 40
(Gp:) 50
(Gp:) 60
Tiempo
Tarea
a
b
c
70
80
En ejecución
Desalojado
Test de planificabilidad
Prueba para verificar si existe un esquema de planificación factible
Test suficiente
Si se pasa el test el conjunto de tareas es definitivamente planificable
Si no se pasa, el conjunto de tareas puede ser planificable, aunque no necesariamente
Test necesario
Si se pasa el test, el conjunto de tareas puede ser planificable, aunque no necesariamente
Si no se pasa, el conjunto de tareas es definitivamente no planificable
Test exacto (=necesario + suficiente)
El conjunto de tareas es planificable si y solo si pasa el test
Utilización mínima garantizada
Es una condición suficiente pero no necesaria
En muchos casos pueden garantizarse los plazos con factores de utilización mayores a U0(N)
Sólo puede utilizarse para conjunto de tareas con plazos igual al periodo
No se puede aplicar a modelos de tareas más complejos
Tiempo límite absoluto
Tiempo límite absoluto
EDF
Siempre se planifica la tarea activa con el tiempo límite absoluto más cercano
0
5
10
15
Factor de utilización con EDF
Los plazos están garantizados si y sólo si
Permite una mayor utilización del procesador. FPS tiene algunas ventajas sobre EDF:
FPS es más sencillo de implementar, la prioridad es estática
EDF requiere un sistema de tiempo de ejecución más complejo
Planificable con EDF y no con FPS
U=3/6 + 4/9 = 0.944
Deadline Miss
Factor de utilización con EDF
Durante las situaciones de sobrecarga (U>1) el comportamiento de FPS es mas predecible
En FPS los procesos de menor prioridad son los que pueden incumplir sus tiempos límites
En EDF es impredecible y puede acarrear un efecto dominó: la primer tarea que cumple su tiempo límite puede provocar que todas las demás lo hagan. Este comportamiento es indeseable en la práctica ya que en aplicaciones reales pueden ocurrir sobrecargas intermitentes debido a condiciones excepcionales: modificaciones en el entorno, cascadas de fallas del sistema, etc.
Efecto dominó en EDF
Para más detalle: Buttazzo, “Rate monotonic vs. EDF: Judgement Day”, EMSOFT 2003.
En RM
Análisis del tiempo de respuesta para FPS
Las pruebas basadas en la utilización para FPS tienen 2 inconvenientes:
No son exactas y,
No son realmente aplicables a un modelo de tareas más general
Se verá una forma diferente basada en el cálculo del tiempo de respuesta en el peor caso de cada tarea, Ri y una simple comprobación:
R ? D
i
i
Análisis del tiempo de respuesta para FPS
El tiempo de respuesta en el peor caso de cada tarea es igual a la suma del tiempo de ejecución en el peor caso para la misma más la interferencia que sufre por la ejecución de tareas con mayor prioridad
La interferencia es máxima cuando todas las tareas se activan a la vez (instante crítico)
Instante crítico
La interferencia es máxima cuando todos las tareas se activan a la vez
El instante inicial se denomina instante crítico
Cálculo de la interferencia
El número de veces que una tarea de prioridad superior, j, se ejecuta durante el intervalo [0, Ri) es:
La función techo obtiene el menor entero mayor que el fraccionario sobre el que actúa. El techo de 1/3 es 1, el de 6/5 es 2, y el de 6/3 es 2.
La interferencia total es:
Cálculo del tiempo de respuesta
donde hp(i) es el conjunto de tareas de prioridad mayor que i. La ecuación no es continua ni lineal y no puede resolverse analíticamente (Joseph y Pandya, 1986)
Cálculo del tiempo de respuesta
Se puede resolver mediante la relación de recurrencia (Audsley et al., 1993):
El conjunto de valores es monótono no decreciente
Un valor aceptable de puede ser Ci (o 0)
Cálculo del tiempo de respuesta
Ejemplo 4
Tarea T C P
a 7 3 3
b 12 3 2
c 20 5 1
Ejemplo 4
Tarea T C P
a 7 3 3
b 12 3 2
c 20 5 1
Ejemplo 3 – revisión
El cálculo de los tiempos de respuesta indica que todas las tareas tienen garantizados sus plazos
Tarea T C P R
a 80 40 1 80
b 40 10 2 15
c 20 5 3 5
Propiedades del análisis del tiempo de respuesta
Proporciona una condición necesaria y suficiente para la garantía de los plazos
Proporciona un análisis del comportamiento temporal del sistema más exacto quel método basado en la utilización
El elemento crítico es el tiempo de cómputo de cada tarea
Optimista: Los plazos pueden fallar aunque el análisis sea positivo
Pesimista: El análisis puede ser negativo y en la realidad no fallen los plazos
R ? D
i
i
Tiempo de ejecución en el peor caso
Interesa el tiempo de ejecución en el peor caso (WCET, worst case execution time)
Hay dos formas de obtener el WCET de una tarea:
1º opción: Medida del tiempo de ejecución
No es fácil saber cuándo se ejecuta el peor caso posible
Sigue siendo usado en la industria para sistemas que no sean hard
WCET
El tiempo de ejecución de una tarea generalmente varía dependiendo de los datos de entrada o diferentes condiciones del entorno.
En muchos casos el espacio de estados es demasiado grande para explorarlo exhaustivamente
Tiempo de ejecución en el peor caso
2º opción: Análisis del código ejecutable
Puede ser muy pesimista
Hace falta tener un modelo adecuado del procesador
Es difícil tener en cuenta los efectos de los dispositivos de hardware (cachés, pipelines, branch prediction y otros componentes especulativos)
Tiempo de ejecución en el peor caso
Casi todas las técnicas de análisis involucran 2
actividades distintas
La 1º toma el código de la tarea y lo descompone en un grafo dirigido de bloques básicos
Un bloque básico es uno secuencial con una sentencia de salto condicional o incondicional al final
La 2º toma el código de máquina correspondiente al bloque básico y usa el modelo del procesador para estimar su WCET
Tiempo de ejecución en el peor caso
Una vez conocido el WCET para todos los bloques básicos se colapsa el grafo. Ej.: la construcción de elección entre 2 bloques básicos se reduce a uno con el WCET más grande
Se pueden utilizar técnicas de reducción de grafos si se dispone de información semántica eficiente.
También se utilizan herramientas como la programación lineal entera (ILP) y programación con restricciones
WCET
Necesidad de información semántica
Coste total: 10×100+coste del bucle, ej.:1005 unidades de t.
Se puede deducir (por ej.a través de análisis estático del código, histórico de ejecuciones) que Cond es verdadera como mucho en 3 veces, se puede obtener valores menos pesimistas, ejemplo: 375 unidades de tiempo
for I in 1.. 10 loop
if Cond then
— basic block of cost 100
else
— basic block of cost 10
end if;
end loop;
Tiempo de ejecución en el peor caso
Estas técnicas suelen requerir anotaciones del desarrollador.Ej:info sobre layout de la memoria, rango de valores de entrada de la tarea, límites de iteraciones, profundidad de anidados, frecuencias de algunos saltos,etc.
También se utiliza el código generado por el compilador por la información semántica que contiene (invocaciones dinámicas, análisis de punteros, etc.)
Evidentemente el código requiere restricciones, por ej.iteraciones y recursiones deben estar limitados
Tiempo de ejecución en el peor caso
El peor desafío que afronta el análisis del WCET proviene de los modernos procesadores con características que intentan reducir el tiempo de ejecución medio pero hacen difícil predecir el peor caso
Los fabricantes, en general, no suministran información sobre la microarquitectura que podría usarse para validar estos modelos abstractos del hardware
Tiempo de ejecución en el peor caso
En el caso de sistemas en tiempo real o, se eligen arquitecturas de procesadores más simples (menos potentes) o se pone más empeño en la medición
En aquéllos de alta integridad se utiliza un enfoque que combine las pruebas y medidas de las unidades de código (bloques básicos) con el análisis para los componentes completos
Generalización del modelo de tareas
El análisis del tiempo de respuesta visto para el modelo de tareas básico puede extenderse con
Tareas esporádicas y aperiódicas
Plazos menores o mayores que los períodos
Interacción mediante secciones críticas
Planificación cooperativa
Fluctuaciones (jitter) en la activación
Tolerancia a fallos
Desfases (offsets)
Referencias
Burns, A. Wellings, A. "Sistemas de Tiempo Real y Lenguajes de Programación", Addison-Wesley (2003) Capítulo 13
Transparencias de Juan Antonio de la Puente http://polaris.dit.upm.es/~jpuente/
Transparencias de Javier Macías Guarasa http://www-lsi.die.upm.es/~carreras/ISSE/sistemas_con_restricciones_1.x2.pdf
 Página anterior | Volver al principio del trabajo | Página siguiente  |