Introducción al tiempo real en sistemas empotrados

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 de tiempo real con recursos compartidos

CONTENIDO

• Modelo y propiedades• Inversión de prioridad• Políticas de planificación con recursos compartidos

BIBIOGRAFIA

• Q. Li: Real-Time concepts for embedded systems. CMP Books, 2003.

• J. Liu: Real-Time Systems, Prentice-Hall, 2000. Capítulo 8.

UPV - EHU

MOISE



• Modelo– Ahora las tareas de tiempo real compiten por el

acceso a los recursos.– La espera por una sección crítica no supone

consumo de CPU (espera por bloqueado).– Se conoce el comportamiento de las tareas en

cuanto a tiempos de ejecución dentro y fuera de la secciones críticas.

• Propiedades– Duración acotada de los bloqueos.– Número de bloqueos acotados.– No interbloqueos (disciplina de programación).

UPV - EHU

MOISE



• Ejemplo:– Un único recurso, una unidad del recurso.

– Prioridades (1 es la menos prioritaria) y expulsión.– Una tarea solicita el recurso en el instante tL de su tiempo de

ejecución– La duración de la SC es ΔL.

Φ C tL ΔL D

10 6 1 4 18

22 7 2 4 15

36 5 2 2 8

UPV - EHU

MOISE



Ejemplo de ejecución

Φ C tL ΔL D

10 6 1 4 18

22 7 2 4 15

36 5 2 2 8

Sección crítica ocupada

3

2

1

UPV - EHU

MOISE


Inversión de prioridad

Φ C tL ΔL D

10 4,5 1 2,5 18

22 7 2 4 15

36 5 2 2 8


D3 se cumple!

3

2

1

UPV - EHU

MOISE


• La presencia de secciones críticas introduce situaciones de incumplimiento de plazos.– En el ejemplo, la tarea más prioritaria 3

abandona la CPU cuando se dispone a ejecutar la SC, ya que ésta está ocupada por 2.

– Precisamente, 2 no ha podido liberar la SC

porque 3 la expulsó de la CPU por prioridad.

• Una tarea de baja prioridad impide a otra de mayor prioridad cumplir el plazo (inversión de prioridad).

• No es posible acotar la duración de la inversión de prioridad (Liu 2000, Cap. 8).

Inversión de prioridad

UPV - EHU

MOISE


Inversión de prioridadespera no acotada

Φ C tL ΔL D

10 7 1 5 18

25 5 - - 15

32 4 1 2 8


3

2

1

UPV - EHU

MOISE


Políticas de planificación con recursos compartidos

• Políticas de planificación para evitar la inversión de prioridad:– Secciones críticas no explulsables.– Herencia de prioridad.– Techo de prioridad.

UPV - EHU

MOISE



Sección crítica no expulsable

Φ C tL ΔL D

10 6 1 4 18

22 7 2 4 15

36 5 2 2 8


3

2

1

UPV - EHU

MOISE



Sección crítica no expulsable

Φ C tL ΔL D

10 4,5 1 2,5 18

22 7 2 4 15

36 5 2 2 8


D3 se cumple!

3

2

1

UPV - EHU

MOISE



Herencia de prioridad• La política de SC no expulsable no evita

problemas de incumplimiento de plazos.• Política de herencia de prioridad:

– Además de su prioridad asignada inicialmente, Pi, se define para cada tarea una prioridad actual, πi, que es con la que se ejecuta en cada momento.

– Inicialmente, πi(0)=Pi.

– Cuando una tarea i accede en un instante t a una SC, comienza a ejecutarla con su prioridad actual πi(t).

– Cuando una tarea h de mayor prioridad se bloquea en un instante t’>t en el acceso a la SC ocupada por i, πi(t’)= πh(t’).

– Cuando i libera la SC en t’’, πi(t’’)= πi(t).

UPV - EHU

MOISE



Ejemplo sin herencia de prioridad

Φ C tL ΔL D

10 7 1 5 18

25 5 - - 15

32 4 1 2 8


3

2

1

1 es expulsado

UPV - EHU

MOISE



Herencia de prioridad

Φ C tL ΔL D

10 7 1 5 18

25 5 - - 15

32 4 1 2 8


π1(3)=π3(3)

3

2

1

1 no es expulsado

UPV - EHU

MOISE



Recursos múltiples

• Cuando las tareas acceden a múltiples recursos compartidos, se añade el problema del interbloqueo.

• La herencia de prioridad evita situaciones de inversión de prioridad, pero no de interbloqueos.

• Hay que combinarla con políticas de prevención de interbloqueos.

UPV - EHU

MOISE



Techo de prioridad

• Es una extensión de la política de herencia de prioridad para múltiples recursos.– Se conoce a priori el conjunto de recursos que cada

tarea va a usar. – Techo de prioridad de un recurso: prioridad de la tarea

de mayor prioridad entre las que están accediendo al recurso.

– Techo del sistema: mayor techo de prioridad de todos los recursos.

– Se aplica herencia de prioridad.– Básicamente, a una tarea se le asigna un recurso libre

si la prioridad de la tarea es mayor que el techo de prioridad del sistema o si ya posee un recurso con techo de prioridad la del sistema.

• Al establecer un orden en la asignación de recursos, evita interbloqueos con múltiples recursos.

Documents

Introducción al tiempo real en sistemas empotrados