4.2-SOE_planificacion para el desarrollo

planificacion de los so

1. PLANIFICACIÓN EN SO
EMBEBIDOS DE TIEMPO
REAL
Basado en: Wang K. C. “Embeddedand Real-Time OperatingSystems” 2ed

2. SISTEMA EMBEBIDO DE TIEMPO REAL
•Un RTOS(Real-Time OperatingSystem) está diseñado para
garantizar que las tareas se ejecuten dentro de plazos
estrictos.
•Tipos de RTOS:
RTOSde tiempo duro: Incumplir un plazo causa fallo catastrófico
(ej.: control de aviones)
RTOSde tiempo blando: Retrasos son tolerables pero indeseables
(ej.: multimedia)
ECP
2

3. PLANIFICACIÓN DE TAREAS EN RTOS
•Algoritmos clave:
•RMS (Rate-MonotonicScheduling): Asigna prioridades estáticas basadas en frecuencias
de tareas (mayor frecuencia → mayor prioridad).
•EDF(EarliestDeadlineFirst): Prioriza tareas con plazos más cercanos (dinámico y
óptimo para sistemas schedulables).
•DMS(Deadline-MonotonicScheduling): Similar a RMS, pero prioriza por plazos
absolutos en lugar de frecuencias.
•Inversión de prioridad
Ocurre cuando una tarea de baja prioridad bloquea a una de alta prioridad.
Soluciones:
Techos de prioridad: Limitan la prioridad máxima de acceso a recursos compartidos.
Herencia de prioridad: Temporalmente eleva la prioridad de la tarea que posee el
recurso bloqueante.
ECP
3

4. PLANIFICACIÓN DE TAREAS EN RTOS–RMS
•RMS es un algoritmo de planificación utilizado para
asignar prioridades a tareas periódicas. Su objetivo es
garantizar que todas las tareas cumplan sus plazos
(deadlines) en sistemas con restricciones de tiempo.
ECP
4

5. PLANIFICACIÓN DE TAREAS EN RTOS–RMS
•Principios básicos:
Tareas periódicas: Cada tarea se ejecuta a intervalos regulares
(ej.: una tarea que lee un sensor cada 10 ms).
Prioridad estática: Las prioridades se asignan de forma fija al
inicio y no cambian durante la ejecución.
Regla de asignación:
A mayor frecuencia (menor período), mayor prioridad.
Ejemplo:
Tarea A (período = 5 ms) → Prioridad alta.
Tarea B (período = 20 ms) → Prioridad baja.
ECP
5

6. PLANIFICACIÓN DE TAREAS EN RTOS–RMS
•Condición de programabilidad (schedulability):
Para que un conjunto de n tareas sea programable bajo RMS, debe cumplirse:
Donde:
Ci= Tiempo de ejecución (worst-case executiontime) de la tareai.
Ti= Período de la tareai.
n= Número de tareas.
Límite de utilización:
Paran=1→ 100% (1 tarea puede usar toda la CPU).
Paran=2→ ~83%.
Paran→∞→ ~69% (límite deln(2)≈ 0.693)
Si la suma deCi/Tisupera este límite, no se puede garantizar que todas las tareas cumplan sus plazos
ECP
6

7. PLANIFICACIÓN DE TAREAS EN RTOS–RMS
•Ejemplo:
Supongamos 3 tareas:
Cálculo de programabilidad:
0.4+0.4+0.15=0.95
El límite para 3 tareas es:
3(2
1/3
−1)≈0.779
Conclusión: 95% > 77.9% →No es programable(se necesitaría reducirCio aumentarTi)
ECP
7
Tarea Ci(ms)Ti(ms)Ci/Ti Prioridad
A 2 5 0.4 Alta(menorTi)
B 4 10 0.4 Media
C 3 20 0.15 Baja(mayorTi)

8. PLANIFICACIÓN DE TAREAS EN RTOS–RMS
•Ventajas
Simple de implementar.
Óptimo para tareas periódicas con prioridades estáticas (ningún otro
algoritmo puede planificar un conjunto de tareas si RMS no puede)
•Desventajas:
No funciona bien con tareas aperiódicas (ej.: eventos externos).
Subutiliza la CPU (límite del 69% para muchas tareas).
No considera deadlinesdiferentes al período (para eso se usa DM o
EDF)
ECP
8

9. PLANIFICACIÓN DE TAREAS EN RTOS–RMS
•Comparación con EDF(EarliestDeadlineFirst):
ECP
9
Característica RMS EDF
Tipo de prioridad Estática Dinámica
Criterio Período (TiTi) Deadline más cercano
Utilización máxima ≤ 69% (paran→∞n→∞) 100%
Complejidad Baja
Mayor (requiere recalcular
prioridades)
Uso típico Sistemas críticos con tareas fijas
Sistemas flexibles con deadlines
variables

10. PLANIFICACIÓN DE TAREAS EN RTOS–EDF
•EDF(EarliestDeadlineFirst) es un algoritmo de planificación dinámico
utilizado en sistemas operativos de tiempo real (RTOS) que asigna
prioridades en función de los deadlines(plazos límite) de las tareas. A
diferencia de RMS (que usa prioridades estáticas basadas en períodos),
EDFes óptimo para sistemas de tiempo real porque puede lograr una
utilización del 100% de la CPU mientras se cumplan todas las
restricciones de tiempo
ECP
10

11. PLANIFICACIÓN DE TAREAS EN RTOS–EDF
•Principios básicos:
Asignación dinámica de prioridades: La tarea con el deadlinemás
cercano en el tiempo tiene la mayor prioridad.
Funciona para tareas periódicas y aperiódicas (ej.: eventos esporádicos).
No tiene límite de utilización teórica: Si el sistema es programable, EDF
puede garantizar que todas las tareas cumplan sus plazos incluso con
un uso del 100% de la CPU (a diferencia de RMS, que tiene un límite
del ~69%).
ECP
11

12. PLANIFICACIÓN DE TAREAS EN RTOS–EDF
•Condición de programabilidad:
Un conjunto de tareas es planificablebajo EDFsi y solo si:
Donde:
Ci=Worst-Case ExecutionTime(WCET, tiempo máximo de ejecución).
Ti= Período de la tarea (o tiempo entredeadlinessi son aperiódicas).
ECP
12

13. PLANIFICACIÓN DE TAREAS EN RTOS–EDF
•Ejemplo:
Tarea A:Ci=2ms,Ti=5ms→2/5=0.4
Tarea B:Ci=3ms,Ti=10ms→3/10=0.3
Tarea C:Ci=2ms,Ti=20ms→2/20=0.1
0.4+0.3+0.1=0.8(≤1)→**Programable
Si la suma supera1, el sistema no es programable (se necesitaría
reducirCio aumentarTi).
ECP
13

14. PLANIFICACIÓN DE TAREAS EN RTOS–EDF
•Ejemplo práctico:
Supongamos 3 tareas:
Secuencia de ejecución:
t=0ms: Se activan todas las tareas.
Deadlines: A (5ms), B (10ms), C (20ms).
Prioridad: A > B > C.
Se ejecuta A (2ms). CPU ocupada hasta t=2ms.
t=2ms: A termina. Siguiente deadlinemás cercano es B (10ms).
Se ejecuta B (3ms). CPU ocupada hasta t=5ms.
t=5ms:
A se reactiva (nuevo período, deadlineen t=10ms).
Deadlines: A (10ms), B (10ms), C (20ms).
Empate: Generalmente, se elige la tarea que ya estaba en ejecución (B).
B termina en t=8ms.
t=8ms:
Deadlines: A (10ms), C (20ms).
Se ejecuta A (2ms). CPU ocupada hasta t=10ms.
t=10ms:
A y B se reactivan.
Deadlines: A (15ms), B (20ms), C (20ms).
Se ejecuta A (2ms), luego B (3ms), etc.
ECP
14
Tarea CiCi(ms) TiTi(ms)
Deadline(desde
su activación)
A 2 5 5 ms
B 3 10 10 ms
C 1 20 20 ms

15. PLANIFICACIÓN DE TAREAS EN RTOS–EDF
•Ventajas:
Óptimo: Si un conjunto de tareas es programable, EDFsiempre encontrará una
secuencia válida.
Alta utilización de CPU: Puede llegar al 100% (a diferencia de RMS, limitado al
~69%).
Funciona con tareas aperiódicas: Útil en sistemas con eventos impredecibles
•Desventajas:
Complejidad: Requiere recalcular prioridades en cada activación de tarea (overhead
mayor que RMS).
Menos predecible en sobrecarga: Si el sistema no es programable, puede fallar
catastróficamente (RMS degrada suavemente).
Dependencia de deadlinesexactos: Si una tarea no declara su deadlinecorrectamente,
el sistema puede fallar.
ECP
15

16. PLANIFICACIÓN DE TAREAS EN RTOS–EDF
•Comparación con RMS:
ECP
16
Criterio RMS EDF
Tipo de prioridad Estática (basada en período)Dinámica (basada endeadline)
Utilización máxima ~69% (paran→∞n→∞) 100%
Optimalidad
No óptimo (falla en algunos
casos schedulables)
Óptimo(siempre que∑Ci/Ti≤1)
Uso típico
Sistemas críticos con tareas
fijas (ej.: control de motores)
Sistemas flexibles
condeadlinesvariables (ej.:
multimedia)

17. PLANIFICACIÓN DE TAREAS EN RTOS–DMS
•DMS(DeadlineMonotonicScheduling)es un algoritmo de planificación
para sistemas de tiempo real que asignaprioridades estáticasbasadas en
losdeadlinesrelativos(plazos límite) de las tareas.
•Es una extensión deRMS (RateMonotonicScheduling), pero en lugar de
usar elperíodo(Ti) para asignar prioridades, utiliza eldeadline
relativo(Di), que puede ser diferente al período.
ECP
17

18. PLANIFICACIÓN DE TAREAS EN RTOS–DMS
•Principios clave:
Prioridad estática: Las prioridades se asignan al inicio y no cambian.
Regla de asignación:
A menorDiDi(deadlinemás corto), mayor prioridad.
Ejemplo:
Tarea A:Di=3msDi=3ms→Alta prioridad.
Tarea B:Di=10msDi=10ms→Baja prioridad.
Casos especiales:
SiDi=Ti(deadlineigual al período), DMSequivale a RMS.
SiDi<Ti, DMSesmás flexibleque RMS.
ECP
18

19. PLANIFICACIÓN DE TAREAS EN RTOS–DMS
•Condición de programabilidad:
La condición para que un conjunto de tareas sea planificablebajo DMSes similar a la
de RMS, pero consideraDien lugar deTi:
Donde:
•Ci= Tiempo de ejecución en el peor caso (WCET).
•Di= Deadlinerelativo (tiempo máximo permitido para completar la tarea desde su
activación).
•n= Número de tareas.
ECP
19

20. PLANIFICACIÓN DE TAREAS EN RTOS–DMS
•Ejemplo:
Cálculo de programabilidad:
0.66+0.25+0.33=1.24
El límite para 3 tareas es3(2
1/3
−1)≈0.78(78%).
1.24 > 0.78 → No es programable bajo DMS(se necesitaría
reducirCio aumentarDi).
ECP
20
Tarea Ci(ms)Di(ms)Ti(ms)Ci/Di
A 2 3 5 0.66
B 1 4 10 0.25
C 2 6 20 0.33

21. PLANIFICACIÓN DE TAREAS EN RTOS–DMS
•Ejemplo de aplicación:
Supongamos un sistema de control industrial con:
Tarea 1: Monitoreo de temperatura (Ci=1ms,Di=2ms,Ti=5ms).
Tarea 2: Control de motor (Ci=2ms,Di=5ms,Ti=10ms).
Asignación de prioridades:
Tarea 1 (Di=2ms) →Prioridad más alta.
Tarea 2 (Di=5ms) →Prioridad más baja.
Secuencia de ejecución:
t=0ms: Se activan ambas tareas.
Se ejecutaTarea 1(1ms) por tener mayor prioridad.
t=1ms: Tarea 1 termina. Se ejecutaTarea 2(2ms).
t=3ms: Tarea 2 termina. CPU inactiva hasta t=5ms (siguiente activación de Tarea
1).
ECP
21

22. PLANIFICACIÓN DE TAREAS EN RTOS–DMS
•Conclusión:
•DMSes idealcuando:
Las tareas tienen deadlinesmás cortos que sus períodos (Di<Ti).
Se requiereprevisibilidad(prioridades estáticas).
No se necesita máxima utilización de CPU (para eso, EDFes mejor).
•Ejemplos típicos:
Control de robots (donde ciertas tareas deben completarse antes de que finalice un
ciclo de control).
Sistemas embebidos con restricciones temporales estrictas, pero períodos
fijos.
Si los deadlinesson iguales a los períodos (Di=Ti),RMS es equivalente y más simple. Si
los deadlinesson dinámicos o se requiere máxima eficiencia,EDFes la mejor opción.
ECP
22

23. PLANIFICACIÓN DE TAREAS EN RTOS–DMS
•Ventajas:
Más flexible que RMScuandoDi<Ti(ej.: tareas con deadlinesmás
estrictos que sus períodos).
Fácil de implementar(prioridades estáticas).
Predecible(útil en sistemas críticos).
•Desventajas:
No óptimo: Al igual que RMS, tiene un límite de utilización (~69%
paran→∞).
No funciona bien con deadlinesdinámicos(para eso se usa EDF).
ECP
23

24. PLANIFICACIÓN DE TAREAS EN RTOS–DMS
•Comparación con RMS y EDF:
ECP
24
Criterio RMS DMS EDF
Base de
prioridad
Período (Ti) Deadlinerelativo (Di)Deadline absoluto (dinámico)
Tipo de
prioridad
Estática Estática Dinámica
Optimalidad No óptimo
No óptimo (pero mejor
que RMS siDi≠Ti)
Óptimo(100% utilización)
Complejidad Baja Baja Alta
Mejor uso Tareas conDi=TiTareas conDi<Ti Sistemas con deadlinesflexibles

25. PLANIFICACIÓN DE TAREAS EN RTOS
•Inversión de prioridad
La inversión de prioridad es un problema crítico en sistemas de tiempo
real donde una tarea de alta prioridad es bloqueada por una tarea de
baja prioridad, violando el principio de que las tareas más importantes
deben ejecutarse primero.
Ocurre cuando se usan mecanismos de sincronización (como semáforos o
mutex) en entornos multitarea.
ECP
25

26. PLANIFICACIÓN DE TAREAS EN RTOS
•Ejemplo de inversión de prioridad:
Supongamos 3 tareas en un sistema:
Tarea H (Alta prioridad).
Tarea M (Media prioridad).
Tarea L (Baja prioridad).
Escenario de inversión:
Paso 1: La tarea L (baja) adquiere un mutex(recurso compartido, ej.: acceso a un sensor).
Paso 2: La tarea H (alta) se activa y trata de adquirir el mismo mutex, pero queda bloqueada
porque L aún lo tiene.
Paso 3: La tarea M (media) se activa y, al no necesitar el mutex, se ejecuta antes que H
(¡aunque H tiene mayor prioridad!).
Resultado:
H está esperando a L, pero M la retrasa.
La prioridad de H está "invertida" temporalmente, ya que M (prioridad media) se ejecuta
antes. ECP
26

27. PLANIFICACIÓN DE TAREAS EN RTOS
•Ejemplo de inversión de prioridad:
Tiempo Evento
-----------|------------------------
t=0 | L (baja) toma el mutex.
t=1 | H (alta) intenta tomar el mutex→ se bloquea.
t=2 | M (media) se activa y ejecuta (¡mientras H espera!).
t=3 | M termina.
t=4 | L libera el mutex→ H finalmente lo obtiene.
ECP
27

28. PLANIFICACIÓN DE TAREAS EN RTOS
•Consecuencias:
Violación de deadlines: La tarea de alta prioridad (H) puede incumplir
su plazo límite.
Comportamiento impredecible: El sistema ya no es determinista, lo cual
es inaceptable en sistemas de tiempo real (ej.: robots, aviónica).
Ejemplo famoso:
En 1997, el roverMars Pathfinderde la NASA sufrió reinicios
frecuentes debido a inversión de prioridad no controlada en su sistema
VxWorks.
ECP
28

29. PLANIFICACIÓN DE TAREAS EN RTOS
•Soluciones comunes:
A. Herencia de Prioridad (PriorityInheritance)
Mecanismo:
Cuando una tarea de alta prioridad (H) es bloqueada por una de baja
prioridad (L), esta última hereda temporalmente la prioridad de H hasta
liberar el recurso.
Así, M no puede interrumpir a L mientras H espera.
Ejemplo:
En el escenario anterior, cuando H intenta tomar el mutex:
L hereda la prioridad de H.
M no puede ejecutarse hasta que L libere el mutex.
H accede al recurso inmediatamente después.
ECP
29

30. PLANIFICACIÓN DE TAREAS EN RTOS
•Soluciones comunes:
B. Techos de Prioridad (PriorityCeiling)
Mecanismo:
Cada recurso compartido (mutex) tiene un "techo" (prioridad máxima predefinida).
Cuando una tarea adquiere el recurso, su prioridad se eleva al techo (evitando que tareas
intermedias lo bloqueen).
Ventaja:
Más predecible que la herencia (no hay cambios dinámicos de prioridad).
C. Protocolo de Donación de Prioridad (PriorityDonation)
Usado en sistemas como Linux RTy FreeRTOS.
Similar a la herencia, pero permite transferencias de prioridad más
complejas (ej.: cadenas de bloqueo).
ECP
30

31. PLANIFICACIÓN DE TAREAS EN RTOS
•Comparación de soluciones:
ECP
31
Solución Complejidad Overhead Previsibilidad Implementación Típica
Herencia de
Prioridad
Media Moderado Buena Mutex en POSIX, FreeRTOS
Techos de
Prioridad
Baja Bajo Excelente VxWorks, QNX
Donación de
Prioridad
Alta Alto Variable Linux RT

32. PLANIFICACIÓN DE TAREAS EN RTOS
•Conclusión:
La inversión de prioridad es un problema serio en sistemas donde el
cumplimiento de deadlineses crucial. Las soluciones como:
Herencia de prioridad (simple y efectiva),
Techos de prioridad (más determinista),
Donación de prioridad (para casos complejos),
garantizan que las tareas de alta prioridad no sean bloqueadas indefinidamente. Su
implementación depende del sistema operativo y los requisitos de previsibilidad.
Escenarios donde es importante
En sistemas embebidos críticos:
Aviónica (control de vuelo).
Robots industriales.
Dispositivos médicos (ej.: marcapasos).
ECP
32