1. Qué es MLFQ
MLFQ (Multilevel Feedback Queue) es una variante de las colas multinivel en la que los procesos pueden moverse entre colas según su comportamiento observado. Un proceso que usa mucho CPU baja de prioridad (a una cola inferior); uno que espera mucho sube (a una cola superior). La retroalimentación (feedback) es la observación del comportamiento del proceso.
MLFQ es el algoritmo más sofisticado de los clásicos. Combina lo mejor de todos: la equidad de Round Robin para los interactivos, la eficiencia de FCFS para los de cálculo, y la adaptabilidad a los cambios de comportamiento.
MLFQ es la base de los planificadores modernos: Windows, macOS y los planificadores de Linux (antes de CFS) usaban variantes de MLFQ.
En colas multinivel (tema 24), el proceso se clasifica al crearlo y no cambia de cola. En MLFQ, la clasificación se hace en tiempo de ejecución: el planificador observa el comportamiento y ajusta la cola. No necesita saber de antemano qué tipo de proceso es.
2. Por qué retroalimentación
La retroalimentación resuelve dos problemas de las colas multinivel:
- Clasificación incorrecta: un proceso que empieza como interactivo y se vuelve de cálculo queda atrapado en la cola interactiva. Con retroalimentación, baja automáticamente.
- Cambios de comportamiento: un proceso puede tener fases interactivas y fases de cálculo. La retroalimentación se adapta a cada fase.
Además, MLFQ no necesita conocer las ráfagas de antemano: observa el comportamiento y ajusta. Esto lo hace aplicable en la práctica, a diferencia de SJF.
3. Cómo funciona
MLFQ tiene varias colas, cada una con su propio algoritmo (típicamente Round Robin con quantum distinto). Los procesos empiezan en la cola superior (mayor prioridad). A medida que usan CPU, bajan de cola. Si esperan mucho, suben.
- Llega un proceso. Se coloca en la cola superior (mayor prioridad). llegada
- Se ejecuta. Recibe un quantum de la cola actual. ejecutar
- Si termina en su quantum: sale del sistema. Era un proceso corto/interactivo. terminar
- Si no termina en su quantum: baja una cola. Era un proceso largo/de cálculo. bajar
- Si espera mucho: sube a la cola superior. subir
- Se repite. bucle
La clave es que el quantum es distinto en cada cola: la cola superior tiene un quantum corto (para buena respuesta), y las inferiores tienen quantums más largos (para eficiencia). Un proceso que usa mucho CPU recibe quantums cada vez más largos, lo que reduce el overhead.
4. Las reglas de MLFQ
MLFQ se define por un conjunto de reglas. Las más comunes son:
| Regla | Descripción |
|---|---|
| R1 | Si la prioridad de A > prioridad de B, A se ejecuta. |
| R2 | Si la prioridad de A = prioridad de B, se ejecutan en Round Robin. |
| R3 | Cuando un proceso llega, se coloca en la cola superior. |
| R4 | Si un proceso usa todo su quantum, baja una cola. |
| R5 | Si un proceso se bloquea en E/S antes de usar su quantum, permanece en la misma cola (o sube). |
| R6 | Periódicamente, todos los procesos suben a la cola superior (envejecimiento). |
La regla R4 es la que hace que los procesos de cálculo bajen de prioridad: si un proceso usa todo su quantum, es porque tiene una ráfaga larga, así que baja. La regla R5 hace que los procesos interactivos (que se bloquean en E/S antes de usar su quantum) mantengan su prioridad alta.
La regla R6 (envejecimiento) evita la inanición: periódicamente, todos los procesos suben a la cola superior, garantizando que todos se ejecuten.
Sin la regla R6, un proceso de cálculo que baja a la cola inferior nunca se ejecuta si siempre hay procesos interactivos en la cola superior. La R6 garantiza que todos los procesos reciban CPU periódicamente.
5. Un ejemplo desarrollado
Tres colas con quantums 2, 4 y 8. Procesos:
| Proceso | Llegada | Ráfaga |
|---|---|---|
| P1 | 0 | 10 |
| P2 | 0 | 3 |
| P3 | 1 | 2 |
Simulación (sin envejecimiento):
- t = 0: Llegan P1 y P2. Ambos en cola 1. Round Robin con q=2: P1(0-2). P1 no termina, baja a cola 2. cola 1
- t = 2: P2(2-4). P2 termina (ráfaga 3 ≤ q=2? No, 3 > 2). P2 baja a cola 2. cola 1
- t = 4: Cola 1 vacía. Se pasa a cola 2 (q=4). P1 tiene 8 restantes, P2 tiene 1 restante. P2(4-5). P2 termina. cola 2
- t = 5: P1(5-9). P1 no termina (le quedan 4). Baja a cola 3. cola 2
- t = 9: Llegó P3 en t=1, está en cola 1. Cola 1 tiene prioridad sobre cola 3. P3(9-11). P3 termina. cola 1
- t = 11: Cola 1 vacía. Se pasa a cola 3 (q=8). P1 tiene 4 restantes. P1(11-15). P1 termina. cola 3
El Gantt resultante es:
Observa cómo P1 (el proceso largo) baja de cola 1 a 2 a 3, mientras que P2 (más corto) baja de 1 a 2 y termina. P3 (el más corto) se ejecuta en cola 1 cuando llega, porque tiene prioridad sobre cola 3.
6. Propiedades
| Propiedad | ¿La cumple? | Comentario |
|---|---|---|
| Adaptabilidad | Sí | Se adapta al comportamiento del proceso sin conocer las ráfagas. |
| Buena respuesta | Sí | Los procesos cortos se ejecutan en la cola superior con quantum corto. |
| Buen throughput | Sí | Los procesos largos reciben quantums más largos en colas inferiores. |
| Ausencia de inanición | Sí (con R6) | La regla R6 garantiza que todos se ejecuten periódicamente. |
| Necesita conocer ráfagas | No | Observa el comportamiento y ajusta. |
| Complejidad | Alta | Más complejo que los algoritmos simples. |
7. Ventajas
- No necesita conocer las ráfagas: se adapta observando el comportamiento.
- Buena respuesta para interactivos: los procesos cortos se quedan en la cola superior.
- Buen throughput para por lotes: los procesos largos reciben quantums más largos.
- Sin inanición: con la regla R6, todos se ejecutan periódicamente.
- Uso real: base de los planificadores de Windows, macOS y Linux (pre-CFS).
8. Desventajas
- Complejidad: muchas reglas y parámetros (número de colas, quantums, intervalo de envejecimiento).
- Difícil de ajustar: elegir los parámetros correctos requiere conocimiento de la carga de trabajo.
- Overhead: mantener varias colas y mover procesos tiene un costo.
- Trampas: un proceso puede engañar al planificador (tema 26).
El número de colas, los quantums y el intervalo de envejecimiento son parámetros que afectan al comportamiento. Elegirlos mal puede hacer que MLFQ sea peor que un algoritmo simple.
9. MLFQ en Linux
Linux usaba MLFQ antes de CFS (núcleo 2.6.23). El planificador O(1) de Linux (2.6.0-2.6.22) tenía 140 colas (una por prioridad), con quantums que aumentaban en las colas inferiores. Los procesos que usaban todo su quantum bajaban de cola; los que se bloqueaban en E/S subían.
El problema era que los parámetros eran difíciles de ajustar y los procesos podían engañar al planificador. Por eso Linux adoptó CFS, que usa un enfoque diferente (vruntime) pero mantiene la idea de favorecer a los procesos interactivos.
Windows y macOS siguen usando variantes de MLFQ en sus planificadores.
10. Simulador interactivo
Este simulador ejecuta MLFQ con 3 colas y quantums 2, 4 y 8. Observa cómo los procesos bajan de cola:
Simulador · MLFQ
| Proceso | Llegada | Ráfaga | Inicio | Fin | Respuesta | Espera | Retorno |
|---|---|---|---|---|---|---|---|
11. Resumen
- MLFQ permite que los procesos se muevan entre colas según su comportamiento.
- Un proceso que usa todo su quantum baja de cola; uno que se bloquea en E/S mantiene su prioridad.
- Los quantums aumentan en las colas inferiores.
- La regla R6 (envejecimiento) evita la inanición.
- No necesita conocer las ráfagas de antemano.
- Combina buena respuesta para interactivos y buen throughput para por lotes.
- Es la base de los planificadores de Windows, macOS y Linux (pre-CFS).
- Es complejo de ajustar y vulnerable a trampas.
12. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es MLFQ?
Colas multinivel con retroalimentación: los procesos se mueven entre colas según su comportamiento.
2. ¿Qué diferencia a MLFQ de las colas multinivel?
En MLFQ, los procesos pueden cambiar de cola. En colas multinivel, la clasificación es fija.
3. ¿Qué ocurre si un proceso usa todo su quantum?
Baja una cola (prioridad menor).
4. ¿Qué ocurre si un proceso se bloquea en E/S antes de usar su quantum?
Permanece en la misma cola (o sube).
5. ¿Qué es la regla R6?
Periódicamente, todos los procesos suben a la cola superior (envejecimiento).
6. ¿Por qué los quantums aumentan en las colas inferiores?
Para reducir el overhead de los procesos de cálculo, que tienen ráfagas largas.
7. ¿Necesita MLFQ conocer las ráfagas de antemano?
No. Observa el comportamiento y ajusta.
8. ¿Qué sistema operativo usa MLFQ actualmente?
Windows y macOS. Linux usaba MLFQ antes de CFS.
9. ¿Por qué Linux abandonó MLFQ?
Porque los parámetros eran difíciles de ajustar y los procesos podían engañar al planificador.
10. ¿Qué problema resuelve la regla R6?
La inanición: garantiza que todos los procesos se ejecuten periódicamente.
Para practicar
- Modifica el simulador para añadir la regla R6 (envejecimiento periódico) y observa el efecto.
- Diseña un proceso que engañe al planificador (tema 26) y verifica.
- Compara MLFQ con Round Robin para la misma carga.
- Explica por qué los quantums aumentan en las colas inferiores.
- Implementa MLFQ con 4 colas y quantums 1, 2, 4, 8.
- Investiga cómo Windows implementa MLFQ.