Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 1
Analisis de Planificación
Dr. Pedro Mejía Alvarez
CINVESTAV-IPN, Departamento de Computación
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 2
Indice
• Planificación.• Analisis de Planificabilidad.• Metodos Exactos.• Metodos Inexactos.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 3
Objetivos
Un método de planificación tiene dos aspectos importantes:
Un algoritmo de planificación que determina el orden de acceso de la tareas a los recursos del sistema ( en particular al procesador ) Un método de análisis que permite calcular el comportamiento temporal del sistema.
Así se puede comprobar si los requisitos temporales están garantizados en todos los casos posibles. En general se estudia el peor comportamiento posible.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 4
Modelo de tareas
Inicialmente consideramos un modelo simple:
— El conjunto de tareas es estático— Todas las tareas son periódicas— Las tareas son independientes unas de otras— Los plazos de respuesta de todas las tareas son iguales a los períodos respectivos— El tiempo de ejecución máximo de cada tarea es conocido— Las operaciones del kernel son instantáneas
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 5
Parámetros de planificación
N Número de tareasT Período de activaciónC Tiempo de ejecución máximoD Plazo de respuestaR Tiempo de respuesta máximoP Prioridad
En el modelo anterior, para todas las tareas :
Se trata de asegurar que
j
Cj < Dj = Tj
Rj < Dj
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 6
Hiperperíodo
En el modelo de tareas simple, el valor
se denomina hiperperíodo del sistema
El comportamiento temporal se repite cada hiperperíodo
H = m c m ( Tj )
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 7
Planificacion
• Metodos Exactos.
• Metodos Inexactos.
• Metodos Estaticos.
• Metodos Dinamicos.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 8
Proceso de Planificación
Planificador
Carga de Trabajode Tiempo Real
Análisis dePlanificabilidad
AplicaciónAplicaciónCríticaCrítica
AplicaciónAplicaciónCríticaCrítica
No es planificableNo es planificableNo es planificableNo es planificable
Tarea
EJECUCIÓNCi
Ti
Di
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 9
Proceso de Planificación (estados)
activación test deaceptación
LISTA
BLOQUEO
EJECUCION
despachar
expulsión
espera enrecurso ocupado
recurso liberado
SI
NO
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 10
Test Exactos
Diseñados para verificar la planificabilidad de unConjunto de tareas de tiempo real.
Si el resultado del test es positivo entonces todasLas tareas cumplen con sus plazos. Si el resultadoEs negativo, alguna tarea pierde su plazo.
Tiene una alta complejidad computacional. Se conocen solo los tests basados en el tiempo deRespuesta y en la demanda de tiempo.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 11
Instante crítico
El cronograma se puede utilizar para comprobar si se cumplen los plazos
— Hay que trazar el cronograma durante un hiperperíodo completo— En el caso más desfavorable, H = O(N )
El tiempo de respuesta es máximo cuando todas las tareas se activan a la vez Se denomina instante crítico Si el instante inicial es crítico basta comprobar el primer ciclo de cada tarea
N
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 12
Análisis del tiempo de respuesta
• La prueba del factor de utilización no es exacta, ni se puede generalizar a modelos de tareas más complejos• La construcción de un cronograma es compleja, incluso considerando que el instante inicial es crítico• Veremos una prueba basada en el cálculo del tiempo de respuesta de cada tarea
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 13
Ecuación del tiempo de respuesta
El tiempo de respuesta de una tarea es la suma desu tiempo de cómputo más la interferencia que sufre
por la ejecución de tareas más prioritarias
j
i
C C
Ri
j j
R = C + Ij j j
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 14
Ecuación del tiempo de respuesta
0 10 20 30 40 50 60 70 80
1
2
3
R3
R3 = C3 + I3
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 15
Cálculo de la interferencia máxima
Para una tareade prioridad superior
Para todas las tareasde prioridad superior
C C
Rj
j j
j
j
IR
TCi
j i
jj
IR
TCj
j
jj hp ij
( )
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 16
Cálculo del tiempo de respuesta
La ecuación del tiempo de respuesta queda así:
Rj es la solución mínima de la ecuación
• La ecuación no es continua ni lineal• No se puede resolver analíticamente
R CR
TCj j
j
jj
j hp j
( )
W CW
TCj
j
jj
j hp j
( )
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 17
Iteración linealLa ecuación del tiempo de respuesta se puederesolver mediante la relación de recurrencia
Un valor inicial aceptable es
Se termina cuandoa) , o bien
b) (no se cumple el plazo)
W CW
TCi
ni
in
jj
j hp i
1
( )
W C Ci i jj hp i
0
( )
W Wn n 1
W Tnj
1
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 18
Ejemplo 4Tarea T C P R
1 7 3 3 32 12 3 2 63 20 5 1 20
W
W
W
10
20
21
3
3 3 6
36
73 6
;
;
Todas las tareas tienen sus plazos garantizadosTenemos una condición suficiente y necesaria
1
2
:
:
W
W
W
W
W
30
31
32
33
34
5 3 3 11
511
73
11
123 14
514
73
14
123 17
517
73
17
123 20
520
73
20
123 20
;
;
;
;
3:
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 19
Test Exacto de Lehhockzky: Basado en la demanda del procesador
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 20
Test Inexactos
Diseñados para verificar la planificabilidad de unConjunto de tareas de tiempo real.
Si el resultado del test es positivo entonces todaslas tareas cumplen con sus plazos. Si el resultado es negativo, entonces no se sabe con certeza si alguna Tarea pierde su plazo.
Tienen una baja complejidad computacional. Se conocen varios tests.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 21
Factor de utilización
La cantidad
es el factor de utilización del procesador Es una medida de la carga del procesador para un conjunto de tareas En un sistema monoprocesador debe ser
U< 1
UC
Tj
jj
N
1
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 22
Condición de garantía de los plazosbasada en la utilización
Para el modelo simple, con prioridades monótonas en frecuencia, los plazos están garantizados si
La cantidad
U (N) = N ( 2 - 1)
es la utilización mínima garantizada para N tareas
0VN
UC
TNj
j
VN
j
N
2 1
1
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 23
Utilización mínima garantizada
N N0
1 1.000
2 0.828
3 0.779
4 0.756
5 0.743
lim U Nn 0 2 0 693log ,
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 24
Ejemplo 1Tarea T C P U
1 30 10 3 0.3332 40 10 2 0.2503 50 12 1 0.240
0.823
El sistema no cumple laprueba de utilización(U > 0.779)La tarea 3 falla en t = 50
0 20 40 60 80 100 120 140 160
fallo!
123
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 25
Ejemplo 2Tarea T C P U
1 16 4 3 0.2502 40 5 2 0.1253 80 32 1 0.400
0.775
Este sistema estágarantizado(U < 0.779)
0 10 20 30 40 50 60 70 80
123
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 26
Ejemplo 3Tarea T C P U
1 20 5 3 0.2502 40 10 2 0.2503 80 40 1 0.500
1.000
Este sistema no pasa laprueba (U < 0.779),pero se cumplen los plazos
0 10 20 30 40 50 60 70 80
123
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 27
Test basado en el periodo: IP
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 28
Test basado en el periodo: PO
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 29
Test basado en la utilizacion: UO