1. Por qué hay que predecir
SJF y SRTF son los algoritmos que minimizan el tiempo de espera promedio, pero tienen un requisito imposible: necesitan conocer la duración de las ráfagas de CPU antes de ejecutarlas. En la práctica, un proceso no sabe cuánto va a durar su próxima ráfaga. Un compilador no sabe si va a tardar 0,1 s o 10 s en compilar el siguiente archivo; un servidor web no sabe si la siguiente petición va a ser un archivo pequeño o uno enorme.
La única información disponible es el historial: las duraciones de las ráfagas anteriores. A partir de ese historial, el sistema puede estimar la duración de la próxima ráfaga. Esa estimación es la que usa SJF (o SRTF) para elegir el siguiente proceso.
La predicción no es perfecta: el sistema se equivocará a veces. Pero un SJF con predicción razonable sigue siendo mejor que FCFS, que no usa ninguna información.
El sistema no adivina la duración de la próxima ráfaga; la estima a partir del historial. La calidad de la estimación depende del método y del parámetro alpha. Un buen método sigue las tendencias sin sobre-reaccionar a los cambios.
2. El problema de la predicción
El problema de la predicción tiene estas características:
- La ráfaga siguiente depende del programa y de los datos: no hay una fórmula que la determine.
- Las ráfagas son variables: siguen una distribución de cola larga (tema 2). La mayoría son cortas, pero unas pocas son muy largas.
- El historial es limitado: guardar todas las ráfagas anteriores consume memoria y tiempo.
- El contexto cambia: un proceso puede tener ráfagas cortas al principio y largas después (por ejemplo, al procesar un archivo grande).
Un buen método de predicción debe:
- Ser rápido: se ejecuta en cada cambio de contexto.
- Usar poca memoria: no puede guardar todo el historial.
- Seguir las tendencias: si las ráfagas están creciendo, la predicción debe crecer.
- No sobre-reaccionar: una ráfaga anormalmente larga no debe distorsionar la predicción para siempre.
3. Métodos simples
Antes de ver el promedio exponencial, veamos dos métodos simples que sirven de referencia:
| Método | Fórmula | Ventajas | Desventajas |
|---|---|---|---|
| Última ráfaga | Tn+1 = tn | Trivial, O(1). | Muy sensible a cambios. Una ráfaga anormal distorsiona la predicción. |
| Promedio simple | Tn+1 = (Σ ti) / n | Suaviza las fluctuaciones. | Memoria O(n). Las ráfagas antiguas pesan igual que las recientes. |
El método de la última ráfaga asume que la próxima ráfaga será igual a la anterior. Funciona bien si las ráfagas son estables, pero falla si hay cambios.
El promedio simple suaviza, pero tiene dos problemas: necesita guardar todas las ráfagas (memoria O(n)) y da el mismo peso a ráfagas antiguas y recientes, lo que hace que reaccione lentamente a los cambios.
El promedio exponencial resuelve ambos problemas.
4. El promedio exponencial
El promedio exponencial (exponential averaging) es un método de predicción que combina la última ráfaga observada con la predicción anterior, ponderando cada una con un factor α (alpha). Las ráfagas antiguas contribuyen cada vez menos, de forma exponencial.
La idea es simple: la predicción para la próxima ráfaga es una mezcla de lo que ocurrió la última vez y de lo que se predijo antes. Si α es grande, se confía más en la última ráfaga (reacción rápida). Si α es pequeño, se confía más en la predicción anterior (suavizado).
El promedio exponencial tiene estas ventajas:
- Memoria O(1): solo necesita guardar la predicción anterior y la última ráfaga.
- Rápido: una sola multiplicación y una suma por predicción.
- Ponderación exponencial: las ráfagas antiguas contribuyen cada vez menos, sin necesidad de guardarlas.
- Ajustable: el parámetro α permite elegir entre reacción rápida y suavizado.
5. La fórmula
La fórmula del promedio exponencial es:
Tn+1 = α · tn + (1 − α) · Tn
Donde:
- Tn+1 es la predicción para la próxima ráfaga.
- tn es la duración real de la última ráfaga observada.
- Tn es la predicción anterior.
- α es el factor de suavizado, entre 0 y 1.
Si expandimos la fórmula, se ve la ponderación exponencial:
Tn+1 = α·tn + α(1−α)·tn−1 + α(1−α)2·tn−2 + … + (1−α)n+1·T0
Cada ráfaga anterior contribuye con un peso que decrece exponencialmente: tn pesa α, tn−1 pesa α(1−α), tn−2 pesa α(1−α)2, y así sucesivamente. Las ráfagas muy antiguas contribuyen casi nada.
La predicción inicial T0 puede ser un valor arbitrario (por ejemplo, 10) o el promedio de las primeras ráfagas. Su influencia desaparece rápidamente gracias al factor (1−α)n.
6. El parámetro alpha
El parámetro α controla el equilibrio entre reacción y suavizado:
| Valor de α | Comportamiento | Cuándo usarlo |
|---|---|---|
| α = 0 | La predicción nunca cambia: Tn+1 = Tn. Ignora la última ráfaga. | Nunca. Es inútil. |
| α = 0,1 | Suavizado fuerte. Reacciona lentamente a los cambios. | Ráfagas muy variables, donde se quiere evitar sobre-reaccionar. |
| α = 0,5 | Equilibrio entre reacción y suavizado. | Caso general. Valor típico. |
| α = 0,9 | Reacción rápida. Sigue de cerca la última ráfaga. | Ráfagas estables, donde se quiere reaccionar rápido. |
| α = 1 | La predicción es la última ráfaga: Tn+1 = tn. Equivale al método de la última ráfaga. | Cuando se confía totalmente en la última observación. |
El valor típico en los sistemas operativos es α = 0,5, aunque varía según el sistema y el tipo de carga de trabajo. En Linux, el parámetro no se usa directamente (Linux no predice ráfagas para planificar), pero el concepto es fundamental para entender SJF y SRTF.
Un α alto reacciona rápido a los cambios pero es sensible al ruido. Un α bajo suaviza pero reacciona lento. No hay un valor óptimo universal: depende de la variabilidad de las ráfagas.
7. Un ejemplo desarrollado
Un proceso tiene estas ráfagas de CPU (en unidades de tiempo): 6, 4, 6, 4, 13, 13, 13. La predicción inicial es T0 = 10. Calculemos la predicción con α = 0,5:
| Ráfaga real (tn) | Predicción anterior (Tn) | Predicción siguiente (Tn+1 = 0,5·tn + 0,5·Tn) |
|---|---|---|
| — (inicial) | — | 10,00 |
| 6 | 10,00 | 0,5·6 + 0,5·10 = 8,00 |
| 4 | 8,00 | 0,5·4 + 0,5·8 = 6,00 |
| 6 | 6,00 | 0,5·6 + 0,5·6 = 6,00 |
| 4 | 6,00 | 0,5·4 + 0,5·6 = 5,00 |
| 13 | 5,00 | 0,5·13 + 0,5·5 = 9,00 |
| 13 | 9,00 | 0,5·13 + 0,5·9 = 11,00 |
| 13 | 11,00 | 0,5·13 + 0,5·11 = 12,00 |
Observa cómo la predicción sigue la tendencia: cuando las ráfagas son 6, 4, 6, 4, la predicción oscila entre 5 y 8. Cuando de repente aparece una ráfaga de 13, la predicción sube gradualmente: 9, 11, 12. No salta de 5 a 13 de golpe, sino que se adapta en unos pocos pasos.
Con α = 0,9, la predicción reaccionaría más rápido: después de la primera ráfaga de 13, saltaría a 0,9·13 + 0,1·5 = 12,2. Con α = 0,1, reaccionaría más lento: 0,1·13 + 0,9·5 = 5,8.
8. Propiedades del promedio exponencial
- Memoria O(1): solo necesita la predicción anterior y la última ráfaga.
- Tiempo O(1): una multiplicación y una suma.
- Ponderación exponencial: las ráfagas antiguas contribuyen cada vez menos.
- Suavizado: reduce el efecto de ráfagas anormalmente largas o cortas.
- Seguimiento de tendencias: si las ráfagas crecen, la predicción crece (con un retraso que depende de α).
- Independencia de la predicción inicial: la influencia de T0 desaparece exponencialmente.
El tiempo de reacción a un cambio súbito es aproximadamente 1/α ráfagas. Con α = 0,5, la predicción tarda unas 2 ráfagas en adaptarse. Con α = 0,1, tarda unas 10.
9. Limitaciones
- No predice cambios abruptos: si un proceso cambia de ráfagas cortas a largas de golpe, la predicción tarda en adaptarse.
- α fijo: un solo valor de α para todos los procesos y todas las situaciones. En la práctica, diferentes procesos tienen diferentes patrones.
- No usa información del programa: el sistema no sabe qué va a hacer el proceso. Solo usa el historial.
- Sensible a la predicción inicial: si T0 es muy diferente de las ráfagas reales, las primeras predicciones serán malas (aunque se corrigen rápidamente).
A pesar de estas limitaciones, el promedio exponencial es el método más usado en la práctica para predecir ráfagas, porque es simple, rápido y razonablemente bueno.
10. Cómo lo usa Linux
Linux no usa el promedio exponencial para planificar la CPU. El planificador de Linux (CFS/EEVDF) no predice ráfagas: usa un sistema de créditos (vruntime) que se acumula a medida que el proceso se ejecuta. La predicción de ráfagas se usa en otros contextos:
- Planificadores de E/S: el planificador de E/S de Linux (CFQ, BFQ) predice si un proceso va a hacer más E/S pronto.
- Prefetching: el sistema predice qué bloques del disco se van a leer a continuación.
- Branch prediction: el procesador predice qué instrucción se ejecutará a continuación (hardware).
Sin embargo, el concepto del promedio exponencial es fundamental para entender SJF y SRTF, y aparece en muchos otros contextos de sistemas operativos y redes (TCP usa un promedio exponencial para estimar el RTT).
11. Simulador interactivo
Este simulador calcula el promedio exponencial para una secuencia de ráfagas. Cambia α y la secuencia para ver cómo afecta la predicción:
Simulador · promedio exponencial
| Paso | Ráfaga real | Predicción anterior | Predicción siguiente |
|---|
12. Resumen
- SJF y SRTF necesitan conocer las ráfagas de antemano, lo que es imposible en la práctica.
- La solución es predecir la próxima ráfaga a partir del historial.
- El método de la última ráfaga es simple pero sensible al ruido.
- El promedio simple suaviza pero necesita memoria O(n) y reacciona lento.
- El promedio exponencial combina la última ráfaga con la predicción anterior: Tn+1 = α·tn + (1−α)·Tn.
- Las ráfagas antiguas contribuyen con peso exponencialmente decreciente.
- α controla el equilibrio entre reacción y suavizado. El valor típico es 0,5.
- El tiempo de reacción a un cambio es aproximadamente 1/α ráfagas.
- Linux no usa predicción de ráfagas para planificar la CPU, pero el concepto aparece en otros contextos.
13. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Por qué SJF necesita predecir las ráfagas?
Porque en la práctica las ráfagas no se conocen de antemano. SJF necesita saber cuál es el proceso más corto antes de ejecutarlo.
2. ¿Cuál es la fórmula del promedio exponencial?
Tn+1 = α·tn + (1 − α)·Tn, donde tn es la última ráfaga y Tn la predicción anterior.
3. ¿Qué efecto tiene aumentar alpha?
La predicción reacciona más rápido a los cambios, pero es más sensible al ruido.
4. ¿Cuánta memoria necesita el promedio exponencial?
O(1): solo necesita la predicción anterior y la última ráfaga.
5. ¿Qué ocurre cuando alpha = 1?
La predicción es igual a la última ráfaga observada. Equivale al método de la última ráfaga.
6. ¿Qué ocurre cuando alpha = 0?
La predicción nunca cambia. Ignora completamente la última ráfaga.
7. ¿Cuántas ráfagas tarda la predicción en adaptarse a un cambio?
Aproximadamente 1/α ráfagas. Con α = 0,5, unas 2 ráfagas.
8. ¿Por qué las ráfagas antiguas contribuyen cada vez menos?
Porque cada ráfaga anterior se multiplica por (1−α) una vez más, lo que reduce su peso exponencialmente.
9. ¿Usa Linux el promedio exponencial para planificar la CPU?
No. Linux no predice ráfagas para planificar. El concepto aparece en otros contextos (E/S, prefetching, TCP).
10. ¿Cuál es la principal limitación del promedio exponencial?
No predice cambios abruptos bien: tarda varias ráfagas en adaptarse a un cambio súbito.
Para practicar
- Calcula la predicción con α = 0,3 para la secuencia 5, 5, 5, 20, 20, 20 (predicción inicial 5).
- Compara la predicción con α = 0,2 y α = 0,8 para la misma secuencia.
- Implementa el promedio exponencial en C y pruébalo con ráfagas reales de un programa.
- Explica por qué un α muy alto es sensible al ruido.
- Demuestra que la suma de los pesos de todas las ráfagas anteriores es 1.
- Investiga cómo TCP usa el promedio exponencial para estimar el RTT.