Modelar procesos en JavaScript

1. Por qué modelar los procesos en código

Un algoritmo de planificación es una función: recibe una lista de procesos y devuelve un orden de ejecución, un diagrama de Gantt y unas métricas. Para programarlo hay que decidir antes cómo se representa un proceso en memoria. Si esa representación es clara y estable, todos los algoritmos comparten el mismo modelo y solo cambia la función de ordenación.

Las ventajas de tener un modelo único son:

• Comparabilidad: todos los algoritmos se prueban sobre las mismas cargas de trabajo, generadas por el mismo generador.
• Reutilización: la función de métricas y el dibujo del Gantt se escriben una sola vez.
• Depuración: si un resultado es inesperado, se puede imprimir la carga de trabajo como JSON y reproducirlo.
• Extensibilidad: añadir un campo (por ejemplo, prioridad o quantum) no rompe los algoritmos que no lo usan.

2. La estructura de datos de un proceso

En JavaScript un proceso es un objeto con propiedades. Se usa un objeto plano (no una clase) para que sea fácil de imprimir, copiar y serializar. La función que lo crea es la única que conoce la estructura:

function crearProceso(pid, llegada, rafaga) {
    return {
        pid: pid,            // identificador (1, 2, 3, ...)
        llegada: llegada,    // instante en que entra al sistema
        rafaga: rafaga,      // tiempo de CPU que necesita
        inicio: 0,           // primera ejecucion (se calcula)
        fin: 0,              // terminacion (se calcula)
        respuesta: 0,        // S - A (se calcula)
        espera: 0,           // T - B (se calcula)
        retorno: 0           // F - A (se calcula)
    };
}

Los primeros tres campos son datos de entrada: los fija el generador o el usuario. Los cinco últimos son resultados: los rellena la función del algoritmo. Separar datos de resultados evita que un algoritmo sobrescriba la entrada por accidente.

Un objeto así se imprime directamente con JSON.stringify, lo que facilita la depuración:

> JSON.stringify(crearProceso(1, 0, 5), null, 2)
{
  "pid": 1,
  "llegada": 0,
  "rafaga": 5,
  "inicio": 0,
  "fin": 0,
  "respuesta": 0,
  "espera": 0,
  "retorno": 0
}

3. Campos y convenciones

Las convenciones que se respetan en todo el curso son:

Los tiempos son enteros porque los simuladores trabajan en unidades discretas. Los programas en C de los temas anteriores usaban enteros por la misma razón. Si en algún momento se quisieran milisegundos reales, bastaría con cambiar la unidad; las fórmulas no cambian.

Los nombres de los campos son en español y en minúscula, sin tildes, para que coincidan con las variables de los programas en C y con los identificadores de JavaScript sin necesidad de comillas.

4. Una carga de trabajo

Una carga de trabajo (workload) es un arreglo de procesos. Es el insumo de cualquier simulación. Se puede escribir a mano, como en los ejemplos de los temas anteriores, o generarla automáticamente.

var carga = [
    crearProceso(1, 0, 5),
    crearProceso(2, 1, 3),
    crearProceso(3, 2, 4),
    crearProceso(4, 4, 2)
];

Una carga de trabajo bien diseñada para probar un algoritmo tiene estas propiedades:

• Variedad de llegadas: algunos en 0, otros más tarde, para ver cómo se comporta la CPU ociosa.
• Variedad de ráfagas: procesos cortos y largos, para ver el efecto convoy y la ventaja de SJF.
• Tamaño pequeño: 3 a 6 procesos son suficientes para calcular a mano y verificar el simulador.
• Reproducibilidad: si se genera aleatoriamente, la semilla debe ser fija para poder repetir el experimento.

5. Generador de cargas de trabajo

Para probar un algoritmo con muchas cargas distintas se necesita un generador. El generador usa un generador de números pseudoaleatorios con semilla, para que el resultado sea reproducible:

/* Generador congruencial lineal (LCG) con semilla. */
function crearGenerador(semilla) {
    var s = semilla >>> 0;
    return function () {
        s = (s * 1664525 + 1013904223) >>> 0;
        return s / 0x100000000;
    };
}

function generarCarga(n, maxLlegada, maxRafaga, semilla) {
    var rnd = crearGenerador(semilla);
    var carga = [];
    for (var i = 0; i < n; i++) {
        var llegada = Math.floor(rnd() * (maxLlegada + 1));
        var rafaga = 1 + Math.floor(rnd() * maxRafaga);
        carga.push(crearProceso(i + 1, llegada, rafaga));
    }
    return carga;
}

El generador tiene cuatro parámetros:

• n: cuántos procesos generar.
• maxLlegada: la llegada máxima posible (las llegadas se distribuyen entre 0 y este valor).
• maxRafaga: la ráfaga máxima posible (entre 1 y este valor).
• semilla: el valor inicial del generador pseudoaleatorio.

Con la misma semilla, el generador produce exactamente la misma carga. Eso permite compartir un ejemplo con un compañero: basta con decir «semilla 42, 4 procesos, llegada máxima 6, ráfaga máxima 8».

6. Función que calcula las métricas

La función del algoritmo recibe una carga de trabajo y devuelve un arreglo ordenado por ejecución, con los campos inicio, fin, respuesta, espera y retorno rellenos. La carga original no se modifica: se trabaja sobre una copia.

FCFS es el caso más sencillo y sirve de plantilla:

function fcfs(procesos) {
    /* Copia para no modificar la entrada. */
    var p = procesos.map(function (x) { return copiar(x); });

    /* Ordenar por llegada (y por pid en caso de empate). */
    p.sort(function (a, b) {
        if (a.llegada !== b.llegada) return a.llegada - b.llegada;
        return a.pid - b.pid;
    });

    /* Recorrer la linea de tiempo. */
    var t = 0;
    for (var i = 0; i < p.length; i++) {
        if (t < p[i].llegada) t = p[i].llegada;   /* CPU ociosa */
        p[i].inicio = t;
        p[i].fin = t + p[i].rafaga;
        t = p[i].fin;
        p[i].respuesta = p[i].inicio - p[i].llegada;
        p[i].retorno = p[i].fin - p[i].llegada;
        p[i].espera = p[i].retorno - p[i].rafaga;
    }
    return p;
}

function copiar(x) {
    return {
        pid: x.pid, llegada: x.llegada, rafaga: x.rafaga,
        inicio: 0, fin: 0, respuesta: 0, espera: 0, retorno: 0
    };
}

La función devuelve el arreglo en orden de ejecución (no en orden de pid). Ese orden es el que se usa para dibujar el Gantt: el primer elemento es el primer bloque, el segundo el siguiente, y así. Las métricas, en cambio, se leen por pid al mostrar la tabla.

Los promedios se calculan con una función genérica que sirve para cualquier algoritmo:

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
    };
}

Y una función de verificación útil para depurar:

function verificar(procesos) {
    /* Comprueba que la suma de las rafagas coincida con el tiempo total. */
    var totalRafaga = 0, totalTiempo = 0;
    for (var i = 0; i < procesos.length; i++) {
        totalRafaga += procesos[i].rafaga;
        if (i === 0) totalTiempo = procesos[i].fin;
        else if (procesos[i].fin > totalTiempo) totalTiempo = procesos[i].fin;
    }
    /* En FCFS sin huecos, totalTiempo debe ser >= totalRafaga. */
    return totalTiempo >= totalRafaga;
}

7. Dibujar el Gantt en el DOM

El Gantt se dibuja como una fila de <span> dentro de un contenedor .gantt, usando flex para que las longitudes sean proporcionales. Cada span tiene una clase de color p0, p1 o p2 y un flex proporcional a la ráfaga:

function dibujarGantt(procesos, ganttEl, ticksEl) {
    ganttEl.innerHTML = '';
    ticksEl.innerHTML = '';
    if (procesos.length === 0) return;

    /* El tiempo total es el fin del ultimo proceso. */
    var total = procesos[procesos.length - 1].fin;
    var t = 0;

    procesos.forEach(function (p, idx) {
        /* Hueco de CPU ociosa, si lo hay. */
        if (p.inicio > t) {
            var hueco = document.createElement('span');
            hueco.className = 'ociosa';
            hueco.style.flex = (p.inicio - t) + ' 1 0';
            hueco.textContent = 'ociosa';
            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);

        /* Marca de tiempo al inicio del bloque. */
        var marca = document.createElement('span');
        marca.style.left = (p.inicio / total * 100) + '%';
        marca.textContent = p.inicio;
        ticksEl.appendChild(marca);

        t = p.fin;
    });

    /* Marca final. */
    var fin = document.createElement('span');
    fin.style.left = '100%';
    fin.textContent = total;
    ticksEl.appendChild(fin);
}

La función asume que el arreglo está ordenado por ejecución (lo que devuelven los algoritmos). Si se le pasa en otro orden, el Gantt saldrá mal. El color se asigna por índice en el orden de ejecución, no por pid, para que procesos adyacentes tengan colores distintos.

8. Renderizar la tabla de métricas

La tabla se genera a partir del arreglo ordenado. Como el arreglo está ordenado por ejecución y no por pid, conviene reordenar por pid para mostrarlo:

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;
    promEl.textContent = 'Promedio: respuesta=' + (sr/n).toFixed(2) +
        ' espera=' + (se/n).toFixed(2) + ' retorno=' + (st/n).toFixed(2);
}

Los promedios se muestran con dos decimales. Si los tiempos son enteros, el promedio puede tener decimales; eso es correcto.

9. Demostración interactiva

Esta demostración reúne todo lo anterior: genera una carga de trabajo con el generador, la ejecuta con FCFS y dibuja el Gantt y la tabla. Cambia los parámetros y observa cómo cambian los resultados:

10. Validación y casos borde

Un simulador robusto debe manejar estos casos sin romperse:

• Un solo proceso: el Gantt tiene un solo bloque; los promedios son iguales a sus métricas.
• Todos llegan en 0: no hay huecos de CPU ociosa; el tiempo total es la suma de las ráfagas.
• Llegadas muy separadas: la CPU queda ociosa entre procesos; el Gantt debe mostrar los huecos y el tiempo total incluye la ociosidad.
• Ráfagas iguales: el orden no afecta a las métricas promedio, solo al orden de salida.
• Procesos con la misma llegada: el desempate debe ser determinista (por pid, por ejemplo). Si no, el resultado depende del orden interno del arreglo.
• Ráfaga de 1: el proceso más corto posible. SJF lo ejecutará primero; Round Robin le dará un turno completo en un quantum.

11. Reutilización en los simuladores

A partir del tema 12, cada algoritmo se implementa como una función con la misma firma que fcfs: recibe un arreglo de procesos y devuelve un arreglo ordenado por ejecución con las métricas rellenas. El Gantt y la tabla son genéricos y no cambian.

La única diferencia entre algoritmos está en el orden de ejecución y en cómo se reparte la CPU (turnos, prioridades). El modelo de datos, el generador, las métricas y el dibujo son los mismos. Por eso, este tema es la base de todo lo que sigue.

En los temas 12, 16, 19, 23, 27, 31, 34 y 40 se construyen simuladores completos; todos parten de este modelo y solo añaden la función del algoritmo y, a veces, controles adicionales (quantum, prioridad, número de colas).

12. Resumen

• Un proceso se modela como un objeto con campos de entrada (pid, llegada, ráfaga) y de salida (inicio, fin, respuesta, espera, retorno).
• Una carga de trabajo es un arreglo de procesos.
• El generador usa un PRNG con semilla para ser reproducible.
• La función del algoritmo no modifica la entrada: trabaja sobre una copia y devuelve el orden de ejecución.
• FCFS ordena por llegada y recorre la línea de tiempo, saltando la CPU ociosa.
• Las métricas se calculan con las mismas fórmulas de los temas 7 y 8.
• El Gantt se dibuja con spans flexibles proporcionales a la ráfaga.
• La tabla se ordena por pid para mostrar los resultados por proceso.
• Los casos borde (un proceso, llegadas iguales, huecos) deben probarse siempre.
• Este modelo se reutiliza en todos los simuladores del curso.

13. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Implementa crearProceso y generarCarga en la consola del navegador y verifica la salida con JSON.stringify.
2. Escribe una función sjf que ordene por ráfaga más corta entre los que ya llegaron y compara con fcfs.
3. Añade un campo prioridad al modelo y verifica que los algoritmos anteriores siguen funcionando.
4. Modifica el generador para que las llegadas sigan una distribución (por ejemplo, más procesos al principio).
5. Implementa la verificación de que la suma de las ráfagas sea igual al tiempo total menos los huecos.
6. Dibuja el Gantt de una carga con un hueco de CPU ociosa y verifica que se muestre.