1. El modelo de tareas periódicas
Una tarea periódica τi se caracteriza por:
| Parámetro | Símbolo | Significado |
|---|---|---|
| Período | Pi | Tiempo entre instancias consecutivas. |
| Tiempo de ejecución | Ci | Tiempo de CPU que necesita cada instancia. |
| Plazo | Di | Tiempo máximo desde la llegada hasta la terminación. Normalmente Di = Pi (plazo implícito). |
| Utilización | Ui | Ci / Pi. Fracción de CPU que necesita. |
Las tareas son independientes (no comparten recursos), preemptibles (se pueden interrumpir) y tienen plazo implícito (Di = Pi).
La utilización total es U = Σ Ui = Σ Ci / Pi. Si U > 1, el sistema no puede cumplir todos los plazos (no hay suficiente CPU).
En este tema asumimos que el plazo es igual al período (Di = Pi). Esta es la suposición más común en los sistemas de tiempo real y simplifica el análisis.
2. Rate Monotonic (RM)
Rate Monotonic (RM) es un algoritmo de planificación de tiempo real que asigna prioridades estáticas a las tareas según su período: la tarea con el período más corto tiene la mayor prioridad. Es un algoritmo de prioridades fijas (no apropiativo dentro de la prioridad, pero apropiativo entre prioridades).
RM es óptimo entre los algoritmos de prioridades fijas: si un conjunto de tareas es planificable por algún algoritmo de prioridades fijas, es planificable por RM.
La regla es simple: menor período = mayor prioridad. No depende del tiempo de ejecución, solo del período.
3. Ejemplo de RM
Tres tareas periódicas:
| Tarea | Período (P) | Ejecución (C) | Utilización (U = C/P) |
|---|---|---|---|
| τ1 | 5 | 2 | 0,40 |
| τ2 | 10 | 3 | 0,30 |
| τ3 | 15 | 4 | 0,27 |
Prioridades por RM: τ1 (P=5) > τ2 (P=10) > τ3 (P=15). La utilización total es 0,40 + 0,30 + 0,27 = 0,97.
Simulación (LCM de los períodos = 30):
En cada período, τ1 se ejecuta primero (2 unidades), luego τ2 (3 unidades), y finalmente τ3 (4 unidades). Todos los plazos se cumplen.
4. Planificabilidad de RM
La pregunta clave es: ¿se pueden cumplir todos los plazos? RM tiene una prueba de planificabilidad basada en la utilización:
Un conjunto de n tareas es planificable por RM si: U ≤ n·(21/n − 1)
El valor n·(21/n − 1) es el límite de utilización para RM. Para n tareas, si la utilización total es menor o igual a este valor, todos los plazos se cumplen. Si es mayor, puede o no ser planificable (hay que verificar con simulación).
| Número de tareas (n) | Límite de utilización |
|---|---|
| 1 | 1,000 |
| 2 | 0,828 |
| 3 | 0,780 |
| 4 | 0,757 |
| 5 | 0,743 |
| ∞ | ln(2) ≈ 0,693 |
Para nuestro ejemplo con 3 tareas, el límite es 0,780. La utilización total es 0,97, que es mayor que 0,780. Esto significa que la prueba no garantiza la planificabilidad, pero puede ser planificable (hay que verificar con simulación). En nuestro ejemplo, todos los plazos se cumplieron.
La prueba es suficiente pero no necesaria: si U ≤ límite, es planificable. Si U > límite, puede ser o no planificable (hay que verificar).
5. Earliest Deadline First (EDF)
EDF (Earliest Deadline First) es un algoritmo de planificación de tiempo real que asigna prioridades dinámicas según el plazo más cercano: la tarea con el plazo más cercano tiene la mayor prioridad. Es un algoritmo apropiativo.
EDF es óptimo entre todos los algoritmos de planificación (no solo los de prioridades fijas): si un conjunto de tareas es planificable por algún algoritmo, es planificable por EDF.
La regla es simple: plazo más cercano = mayor prioridad. La prioridad cambia dinámicamente a medida que se acercan los plazos.
EDF es el algoritmo óptimo para tareas periódicas con plazos implícitos: si un conjunto de tareas es planificable por algún algoritmo, es planificable por EDF. Ningún otro algoritmo puede hacerlo mejor.
6. Ejemplo de EDF
Las mismas tres tareas del ejemplo anterior:
| Tarea | Período (P) | Ejecución (C) |
|---|---|---|
| τ1 | 5 | 2 |
| τ2 | 10 | 3 |
| τ3 | 15 | 4 |
En EDF, las prioridades cambian dinámicamente. En t = 0, los plazos son: τ1 = 5, τ2 = 10, τ3 = 15. Se ejecuta τ1 (plazo más cercano). En t = 2, τ1 termina. Los plazos restantes: τ2 = 10, τ3 = 15. Se ejecuta τ2. En t = 5, τ2 termina. Se ejecuta τ3. En t = 9, τ3 termina. Y así sucesivamente.
En este ejemplo, EDF y RM producen el mismo resultado porque los plazos están ordenados por período (plazo implícito). EDF y RM difieren cuando los plazos no están ordenados por período.
7. Planificabilidad de EDF
EDF tiene una prueba de planificabilidad más simple y más general que RM:
Un conjunto de tareas es planificable por EDF si y solo si: U ≤ 1
Es decir, si la utilización total es ≤ 1 (100 %), todos los plazos se cumplen. Si U > 1, no se pueden cumplir todos los plazos.
Esta prueba es necesaria y suficiente: si U ≤ 1, es planificable; si U > 1, no lo es. No hay casos intermedios.
Para nuestro ejemplo, U = 0,97 ≤ 1, así que es planificable por EDF. Y también por RM (como verificamos por simulación).
EDF puede planificar conjuntos de tareas que RM no puede, porque el límite de EDF (U ≤ 1) es mayor que el de RM (U ≤ n·(2^(1/n) − 1)). Por ejemplo, con 3 tareas, RM admite hasta U = 0,780, mientras que EDF admite hasta U = 1,000.
8. RM vs EDF
| Aspecto | Rate Monotonic (RM) | Earliest Deadline First (EDF) |
|---|---|---|
| Tipo de prioridad | Estática (por período) | Dinámica (por plazo) |
| Apropiativo | Sí (entre prioridades) | Sí |
| Optimalidad | Óptimo entre prioridades fijas | Óptimo entre todos los algoritmos |
| Límite de utilización | n·(2^(1/n) − 1) ≈ 0,693 (n→∞) | 1,000 |
| Complejidad | Baja (prioridades fijas) | Media (hay que actualizar prioridades) |
| Overhead | Bajo | Mayor (más cambios de contexto) |
| Implementación | Simple | Más compleja |
| Uso real | Muy usado (RTOS) | Usado en algunos RTOS |
RM es más simple y tiene menos overhead, pero admite menos carga. EDF es más complejo pero admite más carga. La elección depende de los requisitos del sistema.
9. Limitaciones
- RM: el límite de utilización es bajo (0,693 para muchas tareas). No es óptimo entre todos los algoritmos.
- EDF: mayor overhead (más cambios de contexto). Más complejo de implementar.
- Ambos: asumen plazos implícitos (D = P). Con plazos arbitrarios, el análisis es más complejo.
- Ambos: asumen tareas independientes (sin recursos compartidos). Con recursos compartidos, hay inversión de prioridades.
- Ambos: asumen que el tiempo de ejecución es conocido y constante. En la práctica, varía.
10. Simulador interactivo
Este simulador ejecuta RM y EDF sobre un conjunto de tareas periódicas y muestra si se cumplen los plazos:
Simulador · RM y EDF
Rate Monotonic
EDF
| Tarea | Período | Ejecución | Utilización | RM cumple? | EDF cumple? |
|---|---|---|---|---|---|
11. Resumen
- RM asigna prioridades estáticas por período: menor período = mayor prioridad.
- RM es óptimo entre algoritmos de prioridades fijas.
- La prueba de planificabilidad de RM: U ≤ n·(2^(1/n) − 1).
- EDF asigna prioridades dinámicas por plazo: plazo más cercano = mayor prioridad.
- EDF es óptimo entre todos los algoritmos.
- La prueba de planificabilidad de EDF: U ≤ 1.
- EDF admite más carga que RM pero tiene más overhead.
- Ambos asumen plazos implícitos y tareas independientes.
12. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es Rate Monotonic?
Un algoritmo de tiempo real que asigna prioridades estáticas por período: menor período = mayor prioridad.
2. ¿Qué es EDF?
Earliest Deadline First: asigna prioridades dinámicas por plazo: plazo más cercano = mayor prioridad.
3. ¿Cuál es el límite de utilización de RM para n tareas?
n·(2^(1/n) − 1). Para n→∞, ≈ 0,693.
4. ¿Cuál es el límite de utilización de EDF?
1,000 (100 %).
5. ¿Cuál es más óptimo: RM o EDF?
EDF es óptimo entre todos los algoritmos. RM es óptimo solo entre prioridades fijas.
6. ¿Por qué RM es más usado que EDF en la práctica?
Porque es más simple, tiene menos overhead y las prioridades son estáticas (fáciles de implementar).
7. ¿Qué asumen RM y EDF sobre los plazos?
Que son implícitos: D = P.
8. ¿Qué ocurre si la utilización total supera 1?
No se pueden cumplir todos los plazos: no hay suficiente CPU.
9. ¿Qué asumen RM y EDF sobre las tareas?
Que son independientes (sin recursos compartidos) y preemptibles.
10. ¿Cuándo coinciden RM y EDF?
Cuando los plazos están ordenados por período (plazo implícito). En ese caso, las prioridades son las mismas.
Para practicar
- Calcula el límite de utilización de RM para 2, 3, 5 y 10 tareas.
- Diseña un conjunto de tareas planificable por EDF pero no por RM.
- Simula RM y EDF para las tareas τ1(0,5), τ2(0,8), τ3(0,12) con C=2,3,4.
- Explica por qué EDF tiene más overhead que RM.
- Investiga cómo SCHED_DEADLINE de Linux implementa EDF.
- Explica qué ocurre cuando los plazos no son implícitos.