Simulador de SJF y SRTF - Planificación de la CPU

1. Por qué un simulador conjunto

Ver SJF y SRTF por separado obliga a recordar las métricas de uno para compararlas con el otro. Un simulador conjunto ejecuta ambos sobre la misma carga de trabajo y muestra los resultados uno debajo del otro, lo que hace la comparación inmediata.

Las ventajas de un simulador conjunto son:

Comparabilidad: misma carga, mismos datos, distinto algoritmo. La diferencia se debe solo al algoritmo.
Visualización: los dos Gantt uno encima del otro muestran cómo SRTF interrumpe los procesos.
Comprensión: ver la diferencia en acción es más efectivo que leer una tabla.

Misma carga, distinto algoritmo

La clave del simulador conjunto es que la carga de trabajo es idéntica para ambos algoritmos. Si se generaran cargas distintas, la comparación no sería válida.

2. Arquitectura

El simulador tiene las mismas cinco partes que el de FCFS (tema 12), pero con dos funciones de algoritmo en lugar de una:

Parte	Responsabilidad	Funciones
Modelo	Representar un proceso.	`crearProceso`, `copiar`
Generador	Producir cargas reproducibles.	`crearGenerador`, `generarCarga`
Algoritmo SJF	Ejecutar SJF no apropiativo.	`sjf`
Algoritmo SRTF	Ejecutar SRTF apropiativo.	`srtf`
Vista	Dibujar Gantt y tabla para cada algoritmo.	`dibujarGanttSimple`, `dibujarGanttMulti`, `renderTabla`
Controlador	Leer controles, ejecutar ambos, actualizar la vista.	`dibujar`

3. La función sjf

SJF no apropiativo elige, en cada decisión, el proceso listo con la ráfaga más corta. No interrumpe procesos en curso:

sjf.js

function sjf(procesos) {
    var p = procesos.map(function (x) { return copiar(x); });
    var t = 0;
    var ejecutados = [];
    var restantes = p.slice();
    while (ejecutados.length < p.length) {
        var disponibles = restantes.filter(function (x) { return x.llegada <= t; });
        if (disponibles.length === 0) {
            var sig = restantes.reduce(function (a, b) {
                return a.llegada < b.llegada ? a : b;
            });
            t = sig.llegada;
            disponibles = restantes.filter(function (x) { return x.llegada <= t; });
        }
        var elegido = disponibles.reduce(function (a, b) {
            if (a.rafaga !== b.rafaga) return a.rafaga < b.rafaga ? a : b;
            if (a.llegada !== b.llegada) return a.llegada < b.llegada ? a : b;
            return a.pid < b.pid ? a : b;
        });
        restantes = restantes.filter(function (x) { return x !== elegido; });
        if (t < elegido.llegada) t = elegido.llegada;
        elegido.inicio = t;
        elegido.fin = t + elegido.rafaga;
        t = elegido.fin;
        elegido.respuesta = elegido.inicio - elegido.llegada;
        elegido.retorno = elegido.fin - elegido.llegada;
        elegido.espera = elegido.retorno - elegido.rafaga;
        ejecutados.push(elegido);
    }
    return ejecutados;
}

4. La función srtf

SRTF apropiativo interrumpe al proceso en curso si llega uno con menos tiempo restante. Necesita mantener el tiempo restante de cada proceso:

srtf.js

function srtf(procesos) {
    var restantes = procesos.map(function (x) {
        return { pid: x.pid, llegada: x.llegada, rafaga: x.rafaga,
            restante: x.rafaga, inicio: 0, fin: 0, respuesta: 0,
            espera: 0, retorno: 0, primera: true };
    });
    var ejecutados = [];
    var t = 0;
    while (ejecutados.length < procesos.length) {
        var disponibles = restantes.filter(function (x) { return x.llegada <= t; });
        if (disponibles.length === 0) {
            var sig = restantes.reduce(function (a, b) {
                return a.llegada < b.llegada ? a : b;
            });
            t = sig.llegada;
            disponibles = restantes.filter(function (x) { return x.llegada <= t; });
        }
        var elegido = disponibles.reduce(function (a, b) {
            if (a.restante !== b.restante) return a.restante < b.restante ? a : b;
            if (a.llegada !== b.llegada) return a.llegada < b.llegada ? a : b;
            return a.pid < b.pid ? a : b;
        });
        /* Hasta cuando ejecutar: fin o proxima llegada. */
        var proximaLlegada = Infinity;
        restantes.forEach(function (x) {
            if (x.llegada > t && x.llegada < proximaLlegada) proximaLlegada = x.llegada;
        });
        var duracion = Math.min(elegido.restante,
            isFinite(proximaLlegada) ? proximaLlegada - t : elegido.restante);
        if (duracion <= 0) duracion = elegido.restante;
        if (!isFinite(duracion)) duracion = elegido.restante;
        if (elegido.primera) { elegido.inicio = t; elegido.primera = false; }
        t += duracion;
        elegido.restante -= duracion;
        if (elegido.restante <= 0) {
            elegido.fin = t;
            elegido.respuesta = elegido.inicio - elegido.llegada;
            elegido.retorno = elegido.fin - elegido.llegada;
            elegido.espera = elegido.retorno - elegido.rafaga;
            ejecutados.push(elegido);
            restantes = restantes.filter(function (x) { return x !== elegido; });
        }
    }
    return ejecutados;
}

5. Gantt para SJF (bloque único)

SJF no apropiativo ejecuta cada proceso de una sola vez, así que el Gantt tiene un bloque por proceso. Se dibuja igual que el de FCFS:

dibujarGanttSimple.js

function dibujarGanttSimple(procesos, ganttEl, ticksEl) {
    ganttEl.innerHTML = '';
    ticksEl.innerHTML = '';
    if (procesos.length === 0) return;
    var total = procesos[procesos.length - 1].fin;
    var t = 0;
    procesos.forEach(function (p, idx) {
        if (p.inicio > t) {
            var hueco = document.createElement('span');
            hueco.style.flex = (p.inicio - t) + ' 1 0';
            hueco.textContent = 'ociosa';
            hueco.style.background = 'var(--surface-2)';
            hueco.style.color = 'var(--ink-soft)';
            ganttEl.appendChild(hueco);
        }
        var span = document.createElement('span');
        span.className = 'p' + (idx % 3);
        span.style.flex = p.rafaga + ' 1 0';
        span.textContent = 'P' + p.pid;
        ganttEl.appendChild(span);
        var marca = document.createElement('span');
        marca.style.left = (p.inicio / total * 100) + '%';
        marca.textContent = p.inicio;
        ticksEl.appendChild(marca);
        t = p.fin;
    });
    var fin = document.createElement('span');
    fin.style.left = '100%';
    fin.textContent = total;
    ticksEl.appendChild(fin);
}

6. Gantt para SRTF (múltiples bloques)

SRTF interrumpe procesos, así que un proceso puede tener varios bloques en el Gantt. Hay que reconstruir el trace de ejecución:

dibujarGanttMulti.js

function reconstruirTrace(procesos) {
    /* Re-ejecuta SRTF guardando los bloques. */
    var restantes = procesos.map(function (x) {
        return { pid: x.pid, llegada: x.llegada, rafaga: x.rafaga,
            restante: x.rafaga };
    });
    var bloques = [];
    var t = 0;
    var ejecutados = 0;
    while (ejecutados < procesos.length) {
        var disponibles = restantes.filter(function (x) {
            return x.llegada <= t && x.restante > 0;
        });
        if (disponibles.length === 0) {
            var sig = restantes.filter(function (x) { return x.restante > 0; })
                .reduce(function (a, b) { return a.llegada < b.llegada ? a : b; });
            t = sig.llegada;
            disponibles = restantes.filter(function (x) {
                return x.llegada <= t && x.restante > 0;
            });
        }
        var elegido = disponibles.reduce(function (a, b) {
            if (a.restante !== b.restante) return a.restante < b.restante ? a : b;
            if (a.llegada !== b.llegada) return a.llegada < b.llegada ? a : b;
            return a.pid < b.pid ? a : b;
        });
        var proximaLlegada = Infinity;
        restantes.forEach(function (x) {
            if (x.llegada > t && x.llegada < proximaLlegada && x.restante > 0)
                proximaLlegada = x.llegada;
        });
        var duracion = Math.min(elegido.restante,
            isFinite(proximaLlegada) ? proximaLlegada - t : elegido.restante);
        if (duracion <= 0) duracion = elegido.restante;
        if (!isFinite(duracion)) duracion = elegido.restante;
        bloques.push({ pid: elegido.pid, inicio: t, fin: t + duracion });
        t += duracion;
        elegido.restante -= duracion;
        if (elegido.restante <= 0) ejecutados++;
    }
    return { bloques: bloques, total: t };
}

function dibujarGanttMulti(procesos, ganttEl, ticksEl) {
    ganttEl.innerHTML = '';
    ticksEl.innerHTML = '';
    if (procesos.length === 0) return;
    var info = reconstruirTrace(procesos);
    var total = info.total;
    var cursor = 0;
    var idx = 0;
    info.bloques.forEach(function (b) {
        if (b.inicio > cursor) {
            var hueco = document.createElement('span');
            hueco.style.flex = (b.inicio - cursor) + ' 1 0';
            hueco.textContent = 'ociosa';
            hueco.style.background = 'var(--surface-2)';
            hueco.style.color = 'var(--ink-soft)';
            ganttEl.appendChild(hueco);
        }
        var span = document.createElement('span');
        span.className = 'p' + (idx % 3);
        span.style.flex = (b.fin - b.inicio) + ' 1 0';
        span.textContent = 'P' + b.pid;
        ganttEl.appendChild(span);
        idx++;
        cursor = b.fin;
    });
    /* Ticks: instantes unicos de cambio. */
    var instantes = [0];
    info.bloques.forEach(function (b) {
        if (instantes.indexOf(b.inicio) === -1) instantes.push(b.inicio);
        if (instantes.indexOf(b.fin) === -1) instantes.push(b.fin);
    });
    instantes.sort(function (a, b) { return a - b; });
    instantes.forEach(function (ins) {
        var marca = document.createElement('span');
        marca.style.left = (ins / total * 100) + '%';
        marca.textContent = ins;
        ticksEl.appendChild(marca);
    });
}

7. Tabla comparativa

La tabla muestra las métricas de ambos algoritmos para la misma carga, una al lado de la otra:

renderComparativa.js

function promedios(procesos) {
    var n = procesos.length;
    var sr = 0, se = 0, st = 0;
    for (var i = 0; i < n; i++) {
        sr += procesos[i].respuesta;
        se += procesos[i].espera;
        st += procesos[i].retorno;
    }
    return { respuesta: sr / n, espera: se / n, retorno: st / n };
}

function renderComparativa(resSJF, resSRTF, el) {
    var pSJF = promedios(resSJF);
    var pSRTF = promedios(resSRTF);
    el.innerHTML = '';
    var filas = [
        ['Tiempo de respuesta promedio', pSJF.respuesta, pSRTF.respuesta],
        ['Tiempo de espera promedio', pSJF.espera, pSRTF.espera],
        ['Tiempo de retorno promedio', pSJF.retorno, pSRTF.retorno]
    ];
    filas.forEach(function (f) {
        var tr = document.createElement('tr');
        var td0 = document.createElement('td'); td0.textContent = f[0]; tr.appendChild(td0);
        var td1 = document.createElement('td'); td1.textContent = f[1].toFixed(2); tr.appendChild(td1);
        var td2 = document.createElement('td'); td2.textContent = f[2].toFixed(2); tr.appendChild(td2);
        el.appendChild(tr);
    });
}

8. Los controles

Los controles son los mismos que en los simuladores anteriores: número de procesos, llegada máxima, ráfaga máxima y semilla. Se puede poner la llegada máxima en 0 para ver el caso en que todos llegan en cero (donde SJF y SRTF coinciden).

9. Simulador interactivo

Este simulador ejecuta SJF y SRTF sobre la misma carga y muestra los dos Gantt y las métricas:

Simulador · SJF vs SRTF

Procesos Llegada máxima Ráfaga máxima Semilla

SJF (no apropiativo)

Proceso	Llegada	Ráfaga	Inicio	Fin	Respuesta	Espera	Retorno

SRTF (apropiativo)

Proceso	Llegada	Ráfaga	Inicio	Fin	Respuesta	Espera	Retorno

Comparativa

Métrica	SJF	SRTF

10. La inanición en acción

La inanición ocurre cuando un proceso largo espera indefinidamente porque siempre hay procesos más cortos que se ejecutan antes. En SJF y SRTF, un proceso con ráfaga muy larga puede esperar para siempre si llega un flujo continuo de procesos cortos.

Ejemplo: un proceso con ráfaga 100 llega en 0. Después llegan procesos con ráfaga 1 cada 0,5 unidades. En SJF, el proceso largo nunca se ejecuta porque siempre hay un proceso corto disponible. En SRTF, el proceso largo se interrumpe cada vez que llega uno corto.

Este simulador muestra la inanición: genera un proceso largo (ráfaga 20) seguido de muchos procesos cortos (ráfaga 1) que llegan cada 1 unidad. Observa cómo el proceso largo espera:

Simulador · inanición

Ráfaga del largo Número de cortos

SJF (no apropiativo)

SRTF (apropiativo)

11. Envejecimiento

La solución a la inanición es el envejecimiento (aging): aumentar la prioridad (o reducir la ráfaga estimada) de los procesos que llevan mucho tiempo esperando. Con envejecimiento, un proceso largo que espera suficiente tiempo se vuelve «más corto» que los nuevos y se ejecuta.

El envejecimiento se implementa de varias formas:

Reducir la ráfaga estimada: cada unidad de tiempo que un proceso espera, su ráfaga estimada disminuye en una cantidad fija. Cuando llega a 0, se ejecuta.
Aumentar la prioridad: cada unidad de tiempo que un proceso espera, su prioridad aumenta. Cuando supera la de los procesos cortos, se ejecuta.
Umbral de espera: si un proceso espera más de un tiempo máximo, se ejecuta inmediatamente, sin importar su ráfaga.

El envejecimiento resuelve la inanición pero introduce un compromiso: si se envejece demasiado rápido, los procesos largos se ejecutan antes de tiempo y se pierde la optimalidad. Si se envejece demasiado lento, la inanición persiste.

Envejecimiento y optimalidad

El envejecimiento rompe la optimalidad de SJF/SRTF: un proceso largo puede ejecutarse antes que un proceso corto si ha esperado suficiente tiempo. Pero es un compromiso necesario para evitar la inanición.

12. Verificación y casos de prueba

Caso	Entrada	Resultado esperado
Todos en 0	P1(0,8), P2(0,4), P3(0,2), P4(0,1)	SJF y SRTF coinciden. Espera promedio: 2,75.
Llegadas distintas	P1(0,8), P2(1,4), P3(2,2), P4(3,1)	SRTF mejora: espera 2,75 vs 5,50. SRTF tiene más bloques en el Gantt.
Un proceso	P1(0,5)	Ambos: un bloque 0-5. Métricas iguales.
Hueco de CPU	P1(0,3), P2(5,2)	Ambos: P1 0-3, ociosa 3-5, P2 5-7.
Inanición	P1(0,20), P2..P11(1..10,1)	P1 espera hasta el final en SJF. SRTF interrumpe P1 en cada llegada.

13. Resumen

SJF y SRTF se simulan con las mismas funciones de modelo y vista; solo cambia el algoritmo.
SJF no apropiativo ejecuta cada proceso de una sola vez; SRTF puede interrumpir.
El Gantt de SRTF tiene múltiples bloques por proceso; hay que reconstruir el trace.
SRTF mejora todas las métricas respecto a SJF cuando hay llegadas distintas.
Ambos sufren inanición: un flujo de procesos cortos posterga a los largos.
El envejecimiento evita la inanición a costa de la optimalidad.
Cuando todos llegan en 0, SJF y SRTF coinciden.

14. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

1. ¿Por qué se necesita un Gantt multi-bloque para SRTF?

Porque SRTF interrumpe procesos, así que un proceso puede tener varios bloques en el Gantt.

2. ¿Cuándo coinciden SJF y SRTF?

Cuando todos los procesos llegan en 0: no hay llegadas durante la ejecución, así que no hay interrupciones.

3. ¿Qué es la inanición en SJF/SRTF?

Un proceso largo espera indefinidamente porque siempre hay procesos más cortos que se ejecutan antes.

4. ¿Cómo evita el envejecimiento la inanición?

Aumentando la prioridad (o reduciendo la ráfaga estimada) de los procesos que llevan mucho tiempo esperando.

5. ¿Qué compromiso introduce el envejecimiento?

Rompe la optimalidad: un proceso largo puede ejecutarse antes que un corto si ha esperado suficiente tiempo.

6. ¿Por qué SRTF tiene más cambios de contexto que SJF?

Porque interrumpe procesos cada vez que llega uno más corto.

7. ¿Qué parte del simulador es común a SJF y SRTF?

El modelo de datos, el generador, la vista (Gantt y tabla) y el controlador. Solo cambia la función del algoritmo.

8. ¿Cómo se reconstruye el trace de SRTF para el Gantt?

Re-ejecutando el algoritmo y guardando cada bloque (pid, inicio, fin) a medida que se ejecuta.

9. ¿Qué métrica mejora más SRTF respecto a SJF con llegadas distintas?

El tiempo de respuesta: SRTF da la CPU a los procesos cortos casi de inmediato.

10. ¿Por qué la inanición es más grave en SRTF que en SJF?

Porque SRTF interrumpe al proceso largo en cada llegada de un proceso más corto, mientras que SJF al menos deja que termine una vez que empieza.

Para practicar

Ejecuta el simulador con llegada máxima 0 y verifica que SJF y SRTF coinciden.
Genera un caso con inanición y observa cómo el proceso largo espera en ambos algoritmos.
Modifica el simulador para añadir envejecimiento y verifica que el proceso largo se ejecuta.
Implementa la comparativa de métricas como un gráfico de barras.
Calcula cuántos bloques tiene el Gantt de SRTF para 5 procesos con llegadas 0,1,2,3,4 y ráfagas 10,1,1,1,1.
Dibuja a mano el Gantt de SRTF para el caso de inanición y verifica con el simulador.