Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 1
Planificación con Prioridades Fijas
Dr. Pedro Mejía Alvarez
CINVESTAV-IPN, Sección de Computación
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 2
Indice
• Planificación con prioridades estaticas• Tareas periódicas independientes
• Modelo Rate Monotonic • Factor de Utilización• Instante crítico• Análisis de tiempo de respuesta• Planificación Deadline Monotonic
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 3
Planificación con prioridades fijas
Las tareas se ejecutan como• procesos concurrentesUna tarea puede estar en varios• estadosLas tareas ejecutables se• despachan para su ejecución en orden de prioridadEl despacho puede hacerse
— con desalojo— sin desalojo
En general supondremos• prioridades fijas con desalojo
suspendida
lista
ejecutandose
activar
despachar
suspender
desalojar
bloqueada
activarbloquear
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 4
Modelo Rate Monotonic
La asignación de mayor prioridad a las tareas de menor período ( rate monotonic scheduling: Liu & Layland ) es óptima para el modelo de tareas simple ( tareas periódicas, independientes, con plazos iguales a los períodos )
Si se puede garantizar los plazos de un sistema detareas con otra asignación de prioridades, se puedengarantizar con la asignación monótona en frecuencia
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 5
Modelo RM
• Las instancias de la tareas periodica i se activan
regularmente con una frecuencia constante. El intervalo Ti entre dos instancias consecutivas es el periodo de la tarea.
•Todas las instancias de la tarea i tienen el mismo tiempo
(constante) de ejecución (peor caso) Ci.
•Todas las instancias de una tarea periodica i tienen el
mismo plazo relativo Di, el cual es igual al periodo Ti.• Asumiremos no se comparten recursos entre tareas•No existen restricciones de precedencia entre las tareas.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 6
Modelo RM
• Todos las tareas se ejecutan en un solo procesador• Tiempo en ejecutar el cambio de contexto = 0• Inicialmente no tendremos tareas aperiodicas.•La tarea de mas alta prioridad (y menor periodo) se ejecuta primero. Si hay tareas de igual prioridad, se escoge “arbitrariamente”.• Las tareas son expulsables.•Las tareas no se pueden suspender por si mismas, por ejemplo por operaciones de E/S.•Las tareas se inician tan pronto como arriban al sistema, y tan pronto como se marca su inicio de instancia.Despues trataremos el tema de las tareas aperiodicasy de compartir recursos
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 7
• Rate-Monotonic
• Earliest Deadline First
• Shortest slack time first
(2, 1)
(5, 2.5)
missed deadline
(2, 1)
(5, 2.5)
(2, 1)
(5, 2.5)
0 1 2 3 4 5 6 7 8 9 10
Planificación basada en Prioridades
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 8
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 la prueba de utilizacion consiste en verificar:
U< 1
UC
Tj
jj
N
1
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 9
Factor de utilización
La prueba del factor de utilización puede tener 1 de 3 resultados:
• 0 < U < Umin(N) ----- Éxito• Umin(N) < U < 1.0 ----- Prueba inconclusa•1.0 < U ----- Sobrecarga
La prueba de la utilización es conservadora
Es necesario una prueba mas precisa.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 10
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 ( 21/N - 1)
es la utilización mínima garantizada para N tareas
min
N
j
N
j
j NT
CU
1
/1 12
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 11
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 12
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!
1
2
3
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 13
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
1
2
3
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 14
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
1
2
3
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 15
Rate Monotonic
•RMS no puede utilizar 100% del CPU, aunque el tiempo de cambio de contexto sea cero. A menos que las tareas sean harmónicas.•Tareas Harmónicas: Los periodos de las tareas son múltiplos unos de otros. •Segun estudios estadisticos las tareas llegan a utilizar hasta un 90% del CPU.•Ventajas: Su implementación es facil, eficiente y predecible.•Desventajas:desperdicio del CPU.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 16
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(NN )
• 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 la primera instancia de cada tarea. No hay que analisar todo el hiperperiodo.
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 17
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 18
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
j
C C
Rj
j j
R = C + Ij j j
Dr. Pedro Mejía Alvarez Sistemas de Tiempo Real Transparencia 19
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 20
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 21
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 22
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 23
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 24
Deadline Monotonic
Cuando los plazos son menores o iguales que losperíodos, la asignación de mayor prioridad a lastareas de menor plazo de respuesta(deadline monotonic scheduling) es óptima
El tiempo de respuesta se calcula de la misma forma que con la asignación monótona en frecuencia
— se termina cuando W =W ,
— o cuando W >Dn+1i
n+1i
ni
i
Top Related