1. Por qué un simulador de MLFQ
MLFQ es el algoritmo más complejo de los clásicos. Tiene muchos parámetros (número de colas, quantums, intervalo de refuerzo) y su comportamiento es difícil de predecir a mano. Un simulador interactivo permite experimentar con estos parámetros y ver cómo afectan al Gantt y a las métricas.
El simulador de este tema es el último del bloque 7 y cierra el estudio de los algoritmos clásicos de colas. A partir del bloque 8, el problema se extiende a multiprocesadores.
Cambia el número de colas, los quantums y el intervalo de refuerzo para ver cómo afectan al descenso de los procesos. Un quantum pequeño en la cola superior hace que los procesos bajen rápidamente; uno grande los mantiene arriba.
2. Arquitectura
El simulador tiene las mismas partes que los anteriores, con la adición del refuerzo periódico:
| Parte | Responsabilidad | Funciones |
|---|---|---|
| Modelo | Representar un proceso con cola actual. | crearProceso, copiar |
| Generador | Producir cargas reproducibles. | crearGenerador, generarCarga |
| Algoritmo | Ejecutar MLFQ con N colas y refuerzo. | mlfq |
| Vista | Dibujar Gantt con descenso y tabla. | reconstruirTrace, dibujarGantt, renderTabla |
| Controlador | Leer controles, ejecutar, actualizar. | dibujar, listeners |
3. La función mlfq
La función ejecuta MLFQ con N colas, quantums configurables y refuerzo periódico:
function mlfq(procesos, numColas, quantums, intervaloRefuerzo) {
var p = procesos.map(function (x) {
return { pid: x.pid, llegada: x.llegada, rafaga: x.rafaga,
restante: x.rafaga, cola: 0, inicio: 0, fin: 0,
respuesta: 0, espera: 0, retorno: 0, primera: true,
tiempoEnCola: 0 };
});
p.sort(function (a, b) {
if (a.llegada !== b.llegada) return a.llegada - b.llegada;
return a.pid - b.pid;
});
var colas = [];
for (var i = 0; i < numColas; i++) colas.push([]);
var t = 0;
var idx = 0;
var terminados = 0;
var n = p.length;
var ultimoRefuerzo = 0;
while (idx < n && p[idx].llegada <= t) { colas[0].push(p[idx]); idx++; }
while (terminados < n) {
/* Refuerzo periódico. */
if (intervaloRefuerzo > 0 && t - ultimoRefuerzo >= intervaloRefuerzo) {
for (var c = 1; c < numColas; c++) {
while (colas[c].length > 0) {
var proc = colas[c].shift();
proc.cola = 0;
colas[0].push(proc);
}
}
ultimoRefuerzo = t;
}
/* Encontrar cola de mayor prioridad no vacía. */
var colaActiva = -1;
for (var c = 0; c < numColas; c++) {
if (colas[c].length > 0) { colaActiva = c; break; }
}
if (colaActiva === -1) {
t = p[idx].llegada;
while (idx < n && p[idx].llegada <= t) { colas[0].push(p[idx]); idx++; }
continue;
}
var proc = colas[colaActiva].shift();
if (proc.primera) { proc.inicio = t; proc.primera = false; }
var q = quantums[colaActiva];
var duracion = Math.min(q, proc.restante);
t += duracion;
proc.restante -= duracion;
while (idx < n && p[idx].llegada <= t) { colas[0].push(p[idx]); idx++; }
if (proc.restante <= 0) {
proc.fin = t;
proc.respuesta = proc.inicio - proc.llegada;
proc.retorno = proc.fin - proc.llegada;
proc.espera = proc.retorno - proc.rafaga;
terminados++;
} else {
/* Baja de cola si usó todo el quantum. */
if (duracion === q && colaActiva < numColas - 1) {
proc.cola = colaActiva + 1;
colas[colaActiva + 1].push(proc);
} else {
colas[colaActiva].push(proc);
}
}
}
return p;
}4. Gantt con descenso de colas
El Gantt de MLFQ muestra los bloques de cada proceso, coloreados por cola. Un proceso que desciende de cola cambia de color. Esto hace visible el comportamiento de MLFQ:
function reconstruirTrace(procesos, numColas, quantums, intervaloRefuerzo) {
/* Re-ejecutar MLFQ guardando bloques con cola. */
var p = procesos.map(function (x) {
return { pid: x.pid, llegada: x.llegada, rafaga: x.rafaga,
restante: x.rafaga, cola: 0 };
});
p.sort(function (a, b) {
if (a.llegada !== b.llegada) return a.llegada - b.llegada;
return a.pid - b.pid;
});
var colas = [];
for (var i = 0; i < numColas; i++) colas.push([]);
var t = 0;
var idx = 0;
var terminados = 0;
var n = p.length;
var ultimoRefuerzo = 0;
var bloques = [];
while (idx < n && p[idx].llegada <= t) { colas[0].push(p[idx]); idx++; }
while (terminados < n) {
if (intervaloRefuerzo > 0 && t - ultimoRefuerzo >= intervaloRefuerzo) {
for (var c = 1; c < numColas; c++) {
while (colas[c].length > 0) {
var proc = colas[c].shift();
proc.cola = 0;
colas[0].push(proc);
}
}
ultimoRefuerzo = t;
}
var colaActiva = -1;
for (var c = 0; c < numColas; c++) {
if (colas[c].length > 0) { colaActiva = c; break; }
}
if (colaActiva === -1) {
t = p[idx].llegada;
while (idx < n && p[idx].llegada <= t) { colas[0].push(p[idx]); idx++; }
continue;
}
var proc = colas[colaActiva].shift();
var q = quantums[colaActiva];
var duracion = Math.min(q, proc.restante);
bloques.push({ pid: proc.pid, inicio: t, fin: t + duracion, cola: colaActiva });
t += duracion;
proc.restante -= duracion;
while (idx < n && p[idx].llegada <= t) { colas[0].push(p[idx]); idx++; }
if (proc.restante <= 0) {
terminados++;
} else {
if (duracion === q && colaActiva < numColas - 1) {
proc.cola = colaActiva + 1;
colas[colaActiva + 1].push(proc);
} else {
colas[colaActiva].push(proc);
}
}
}
return { bloques: bloques, total: t };
}5. La tabla de métricas
La tabla muestra los resultados ordenados por pid, con las tres métricas:
function renderTabla(procesos, filasEl, promEl) {
var ordenado = procesos.slice().sort(function (a, b) { return a.pid - b.pid; });
filasEl.innerHTML = '';
var sr = 0, se = 0, st = 0;
ordenado.forEach(function (p) {
var tr = document.createElement('tr');
[ 'P' + p.pid, p.llegada, p.rafaga, p.inicio, p.fin,
p.respuesta, p.espera, p.retorno ].forEach(function (v) {
var td = document.createElement('td');
td.textContent = v;
tr.appendChild(td);
});
filasEl.appendChild(tr);
sr += p.respuesta; se += p.espera; st += p.retorno;
});
var n = ordenado.length;
if (n === 0) { promEl.textContent = ''; return; }
promEl.textContent = 'Promedio: respuesta=' + (sr/n).toFixed(2) +
' espera=' + (se/n).toFixed(2) + ' retorno=' + (st/n).toFixed(2);
}6. Los controles
Los controles permiten ajustar los parámetros de MLFQ:
- Procesos: número de procesos (2 a 8).
- Llegada máxima: llegada máxima posible.
- Ráfaga máxima: ráfaga máxima posible.
- Número de colas: 2 a 4 colas.
- Intervalo de refuerzo: 0 (sin refuerzo) a 50.
- Semilla: semilla del generador pseudoaleatorio.
Los quantums se calculan automáticamente: cola 0 = 2, cola 1 = 4, cola 2 = 8, cola 3 = 16 (potencias de 2).
7. Simulador interactivo
Este simulador ejecuta MLFQ con parámetros ajustables. El Gantt muestra los bloques coloreados por cola: cada color es una cola distinta. Observa cómo los procesos descienden:
Simulador · MLFQ
| Proceso | Llegada | Ráfaga | Inicio | Fin | Respuesta | Espera | Retorno |
|---|---|---|---|---|---|---|---|
8. Refuerzo periódico
El refuerzo periódico (priority boost) mueve todos los procesos a la cola superior cada S unidades de tiempo. Actívalo con el control «Refuerzo» y observa cómo los procesos que habían descendido vuelven a la cola superior.
El refuerzo es esencial para evitar la inanición: sin él, un proceso de cálculo que baja a la cola inferior nunca se ejecuta si siempre hay procesos interactivos en la cola superior.
El valor de S determina el equilibrio entre equidad y eficiencia. Un S corto hace que todos los procesos se ejecuten con el quantum de la cola superior (más equitativo pero más overhead). Un S largo permite que los procesos de cálculo reciban quantums más largos (más eficiente pero menos equitativo).
9. Verificación y casos de prueba
| Caso | Entrada | Resultado esperado |
|---|---|---|
| Un proceso | P1(0,5) | Un bloque 0-5 en cola 0. |
| Todos en 0, ráfagas cortas | P1(0,2), P2(0,3), P3(0,1) | Todos se ejecutan en cola 0 (ninguno usa todo su quantum). |
| Proceso largo | P1(0,10) | P1 desciende de cola 0 a 1 a 2. |
| Con refuerzo | P1(0,10), S=5 | P1 desciende y luego sube a cola 0 en t=5. |
| Múltiples colas | 4 colas, P1(0,20) | P1 desciende por todas las colas. |
10. Resumen
- El simulador de MLFQ permite experimentar con número de colas, quantums e intervalo de refuerzo.
- Los quantums son potencias de 2: 2, 4, 8, 16.
- El Gantt muestra los bloques coloreados por cola.
- El refuerzo periódico mueve todos los procesos a la cola superior.
- Sin refuerzo, los procesos de cálculo descienden y pueden sufrir inanición.
- Con refuerzo, todos los procesos se ejecutan periódicamente.
- El simulador es la culminación del bloque 7 (colas multinivel).
11. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué parámetros ajusta el simulador?
Número de procesos, llegada máxima, ráfaga máxima, número de colas, intervalo de refuerzo y semilla.
2. ¿Cómo se calculan los quantums?
Potencias de 2: cola 0 = 2, cola 1 = 4, cola 2 = 8, cola 3 = 16.
3. ¿Qué ocurre cuando un proceso usa todo su quantum?
Baja una cola (si no está en la última).
4. ¿Qué ocurre con el refuerzo periódico?
Todos los procesos suben a la cola superior.
5. ¿Qué muestra el Gantt?
Los bloques de cada proceso, coloreados por cola.
6. ¿Qué ocurre sin refuerzo cuando hay procesos interactivos?
Los procesos de cálculo descienden y pueden sufrir inanición.
7. ¿Por qué el refuerzo es esencial?
Para evitar la inanición de las colas inferiores.
8. ¿Qué valor de refuerzo hace que MLFQ se comporte como Round Robin?
Un valor muy corto (S → 0).
9. ¿Qué valor de refuerzo hace que MLFQ se comporte como colas multinivel?
Un valor muy largo (S → ∞).
10. ¿Cuál es el trade-off del refuerzo?
S corto: más equitativo pero más overhead. S largo: más eficiente pero menos equitativo.
Para practicar
- Experimenta con 2, 3 y 4 colas y observa el descenso.
- Activa el refuerzo con S=10 y observa cómo los procesos suben.
- Compara MLFQ con Round Robin para la misma carga.
- Diseña un caso donde la inanición sea evidente sin refuerzo.
- Implementa la trampa de la E/S en el simulador y observa.
- Investiga cómo Windows ajusta los parámetros de MLFQ.