1. Qué son las colas multinivel
Las colas multinivel (multilevel queue) dividen la cola de listos en varias colas separadas, cada una con su propio algoritmo de planificación. Los procesos se clasifican en una cola según su tipo (interactivo, por lotes, del sistema) y cada cola se planifica de forma independiente. La CPU se reparte entre las colas según una política de scheduling entre colas.
La idea es que diferentes tipos de procesos tienen necesidades distintas: los interactivos necesitan buena respuesta, los de cálculo necesitan throughput, los del sistema necesitan prioridad. Una sola cola con un solo algoritmo no puede satisfacer a todos.
Las colas multinivel son la generalización de la planificación por prioridades: en lugar de una prioridad numérica, hay colas discretas, cada una con su propio algoritmo.
En la planificación por prioridades, todos los procesos están en la misma cola ordenada por prioridad. En las colas multinivel, hay colas separadas, cada una con su propio algoritmo. Un proceso no puede cambiar de cola (en esta versión).
2. Por qué varias colas
Un solo algoritmo no puede satisfacer a todos los tipos de procesos:
- FCFS: bueno para por lotes, malo para interactivos.
- SJF: bueno para minimizar espera, pero necesita conocer ráfagas.
- Round Robin: bueno para interactivos, malo para por lotes (overhead).
- Prioridades: flexible, pero puede causar inanición.
Con colas multinivel, cada tipo de proceso tiene su propia cola con el algoritmo más adecuado. Por ejemplo:
- Cola 1 (sistema): máxima prioridad, FCFS. Los procesos del sistema se ejecutan primero.
- Cola 2 (interactivos): prioridad alta, Round Robin con quantum corto.
- Cola 3 (por lotes): prioridad baja, FCFS o SJF.
3. Cómo funciona
El funcionamiento de las colas multinivel tiene dos niveles:
- Clasificación. Cuando un proceso llega, se asigna a una cola según su tipo (sistema, interactivo, por lotes). Esta asignación es fija: el proceso no cambia de cola. clasificar
- Planificación intra-cola. Cada cola tiene su propio algoritmo: FCFS, Round Robin, SJF, etc. Los procesos dentro de una cola se planifican según ese algoritmo. intra
- Planificación inter-cola. La CPU se reparte entre las colas según una política: prioridad fija, tiempo compartido, etc. inter
La planificación inter-cola es la que determina qué cola recibe la CPU en cada momento. Las opciones más comunes son:
- Prioridad fija: la cola de mayor prioridad siempre se ejecuta primero. Solo se ejecuta una cola inferior si las superiores están vacías.
- Tiempo compartido: cada cola recibe una fracción del tiempo de CPU (por ejemplo, 50 %, 30 %, 20 %).
- Prioridad con quantum: la cola de mayor prioridad recibe un quantum; si no termina, pasa a la siguiente cola.
4. Cómo se reparte la CPU entre colas
El reparto de la CPU entre colas es el aspecto más importante de las colas multinivel. Hay dos enfoques principales:
| Enfoque | Cómo funciona | Ventaja | Desventaja |
|---|---|---|---|
| Prioridad fija | La cola de mayor prioridad siempre tiene la CPU. Solo se ejecuta una cola inferior si las superiores están vacías. | Simple, determinista. | Inanición de las colas inferiores. |
| Tiempo compartido | Cada cola recibe una fracción del tiempo de CPU (por ejemplo, 50 %, 30 %, 20 %). | Equitativo, sin inanición. | Más complejo, overhead de temporizador. |
| Prioridad con envejecimiento | La prioridad de una cola aumenta si espera mucho. Garantiza que todas se ejecuten. | Evita inanición. | Más complejo. |
En la práctica, se usa una combinación: prioridad fija con envejecimiento, o tiempo compartido con prioridades.
5. Algoritmos por cola
Cada cola puede usar un algoritmo diferente, según el tipo de proceso:
| Tipo de proceso | Cola típica | Algoritmo típico | Quantum |
|---|---|---|---|
| Sistema | Cola 1 (máxima prioridad) | FCFS | — |
| Interactivo | Cola 2 (alta prioridad) | Round Robin | Corto (1-10 ms) |
| Por lotes | Cola 3 (baja prioridad) | FCFS o SJF | Largo o sin quantum |
Los procesos del sistema tienen la máxima prioridad porque son críticos para el funcionamiento del SO. Los interactivos tienen prioridad alta para buena respuesta. Los de cálculo tienen prioridad baja porque no son urgentes.
6. Un ejemplo desarrollado
Tres colas con reparto por prioridad fija:
| Cola | Prioridad | Algoritmo | Procesos |
|---|---|---|---|
| Cola 1 (sistema) | Alta | FCFS | S1(0,3), S2(2,2) |
| Cola 2 (interactivos) | Media | Round Robin (q=2) | I1(0,4), I2(1,3) |
| Cola 3 (por lotes) | Baja | FCFS | B1(0,6), B2(3,4) |
Con prioridad fija, la cola 1 se ejecuta primero. Mientras haya procesos en la cola 1, las demás esperan. Luego la cola 2, y finalmente la cola 3.
Simulación:
- t = 0: Llegan S1, I1, B1. Cola 1 tiene S1. Se ejecuta S1 (0-3). cola 1
- t = 2: Llega S2. Se encola en cola 1. Pero S1 sigue ejecutándose (no apropiativo dentro de la cola). encolar
- t = 3: S1 termina. Cola 1 tiene S2. Se ejecuta S2 (3-5). cola 1
- t = 5: S2 termina. Cola 1 vacía. Se pasa a cola 2. I1 tiene 4 unidades, I2 tiene 3. Round Robin con q=2: I1(5-7), I2(7-9), I1(9-11). cola 2
- t = 11: Cola 2 vacía. Se pasa a cola 3. B1 tiene 6, B2 tiene 4. FCFS: B1(11-17), B2(17-21). cola 3
El Gantt resultante es:
Los procesos de la cola del sistema terminan primero (0-5), luego los interactivos (5-11), y finalmente los de por lotes (11-21). Los procesos de por lotes esperan mucho, pero es aceptable porque no son urgentes.
7. Propiedades
| Propiedad | ¿La cumple? | Comentario |
|---|---|---|
| Flexibilidad | Sí | Cada cola puede usar un algoritmo distinto. |
| Adaptabilidad | Parcial | Solo si el proceso puede cambiar de cola (MLFQ). |
| Equidad | Depende | Depende del reparto entre colas. |
| Ausencia de inanición | No (con prioridad fija) | Las colas inferiores pueden esperar indefinidamente. |
| Complejidad | Media | Más complejo que un solo algoritmo, pero menos que MLFQ. |
8. Ventajas
- Flexibilidad: cada tipo de proceso tiene el algoritmo más adecuado.
- Simplicidad: más simple que MLFQ (sin migración entre colas).
- Predictibilidad: el comportamiento de cada cola es conocido.
- Uso real: muchos sistemas usan colas multinivel (Linux, Windows).
9. Desventajas
- Inanición: con prioridad fija, las colas inferiores pueden esperar indefinidamente.
- Rigidez: un proceso no puede cambiar de cola, aunque su comportamiento cambie.
- Clasificación: hay que clasificar los procesos al crearlos, lo que puede ser difícil.
- Overhead: mantener varias colas tiene un costo.
Con prioridad fija, si la cola del sistema siempre tiene procesos, las colas inferiores nunca se ejecutan. La solución es el envejecimiento o el tiempo compartido.
10. Colas multinivel en Linux
Linux usa colas multinivel en su planificador. La clase de planificación (stop, deadline, real-time, fair, idle) determina en qué cola está un proceso. Dentro de la clase fair (CFS), todos los procesos comparten una cola ordenada por vruntime.
En versiones anteriores de Linux (antes de CFS), se usaban colas multinivel con prioridades: 140 prioridades (0-139), cada una con su propia cola. Las prioridades 0-99 eran de tiempo real (SCHED_FIFO/SCHED_RR), y las 100-139 de la clase normal (con nice).
Windows también usa colas multinivel: 32 niveles de prioridad, cada uno con su propia cola. Los niveles 16-31 son de tiempo real, y los 1-15 de la clase normal.
11. Simulador interactivo
Este simulador ejecuta colas multinivel con prioridad fija y reparto por colas. Tres colas: sistema (FCFS), interactivos (Round Robin q=2), por lotes (FCFS):
Simulador · colas multinivel
| Proceso | Cola | Llegada | Ráfaga | Inicio | Fin | Respuesta | Espera | Retorno |
|---|---|---|---|---|---|---|---|---|
12. Resumen
- Las colas multinivel dividen los procesos en varias colas, cada una con su propio algoritmo.
- La clasificación es fija: un proceso no cambia de cola.
- La CPU se reparte entre colas por prioridad fija o tiempo compartido.
- Cada cola puede usar un algoritmo distinto (FCFS, Round Robin, SJF).
- Con prioridad fija, las colas inferiores pueden sufrir inanición.
- Linux y Windows usan colas multinivel en sus planificadores.
- Las colas multinivel son más simples que MLFQ pero menos adaptables.
13. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué son las colas multinivel?
Varias colas de listos, cada una con su propio algoritmo, y un reparto de la CPU entre ellas.
2. ¿Puede un proceso cambiar de cola en colas multinivel?
No. La clasificación es fija. (En MLFQ sí puede cambiar.)
3. ¿Cómo se reparte la CPU entre colas?
Por prioridad fija, tiempo compartido, o prioridad con envejecimiento.
4. ¿Qué algoritmo usa típicamente la cola de interactivos?
Round Robin con quantum corto.
5. ¿Qué problema tiene la prioridad fija?
Inanición de las colas inferiores si las superiores siempre tienen procesos.
6. ¿Cómo resuelve el tiempo compartido la inanición?
Dando a cada cola una fracción del tiempo de CPU.
7. ¿Usa Linux colas multinivel?
Sí. La clase de planificación determina la cola.
8. ¿Cuántas prioridades tenía Linux antes de CFS?
140 (0-139): 0-99 de tiempo real, 100-139 de la clase normal.
9. ¿En qué se diferencia colas multinivel de MLFQ?
En colas multinivel, el proceso no cambia de cola. En MLFQ, sí.
10. ¿Qué desventaja tiene la clasificación fija?
Un proceso no puede cambiar de cola aunque su comportamiento cambie.
Para practicar
- Modifica el simulador para usar tiempo compartido (50/30/20) en lugar de prioridad fija.
- Diseña un conjunto de procesos donde la inanición sea evidente.
- Implementa el envejecimiento entre colas y verifica que evita la inanición.
- Compara colas multinivel con un solo algoritmo (FCFS) para la misma carga.
- Investiga cómo Windows implementa las colas multinivel.
- Explica por qué la cola del sistema tiene la máxima prioridad.