Tiempo efectivo de acceso

1. El problema: cuantificar el costo

La TLB acelera la traducción, pero ¿cuánto? Para comparar diseños de hardware (tamaño de TLB, número de niveles, tiempo de memoria) y de software (patrones de acceso), se necesita una métrica única: el tiempo medio que tarda un acceso a memoria, incluyendo la traducción. Esa métrica es el tiempo efectivo de acceso (TEA).

El TEA se usa en el diseño de procesadores, en el análisis de rendimiento y en los exámenes de sistemas operativos. Es una de las fórmulas más importantes del curso.

2. Repaso: paginación y TLB

Con paginación, cada acceso a memoria requiere consultar la tabla de páginas. Con tablas multinivel (tema 22), son varios accesos a memoria (uno por nivel) antes de acceder a la RAM. La TLB (tema 24) es una caché de hardware que recuerda las traducciones recientes, reduciendo el costo a casi cero en el caso común.

Recordemos los tiempos típicos:

3. La fórmula del TEA: derivación

Sea p la tasa de aciertos de la TLB (probabilidad de hit), t_hit el tiempo de un acierto y t_miss el tiempo de un fallo. El tiempo efectivo de acceso es la media ponderada:

TEA = p × t_hit + (1 − p) × t_miss

Es la esperanza matemática del tiempo de acceso. Si p = 1 (siempre acierto), TEA = t_hit. Si p = 0 (siempre fallo), TEA = t_miss.

La derivación es directa: en una fracción p de los accesos se tarda t_hit, y en la fracción (1−p) se tarda t_miss. La media es la suma ponderada.

4. Caso sin TLB: un nivel

Sin TLB, cada acceso requiere consultar la tabla de páginas. Con una tabla de un solo nivel:

• Acceso a la tabla: t_mem.
• Acceso a la RAM: t_mem.
• TEA = 2 × t_mem.

Si t_mem = 100 ns, TEA = 200 ns. Cada acceso tarda el doble que un acceso a la RAM pura.

5. Caso sin TLB: multinivel

Con tablas multinivel de k niveles, cada acceso requiere consultar k tablas antes de acceder a la RAM:

TEA (sin TLB) = (k + 1) × t_mem

Con k = 4 (x86-64) y t_mem = 100 ns: TEA = 5 × 100 = 500 ns. Cada acceso tarda 5 veces más que un acceso a la RAM pura.

6. Caso con TLB: acierto y fallo

Con TLB, hay dos casos:

• Acierto (probabilidad p): TLB (t_TLB) + RAM (t_mem). Costo = t_TLB + t_mem.
• Fallo (probabilidad 1−p): TLB (t_TLB) + tabla (k × t_mem) + RAM (t_mem) + actualización de TLB (t_update, incluida en el fallo). Costo = t_TLB + (k + 1) × t_mem.

En la práctica, t_TLB es muy pequeño (~1 ns) y t_update se incluye en el costo del fallo.

7. La fórmula completa con TLB

Sustituyendo en la fórmula general:

TEA = p × (t_TLB + t_mem) + (1 − p) × (t_TLB + (k + 1) × t_mem)

donde:

• p: tasa de aciertos de la TLB.
• t_TLB: tiempo de acceso a la TLB.
• t_mem: tiempo de acceso a la RAM.
• k: número de niveles de la tabla de páginas.

Esta fórmula permite calcular el TEA para cualquier configuración de hardware.

8. Ejemplos resueltos paso a paso

Ejemplo 1: t_mem = 100 ns, t_TLB = 1 ns, k = 4, p = 0,98.

• t_hit = 1 + 100 = 101 ns.
• t_miss = 1 + 5 × 100 = 501 ns.
• TEA = 0,98 × 101 + 0,02 × 501 = 98,98 + 10,02 = 109 ns.

Ejemplo 2: Sin TLB, con 4 niveles: TEA = 5 × 100 = 500 ns. La TLB reduce el costo en un factor de 4,59.

Ejemplo 3: p = 0,99, mismos tiempos: TEA = 0,99 × 101 + 0,01 × 501 = 99,99 + 5,01 = 105 ns.

Ejemplo 4: t_mem = 80 ns, t_TLB = 1 ns, k = 4, p = 0,98: TEA = 0,98 × 81 + 0,02 × 401 = 79,38 + 8,02 = 87,4 ns.

9. Efecto de la tasa de aciertos

La tasa de aciertos p tiene un impacto enorme. Con t_mem = 100 ns, t_TLB = 1 ns, k = 4:

Con p = 1, TEA = 101 ns (el mínimo posible con TLB). Sin TLB, 500 ns. La TLB puede reducir el costo en un factor de 5.

La diferencia entre p = 0,98 y p = 0,99 es pequeña (4 ns), pero la diferencia entre p = 0,90 y p = 0,98 es grande (32 ns). La tasa de aciertos es crítica por debajo del 95 %.

10. Efecto del número de niveles

El número de niveles k afecta al costo del fallo. Con t_mem = 100 ns, t_TLB = 1 ns, p = 0,98:

El TEA crece con el número de niveles, pero de forma moderada (porque los fallos son raros). Sin embargo, el costo sin TLB crece linealmente. La TLB es más importante cuanto más niveles tiene la tabla.

11. Efecto del tiempo de memoria

El tiempo de acceso a la RAM (t_mem) afecta tanto al acierto como al fallo. Con t_TLB = 1 ns, k = 4, p = 0,98:

El TEA crece linealmente con t_mem. Por eso la memoria rápida (menor t_mem) es importante, y la TLB (que reduce el número de accesos a la RAM) es más valiosa con memorias lentas.

12. Comparación de escenarios reales

Diferentes configuraciones de hardware y software producen distintos TEA:

13. Extensión: memoria virtual y swap

El TEA se puede extender para incluir la memoria virtual (swap). Si una página no está en la RAM, se produce un fallo de página y se carga desde el disco. El costo de un fallo de página es enorme (milisegundos). La fórmula extendida:

TEA = p_TLB × t_hit + (1 − p_TLB) × [p_RAM × t_miss + (1 − p_RAM) × t_swap]

donde:

• p_TLB: tasa de aciertos de la TLB.
• p_RAM: probabilidad de que la página esté en la RAM (dado un fallo de TLB).
• t_swap: tiempo de acceso al disco (swap) en ms.

Como t_swap es miles de veces mayor que t_mem, incluso una tasa baja de fallos de página domina el TEA. Por eso es crítico mantener la tasa de fallos de página baja (hiperpaginación, tema 33).

14. Experimento en C

El programa siguiente calcula el TEA para distintos valores de los parámetros:

#include <stdio.h>

int main(void)
{
    double t_mem = 100.0;
    double t_tlb = 1.0;
    int k = 4;
    double t_tabla = k * t_mem;

    printf("=== Efecto de la tasa de aciertos ===\\n");
    double ps[] = {0.90, 0.95, 0.98, 0.99, 0.999, 1.0};
    for (int i = 0; i < 6; i++) {
        double p = ps[i];
        double tea = p * (t_tlb + t_mem) + (1 - p) * (t_tlb + t_tabla + t_mem);
        printf("p=%.3f -> TEA = %.2f ns\\n", p, tea);
    }

    printf("\\n=== Efecto del número de niveles (p=0.98) ===\\n");
    for (int kk = 1; kk <= 4; kk++) {
        double tt = kk * t_mem;
        double tea = 0.98 * (t_tlb + t_mem) + 0.02 * (t_tlb + tt + t_mem);
        printf("k=%d -> TEA = %.2f ns\\n", kk, tea);
    }

    printf("\\n=== Efecto del tiempo de memoria (p=0.98, k=4) ===\\n");
    double ms[] = {50.0, 100.0, 200.0};
    for (int i = 0; i < 3; i++) {
        double tm = ms[i];
        double tt = 4 * tm;
        double tea = 0.98 * (t_tlb + tm) + 0.02 * (t_tlb + tt + tm);
        printf("t_mem=%.0f ns -> TEA = %.2f ns\\n", tm, tea);
    }

    double sin_tlb = 5 * t_mem;
    printf("\\nSin TLB (4 niveles): %.2f ns\\n", sin_tlb);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o tea tea.c
$ ./tea
=== Efecto de la tasa de aciertos ===
p=0,900 -> TEA = 141,00 ns
p=0,950 -> TEA = 121,00 ns
p=0,980 -> TEA = 109,00 ns
p=0,990 -> TEA = 105,00 ns
p=0,999 -> TEA = 101,40 ns
p=1,000 -> TEA = 101,00 ns

=== Efecto del número de niveles (p=0.98) ===
k=1 -> TEA = 103,00 ns
k=2 -> TEA = 105,00 ns
k=3 -> TEA = 107,00 ns
k=4 -> TEA = 109,00 ns

=== Efecto del tiempo de memoria (p=0.98, k=4) ===
t_mem=50 ns -> TEA = 55,00 ns
t_mem=100 ns -> TEA = 109,00 ns
t_mem=200 ns -> TEA = 217,00 ns

Sin TLB (4 niveles): 500,00 nsSin TLB (4 niveles): 500,00 ns

15. Probar con un simulador

Este simulador calcula el TEA para distintos valores de los parámetros, incluyendo la extensión a memoria virtual (swap).

16. En Linux

El TEA no se mide directamente en Linux, pero se puede observar su efecto en el rendimiento:

$ perf stat -e dTLB-load-misses,dTLB-loads ./tlb 1048576 1
$ perf stat -e dTLB-load-misses,dTLB-loads ./tlb 1048576 1024

• perf stat: cuenta los fallos y accesos a la TLB.
• La tasa de aciertos se calcula como 1 - (misses / loads).
• Comparar los resultados con distintos patrones de acceso muestra el efecto de la TLB.

17. Resumen

• El TEA es el costo medio de un acceso, ponderado por la tasa de aciertos de la TLB.
• Fórmula: TEA = p × t_hit + (1 − p) × t_miss.
• Sin TLB: TEA = (k + 1) × t_mem.
• Con TLB: TEA = p × (t_TLB + t_mem) + (1 − p) × (t_TLB + (k+1) × t_mem).
• La tasa de aciertos tiene un impacto enorme: por debajo del 95 % el TEA crece rápidamente.
• El número de niveles afecta moderadamente al TEA (porque los fallos son raros).
• El tiempo de memoria afecta linealmente al TEA.
• La extensión a swap muestra que los fallos de página dominan el TEA.
• El TEA permite comparar diseños de hardware y de software.

18. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Calcula el TEA para t_mem=100 ns, t_TLB=1 ns, k=4, p=0,95. ¿Cuánto es?
2. ¿Qué tasa de aciertos se necesita para que el TEA sea ≤ 110 ns con los mismos tiempos?
3. Compara el TEA con TLB (p=0,98) y sin TLB para 1 nivel y 4 niveles.
4. Modifica tea.c para calcular el TEA para p de 0,5 a 1,0 en pasos de 0,05.
5. Explica por qué un pequeño aumento en la tasa de aciertos puede reducir mucho el TEA.
6. Calcula el TEA extendido con p_TLB=0,98, p_RAM=0,999, t_mem=100 ns, t_swap=10 ms.
7. Investiga cómo se mide la tasa de aciertos de la TLB en hardware real.
8. Dibuja una gráfica del TEA en función de p para los tiempos del ejemplo.
9. Compara el TEA de dos procesadores: uno con TLB de 64 entradas (p=0,95) y otro con 512 entradas (p=0,99).
10. Explica por qué la TLB es más importante en sistemas con tablas de 4 niveles que en sistemas con 1 nivel.