Planificación de Sistemas de Tiempo Real - OCW UPMocw.upm.es/.../material-de-clase/transp_cap5_planificacion_str.pdf · Planificacion de Sistemas de Tiempo Real 27 Algoritmo para

Sistemas de Tiempo Real

Planificación de Sistemas de Tiempo Real

Javier García Martín

2

Capítulo 4

Planificación de Sistemas de Tiempo Real

1. Introducción 2. Ejecutivo Cíclico 3. Prioridades de tareas en Ada 4. Políticas de gestión de procesos en Ada

5. Protocolos de acceso a recursos 6. Planificación Monótona en Frecuencia (RMS) 7. Extensiones a la planificación RMS 8. Análisis del tiempo de respuesta

9. Planificación dinámica

Planificacion de Sistemas de Tiempo Real

3

1.- Introducción

RU12

RU21 RU22

RU11 Rut-Int

: :

Rut-Int : :

T1

D1

C1

P1

T2

D2

C2

P2

T3

D3

C3

FMax5

D5

C5

P5

FMax4

D4

C4

P4R1

R2

P3

Recursos Comunes Procesos Aperiódicos Procesos Periódicos

4

♦ Objetivo El objetivo es que todos los procesos cumplan sus plazos. Los motivos para dejar de cumplir un plazo: • el retraso por la ejecución de procesos de mayor prioridad • el tiempo de cómputo del propio proceso • el tiempo que el proceso espera recursos compartidos.


5

♦ Métodos de planificación

Algoritmo de planificación Medio de predicción del comportamiento temporal del sistema (determinista)

P1 (Prior. 5) P2 (Prior. 8) P3 (Prior. 4)

CPU

Run Time S.O

(núcleo)

Asignación de prioridades

Gestión de procesos

6

Aspectos importantes: • garantizar las restricciones en cualquier circunstancia

(peor de los casos posibles) • utilizar políticas de planificación adecuadas para sistemas de tiempo real.

Clasificación de los métodos de planificación: • expulsores (con desalojo) • no expulsores (sin desalojo)

Otra clasificación … momento en que se asignan las prioridades: • estáticos • dinámicos


7

Ejemplo Tarea Ti Ci Pi

A 100 35 Mayor B 150 25 Media C 200 70 Menor

Orden de ejecución de los procesos

C

B

A 35

25

35 35 35 35

25 25 25

40 20 10 65 5

0 100 150 200 300 400 450

15

A A A A A B B B B C C C

8

♦ Notación ti: tarea i-ésima N: número de tareas Ti: período de la tarea i Ci: tiempo de cómputo de la tarea i Di: plazo de respuesta de la tarea i Ri: tiempo de respuesta máximo de la tarea i Pi: prioridad de la tarea i


9

t

Retardo.Min.

Di

a b c

Retardo.Max.

T.Max.Trans.

C1 = a + b + c

Activación Fin Ejecución

a

Activación Fin Ejecución

b

Ti Ti Di

C2 = a + b

Ci = máx. tiempo de computo

Ri Ri

Objetivo de la planificación: asegurar que siempre se cumple que Ri < Di.

10

♦ Factor de utilización de la CPU

U = ∑Ci/Ti , i=1..N

siendo N el número de tareas.

Sistemas monoprocesador: U < 1

Para una sola tarea: Ci < Ti si Ci = Ti => 100% de CPU ocupada


11

Definición de un método de planificación:

1.- Algoritmo de planificación Explusor/No expulsor;

Asignación de prioridades; Protocolo de acceso a recursos compartidos ...

2.- Predicción de cumplimiento de plazos

f(∑Ci/Ti, Di, Ri, Bi, ...)

12

2.- Ejecutivo cíclico

Tarea Ti Ci Di A 25 Ca Da B 50 Cb Db C 50 Cc Dc D 75 Cd Dd E 150 Ce De

Ciclo Principal

Tm = mcm(Ti) Ciclos secundarios

Ts | Tm = k * Ts En nuestro ejemplo

Tm = mcm (25,50,50,75,150) = 150 Ts = 25 | 6 * 25 = 150


13

Orden de ejecución de los procesos:

Comprobar: • restricciones en forma de plazos • tiempos de cómputo de los procesos

tareas A B A C A DB A C A B A

25 50 75 100 125

Ts

Tm

D E C

150 0

14

procedure Ejecutivo_Ciclico is type Numero_Ciclo is mod 6; Ciclo_Secundario: Numero_Ciclo := 0; Siguiente: Time := Clock; Periodo: constant := 25; begin loop case Ciclo_Secundario is when 0 => A; B; D; when 1 => A; C; E; when 2 => A; B; when 3 => A; C; D; when 4 => A; B; when 5 => A; C; end case; Ciclo_Secundario := Ciclo_Secundario + 1; siguiente := siguiente + periodo; delay until siguiente; end loop; end Ejecutivo_Ciclico;


15

Consideraciones • no existe concurrencia • no se necesitan mecanismos de excluión mútua • análisis de la planificabilidad del sistema está incorporado en la propia

construcción • procesos con un tiempo de cómputo grande en varias partes

Inconvenientes. • rigidez del plan • sistemas con un número considerable de procesos con periodos dispares • procesos esporádicos

16

3.- Prioridades de tareas en Ada • prioridad estática

task A is pragma priority (p) end A;

• prioridad dinámica

package Ada.Dynamic_Priorities is procedure Set_Priority (Priority : System.Any_Priority; T : Ada.Task_Identification.Task_Id := Ada.Task_Identification.Current_Task); function Get_Priority (T : Ada.Task_Identification.Task_Id := Ada.Task_Identification.Current_Task) return System.Any_Priority; end Ada.Dynamic_Priorities;


17

• prioridad base • prioridad activa: la mayor entre prioridad base y prioridad heredada Una tarea hereda una prioridad en tiempo de ejecución: • al utilizar un objeto protegido que tiene asignada una prioridad • al ser activada, hereda la prioridad de la tarea padre • al ejecutar la instrucción accept hereda la prioridad activa de la tarea que hace

la llamada

18

4.- Políticas de gestión de procesos en Ada

♦ Política de ordenación de procesos (task dispatching policies) seleccionar la siguiente tarea a ejecutar en los task dispatching points task dispatching points: • la tarea en ejecución queda bloqueada • la tarea en ejecución termina • una tarea pasa a estar lista para su ejecución • la tarea en ejecución completa un sentencia accept


19

Funcionamiento de la política FIFO_Within_Priorities. • Una cola de tareas listas (en espera de ejecución) por cada nivel de prioridad. Cada una de

estas colas sigue una política FIFO. • Si una tarea bloqueada pasa a estar lista para ejecución, se colocará al final de la cola de

tareas de igual prioridad que su prioridad activa. • Cuando una tarea es expulsada de la CPU se coloca la primera de la cola en vez de la última,

(excepción a la ordenación FIFO). • Cuando se modifica dinámicamente la prioridad de una tarea que está en espera de

ejecución, se desplazará a la cola de tareas correspondiente a su nueva prioridad • En el momento de la modificación de la prioridad base de una tarea en ejecución, la tarea se

desplaza a la cola de tareas listas de igual prioridad a su prioridad activa. • Cuando una tarea ejecuta una instrucción delay que no provoca un bloqueo, dicha tarea

pasará a la cola de tareas en espera de ejecución correspondiente a su prioridad activa (provoca un cambio de contexto).

pragma Task_Dispatching_Policy (Identificador_de_Política) ;

20

♦ Política de gestión de colas de entrada (entry queuing policies)

Orden en que son atendidas las tareas que quedan en espera de una entrada (entrada de sincronización de una tarea o entrada a un objeto protegido).

El lenguaje especifica: FIFO_Queuing y Priority_Queuing.

pragma Queuing_Policy (Identificador_de_Política) ;


21

5.- Protocolos de acceso a recursos

♦ Introducción. Un protocolo asociado a un recurso:

• marca las normas de acceso que van a seguir los procesos que quieren utilizarlo

• facilita la limitación del tiempo máximo que un proceso puede llegar a estar

bloqueado

• proporciona un método para calcular ese tiempo máximo de bloqueo

22

Inversión de Prioridades.

Bloqueo

t1

t2

t3

t4

[a] [b] [c] [d]t


23

Inversión de Prioridades.

Tiempo de Bloqueo Bi:

Tiempo esperando para acceder a un recurso debido a tareas de menor prioridad que ella.

t1

t2

t3

t4

Inversión de prioridad

N

[a] [b] [c] [d]t

24

♦ Protocolo de herencia de prioridad

Funcionamiento

t1 (Prior. 8) t2 (Prior. 6) t3 (Prior. 4) t4 (Prior. 2)

Acceso a Recurso

Acceso aRecurso

Acceso aRecurso


25

Ejemplo Tarea Pi Recursos Inicio

t1 4 R1 R2 4 t2 3 R2 2 t3 2 - 2 t4 1 R1 0

t1

t2

t3

t4

t

Ejecutando

En espera

Bloqueado

Accede a R2

Accede a R1

26

Características

Un mismo proceso de < prioridad No bloquean 2 veces a un mismo proceso

Un mismo recurso compartido en una misma activación Ejemplo: max(RU21,RU31) + RU42.

Tarea Recursos t1 R1 R2 t2 R1 t3 R1 t4 R2

Ejemplo: max(RU21,RU22) + RU32.

Tarea Recursos

t1 R1 R2 R3

t2 R1 R2

t3 R3


27

Algoritmo para el cálculo de los tiempos máximos de bloqueo RUi = tiempo máximo que la tarea i utiliza el recurso R PCr = Máxima prioridad de todas las tareas que utilizan el recurso R Pi = Prioridad de la tarea i b = actualización dinámica del tiempo máximo de bloqueo

1.- ordenar las tareas por orden de mayor a menor prioridad t1, t2, .. tn 2.- b := 0 3.- i := n 4.- Bi := b 5.- si RUi > b entonces b := RUi 6.- si i = 1 entonces Fin del Algoritmo si Pi-1 > PCr entonces b := 0 7.- i := i-1; ir al paso 4

28

♦ Protocolo de techo de prioridad mejora al anterior cuando se trabaja con varios recursos

t1

t2

t3

t4

t5

t6

Recursos

R1

R2

R3

Tareas Prioridades Techos

P1

P2

P3

P4

P5

P6

P2

P2

P4

Techo Actual del Sistema: si R1 o R2 ocupados = P2 si no si R3 ocupado = P4


29

Funcionamiento Un proceso ti puede adquirir un recurso si se cumple la condición:

Pi > Techo Actual del Sistema En caso contrario

el proceso quedará bloqueado el proceso bloqueante hereda su prioridad.

t1

t2

t3

t4

t

30

Características • Un proceso se bloquea como máximo 1 vez por cada activación • Peor caso de bloqueo para un proceso ti:

Máximo tiempo que un proceso de < prioridad que Pi utiliza un recurso compartido con techo de prioridad ≥ que Pi


31

Algoritmo para el cálculo de los tiempos máximos de bloqueo PCr = Techo del Recurso r br será una variable asociada al recurso r

1.- Ordenar las tareas de mayor a menor prioridad t1,t2,..tn 2.- ∀r br := 0 3.- i := n 4.- Bi := ∀r max(br) 5.- ∀r ∈Recursos accedidos por ti si RUir > br entonces br := RUir 6.- si i=1 entonces Fin si Pi-1 > PCr entonces br := 0 7.- I := i –1; ir al paso 4

32

♦ Protocolo de techo de prioridad inmediato Funcionamiento

Techo de prioridad de recursos (igual que anterior) Cuando un proceso entra en un recurso hereda PCr aunque no bloquee a nadie

Algoritmo para el cálculo de los tiempos máximos de bloqueo (igual que anterior)

t1

t2

t3

t4

t


33

♦ Programación en Ada95

Protocolo de Techo de Prioridad Inmediato Pragma Locking_Policy (Identificador)

--------------EJEMPLO DE TECHO DE PRIORIDADES ---- pragma Locking_Policy (Ceiling_Locking) ; pragma Task_Dispatching_Policy (Fifo_Within_Priorities) ; ------------------ DEFINICIONES ------------------ procedure Principal is ...... task A is pragma Priority (Prioridad_A) ; end A ; task B is pragma Priority (Prioridad_B) ; end B ; task C is pragma Priority (Prioridad_C) ; end C ;

34

Protected Objeto is pragma Priority (Prioridad_Recurso) ; -- Prioridad de Techo entry E (...) ; procedure P (...) ; private --definicion de datos end Objeto ;


35

------------------- CUERPOS ---------------------- Protected body Objeto is ... end Objeto ; task body A is ... end A ; task body B is ... end B ; task body c is ... end c ; ------------------------------------------------- begin null ; end Principal ; -------------------------------------------------

36

6.- Planificación monótona en frecuencia (RMS) Condiciones iniciales

Todos los procesos: • Son periódicos • El plazo Di = Ti • Son independientes

Asignación de prioridades “mayor prioridad al proceso mas frecuente” las prioridades se asignan de forma inversamente proporcional a los periodos

Ejemplo: Robot Autónomo

Tarea Ti t1 Comprobar la desviación de la dirección a seguir 10 t2 Comprobar la temperatura del motor 40 t3 Comprobar la presencia de obstáculos 20

P1=3, P2=1 y P3=2


37

Teorema 1. La planificación RMS es óptima

Teorema 2. Planificabilidad basado en el uso de CPU Un sistema con planificación RMS será planificable si cumple la condición

(suficiente pero no necesaria)

N 1 2 3 4 5 U(N) 1.000 0.828 0.779 0.756 0.743

Teorema 3. Instante crítico

Un sistema es planificable si y solo si todos sus procesos cumplen su primer plazo habiendo comenzado todos simultáneamente en el instante cero

Ti∑ ≤ U(N) = N ⋅ (2 1/N−1)Ci

i=1

N

38

Ejemplo Tarea Ti Ci Ui

t1 100 40 0.4 t2 150 40 0.267 t3 350 90 0.3

0.967 > U(3)=0.779

t 1

t 2

t 3

4 0 *

4 0 *

1 0

4 0 *

4 0 *

2 0

4 0 *

1 0 5 0 *

0 1 0 0 1 5 0 2 0 0 3 0 0t

t 1 t 1 t 1 t 2

t 2 t 3 3 5 0

t 3

t 1 t 2

A c t i v a c i o n e s d e t a r e a s

4 0 *


39

Expresión matemática del Teorema 3

Un sistema será planificable si y solo si se cumple la condición

∀i, 1≤i≤N

(k,m) ∈Gi

TkGi = (k,m) 1≤ k ≤ i, m=1,..,

Ti

∑ Cj ≤ 11mTkj=1

i mTk

Tjmin

40

Ejemplo Para las tareas del ejemplo anterior

G1 = (1,1) G2 = (1,1) (2,1) G3 = (1,1) (1,2) (1,3) (2,1) (2,2) (3,1)

Para i = 1

Para i = 2

Para i = 3

∑ Cj ≤ 11T1j=1

1 T1

Tj(1,1):

∑ Cj ≤ 11T1j=1

2 T1

Tj(1,1):

∑ Cj ≤ 113T1j=1

3 3T1

Tj(1,3):


41

7.- Extensiones a la planificación RMS Particularizamos el teorema 2 para una tarea ti Una tarea ti es planificable si se cumple la condición

(suficiente pero no necesaria)

Un sistema es planificable si todas sus tareas son planificables

+ + . . . + + ≤ U(i) = i ⋅ (2 1/i−1)Ti

CiT1

C1T2

C2Ti-1

Ci-1

42

♦ Interrupciones Estimar/limitar la frecuencia máxima de activación de la interrupción (obtenemos Tint)

si Tint < Ti , la tarea ti es planificable si se cumple la condición

si Tint ≥ Ti , la tarea ti es planificable si se cumple la condición

Incorpora la interrupción como una tarea periódica mas, pero “colándose” al resto de tareas más prioritarias que ella.

+ . . . + + + ≤ U(i) = i ⋅ (2 1/i−1) Ti

Ci T1

C1 Ti

Cint Ti-1

Ci-1

+ . . . + + + ≤ U(i) = i ⋅ (2 1/i−1) Ti

Ci T1

C1 Tint

Cint Ti-1

Ci-1


43

Ejemplo Tarea Ti Ci Ui

t1 100 20 0.2

t2 150 40 0.267

Int 200 60 0.3

t4 350 20 0.057

para t1: C1/T1 + Cint/T1 < U(1) = 1 para t2: C1/T1 + C2/T2 + Cint/T2 < U(2) = 0.828 para tint: Cint/T1 < U(1) = 1 para t4: C1/T1 + C2/T2 + Cint/Tint + C4/T4 < U(4) = 0.756

44

♦ Tareas esporádicas

El periodo mínimo de activación de la tarea esporádica se puede limitar por software Si la rutina de tratamiento de interrupción del ejemplo anterior se encarga de despertar a una tarea esporádica cuyo periodo de activación está limitado a 400

Tarea Ti Ci Ui t1 100 20 0.2 t2 150 40 0.267 Int 200 60 0.3 t4 350 20 0.057 t5 400 30 0.075


45

♦ Recursos compartidos En el apartado anterior vimos la forma de calcular los tiempos de bloqueo Bi. La condición de planificabilidad de una tarea ti:

+. . . + + + ≤ U(i) = i ⋅ (2 1/i−1) Ti

Ci T1

C1 Ti

Bi Ti-1

Ci-1

46

♦ Plazos de respuesta anteriores a los periodos Holgura Hi.

t

Di Ti

Hi

Ci Ri

ti

La tarea ti será planificable si cumple la condición

+. . . + + + ≤ U(i) = i ⋅ (2 1/i−1) Ti

Ci T1

C1 Ti

Hi Ti-1

Ci-1


47

8.- Análisis de tiempos de respuesta

Un sistema es planificable si y solo si para todos los procesos el tiempo de respuesta máximo que se puede dar es menor que su plazo correspondiente.

El sistema es planificable si y solo si ∀i Ri ≤ Ti

∑ ⋅ Cj Tj j∈hp(i)

Ri Ri = Ci +

48

Esta ecuación se resolverá de una forma iterativa

El algoritmo finalizará cuando

a) W n+1 = W n

b) W n+1 > Ti , en este caso no se estaría cumpliendo el plazo

Wi n+1= Ci + ∑ ⋅ Cj Tj j∈hp(i)

Win

partiendo de

∑ Cj j∈hp(i)

Wi 0= Ci +


49

Ejemplo (A.Burns) Tarea Ti Ci

t1 7 3 t2 12 3 t3 20 5

para la tarea t1: W10 = 3 = R1

para la tarea t2: W2

0 = 3 +3 = 6 W2

1 = 3 + 6/7 ⋅ 3 = 6 = R2 para la tarea t3: W3

0 = 5 + 3 + 3 = 11 W3

1 = 5 + 11/7 ⋅ 3 + 11/12 ⋅ 3 = 14 W3

2 = 5 + 14/7 ⋅ 3 + 14/12 ⋅ 3 = 17 W3

3 = 5 + 17/7 ⋅ 3 + 17/12 ⋅ 3 = 20 W3

4 = 5 + 20/7 ⋅ 3 + 20/12 ⋅ 3 = 20 = R3 ∀i Ri ≤ Ti

50

♦ Tiempo de Bloqueo

♦ Interrupciones - Procesos esporádicos


Ri Ri = Ci + Bi +


Ri Ri = Ci + Bi + + ⋅ Cint Tint

Ri


51

Planificación monótona en plazos (DMS) Asigna las prioridades de forma inversamente proporcional a los Di

Tarea Ti Ci Di t1 100 20 80 t2 150 40 70 t3 200 60 100 t4 350 20 50

Prioridades: P4 > P2 > P1 > P3 Para sistemas en los que Di < Ti la DMS es óptima.

52

9.- Planificación dinámica Determina la prioridad de los procesos en tiempo de ejecución

EDF (Earliest Deadline First)

En un instante dado el sistema selecciona para su ejecución al proceso que tiene el siguiente plazo mas próximo


53

Ejemplo Proceso Ci Ti

P1 3 13 P2 12 24 P3 2 10 P4 5 45

Di = Ti

P 1

P 2

P 3

P 4

u .t .4 55 4 03 53 02 52 01 51 0 5 0

54

Análisis de planificabilidad

∑ ≤ 1 , N = nº de procesos existentesTiCi

i=1

N

Documents

Planificación de Sistemas de Tiempo Real - OCW UPMocw.upm.es/.../material-de-clase/transp_cap5_planificacion_str.pdf · Planificacion de Sistemas de Tiempo Real 27 Algoritmo para