Planificación del sistema operativo (página 2)

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