Upload
garret
View
50
Download
1
Embed Size (px)
DESCRIPTION
CONCURRENCIA. PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL. Juan Antonio Fernández Madrigal, 2004 Departamento de Ingeniería de Sistemas y Automática Universidad de Málaga. Planificación de Procesos en Sistemas en Tiempo Real. Introducción. Hardware para Sistemas en T.R. - PowerPoint PPT Presentation
Citation preview
CONCURRENCIA. PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Juan Antonio Fernández Madrigal, 2004
Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
Planificación de Procesos en Sistemas en Tiempo Real
Software paraSistemas en T.R.
Software paraSistemas en T.R.
Tema III. InterfacesTema III. Interfaces
Tema IV. InterrupcionesTema IV. Interrupciones
Tema V. RedesTema V. Redes
Tema VI. PlanificaciónTema VI. Planificación
Tema VII. Sistemas OperativosTema VII. Sistemas Operativos
Tema VIII. ProgramaciónTema VIII. Programación
Hardware paraSistemas en T.R.Hardware para
Sistemas en T.R.
IntroducciónIntroducción
Tema II. MicroprocesadoresTema II. Microprocesadores
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
Planificación de Procesos en Sistemas en Tiempo Real
1. Teoría de la Planificación de Procesos de Tiempo Real
2. Modelado de Procesos y Conceptos Generales
3. Taxonomía de los Algoritmos de Planificación
4. Planificadores por Prioridades
5. Planificación con Prioridades Estáticas (RMS)
6. Planificación con Prioridades Dinámicas (EDF)
7. Conclusiones
8. Bibliografía Básica y Bibliografía Original
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
1. Teoría de la Planificación de Procesos de Tiempo Real(Real-Time Scheduling Theory)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Propósito: Satisfacer las restricciones temporales de los procesos concurrentes de un sistema informático en tiempo real.
Propósito: Satisfacer las restricciones temporales de los procesos concurrentes de un sistema informático en tiempo real.
Procedimiento: Planificar los recursos del sistema de acuerdo a ciertos algoritmos, de tal manera que la temporización del sistema sea predecible, comprensible y mantenible.
Procedimiento: Planificar los recursos del sistema de acuerdo a ciertos algoritmos, de tal manera que la temporización del sistema sea predecible, comprensible y mantenible.
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
2. Modelado de Procesos y Conceptos Generales
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
PROCESOS
Periódicos oSíncronos
Esporádicos oAsíncronos
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
2. Modelado de Procesos y Conceptos Generales
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
rp cp
dp
pp
procesos periódicosprocesos periódicos
tiempo
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
mine
ce
2. Modelado de Procesos y Conceptos Generales
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
tiempo
de
procesos esporádicosprocesos esporádicos
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
2. Modelado de Procesos y Conceptos Generales
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
mine
ce
tiempo
de
reducción de esporádicos a periódicosreducción de esporádicos a periódicos
= pa= pa
= ca= ca
= da= da
ra=0ra=0
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
2. Modelado de Procesos y Conceptos Generales
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
tiemporp cp
dp
pp
sincronización entre procesossincronización entre procesos
p1(1) p1(2)p2(1) p2(2)
p3(1) p3(2)
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
2. Modelado de Procesos y Conceptos Generales
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
conceptos generalesconceptos generales
Planificación: asignación de tiempo de procesador a los procesosFactor de Uso del Procesador (U): tiempo durante el que el procesador está asignado a algún proceso, si se aplica cierta planificaciónPlanificador: algoritmo que genera una planificaciónPlanificación Admisible: planificación que respeta las restricciones temporales de los procesosPlanificación Estable: planificación admisible que respeta las restricciones temporales de los procesos más importantes (“críticos”) bajo sobrecarga transitoriaOptimalidad de Planificadores: un planificador es óptimo si, existiendo una planificación admisible, encuentra una planificación admisibleTest de Planificabilidad: algoritmo que permite saber si existe una planificación admisible para un conjunto de procesos
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
2. Modelado de Procesos y Conceptos Generales
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
conceptos relativos a procesos concurrentesconceptos relativos a procesos concurrentes
Hiperperíodo: mínimo común múltiplo de los períodos de todos los procesos del sistema.
Planificación Expulsiva (preemptive): planificación en la que un proceso puede quitarle a otro el recurso del procesador en cualquier momento
Planificación No Expulsiva (non-preemptive): planificación en la que un proceso debe terminar su uso del procesador antes de cedérselo a otro (suele ser NP-hard)
Relación de Precedencia: relación entre dos procesos o subprocesos que implica que uno debe terminar su ejecución antes de que el otro comience
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
3. Taxonomía de los Algoritmos de Planificación
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Planificación de Procesos de Tiempo Real
Monoprocesador Multiprocesador / Distribuida
Estática (off-line) Dinámica (on-line)
Con esporádicos
Con inversión de prioridades
EDF / MLF Computaciónimprecisa
MUF
Compartiendorecursos
Robado de Ciclos /Sobrecarga
RMS
Consobrecarga
Conprecedencias
Planificación de Procesos de Tiempo Real
Monoprocesador
Estática (off-line) Dinámica (on-line)
EDF / MLFRMS
Consobrecarga
Conprecedencias
(Liu y Layland, 1973)
(Liu y Layland, 1973)
(Liu y Layland, 1973)
(Liu y Layland, 1973)
(Sha et al., 1986)(Sha et al., 1986)
(Chetto et al., 1990)(Chetto et al., 1990)
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
4. Planificadores por Prioridades
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Prácticamente la totalidad de los planificadores actuales.
Se le asigna una prioridad a cada proceso (off-line u on-line).
En cada momento se ejecuta el proceso disponible de mayor prioridad.
En los algoritmos que siguen, se supone planificación expulsiva.
La planificación por prioridad reduce el número de planificaciones admisibles
que pueden encontrarse, pero aún así la optimalidad está garantizada en
ciertos casos.
No es criterio válido para obtener una planificación admisible el otorgar
mayor prioridad a los procesos más importantes.
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
4. Planificadores por Prioridades
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Ejemplo de asignación de prioridades por importancia:
c1=8 r1=0 d1=24 p1=24c2=20 r2=0 d2=44 p2=44
tiempo
P1
P2
24 4820
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Requisitos: procesos independientes y periódicos, ri=0, planificación
expulsiva, tiempos de respuesta (deadlines) iguales a los períodos (di=pi).
Algoritmo de asignación de prioridades: tendrá más prioridad el proceso que
tenga un período menor (asignación de prioridad monotónica en frecuencia).
Optimalidad: el algoritmo es óptimo.
Test de planificabilidad: el factor de uso del procesador debe ser menor o
igual que el factor de uso garantizado del procesador.
Ui1
n cipi UGnn 2
1n 1<
limn UGnln2 0.69Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c1=8 r1=0 d1=24 p1=24c2=20 r2=0 d2=44 p2=44
U = 8/24+20/44 = 0.79 < UG2 = 2(21/2-1) = 0.83
tiempo
P1
P2
248 32 36
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Planificación RMS estable (con sobrecarga)Planificación RMS estable (con sobrecarga)
Objetivo: bajo tiempos de cómputo medios, obtener tiempo real duro (hard)
para todos los procesos. Bajo tiempos de cómputo máximos (sobrecarga),
obtener tiempo real duro para procesos críticos y blando (soft) para procesos
no críticos.
I. [U]críticos < [UGn]críticos
II. [Um]todos < [UGn]todos
III. [máx(pi)]críticos < [mín(pj)]no-críticos
necesarionecesario
necesarionecesario
Se puede forzarSe puede forzar
Paso previo: considerar críticos a procesos no críticos que violen III.
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Forzado de la condición III de estabilidadForzado de la condición III de estabilidad
Algoritmo de Transformación de Períodos: modificar los períodos de algunos
procesos sin modificar los procesos, hasta cumplir la condición III de
estabilidad.
Dos acciones posibles para modificar el sistema: se repiten hasta que se
cumpla la condición.
Acción A: ampliar el período de un proceso no-crítico. Se desglosa el proceso
Pi en k procesos, cada uno con período k*pi y con su primera activación
desplazada.
Acción A: ampliar el período de un proceso no-crítico. Se desglosa el proceso
Pi en k procesos, cada uno con período k*pi y con su primera activación
desplazada.
Acción B: reducir el período de un proceso crítico. Se ejecuta el proceso Pi
en k fases consecutivas, cada una con período pi /k.
Acción B: reducir el período de un proceso crítico. Se ejecuta el proceso Pi
en k fases consecutivas, cada una con período pi /k.
Fase 1 Fase 2 Fase 1 Fase 2 Fase 1 Fase 2
Bucle: mientras haya algún proceso conflictivo (crítico con período mayor que
un no-crítico, o viceversa), aplicarle la acción correspondiente. Si se violan las
condiciones I ó II de estabilidad, deshacer el cambio.
Bucle: mientras haya algún proceso conflictivo (crítico con período mayor que
un no-crítico, o viceversa), aplicarle la acción correspondiente. Si se violan las
condiciones I ó II de estabilidad, deshacer el cambio.
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c1=10 r1=0 cm1=4 d1=17 p1=17c2=5 r2=0 cm2=2 d2=9 p2=9c3=15 r3=0 cm3=5 d3=28 p3=28
RMS
tiempo
P1
P2
0
P3
5 10 15 20 25 30 35 40 45 50 55 60
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c1=10 r1=0 cm1=4 d1=17 p1=17c2=5 r2=0 cm2=2 d2=9 p2=9c3=15 r3=0 cm3=5 d3=28 p3=28
RMS
tiempo
P1
P2
0
P3
5 10 15 20 25 30 35 40 45 50 55 60
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c1=10 r1=0 cm1=4 d1=17 p1=17c2=5 r2=0 cm2=2 d2=9 p2=9c3=15 r3=0 cm3=5 d3=28 p3=28
Transformación de Períodos(chequeo de condiciones)
I. [U]críticos < [UGn]críticos : 0.59 < 1 : se cumple
II. [Um]todos < [UGn]todos : 0.64 < 0.78 : se cumple
III. [máx(pi)]críticos < [mín(pj)]no-críticos : 17 < 9 : no se cumple
No se puede incluir P2 como crítico:
no se cumple la condición I (U=1.1)No se puede incluir P2 como crítico:
no se cumple la condición I (U=1.1)
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c1=10 r1=0 cm1=4 d1=17 p1=17c2=5 r2=0 cm2=2 d2=9 p2=9c3=15 r3=0 cm3=5 d3=28 p3=28
Transformación de Períodos(Acción A sobre P2)
Transformación de P2: se desglosa en 2 procesos P21 y P22 con:
c21=5 r21=0 cm21=2 d21=18 p21=18c22=5 r22=0 cm22=2 d22=18 p22=18(Primera activación de P22 en t=9)
Cumple las tres
condiciones
de estabilidad
Cumple las tres
condiciones
de estabilidad
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c1=10 r1=0 cm1=4 d1=17 p1=17c21=5 r21=0 cm21=2 d21=18 p21=18c22=5 r22=0 cm22=2 d22=18 p22=18(Primera activación de P22 en t=9)c3=15 r3=0 cm3=5 d3=28 p3=28
RMS
tiempo
P1
P21
0
P3
5 10 15 20 25 30 35 40 45 50 55 60
P22
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c1=10 r1=0 cm1=4 d1=17 p1=17c21=5 r21=0 cm21=2 d21=18 p21=18c22=5 r22=0 cm22=2 d22=18 p22=18(Primera activación de P22 en t=9)c3=15 r3=0 cm3=5 d3=28 p3=28
RMS
tiempo
P1
P21
0
P3
5 10 15 20 25 30 35 40 45 50 55 60
P22
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c1=10 r1=0 cm1=4 d1=17 p1=17c2=5 r2=0 cm2=2 d2=9 p2=9c3=15 r3=0 cm3=5 d3=28 p3=28
Transformación de Períodos(Acción B sobre P1)
Transformación de P1: se secuencia en 2 fases, cada una con:
c’1=5 r’1=0 cm’1=2 d’1=8.5 p’1=8.5 Cumple las tres
condiciones
de estabilidad
Cumple las tres
condiciones
de estabilidad
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c’1=5 r’1=0 cm’1=2 d’1=8.5 p’1=8.5c2=5 r2=0 cm2=2 d2=9 p2=9c3=15 r3=0 cm3=5 d3=28 p3=28
RMS
tiempo
P’1
P2
0
P3
5 10 15 20 25 30 35 40 45 50 55 60
f1 f2 f1 f2 f1 f2 f1 f2
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
5. Planificación con Prioridades Estáticas (Rate Monotonic Scheduling = RMS)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
c’1=5 r’1=0 cm’1=2 d’1=8.5 p’1=8.5c2=5 r2=0 cm2=2 d2=9 p2=9c3=15 r3=0 cm3=5 d3=28 p3=28
RMS
tiempo
P’1
P2
0
P3
5 10 15 20 25 30 35 40 45 50 55 60
f1 f2 f1 f2 f1 f2 f1 f2
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Requisitos: procesos independientes y periódicos, ri=0, planificación
expulsiva, tiempos de respuesta (deadlines) iguales a los períodos (di=pi).
Algoritmo de asignación de prioridades: tendrá más prioridad el proceso que
tenga un tiempo límite menor (tiempo en el que cumplirá su próximo deadline)
Optimalidad: el algoritmo es óptimo. Buen comportamiento respecto al
número de expulsiones (bajo), respecto a otros algoritmos.
Test de planificabilidad: el factor de uso del procesador debe ser menor o
igual a 1 (U<1).
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Planificación EDF para procesos dependientesPlanificación EDF para procesos dependientes
Objetivo: producir una planificación admisible que respete las precedencias
temporales de los procesos.
Procedimiento: algoritmo de Chetto et al. de revisión de los tiempos límite.
Optimalidad: sigue siendo óptimo: si hay solución, encuentra una solución.
Test de planificabilidad (U<1): deja de ser válido: si, aún existiendo solución
con procesos independientes, no existiera solución en el caso de procesos
dependientes, el algoritmo EDF con los tiempos límites revisados
proporcionaría una planificación no admisible.
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Algoritmo de Chetto et al. de revisión de tiempos límiteAlgoritmo de Chetto et al. de revisión de tiempos límite
Procedimiento: transforma los tiempos límite para conseguir un sistema
idéntico que cumpla las restricciones de precedencia.
Fase I: enumeración de todos los procesos a ejecutar, según el hiperperíodo.
Fase II: obtención del grafo de precedencia (GdP).
Fase III: obtención del orden topológico inverso de los procesos en el GdP.
Fase IV: obtención de los tiempos límite sin revisar (di)
Fase V: cálculo de tiempos límite revisados (d*i=mín(di,mín{d*k-ck:Pi→Pk}))
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
P1={P11,P12} c11=4 c12=4 r1=0 d1=32 p1=32P2={P21,P22 ,P23 ,P24} c21=4 c22=4 c23=4 c24=4 r2=0 d2=64 p1=64P3={P31,P32} c31=8 c31=8 r3=0 d3=64 p3=64
P11(1), P12(1), P11(2), P12(2), P21(1), P22(1), P23(1), P24(1), P31(1), P32(1)
P1 P2 P3
Fase I: enumeración de todos los procesos a ejecutar, según el hiperperíodo.
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
P1={P11,P12} c11=4 c12=4 r1=0 d1=32 p1=32P2={P21,P22 ,P23 ,P24} c21=4 c22=4 c23=4 c24=4 r2=0 d2=64 p1=64P3={P31,P32} c31=8 c31=8 r3=0 d3=64 p3=64
Fase II: obtención del grafo de precedencia (GdP).
P11(1) P12(1) P11(2) P12(2)
P21(1) P22(1) P23(1) P24(1)
P31(1) P32(1)
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
P1={P11,P12} c11=4 c12=4 r1=0 d1=32 p1=32P2={P21,P22 ,P23 ,P24} c21=4 c22=4 c23=4 c24=4 r2=0 d2=64 p1=64P3={P31,P32} c31=8 c31=8 r3=0 d3=64 p3=64
Fase III: obtención del orden topológico inverso de los procesos en el GdP.
P11(1) P12(1) P11(2) P12(2)
P21(1) P22(1) P23(1) P24(1)
P31(1) P32(1)
P12(2), P24(1) , P32(1) , P11(2) , P23(1) , P12(1) , P22(1) , P31(1) , P11(1) , P12(1)
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
P1={P11,P12} c11=4 c12=4 r1=0 d1=32 p1=32P2={P21,P22 ,P23 ,P24} c21=4 c22=4 c23=4 c24=4 r2=0 d2=64 p1=64P3={P31,P32} c31=8 c31=8 r3=0 d3=64 p3=64
Fase IV: obtención de los tiempos límite sin revisar (di=k.pi)
P11(1) P12(1) P11(2) P12(2)
P21(1) P22(1) P23(1) P24(1)
P31(1) P32(1)
6464
6464
6464
6464
6464
3232
6464
6464
3232
6464
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
mín(64)=64mín(64)=64mín(64,60-4,64-8)=56
mín(64,60-4,64-8)=56
mín(64)=64mín(64)=64mín(64,64-4)=60mín(64,64-4)=60mín(64,60-4,64-8)=56
mín(64,60-4,64-8)=56
mín(32,32-4,56-4)=28
mín(32,32-4,56-4)=28
mín(64)=64mín(64)=64mín(64,64-4)=60mín(64,64-4)=60mín(32,60-4)=32mín(32,60-4)=32mín(32,32-4,56-4)=28
mín(32,32-4,56-4)=28
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
P1={P11,P12} c11=4 c12=4 r1=0 d1=32 p1=32P2={P21,P22 ,P23 ,P24} c21=4 c22=4 c23=4 c24=4 r2=0 d2=64 p1=64P3={P31,P32} c31=8 c31=8 r3=0 d3=64 p3=64
Fase V: cálculo de tiempos límite revisados (d*i=mín(di,mín{d*k-ck:Pi→Pk}))
P11(1) P12(1) P11(2) P12(2)
P21(1) P22(1) P23(1) P24(1)
P31(1) P32(1)
P12(2), P24(1) , P32(1) , P11(2) , P23(1) , P12(1) , P22(1) , P31(1) , P11(1) , P12(1)
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
6. Planificación con Prioridades Dinámicas (Earliest Deadline First = EDF)
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
Cronograma:
mín(64)=64mín(64)=64mín(64,60-4,64-8)=56
mín(64,60-4,64-8)=56
mín(64)=64mín(64)=64mín(64,64-4)=60mín(64,64-4)=60mín(64,60-4,64-8)=56
mín(64,60-4,64-8)=56
mín(32,32-4,56-4)=28
mín(32,32-4,56-4)=28
mín(64)=64mín(64)=64mín(64,64-4)=60mín(64,64-4)=60mín(32,60-4)=32mín(32,60-4)=32mín(32,32-4,56-4)=28
mín(32,32-4,56-4)=28P11(1) P12(1) P11(2) P12(2)
P21(1) P22(1) P23(1) P24(1)
P31(1) P32(1)
tiempo
P1
P2
0
P35 10 15 20 25 30 35 40 45 50 55 60 65
U=8/32+16/64+16/64=
3/4U=8/32+16/64+16/64=
3/4
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
7. Conclusiones
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
La planificación de tareas es de vital importancia en los sistemas en tiempo real.
En general, el problema es complicado e incluso irresoluble en tiempo polinomial.
Existen aproximaciones razonables que permiten obtener soluciones en casos
cercanos a los prácticos.
Los sistemas operativos y lenguajes de programación juegan un papel
imprescindible en la planificación de tareas de tiempo real, pero actualmente sólo
implementan planificación guiada por prioridades.
La planificación de tiempo real es un área de gran desarrollo en los últimos años.
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
8. Bibliografía Básica
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
BURNS A. y WELLINGS A. (2001). “Real-Time Systems and Programming
Languages”, 3ª edición, Addison-Wesley, ISBN 0-201-72988-1. (CAPÍTULO 13)
LIU J.W.S. (2000). “Real-Time Systems". Prentice Hall, ISBN 0-13-099651-3
(CAPÍTULOS 4,6,12)
DE LA PUENTE J.A. (1988). “Planificación de la Ejecución de Procesos en
Sistemas en Tiempo Real”, Universidad Politécnica de Valencia, Apuntes.
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga
8. Bibliografía Original
PLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REALPLANIFICACIÓN DE PROCESOS EN SISTEMAS EN TIEMPO REAL
HILLIER F.S. y LIEBERMAN G. J. (1991). “Introducción a la Investigación de Operaciones”. Mc.Graw Hill Interamericana.
STANKOVIC J.A. (1988). "Misconceptions About Real-Time Computing. A Serious Problem for Next-Generation Systems".
IEEE Computer vol. 21, no. 10.
RAMAMRITHAM K. y STANKOVIC J.A. (1994). "Scheduling Algorithms and Operating Systems Support for Real-Time
Systems". Proceedings of the IEEE, vol. 82, no. 1
XU J. y PARNAS D.L. (1993). "On Satisfying Timing Constraints in Hard-Real-Time Systems". IEEE Transactions on
Software Engineering, vol. 19, no. 1, pp. 70-84
GHOSH K., MUKHERJEE B., y SCHWAN K. (1994). "A Survey of Real-Time Operating Systems". Informe Técnico GIT-CC-
93/18 del Instituto Tecnológico de Georgia.
LIU C.L. y LAYLAND J.W. (1973). "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment". Journal
of the Association for Computing Machinery, vol. 20, no. 1, pp. 46-61.
SHA L., LEHOCZKY J.P. y JENSEN E.D. (1986). "Solutions for Some Practical Problems in Prioritized Preemptive
Scheduling". Proceedings of the IEEE Real-Time Systems Symposium.
CHETTO H., SILLY M., BOUTENCHOUF T. (1990). "Dynamic Scheduling of Real-Time Tasks under Precedence
Constraints". The Journal of Real-Time Systems, vol. 2, pp. 181-194.
IntroducciónIntroducción
Modelo de ProcesosModelo de Procesos
TaxonomíaTaxonomía
Algoritmos de Planificación
Algoritmos de Planificación
Juan Antonio Fernández Madrigal, 2003Departamento de Ingeniería de Sistemas y Automática
Universidad de Málaga