Simulador de algoritmos de reemplazo

1. Qué vamos a simular

Para comparar algoritmos de reemplazo hay que fijar todas las condiciones menos una: la misma cadena de referencias, la misma cantidad de marcos, el mismo estado inicial (memoria vacía) y el mismo criterio (fallo o acierto en cada acceso). Lo único que cambia es la regla con la que cada algoritmo elige su víctima. Si no se cumplen esas condiciones, cualquier comparación es tramposa.

Los contendientes ya los conoces:

• FIFO (tema 35): reemplaza la página más antigua.
• LRU (tema 37): reemplaza la menos usada recientemente.
• Reloj (tema 38): da segundas oportunidades con el bit R y reemplaza la primera página que no se usó.
• Óptimo (tema 36): reemplaza la que se usará más tarde. Es imposible de implementar, pero es la cota.

El simulador procesa una cadena y mide, para cada algoritmo: fallos, aciertos y tasa de fallos. Además lleva el detalle acceso por acceso, para ver no solo cuántos fallos hubo, sino dónde aparecen.

2. Los cuatro algoritmos, lado a lado

Algoritmo de pila (stack algorithm): aquel en el que las páginas en memoria con k marcos están siempre incluidas en las que estarían con k+1. LRU y óptimo lo son; FIFO y reloj no. Por eso los de pila nunca sufren la anomalía de Belady, y los otros dos sí pueden sufrirla.

Esa propiedad es la que explica los resultados que verás en este tema: agregar un marco nunca puede perjudicar a LRU ni al óptimo, pero sí puede aumentar los fallos de FIFO y del reloj.

3. El programa de comparación

El programa siguiente implementa los cuatro algoritmos en funciones sim_* y ejecuta todas sobre la misma cadena. El número de marcos se pasa como argumento:

#include <stdio.h>
#include <stdlib.h>

#define NSEQ 12
static int seq[NSEQ] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};

/* FIFO: cola circular */
static int sim_fifo(int marcos)
{
    int mem[16], n = 0, fifo = 0, fallos = 0;
    for (int i = 0; i < NSEQ; i++) {
        int p = seq[i], found = 0;
        for (int j = 0; j < n; j++)
            if (mem[j] == p) { found = 1; break; }
        if (!found) {
            fallos++;
            if (n < marcos) mem[n++] = p;
            else { mem[fifo] = p; fifo = (fifo + 1) % marcos; }
        }
    }
    return fallos;
}

/* LRU: víctima con el último uso más antiguo */
static int sim_lru(int marcos)
{
    int mem[16], ultimo[16], n = 0, fallos = 0;
    for (int i = 0; i < NSEQ; i++) {
        int p = seq[i], found = -1;
        for (int j = 0; j < n; j++)
            if (mem[j] == p) { found = j; break; }
        if (found >= 0) {
            ultimo[found] = i;
        } else {
            fallos++;
            if (n < marcos) { mem[n] = p; ultimo[n] = i; n++; }
            else {
                int victima = 0;
                for (int j = 1; j < marcos; j++)
                    if (ultimo[j] < ultimo[victima]) victima = j;
                mem[victima] = p; ultimo[victima] = i;
            }
        }
    }
    return fallos;
}

/* Reloj: segunda oportunidad con una mano */
static int sim_reloj(int marcos)
{
    int mem[16], ref[16], n = 0, mano = 0, fallos = 0;
    for (int i = 0; i < NSEQ; i++) {
        int p = seq[i], found = -1;
        for (int j = 0; j < n; j++)
            if (mem[j] == p) { found = j; break; }
        if (found >= 0) {
            ref[found] = 1;
        } else {
            fallos++;
            if (n < marcos) { mem[n] = p; ref[n] = 1; n++; }
            else {
                while (ref[mano] == 1) { ref[mano] = 0; mano = (mano + 1) % marcos; }
                mem[mano] = p; ref[mano] = 1;
                mano = (mano + 1) % marcos;
            }
        }
    }
    return fallos;
}

/* Óptimo: víctima con el próximo uso más lejano */
static int sim_optimo(int marcos)
{
    int mem[16], n = 0, fallos = 0;
    for (int i = 0; i < NSEQ; i++) {
        int p = seq[i], found = 0;
        for (int j = 0; j < n; j++)
            if (mem[j] == p) { found = 1; break; }
        if (!found) {
            fallos++;
            if (n < marcos) mem[n++] = p;
            else {
                int victima = 0, lejano = -1;
                for (int j = 0; j < marcos; j++) {
                    int proximo = NSEQ;   /* nunca más */
                    for (int k = i + 1; k < NSEQ; k++)
                        if (seq[k] == mem[j]) { proximo = k; break; }
                    if (proximo > lejano) { lejano = proximo; victima = j; }
                }
                mem[victima] = p;
            }
        }
    }
    return fallos;
}

int main(int argc, char **argv)
{
    int marcos = argc > 1 ? atoi(argv[1]) : 3;
    printf("marcos=%d\n", marcos);
    printf("FIFO   : %d fallos de %d\n", sim_fifo(marcos), NSEQ);
    printf("LRU    : %d fallos de %d\n", sim_lru(marcos), NSEQ);
    printf("Reloj  : %d fallos de %d\n", sim_reloj(marcos), NSEQ);
    printf("Óptimo : %d fallos de %d\n", sim_optimo(marcos), NSEQ);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o reemplazo reemplazo.c
$ ./reemplazo 3
marcos=3
FIFO   : 9 fallos de 12
LRU    : 10 fallos de 12
Reloj  : 9 fallos de 12
Óptimo : 7 fallos de 12
$ ./reemplazo 4
marcos=4
FIFO   : 10 fallos de 12
LRU    : 8 fallos de 12
Reloj  : 10 fallos de 12
Óptimo : 6 fallos de 12

Compara las dos ejecuciones: FIFO y reloj empeoran al pasar de 3 a 4 marcos (de 9 a 10 fallos), mientras LRU y óptimo mejoran. Es la anomalía de Belady en acción, y la verás reproducida en el simulador de la sección 5.

4. Las cadenas de prueba

No existe un algoritmo «mejor» en abstracto: el resultado depende de la cadena. El simulador incluye cuatro cadenas con propósitos distintos; esta tabla muestra lo que produce cada una con 3 marcos, para que la uses como predicción antes de ejecutar:

Las mismas cadenas servirán para dos lecciones: cuando el conjunto de trabajo entra en memoria, todos los algoritmos empatan tras la carga inicial; cuando no entra, ningún algoritmo en línea puede evitar los fallos, y solo el óptimo se salva porque conoce el futuro.

5. El simulador interactivo

Configura los marcos y la cadena (o elige una de las cuatro de prueba) y ejecuta: verás la tabla de fallos, la gráfica y el detalle de cada acceso para los cuatro algoritmos a la vez.

6. Qué observar

• El óptimo es la cota. Con 3 marcos y la cadena clásica: 7 fallos, y ningún algoritmo real puede bajar de ahí. La columna «Fallos de más» de la tabla mide cuánto le falta a cada uno para llegar a la cota.
• La anomalía de Belady. Ejecuta la cadena clásica con 3 y con 4 marcos: FIFO y reloj pasan de 9 a 10 fallos; LRU baja de 10 a 8 y el óptimo de 7 a 6. Más memoria no siempre significa menos fallos: solo los algoritmos de pila lo garantizan.
• LRU no siempre gana a FIFO. En la cadena clásica con 3 marcos, FIFO falla 9 y LRU falla 10; con 4 marcos se invierte (8 contra 10). Las cadenas cortas castigan a unos y favorecen a otros; por eso en la práctica se comparan sobre trazas largas.
• El reloj se parece a FIFO en cadenas cortas. Empata en la clásica (9 y 9): varios de los bits R acaban todos en 1 y la mano da vueltas sin poder distinguir. Su ventaja aparece en cargas grandes, donde cuesta un bit en lugar de un registro de orden completo (tema 38).
• La localidad cambia todo. En la cadena con localidad, los cuatro mejores resultados se acercan (5 a 7 fallos) y las diferencias entre algoritmos se reducen: cuando el conjunto de trabajo entra en memoria, la política de reemplazo importa poco.
• El barrido castiga a todos los algoritmos en línea. Con 6 páginas en ciclo y solo 3 marcos, FIFO, LRU y reloj fallan en los 12 accesos: cualquier página que se cargue será reemplazada antes de volver a usarse. El óptimo acierta 3 veces solo porque conoce el futuro.

7. Limitaciones del simulador

El simulador es deliberadamente simple. No modela:

• Los tiempos: cuenta fallos y aciertos, pero no cuánto tarda cada uno ni el costo de escribir una página sucia al disco.
• La TLB ni la traducción de direcciones: todos los accesos llegan ya resueltos a la comparación.
• La asignación de marcos entre procesos: simula un solo proceso con todos los marcos para él (el reparto real se estudia en el tema 33).
• Las trazas reales: las cadenas cortas cabe inventarlas a mano, pero las conclusiones representativas salen de millones de accesos registrados.

8. En Linux

En un sistema real los «fallos» del simulador son los fallos de página del proceso. El sistema los cuenta y las herramientas los muestran:

$ /usr/bin/time -v ./programa 2>&1 | grep -i 'page faults'
	Minor (reclaiming a frame) page faults: 10234
	Major (requiring I/O) page faults: 0
$ perf stat -e page-faults ./programa
      1.024.318      page-faults

• Un fallo menor no toca el disco: la página ya estaba en RAM (tema 30).
• Un fallo mayor requiere leer del disco o del swap: es el que domina el tiempo.
• Cuando la memoria aprieta, los contadores de reemplazo pgscan y pgsteal de /proc/vmstat muestran el trabajo del gestor (tema 38).

9. Resumen

• Comparar algoritmos exige la misma cadena, los mismos marcos y el mismo estado inicial.
• El óptimo marca la cota inferior de fallos; ningún algoritmo real puede bajarla.
• LRU y óptimo son algoritmos de pila: más marcos nunca aumentan sus fallos.
• FIFO y reloj no lo son: con la cadena clásica pasan de 9 a 10 fallos al agregar un marco (anomalía de Belady).
• En cadenas con localidad todos mejoran y las diferencias se acortan; en barridos sin localidad todos los algoritmos en línea fallan casi siempre.
• La tabla de fallos, la gráfica y el detalle por acceso permiten ver dónde y por qué cada algoritmo pierde.

10. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta la cadena clásica con 3, 4 y 5 marcos y anota la tabla completa de fallos.
2. Comprueba que con 3 marcos en la cadena clásica FIFO (9) gana a LRU (10) y explica por qué ocurre.
3. Verifica con el simulador que la cadena 2, 5, 2, 4, 2, 5, 1, 1, 1, 5, 3, 5 con 3 marcos da 6 fallos en FIFO y 5 en el reloj, y explica por qué: el bit R de una página recién usada la salva del reemplazo.
4. Modifica reemplazo.c para que la cadena se pase por línea de comandos.
5. Genera 100 cadenas aleatorias con un script y compara los promedios; ¿en qué porcentaje gana cada algoritmo?
6. Explica por qué el óptimo, aun siendo la cota, no puede implementarse en un sistema real.
7. Compara las cadenas «Con localidad» y «Barrido» con los mismos marcos y relaciona la diferencia con el conjunto de trabajo (tema 33).