planificación en sistemas de tiempo real

UPV - EHU

MOISE

Konputagailuen Arkitektura eta Teknologia SailaDepartamento de Arquitectura y Tecnología de Computadores 1

Introducción al tiempo real en sistemas

empotrados

Departamento de Arquitectura y Tecnología de Computadores

Universidad del País Vasco / Euskal Herriko Unibertsitatea

Master en Ingeniería de Sistemas Empotrados

UPV - EHU

MOISE


Contenido

• Introducción• Soporte de interrupciones• Conceptos de sistemas operativos• Planificación en sistemas de tiempo real• Mecanismos de sincronización y comunicación• Planificación de tiempo real con recursos

compartidos

UPV - EHU

MOISE


Planificación en sistemas de tiempo real

CONTENIDO

• Introducción• Modelo de tareas de tiempo real• Criterios para la planificación en tiempo real• Políticas de planificación para tiempo real• Planificación con tareas aperiódicas

BIBIOGRAFIA

• Q. Li: Real-Time concepts for embedded systems. CMP Books, 2003.• J. Liu: Real-Time Systems, Prentice-Hall, 2000• H. Kopetz: Real-Time Systems: design principles for distributed embedded

applications. Kluwer, 1997.• J.A. de la Puente et al: Introducción a los sistemas de tiempo real.

http://polaris.dit.upm.es/~aalonso/doctorado/str.html#Transparencias• J.A. de la Puente: Diseño de sistemas de tiempo real.

http://www.depeca.uah.es/docencia/doctorado/cursos04_05/82622/documentos/str/Puente-Desarrollo-str.pdf

http://polaris.dit.upm.es/~aalonso/doctorado/str.html#Transparencias



UPV - EHU

MOISE


Introducción

• Dado un conjunto de tareas, se trata de planificar su ejecución de forma que todas ellas cumplan los plazos.

• Requiere políticas de planificación específicas.

UPV - EHU

MOISE


IntroducciónEnfoques (1)

• Algunos sistemas operativos soportan procesos de “clase de tiempo real”.– Son procesos con prioridades estáticas más altas

que los procesos de tiempo compartido.– Ejemplos: Unix SVR4, Windows– Sólo adecuados para sistemas flexibles (soft real-

time):• Contienen código no expulsable en el núcleo.• En general, demasiado voluminosos para sistemas

empotrados y poco fiables.

UPV - EHU

MOISE



• Enfoque de máquina virtual– Un núcleo RT planifica el SO como una tarea más.– Ejemplo: RT-Linux– El núcleo RT intercepta las interrupciones del

hardware, por lo que la ejecución del SO puede ser interrumpida en cualquier momento.

– Es posible comunicar tareas mediante colas FIFO.

(Extraído del curso de J.A. de la Puente, UPM)

UPV - EHU

MOISE



• Sobre la máquina desnuda: fabricar un núcleo básico ad-hoc con un planificador de tareas de tiempo real.– Costoso en tiempo de desarrollo.


UPV - EHU

MOISE



• Sistemas Operativos de Tiempo Real (RTOS) específicos.– Flexibles– Ejemplos: LynxOS, QNX, VxWorks, FreeRTOS, MARTE

(Univ. de Cantabria)…– Estándar POSIX: apartados para sistemas de tiempo

real que definen normas y servicios específicos a incluir.


UPV - EHU

MOISE


Modelo de tareas de tiempo real

• Acción. Mínima cantidad de cómputo en un sistema de tiempo real.– Ejemplo: decodificar un cuadro de video.– Requiere un recurso de cómputo.

• Tarea. Conjunto de acciones repetidas a lo largo del tiempo.– Ejemplo: visualizar una secuencia de video.

τ= <J1, J2, …>

UPV - EHU

MOISE



• Instante de activación de la acción, rk

– La acción puede empezar a ejecutarse. • límite de la acción, dk.

– La acción debe haber terminado

• Tarea periódica: rk = r0 + kT– Habitualmente: rk+1 = di

y entonces el periodo es: T = dk − rk

• Tarea aperiódica: rk+1 − rk variable.

J0 J1 J2

r0 r1 r2 r3d0 d1 d2

UPV - EHU

MOISE


Jk

Rk


• Plazo de ejecución, Dk = dk − rk

– Condición necesaria: Ck < Dk

• Tiempo de respuesta, Rk

Ck

Dk

rk dk

UPV - EHU

MOISE


Modelo de tareas de tiempo realPlazos

• Plazo estricto– Todas las acciones deben ocurrir dentro del plazo– Los fallos pueden ser catastróficos– Ejemplo: sistema de control de vuelo

• Plazo flexible– Se pueden incumplir plazos de vez en cuando– El valor de la respuesta decrece con el paso del tiempo– Ejemplo: sistema de adquisición

• Plazo firme– Se pueden perder plazos ocasionalmente– Las respuestas fuera de plazo no tienen valor– Ejemplo: Sistemas multimedia

UPV - EHU

MOISE




UPV - EHU

MOISE



• Sistemas garantizados– Plazos estrictos– Validación

• Sistemas de esfuerzo óptimo (best-effort)– Plazos flexibles– Requisitos estadísticos– Criterios de Calidad de Servicio (QoS):

• Tasa de cumplimiento del plazo• Tiempos de respuesta• etc

UPV - EHU

MOISE


Modelo de tareas de tiempo realParámetros

• N tareas periódicas• 1 procesador• Parámetros temporales de las tareas:

– Tarea τi : (Φi, Ti, Ci, Di)– Una acción Ji,k

• Se activa en ri,k = Φi + kTi

• Debe terminar antes de di,k = Φi + kTi + Di

Habitualmente: Di = Ti

UPV - EHU

MOISE


Criterios para la planificación en tiempo real

• Dado un conjunto de tareas de tiempo real {τ1, τ2, …, τN}

el objetivo es proporcionar una planificación viable.

• Condición necesaria para la viabilidad (para tareas periódicas):

U=∑ Ci/Ti < 1• Tareas aperiódicas: encontrar periodo mínimo (si es

posible) y expresarlas como periódicas con ese periodo.

UPV - EHU

MOISE


Criterios para la planificación en tiempo real

• La viabilidad es un criterio absoluto en sistemas de plazo estricto.

• Sistemas de plazo no estricto: – Plazo flexible: minimizar la magnitud de los

retrasos.– Plazo firme: minimizar el número de retrasos.

UPV - EHU

MOISE


Criterios para la planificación en tiempo realEjemplo

¿viable?

Φ T C Dτ1 0 4 1 4τ2 0 6 1 6τ3 0 12 2 12τ4 0 12 3 12

UPV - EHU

MOISE


Políticas de planificación para tiempo realTipos de planificación

• Según cuándo se elabora la planificación:– Planificación estática

• Todos los parámetros temporales son fijos y conocidos.

• Puede establecerse un hiperperiodo (m.c.m. de todos los Ti).

• El plan se elabora antes de la ejecución y se almacena en una tabla.

• El planificador se limita a consultar la tabla en determinados instantes para seleccionar la tarea a ejecutar.

– Planificación dinámica• No existe un plan preestablecido.

UPV - EHU

MOISE


Políticas de planificación para tiempo real.Ejecutivo cíclico

• Planificación estática con un esquema periódico.

Φ T C Dτ1 0 4 1 4τ2 0 6 1 6τ3 0 12 2 12τ4 0 12 3 12

Periodo principal: H = mcm(Ti) = 12

τ1 τ2 τ1 τ1 τ1 τ1 τ1τ2 τ2τ2 τ4τ4 τ3τ3

Periodo secundario:TS = 4

UPV - EHU

MOISE



• Plan cíclico:

Ciclo secundario Acciones a activar

1 τ1 τ2 τ3

2 τ1 τ4

3 τ1 τ2

τ1 τ2 τ1 τ1 τ2τ4τ3

UPV - EHU

MOISE



• ¿Cómo definir el periodo secundario, TS?• Condiciones:

– La ejecución de cada acción debe caber en un ciclo.

– Debe ser un divisor entero del periodo de alguna tarea (y por lo tanto de H).

– Entre el periodo de activación de una acción y su tiempo límite debe de haber al menos un ciclo completo.

UPV - EHU

MOISE



• No es posible cumplir simultáneamente las condiciones (1) y (3).

• Solución: segmentar tareas.

Φ T C Dτ1 0 4 1 4τ2 0 6 1 6τ3 0 12 5 12

UPV - EHU

MOISE


Políticas de planificación para tiempo real.Ejecutivo cíclico con segmentación de tareas

Φ T C Dτ1 0 4 1 4τ2 0 6 1 6τ31 0 12 2 12τ32 - 12 3 12

τ1 τ2 τ1 τ1 τ2τ31 τ32

UPV - EHU

MOISE


Políticas de planificación para tiempo real.Ejecutivo cíclico. Limitaciones.

• En general, el problema de construir el plan cíclico es muy complejo (NP-duro).

• Sólo apto para tareas periódicas.

UPV - EHU

MOISE


Políticas de planificación para tiempo real.Basadas en prioridades

• Las tareas son expulsables.• Admiten tareas aperiódicas (y esporádicas).• Prioridades fijas:

– Rate Monotonic (RM). Mayor prioridad para las tareas de menor periodo.

– Deadline Monotonic (DM). Mayor prioridad para las tareas de plazo más corto.(RM y DM son equivalentes cuando Di = Ti).

• Prioridades dinámicas:– Earliest Deadline First (EDF). Se planifica la tarea cuyo

plazo está más cercano a expirar.• La condición de viabilidad (U<1) es necesaria y suficiente

para que EDF encuentre una forma de cumplir todos los plazos.

UPV - EHU

MOISE


Políticas de planificación para tiempo real.RM

Φ T C Dτ1 0 4 1 4τ2 0 6 1 6τ3 0 12 2 12τ4 0 12 3 12

τ1 τ2 τ1 τ1 τ1 τ1 τ1τ2 τ2τ2 τ4τ4 τ3τ3 τ4 τ4 τ4 τ4

UPV - EHU

MOISE


Políticas de planificación para tiempo real.DM vs RM

Φ T C Dτ1 0 4 1 4τ2 0 6 1 6τ3 0 12 2 12τ4 0 12 3 9

τ1 τ2 τ1 τ1τ2τ4τ3 τ4RM τ4

D4 se cumple!

τ1 τ2 τ1 τ1τ2τ4 τ3τ4 τ3DM

UPV - EHU

MOISE


Políticas de planificación para tiempo real.EDF

Φ T C Dτ1 0 4 1 4τ2 0 6 1 6τ3 0 12 2 12τ4 0 12 3 12

τ1 τ2 τ1 τ1τ2τ4τ3 τ4 τ4

UPV - EHU

MOISE


Políticas de planificación para tiempo real.EDF

Φ T C Dτ1 0 4 1 4τ2 0 6 1 6τ3 0 12 2 12τ4 0 12 3 9

τ1 τ2 τ1 τ1τ2τ4 τ3τ4

UPV - EHU

MOISE


Planificación con tareas aperiódicas

• Tarea aperiódica– Se activa como respuesta a un suceso externo. – Puede tener restricciones de tiempo o no.– Tarea esporádica: Tarea aperiódica con

restricciones de tiempo críticas.• Objetivos:

– Garantizar plazos de las tareas críticas (esporádicas y periódicas).

– Buenos tiempos de respuesta para las aperiódicas no críticas.

UPV - EHU

MOISE


Planificación con tareas aperiódicas.Políticas

• Procesamiento en segundo plano– Prioridades bajas para las tareas aperiódicas no

críticas.• Procesamiento por interrupciones

– Las tareas aperiódicas se tratan inmediatamente.• Reserva de ancho de banda

– Reserva a priori de capacidad de CPU para tareas aperiódicas.

– Se procesan inmediatamente.• Extracción dinámica de holgura

– Reserva de capacidad de CPU para tareas aperiódicas en tiempo de ejecución.

planificación en sistemas de tiempo real

Documents