1. Qué es la inanición
La inanición (starvation) ocurre cuando un proceso está listo para ejecutarse pero nunca recibe la CPU, porque siempre hay otros procesos que tienen preferencia sobre él. El proceso espera indefinidamente: no termina, no progresa, no responde.
La inanición no es un bloqueo (deadlock): el proceso no está esperando un recurso que nunca se libera; está esperando la CPU, que se da a otros procesos. La CPU está disponible, pero el planificador nunca la elige.
La inanición es un problema de equidad (fairness): el sistema favorece a unos procesos a costa de otros. Es el precio de la optimización: SJF favorece a los cortos, la planificación por prioridades favorece a los importantes, y los largos o de baja prioridad pagan el costo.
En un bloqueo (deadlock), el proceso espera un recurso que nunca se libera. En la inanición, el proceso espera la CPU, que se da a otros. La diferencia es que en la inanición el sistema podría darle la CPU, pero elige no hacerlo.
2. Cuándo ocurre
La inanición ocurre en algoritmos que favorecen a ciertos procesos sobre otros:
- SJF y SRTF: un proceso largo espera indefinidamente si llega un flujo continuo de procesos más cortos.
- Planificación por prioridades: un proceso de baja prioridad espera indefinidamente si siempre hay procesos de mayor prioridad.
- Colas multinivel: un proceso en la cola de baja prioridad espera si las colas superiores nunca se vacían.
La inanición NO ocurre en:
- FCFS: todo proceso que llega se ejecuta eventualmente (en orden de llegada).
- Round Robin: todos los procesos reciben turnos periódicos.
- Algoritmos con envejecimiento: la prioridad aumenta con el tiempo, garantizando que todo proceso se ejecute.
3. Un ejemplo desarrollado
Un proceso largo (P1, ráfaga 20) llega en 0. Después llegan procesos cortos (ráfaga 1) cada 1 unidad de tiempo:
| Proceso | Llegada | Ráfaga |
|---|---|---|
| P1 | 0 | 20 |
| P2 | 1 | 1 |
| P3 | 2 | 1 |
| P4 | 3 | 1 |
| ... | ... | 1 |
En SJF no apropiativo, P1 se ejecuta primero (0-20). Los procesos cortos que llegan durante su ejecución esperan. Cuando P1 termina, se ejecutan los cortos en orden. No hay inanición porque P1 ya se ejecutó.
Pero si los procesos cortos llegan antes de que P1 empiece (todos en 0, o P1 llega después), la situación cambia. Supongamos que P1 (ráfaga 20) llega en 0, y P2, P3, ... (ráfaga 1) llegan en 0, 1, 2, ... En SJF, los cortos se ejecutan primero. Si llegan suficientes cortos, P1 espera indefinidamente.
En la planificación por prioridades, el caso es más claro: si P1 tiene prioridad 1 y los cortos tienen prioridad 5, P1 nunca se ejecuta mientras haya cortos listos. Y si los cortos llegan continuamente, P1 espera para siempre.
4. Consecuencias
La inanición tiene consecuencias graves:
- El proceso nunca termina: un proceso que no se ejecuta no progresa. Si es un servicio crítico, el sistema falla.
- Desperdicio de recursos: el proceso ocupa memoria, descriptores de archivo y otros recursos mientras espera.
- Insatisfacción del usuario: un proceso que no responde parece «colgado».
- Violación de plazos: en sistemas de tiempo real, la inanición puede causar que se incumplan plazos.
La inanición es un problema de liveness (vivacidad): el sistema está activo, pero un proceso individual no progresa. Es distinto de un deadlock, donde todo el sistema se bloquea.
5. Qué es el envejecimiento
El envejecimiento (aging) es una técnica que aumenta gradualmente la prioridad de un proceso a medida que espera. Con el tiempo, un proceso de baja prioridad acumula suficiente prioridad para superar a los procesos nuevos y finalmente ejecutarse.
El envejecimiento garantiza que todo proceso que espera suficiente tiempo finalmente se ejecuta. Es la solución estándar a la inanición en la planificación por prioridades y en SJF.
La idea es simple: la prioridad de un proceso no es fija, sino que aumenta con el tiempo de espera. Un proceso que acaba de llegar tiene su prioridad base; uno que lleva esperando mucho tiene una prioridad mayor.
Con envejecimiento, ningún proceso espera indefinidamente. Eventualmente, su prioridad supera a la de cualquier proceso nuevo y se ejecuta. Es la garantía de liveness que falta en SJF y en la planificación por prioridades.
6. Cómo se implementa
El envejecimiento se puede implementar de varias formas:
| Método | Cómo funciona | Ventaja | Desventaja |
|---|---|---|---|
| Prioridad dinámica por espera | La prioridad aumenta en 1 cada unidad de tiempo que el proceso espera. | Simple, garantiza progreso. | Los procesos largos se ejecutan antes de tiempo. |
| Ráfaga estimada decreciente | La ráfaga estimada disminuye en 1 cada unidad de tiempo que el proceso espera. | Se integra con SJF. | Complejo de implementar. |
| Umbral de espera | Si un proceso espera más de T unidades, se ejecuta inmediatamente. | Simple, límite claro. | Discontinuo: todos los procesos que superan el umbral se ejecutan juntos. |
| Prioridad por tiempo de espera | La prioridad es una función del tiempo de espera (por ejemplo, prioridad = base + espera / 10). | Suave, ajustable. | Hay que elegir la función. |
En la práctica, el método más común es el primero: aumentar la prioridad en 1 cada unidad de tiempo. Es simple y garantiza que todo proceso se ejecute en un tiempo acotado.
El envejecimiento se puede implementar en el planificador de dos formas:
- Actualización periódica: cada cierto tiempo (por ejemplo, cada 100 ms), se recorre la cola de listos y se aumenta la prioridad de todos los procesos.
- Actualización por evento: cada vez que se toma una decisión de planificación, se calcula la prioridad efectiva de cada proceso como prioridad_base + tiempo_esperado / factor.
7. El compromiso del envejecimiento
El envejecimiento resuelve la inanición, pero introduce un compromiso:
- Si se envejece demasiado rápido: los procesos de baja prioridad se ejecutan antes de tiempo, perdiendo la optimalidad de SJF o la intención de las prioridades.
- Si se envejece demasiado lento: la inanición persiste por mucho tiempo antes de resolverse.
El parámetro clave es la velocidad de envejecimiento: cuánto aumenta la prioridad por unidad de tiempo. Un valor típico es 1 punto de prioridad por segundo de espera. Con este valor, un proceso de prioridad 1 que espera 10 segundos alcanza prioridad 11, superando a un proceso de prioridad 10 que acaba de llegar.
Con envejecimiento, un proceso largo puede ejecutarse antes que un proceso corto si ha esperado suficiente tiempo. Esto rompe la optimalidad de SJF, pero es un compromiso necesario para garantizar la equidad.
8. Envejecimiento en Linux
Linux implementa una forma de envejecimiento en la clase normal (SCHED_OTHER). El planificador CFS/EEVDF usa el vruntime (tiempo virtual): un proceso que espera acumula vruntime lentamente, y cuando recibe la CPU, su vruntime aumenta. Los procesos que han esperado más tienen menos vruntime y se ejecutan antes. Esto es, en esencia, una forma de envejecimiento.
En las clases de tiempo real (SCHED_FIFO, SCHED_RR), no hay envejecimiento: la prioridad es fija. El programador es responsable de evitar la inanición asignando prioridades correctamente.
En el planificador CFS, el envejecimiento está integrado en el algoritmo: no hay un mecanismo separado, sino que el vruntime garantiza que los procesos que esperan más reciben la CPU antes.
9. Alternativas al envejecimiento
Además del envejecimiento, hay otras técnicas para evitar la inanición:
- Round Robin: dar turnos a todos los procesos periódicamente, sin importar la prioridad. Esto garantiza que todos reciban CPU, pero reduce la efectividad de las prioridades.
- Colas multinivel con realimentación: mover procesos entre colas según su comportamiento. Un proceso que espera mucho en una cola baja se mueve a una cola superior.
- Límite de tiempo por prioridad: un proceso de alta prioridad solo puede ejecutarse durante un tiempo máximo antes de ceder la CPU a uno de menor prioridad.
- Fair share scheduling: repartir la CPU equitativamente entre usuarios o grupos, independientemente de las prioridades individuales.
En la práctica, la combinación de prioridades dinámicas + envejecimiento + Round Robin para desempatar es la solución más común.
10. Simulador interactivo
Este simulador muestra la inanición y cómo el envejecimiento la evita. Un proceso largo de baja prioridad espera mientras llegan procesos cortos de alta prioridad. Con el envejecimiento activado, el proceso largo finalmente se ejecuta:
Simulador · inanición y envejecimiento
Sin envejecimiento (velocidad 0)
Con envejecimiento
11. Resumen
- La inanición ocurre cuando un proceso espera indefinidamente porque siempre hay otros con preferencia.
- Ocurre en SJF, SRTF y la planificación por prioridades.
- No ocurre en FCFS ni en Round Robin.
- El envejecimiento aumenta la prioridad de un proceso a medida que espera.
- Con envejecimiento, todo proceso que espera suficiente tiempo finalmente se ejecuta.
- La velocidad de envejecimiento controla el equilibrio entre equidad y optimalidad.
- Linux implementa envejecimiento implícito en CFS mediante el vruntime.
- Las clases de tiempo real no tienen envejecimiento: la prioridad es fija.
- Alternativas: Round Robin, colas multinivel con realimentación, límite de tiempo por prioridad.
12. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es la inanición?
Un proceso listo que nunca recibe la CPU porque siempre hay otros con preferencia sobre él.
2. ¿En qué algoritmos ocurre la inanición?
En SJF, SRTF y la planificación por prioridades.
3. ¿En qué algoritmos NO ocurre la inanición?
En FCFS y Round Robin.
4. ¿Qué es el envejecimiento?
Aumentar la prioridad de un proceso a medida que espera, hasta que finalmente se ejecuta.
5. ¿Qué garantiza el envejecimiento?
Que todo proceso que espera suficiente tiempo finalmente se ejecuta.
6. ¿Qué compromiso introduce el envejecimiento?
Rompe la optimalidad: un proceso largo puede ejecutarse antes que un corto si ha esperado suficiente tiempo.
7. ¿Cómo implementa Linux el envejecimiento?
En CFS, mediante el vruntime: los procesos que esperan más tienen menos vruntime y se ejecutan antes.
8. ¿Las clases de tiempo real de Linux tienen envejecimiento?
No. La prioridad es fija. El programador es responsable de evitar la inanición.
9. ¿Qué es la diferencia entre inanición y deadlock?
En la inanición, el proceso espera la CPU que se da a otros. En el deadlock, el proceso espera un recurso que nunca se libera.
10. ¿Qué alternativa a el envejecimiento garantiza que todos reciban CPU?
Round Robin: todos los procesos reciben turnos periódicos.
Para practicar
- Diseña un conjunto de procesos donde la inanición sea evidente en SJF.
- Implementa el envejecimiento con velocidad 1 y verifica que el proceso largo se ejecuta.
- Compara el envejecimiento con velocidad 0,5 y 2 para el mismo conjunto.
- Explica por qué el envejecimiento rompe la optimalidad de SJF.
- Diseña un esquema de envejecimiento basado en la ráfaga estimada decreciente.
- Investiga cómo el vruntime de CFS implementa el envejecimiento.