Simulador multiprocesador - Planificación de la CPU

1. Por qué un simulador multiprocesador

La planificación en multiprocesadores tiene varios parámetros que afectan al rendimiento: número de CPUs, estrategia de colas, balanceo. Un simulador permite experimentar con estos parámetros y ver el efecto en el Gantt y en las métricas.

Este simulador es el último del bloque 8 y cierra el estudio de la planificación en multiprocesadores. A partir del bloque 9, el problema se extiende a tiempo real.

2. Arquitectura

El simulador tiene las mismas partes que los anteriores, con tres estrategias:

Estrategia	Descripción	Función
Cola global	Una cola compartida; los procesos se asignan al CPU que queda libre primero.	`globalQueue`
Por núcleo (sin balanceo)	Una cola por CPU; los procesos se asignan round-robin por llegada.	`porCPU`
Por núcleo (con balanceo)	Una cola por CPU; los procesos se asignan al CPU menos cargado.	`porCPUBalanceado`

3. Cola global

En la cola global, todos los procesos se almacenan en una única cola. Cuando un CPU queda libre, toma el siguiente proceso de la cola. Esto produce un balanceo automático:

globalQueue.js

function globalQueue(procesos, numCPUs) {
    var p = procesos.map(function (x) {
        return { pid: x.pid, llegada: x.llegada, rafaga: x.rafaga };
    });
    p.sort(function (a, b) {
        if (a.llegada !== b.llegada) return a.llegada - b.llegada;
        return a.pid - b.pid;
    });
    var cpuTimes = [];
    for (var i = 0; i < numCPUs; i++) cpuTimes.push(0);
    var resultados = [];
    p.forEach(function (proc) {
        /* Elegir el CPU que queda libre antes. */
        var mejorCPU = 0;
        var mejorTiempo = Math.max(cpuTimes[0], proc.llegada);
        for (var c = 1; c < numCPUs; c++) {
            var tiempo = Math.max(cpuTimes[c], proc.llegada);
            if (tiempo < mejorTiempo) { mejorTiempo = tiempo; mejorCPU = c; }
        }
        var inicio = Math.max(cpuTimes[mejorCPU], proc.llegada);
        var fin = inicio + proc.rafaga;
        cpuTimes[mejorCPU] = fin;
        resultados.push({ pid: proc.pid, llegada: proc.llegada, rafaga: proc.rafaga,
            cpu: mejorCPU, inicio: inicio, fin: fin,
            respuesta: inicio - proc.llegada, retorno: fin - proc.llegada,
            espera: (fin - proc.llegada) - proc.rafaga });
    });
    return resultados;
}

4. Cola por núcleo sin balanceo

En la cola por núcleo sin balanceo, los procesos se asignan round-robin por llegada: el primer proceso al CPU 0, el segundo al CPU 1, etc. No hay migración:

porCPU.js

function porCPU(procesos, numCPUs) {
    var p = procesos.map(function (x) {
        return { pid: x.pid, llegada: x.llegada, rafaga: x.rafaga };
    });
    p.sort(function (a, b) {
        if (a.llegada !== b.llegada) return a.llegada - b.llegada;
        return a.pid - b.pid;
    });
    var cpuTimes = [];
    for (var i = 0; i < numCPUs; i++) cpuTimes.push(0);
    var resultados = [];
    p.forEach(function (proc, idx) {
        var cpu = idx % numCPUs;
        var inicio = Math.max(cpuTimes[cpu], proc.llegada);
        var fin = inicio + proc.rafaga;
        cpuTimes[cpu] = fin;
        resultados.push({ pid: proc.pid, llegada: proc.llegada, rafaga: proc.rafaga,
            cpu: cpu, inicio: inicio, fin: fin,
            respuesta: inicio - proc.llegada, retorno: fin - proc.llegada,
            espera: (fin - proc.llegada) - proc.rafaga });
    });
    return resultados;
}

5. Cola por núcleo con balanceo

En la cola por núcleo con balanceo, los procesos se asignan al CPU menos cargado en el momento de llegada:

porCPUBalanceado.js

function porCPUBalanceado(procesos, numCPUs) {
    var p = procesos.map(function (x) {
        return { pid: x.pid, llegada: x.llegada, rafaga: x.rafaga };
    });
    p.sort(function (a, b) {
        if (a.llegada !== b.llegada) return a.llegada - b.llegada;
        return a.pid - b.pid;
    });
    var cpuTimes = [];
    for (var i = 0; i < numCPUs; i++) cpuTimes.push(0);
    var resultados = [];
    p.forEach(function (proc) {
        var cpu = 0;
        var minT = Math.max(cpuTimes[0], proc.llegada);
        for (var c = 1; c < numCPUs; c++) {
            var tiempo = Math.max(cpuTimes[c], proc.llegada);
            if (tiempo < minT) { minT = tiempo; cpu = c; }
        }
        var inicio = Math.max(cpuTimes[cpu], proc.llegada);
        var fin = inicio + proc.rafaga;
        cpuTimes[cpu] = fin;
        resultados.push({ pid: proc.pid, llegada: proc.llegada, rafaga: proc.rafaga,
            cpu: cpu, inicio: inicio, fin: fin,
            respuesta: inicio - proc.llegada, retorno: fin - proc.llegada,
            espera: (fin - proc.llegada) - proc.rafaga });
    });
    return resultados;
}

6. Gantt por CPU

El Gantt se dibuja por CPU: cada CPU tiene su propia barra. Los procesos se colocan en la barra del CPU al que fueron asignados:

dibujarGanttCPU.js

function dibujarGanttCPU(resultados, cpu, numCPUs, ganttEl, ticksEl) {
    ganttEl.innerHTML = '';
    ticksEl.innerHTML = '';
    var misProcs = resultados.filter(function (r) { return r.cpu === cpu; });
    if (misProcs.length === 0) return;
    misProcs.sort(function (a, b) { return a.inicio - b.inicio; });
    var total = resultados.reduce(function (m, r) { return r.fin > m ? r.fin : m; }, 0);
    var t = 0;
    var idx = 0;
    misProcs.forEach(function (r) {
        if (r.inicio > t) {
            var hueco = document.createElement('span');
            hueco.style.flex = (r.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 = (r.fin - r.inicio) + ' 1 0';
        span.textContent = 'P' + r.pid;
        ganttEl.appendChild(span);
        var marca = document.createElement('span');
        marca.style.left = (r.inicio / total * 100) + '%';
        marca.textContent = r.inicio;
        ticksEl.appendChild(marca);
        t = r.fin;
        idx++;
    });
    var fin = document.createElement('span');
    fin.style.left = '100%';
    fin.textContent = total;
    ticksEl.appendChild(fin);
}

7. Tabla comparativa

La tabla muestra las métricas de cada estrategia para la misma carga:

renderComparativa.js

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

function renderComparativa(resGlobal, resPorCPU, resBalanceado, el) {
    var pG = promedios(resGlobal);
    var pP = promedios(resPorCPU);
    var pB = promedios(resBalanceado);
    el.innerHTML = '';
    var filas = [
        ['Tiempo de respuesta promedio', pG.respuesta, pP.respuesta, pB.respuesta],
        ['Tiempo de espera promedio', pG.espera, pP.espera, pB.espera],
        ['Tiempo de retorno promedio', pG.retorno, pP.retorno, pB.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);
        var td3 = document.createElement('td'); td3.textContent = f[3].toFixed(2); tr.appendChild(td3);
        el.appendChild(tr);
    });
}

8. Los controles

Los controles permiten ajustar la carga de trabajo:

Estrategia: cola global, por núcleo sin balanceo, por núcleo con balanceo.
Procesos: número de procesos (2 a 12).
Llegada máxima: llegada máxima posible.
Ráfaga máxima: ráfaga máxima posible.
Número de CPUs: 2 a 4.
Semilla: semilla del generador pseudoaleatorio.

9. Simulador interactivo

Este simulador compara las tres estrategias en 2 CPUs. Cambia la estrategia y observa cómo se distribuyen los procesos:

Simulador · multiprocesador

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

CPU 0

CPU 1

Proceso	Llegada	Ráfaga	CPU	Inicio	Fin	Respuesta	Espera	Retorno

10. Verificación y casos de prueba

Caso	Entrada	Resultado esperado
Un proceso	P1(0,5), 2 CPUs	Se asigna a CPU 0. Un bloque 0-5.
Procesos iguales	P1(0,4), P2(0,4), 2 CPUs	Cola global: ambos empiezan en 0. Por núcleo: P1 en CPU0, P2 en CPU1.
Desbalanceo	P1(0,10), P2(0,1), P3(0,1), 2 CPUs	Por núcleo sin balanceo: P1 en CPU0, P2 en CPU1, P3 en CPU0 (espera 10). Con balanceo: mejor distribución.
Llegadas distintas	P1(0,5), P2(3,2), 2 CPUs	Cola global: P1 en CPU0, P2 en CPU1 (o CPU0 si está libre).

11. Resumen

El simulador compara cola global, por núcleo sin balanceo y por núcleo con balanceo.
La cola global asigna al CPU que queda libre primero.
La cola por núcleo sin balanceo asigna round-robin por llegada.
La cola por núcleo con balanceo asigna al CPU menos cargado.
El Gantt se dibuja por CPU.
El balanceo mejora la distribución pero puede perder afinidad.
El simulador es la culminación del bloque 8 (multiprocesadores).

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

1. ¿Qué tres estrategias compara el simulador?

Cola global, por núcleo sin balanceo y por núcleo con balanceo.

2. ¿Cómo asigna la cola global?

Al CPU que queda libre primero.

3. ¿Cómo asigna la cola por núcleo sin balanceo?

Round-robin por llegada: el primer proceso al CPU 0, el segundo al CPU 1, etc.

4. ¿Cómo asigna la cola por núcleo con balanceo?

Al CPU menos cargado en el momento de llegada.

5. ¿Qué estrategia produce el mejor balanceo?

Cola global o por núcleo con balanceo.

6. ¿Qué estrategia puede producir desbalanceo?

Por núcleo sin balanceo.

7. ¿Qué estrategia preserva mejor la afinidad?

Por núcleo (con o sin balanceo), porque los procesos tienden a quedarse en el mismo CPU.

8. ¿Cómo se dibuja el Gantt en el simulador?

Una barra por CPU, con los procesos asignados a ese CPU.

9. ¿Qué métrica mejora más con el balanceo?

El tiempo de retorno promedio, porque los procesos se distribuyen mejor.

10. ¿Qué bloque del curso cierra este simulador?

El bloque 8 (planificación en multiprocesadores).

Para practicar

Ejecuta el simulador con las tres estrategias y compara los Gantt.
Diseña un caso donde el desbalanceo sea evidente sin balanceo.
Implementa el balanceo periódico en el simulador por núcleo.
Compara el rendimiento con 2, 3 y 4 CPUs.
Explica por qué la cola global no escala bien.
Investiga cómo Linux implementa el balanceo en la práctica.