Simulador de TLB

1. Qué vamos a simular

El simulador procesa una secuencia de accesos a páginas virtuales y mantiene una TLB de tamaño fijo. En cada acceso:

• Busca la página en la TLB: si está (acierto), no se reemplaza nada.
• Si no está (fallo): se carga la entrada en la TLB, reemplazando una existente si la TLB está llena, según la política elegida.

El simulador muestra el estado de la TLB tras cada acceso, el tipo de resultado (acierto/fallo) y las estadísticas finales (aciertos, fallos, tasa, tiempo medio).

2. El programa de ejemplo

Este programa en C simula una TLB con política FIFO y procesa una secuencia de páginas:

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

int main(int argc, char **argv)
{
    int size = argc > 1 ? atoi(argv[1]) : 4;
    int tlb[16]; int n = 0;  /* TLB como array FIFO */
    int hits = 0, misses = 0;

    int seq[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int nseq = 12;
    for (int i = 0; i < nseq; i++) {
        int page = seq[i];
        int found = 0;
        for (int j = 0; j < n; j++)
            if (tlb[j] == page) { found = 1; break; }
        if (found) { hits++; printf("pág %d: HIT\\n", page); }
        else {
            misses++;
            if (n < size) tlb[n++] = page;
            else { /* FIFO: sacar el primero */
                for (int j = 0; j < size - 1; j++) tlb[j] = tlb[j+1];
                tlb[size-1] = page;
            }
            printf("pág %d: MISS\\n", page);
        }
    }
    printf("Hits=%d Misses=%d Tasa=%.1f%%\\n", hits, misses, 100.0*hits/nseq);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o tlb_sim tlb_sim.c
$ ./tlb_sim 4
pág 1: MISS
pág 2: MISS
pág 3: MISS
pág 4: MISS
pág 1: HIT
pág 2: HIT
pág 5: MISS
pág 1: HIT
pág 2: HIT
pág 3: MISS
pág 4: MISS
pág 5: MISS
Hits=5 Misses=7 Tasa=41,7%

3. Políticas de reemplazo

Cuando la TLB está llena y hay un fallo, hay que elegir qué entrada reemplazar. Las políticas más comunes:

En la práctica, las TLB de hardware usan aproximaciones a LRU (como el bit de uso) por simplicidad.

4. Procesamiento de la secuencia

Para cada página de la secuencia:

1. Buscar en la TLB: si está, es un acierto (hit). No se modifica la TLB.
2. Si no está (miss): si la TLB tiene espacio, se añade. Si está llena, se reemplaza según la política.
3. Actualizar estadísticas: contar hits y misses.
4. Calcular tiempo medio: TEA = (hits × t_hit + misses × t_miss) / total.

5. El simulador interactivo

TLB configurable con política FIFO o LRU. Introduce una secuencia de páginas y observa el proceso paso a paso.

6. Qué observar

• La secuencia de Belady: con FIFO, la secuencia 1,2,3,4,1,2,5,1,2,3,4,5 con TLB de 3 entradas produce más fallos que con 4.
• LRU vs FIFO: LRU suele ser mejor, pero no siempre.
• El tamaño de la TLB: una TLB más grande reduce los fallos.
• La localidad: secuencias con repetición tienen alta tasa de aciertos.

7. Limitaciones del simulador

Este simulador es una simplificación. No modela:

• La TLB de dos niveles (L1 y L2).
• Las páginas grandes (huge pages).
• La invalidación de la TLB en cambios de contexto.
• El costo real de un fallo (consulta a la tabla multinivel).

8. En Linux

La TLB se gestiona por hardware. Linux invalida la TLB en cambios de contexto y en operaciones de mmap/munmap/mprotect. Las herramientas para observar:

$ perf stat -e dTLB-load-misses,dTLB-loads,iTLB-load-misses,iTLB-loads ./prog$ perf stat -e dTLB-load-misses,dTLB-loads,iTLB-load-misses,iTLB-loads ./prog

• dTLB-load-misses: fallos de TLB de datos.
• dTLB-loads: accesos a la TLB de datos.
• iTLB-load-misses: fallos de TLB de instrucciones.
• iTLB-loads: accesos a la TLB de instrucciones.

9. Resumen

• El simulador procesa una secuencia de páginas con una TLB de tamaño fijo.
• La política de reemplazo (FIFO o LRU) determina qué entrada se reemplaza en un fallo.
• El simulador muestra aciertos, fallos, el estado de la TLB y el tiempo medio.
• La tasa de aciertos depende del tamaño de la TLB y de la localidad de la secuencia.
• En Linux, la TLB se gestiona por hardware y se observa con perf.

10. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Procesa la secuencia 1,2,3,4,1,2,5,1,2,3,4,5 con TLB de 3 y 4 entradas. ¿Cuántos fallos hay en cada caso?
2. Compara FIFO y LRU con la misma secuencia y tamaño. ¿Cuál tiene menos fallos?
3. Modifica el simulador para soportar la política Random.
4. Calcula el TEA para 5 aciertos y 7 fallos con t_hit=1 y t_miss=20.
5. Explica la anomalía de Belady y por qué ocurre con FIFO.
6. Investiga cómo implementa el hardware la política LRU en la TLB.
7. Dibuja el estado de la TLB tras cada acceso para la secuencia del ejemplo.