Simulador de intercalados

1. Por qué un simulador de intercalados

En el tema 3 viste que un contador compartido da resultados distintos en cada ejecución. En el tema 4 viste que counter++ son tres instrucciones de máquina y que el planificador puede intercalarlas de formas que corrompen el valor. Pero en la práctica, nunca ves todos los intercalados: el planificador elige uno al azar, y solo ves el resultado, no el intercalado que lo produjo.

Este simulador recorre todos los intercalados posibles de dos hilos que ejecutan counter++ (una vez cada uno) y cuenta cuántos producen el resultado correcto y cuántos el incorrecto. Es una herramienta de análisis: permite ver, de forma determinista, lo que en la realidad solo se ve por azar.

El simulador es útil para:

• Entender la magnitud del problema: ver cuántos intercalados son incorrectos.
• Visualizar los intercalados: ver la secuencia exacta de instrucciones que produce cada resultado.
• Experimentar: cambiar el número de hilos y de incrementos.
• Validar soluciones: verificar que una solución (como _Atomic) elimina todos los intercalados incorrectos.

2. El modelo: dos hilos, tres instrucciones

El modelo más simple es dos hilos que ejecutan counter++ una vez cada uno. Cada hilo tiene tres instrucciones:

• L (LOAD): leer el valor de counter a un registro.
• A (ADD): incrementar el registro.
• S (STORE): escribir el registro a counter.

El estado compartido es un solo entero: counter, que empieza en 0. Cada hilo tiene su propio registro (R1 para el hilo 0, R2 para el hilo 1).

El resultado correcto es 2: cada hilo incrementa el contador una vez.

3. Qué es un intercalado

Un intercalado (interleaving) es una secuencia de instrucciones de dos o más hilos que respeta el orden interno de cada hilo. Es decir, las instrucciones de cada hilo aparecen en el mismo orden en que las escribió el programador, pero se mezclan con las de los otros hilos.

Por ejemplo, si el hilo 0 tiene instrucciones L0, A0, S0 y el hilo 1 tiene L1, A1, S1, entonces un intercalado válido es: L0, L1, A0, A1, S0, S1. Otro intercalado válido es: L0, A0, S0, L1, A1, S1.

Un intercalado inválido sería: L0, A0, L1, S0, A1, S1, porque S0 aparece antes de A1 pero después de L1, lo que viola el orden interno del hilo 1 (L1 debe ir antes de A1).

El simulador solo genera intercalados válidos: respeta el orden interno de cada hilo.

4. El espacio combinatorio

Para dos hilos con 3 instrucciones cada uno, el número de intercalados válidos es el número de formas de elegir 3 posiciones entre 6 para las instrucciones del hilo 0 (las restantes son del hilo 1):

C(6, 3) = 6! / (3! × 3!) = 20 intercalados.

De estos 20, solo 2 producen el resultado correcto (2): cuando un hilo completa todas sus instrucciones antes de que el otro empiece. Los otros 18 producen 1.

La probabilidad de obtener el resultado correcto es 2/20 = 10 %. La probabilidad de obtener 1 es 18/20 = 90 %.

Con más hilos y más incrementos, el número de intercalados crece factoralmente, pero la probabilidad de obtener el resultado correcto disminuye exponencialmente.

Con 2 hilos y 3 incrementos por hilo, hay 48620 intercalados posibles, y solo 2 producen el resultado correcto (6). La probabilidad de obtener el resultado correcto es del 0,004 %.

5. Enumerar todos los intercalados

Para enumerar todos los intercalados válidos, se usa un algoritmo recursivo: en cada paso, se elige la siguiente instrucción de uno de los hilos (la que sigue en su secuencia interna) y se añade al intercalado. Se repite hasta que no quedan instrucciones.

function enumerar(hilos) {
    /* hilos: array de arrays de instrucciones por hilo. */
    /* Retorna todos los intercalados válidos. */
    var resultados = [];
    function recorrer(estado, intercalado) {
        /* estado[i] = cuántas instrucciones del hilo i se han usado. */
        var todosTerminados = true;
        for (var i = 0; i < hilos.length; i++) {
            if (estado[i] < hilos[i].length) {
                todosTerminados = false;
                break;
            }
        }
        if (todosTerminados) {
            resultados.push(intercalado.slice());
            return;
        }
        for (var i = 0; i < hilos.length; i++) {
            if (estado[i] < hilos[i].length) {
                /* Añadir la siguiente instrucción del hilo i. */
                estado[i]++;
                intercalado.push({ hilo: i, instruccion: hilos[i][estado[i] - 1] });
                recorrer(estado, intercalado);
                intercalado.pop();
                estado[i]--;
            }
        }
    }
    var estado = [];
    for (var i = 0; i < hilos.length; i++) estado.push(0);
    recorrer(estado, []);
    return resultados;
}

El algoritmo explora todas las combinaciones posibles respetando el orden interno de cada hilo. La complejidad es O((3n)! / (3!)^n), que crece rápidamente.

6. Ejecutar un intercalado

Para ejecutar un intercalado, se simula el estado compartido (counter) y los registros de cada hilo. Se procesan las instrucciones en el orden del intercalado:

function ejecutar(intercalado) {
    var counter = 0;
    var registros = [0, 0]; /* un registro por hilo */
    intercalado.forEach(function (ins) {
        var h = ins.hilo;
        if (ins.instruccion === 'L') {
            registros[h] = counter;        /* LOAD: leer counter a registro */
        } else if (ins.instruccion === 'A') {
            registros[h]++;                /* ADD: incrementar registro */
        } else if (ins.instruccion === 'S') {
            counter = registros[h];        /* STORE: escribir registro a counter */
        }
    });
    return counter;
}

La función devuelve el valor final de counter. Se compara con el valor esperado (número de hilos × incrementos por hilo) para determinar si el intercalado es correcto.

7. Contar correctos e incorrectos

Para contar los intercalados correctos e incorrectos:

function contar(hilos, incrementos) {
    /* Construir las instrucciones de cada hilo. */
    var instrucciones = [];
    for (var h = 0; h < hilos; h++) {
        var inst = [];
        for (var i = 0; i < incrementos; i++) {
            inst.push('L');
            inst.push('A');
            inst.push('S');
        }
        instrucciones.push(inst);
    }
    /* Enumerar todos los intercalados. */
    var intercalados = enumerar(instrucciones);
    /* Ejecutar cada uno y contar. */
    var correctos = 0;
    var incorrectos = 0;
    var esperado = hilos * incrementos;
    intercalados.forEach(function (ic) {
        var resultado = ejecutar(ic);
        if (resultado === esperado) correctos++;
        else incorrectos++;
    });
    return { total: intercalados.length, correctos: correctos,
             incorrectos: incorrectos, esperado: esperado };
}

Esta función devuelve el número total de intercalados, los correctos, los incorrectos y el resultado esperado.

8. La probabilidad de error

La probabilidad de obtener un resultado correcto es el número de intercalados correctos dividido por el total. La probabilidad de error es 1 menos esa probabilidad.

Para dos hilos con un incremento cada uno:

• Total de intercalados: 20.
• Correctos: 2.
• Incorrectos: 18.
• Probabilidad de correcto: 2/20 = 10 %.
• Probabilidad de error: 90 %.

Para dos hilos con 3 incrementos cada uno:

• Total de intercalados: 48620.
• Correctos: 2.
• Incorrectos: 48618.
• Probabilidad de correcto: 2/48620 ≈ 0,004 %.
• Probabilidad de error: ≈ 99,996 %.

Esto explica por qué el resultado del experimento del tema 3 es siempre incorrecto: con 4 hilos y 100.000 incrementos, la probabilidad de obtener el resultado correcto es prácticamente cero.

9. Simulador interactivo

Este simulador enumera todos los intercalados de dos hilos que ejecutan counter++ (con N incrementos cada uno) y cuenta cuántos producen el resultado correcto:

10. Extensiones posibles

• Más hilos: extender el simulador para 3 o 4 hilos.
• Otras operaciones: simular counter--, counter += 2, etc.
• Verificación de soluciones: verificar que _Atomic elimina todos los intercalados incorrectos.
• Visualización: mostrar los intercalados incorrectos como secuencias de instrucciones.
• Probabilidad de error con N hilos: calcular la probabilidad para N hilos y M incrementos.

11. Resumen

• Un intercalado es una secuencia de instrucciones que respeta el orden interno de cada hilo.
• Para dos hilos con 1 incremento cada uno, hay 20 intercalados posibles, de los cuales solo 2 son correctos.
• La probabilidad de obtener el resultado correcto es del 10 %.
• Con más incrementos, la probabilidad de correcto disminuye exponencialmente.
• El simulador enumera todos los intercalados y cuenta los correctos e incorrectos.
• Los intercalados incorrectos se producen cuando ambos hilos leen el mismo valor antes de que alguno escriba.
• La atomicidad elimina todos los intercalados incorrectos.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta el simulador con 1 incremento y verifica que hay 20 intercalados, de los cuales 2 son correctos.
2. Ejecuta con 2 incrementos y verifica que hay 924 intercalados.
3. Ejecuta con 3 incrementos y verifica que hay 48620 intercalados.
4. Modifica el simulador para 3 hilos y calcula el número de intercalados.
5. Explica por qué la probabilidad de correcto disminuye exponencialmente.
6. Investiga cómo se podría visualizar los intercalados incorrectos como secuencias de instrucciones.