Tasa de fallos y rendimiento

1. El problema: los fallos son caros

Un acceso a la RAM tarda ~100 ns. Un fallo de página menor tarda ~10 µs (100× más). Un fallo de página mayor (con lectura del disco) tarda ~10 ms (100.000× más). Por eso, incluso una tasa de fallos muy baja puede dominar el tiempo de ejecución.

Si un programa tiene 1000 accesos, de los cuales 999 son aciertos (100 ns) y 1 es un fallo mayor (10 ms), el tiempo total es 999 × 100 ns + 10 ms = 0,1 ms + 10 ms = 10,1 ms. El fallo contribuye el 99 % del tiempo.

Esta diferencia de escala es la razón por la que la memoria virtual, aunque poderosa, requiere un cuidado extremo en el diseño del sistema y del software.

2. Repaso: TEA y memoria virtual

El tiempo efectivo de acceso (TEA) con TLB (tema 25) es:

TEA_TLB = p_TLB × t_hit + (1 − p_TLB) × t_miss

Con memoria virtual, hay que añadir el costo de los fallos de página. La fórmula se extiende para incluir la probabilidad de que una página no esté en la RAM.

Recordemos los tiempos típicos:

3. El costo de un fallo de página

El costo de un fallo de página depende del tipo (tema 30):

Un fallo mayor es 1000× más costoso que un fallo menor, y 100.000× más costoso que un acceso a la RAM.

4. La fórmula del TEA con memoria virtual

La fórmula extendida incluye la tasa de fallos de página. Sea p_RAM la probabilidad de que, dado un fallo de TLB, la página esté en la RAM:

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

donde:

• p_TLB: tasa de aciertos de la TLB.
• t_hit: tiempo de acierto de TLB (t_TLB + t_mem).
• t_miss: tiempo de fallo de TLB (t_TLB + t_tabla + t_mem).
• p_RAM: probabilidad de que la página esté en la RAM (dado un fallo de TLB).
• t_pagefault: tiempo de un fallo de página mayor (lectura del disco).

Si p_RAM = 1 (todas las páginas en RAM), la fórmula se reduce al TEA con TLB (tema 25). Si p_RAM < 1, el término de fallo de página domina.

5. Caso sin fallos de página

Cuando todas las páginas están en la RAM (p_RAM = 1), no hay fallos de página y el TEA es el del tema 25:

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

Con t_mem = 100 ns, t_TLB = 1 ns, k = 4, p_TLB = 0,98: TEA = 109 ns.

6. Caso con fallos menores

Si hay fallos menores (páginas en RAM pero no mapeadas), el costo de un fallo de TLB aumenta ligeramente:

• t_miss_minor = t_TLB + t_tabla + t_minor (donde t_minor ≈ 10 µs).
• TEA = p_TLB × t_hit + (1 − p_TLB) × t_miss_minor.

Como t_minor (10 µs) es 100× mayor que t_mem (100 ns), incluso unos pocos fallos menores aumentan el TEA. Pero como los fallos menores son raros (solo la primera escritura), el impacto es limitado.

7. Caso con fallos mayores

Si hay fallos mayores (páginas en disco), el costo es enorme:

• t_miss_major = t_TLB + t_tabla + t_major (donde t_major ≈ 10 ms).
• TEA = p_TLB × t_hit + (1 − p_TLB) × [p_RAM × t_miss + (1 − p_RAM) × t_miss_major].

Como t_major (10 ms) es 100.000× mayor que t_mem (100 ns), incluso una tasa muy baja de fallos mayores domina el TEA.

8. Ejemplos resueltos paso a paso

Ejemplo 1: t_mem = 100 ns, t_TLB = 1 ns, k = 4, p_TLB = 0,98, p_RAM = 0,999, t_major = 10 ms.

• t_hit = 1 + 100 = 101 ns.
• t_miss = 1 + 5 × 100 = 501 ns.
• TEA = 0,98 × 101 + 0,02 × [0,999 × 501 + 0,001 × 10.000.000] = 98,98 + 0,02 × [500,499 + 10.000] = 98,98 + 0,02 × 10.500,499 = 98,98 + 210,01 = 309 ns.

Un solo fallo de página mayor cada 1000 accesos aumenta el TEA de 109 ns a 309 ns.

Ejemplo 2: Mismo escenario pero p_RAM = 0,99 (1 % de fallos de página):

• TEA = 0,98 × 101 + 0,02 × [0,99 × 501 + 0,01 × 10.000.000] = 98,98 + 0,02 × [495,99 + 100.000] = 98,98 + 0,02 × 100.495,99 = 98,98 + 2009,92 = 2108,9 ns.

El TEA se multiplica por 20. Un 1 % de fallos de página arruina el rendimiento.

Ejemplo 3: p_RAM = 0,9999 (0,01 % de fallos):

• TEA = 0,98 × 101 + 0,02 × [0,9999 × 501 + 0,0001 × 10.000.000] = 98,98 + 0,02 × [500,9499 + 1000] = 98,98 + 0,02 × 1000,9499 = 98,98 + 20,02 = 119 ns.

Incluso un 0,01 % de fallos de página (1 cada 10.000 accesos) aumenta el TEA de 109 ns a 119 ns.

9. Por qué unos pocos fallos bastan

La razón es la enorme diferencia de escala: un fallo de página mayor (10 ms) equivale a 100.000 accesos a la RAM (100 ns cada uno). Un solo fallo cada 100.000 accesos duplica el TEA.

Por eso, los sistemas operativos invierten mucho esfuerzo en evitar fallos de página:

• Prefetching: cargar páginas por adelantado.
• Reemplazo inteligente: elegir la víctima que menos se usará.
• Memoria suficiente: evitar el swap.
• Localidad: los programas bien diseñados tienen pocos fallos.

10. Efecto de la tasa de fallos

La tasa de fallos de página (1 − p_RAM) tiene un impacto enorme. Con t_mem = 100 ns, t_TLB = 1 ns, k = 4, p_TLB = 0,98, t_major = 10 ms:

La relación es casi lineal en la tasa de fallos: cada 0,1 % de fallos añade ~200 ns al TEA. Una tasa del 1 % ya arruina el rendimiento.

11. Hiperpaginación (thrashing)

La hiperpaginación (thrashing) ocurre cuando un proceso usa más páginas de las que caben en la RAM, y el sistema pasa todo el tiempo moviendo páginas entre la RAM y el disco. El rendimiento cae a casi cero.

Es el caso extremo de una tasa de fallos de página alta. Se estudia en detalle en el tema 33.

12. Experimento en C

El programa siguiente toca un bloque grande de memoria y mide el tiempo, mostrando el efecto de los fallos de página:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double ahora(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec/1e9; }

int main(int argc, char **argv)
{
    size_t tam = argc > 1 ? (size_t)strtoul(argv[1], NULL, 10) : (500 << 20);
    char *p = malloc(tam);
    if (p == NULL) { fprintf(stderr, "sin memoria\\n"); return 1; }

    size_t paginas = tam / 4096;
    double t0 = ahora();
    for (size_t i = 0; i < paginas; i++) p[i * 4096] = 1;
    double t1 = ahora();
    printf("Tocar %zu páginas (%zu MiB): %.3f s (%.2f ms/pág)\\n",
           paginas, tam >> 20, t1 - t0, (t1 - t0) * 1000 / paginas);

    free(p);
    return 0;
}

$ gcc -std=c17 -O2 -Wall -Wextra -o tasafallos tasafallos.c
$ ./tasafallos 500
Tocar 128000 páginas (500 MiB): 0,256 s (0,002 ms/pág)
$ ./tasafallos 2000
Tocar 512000 páginas (2000 MiB): 1,024 s (0,002 ms/pág)

El tiempo es proporcional al tamaño porque la RAM se entrega al tocar (paginación por demanda). Cada página cuesta ~2 µs (fallo menor). Si el sistema usara swap, el tiempo sería miles de veces mayor.

13. Probar con un simulador

Este simulador calcula el TEA con memoria virtual para distintos valores de los parámetros.

14. En Linux

$ grep pgmajfault /proc/vmstat
$ perf stat -e page-faults,major-faults ./tasafallos 500$ perf stat -e page-faults,major-faults ./tasafallos 500

• pgmajfault: número de fallos mayores del sistema.
• perf stat: cuenta los fallos por programa.
• Comparar los resultados con distintos tamaños muestra el efecto de los fallos.

15. Resumen

• Los fallos de página son caros: un fallo mayor cuesta 100.000× más que un acceso a la RAM.
• El TEA con memoria virtual incluye el costo de los fallos de página.
• Unos pocos fallos bastan para dominar el tiempo de ejecución.
• La hiperpaginación es el caso extremo: el sistema pasa todo el tiempo moviendo páginas.
• Prefetching, reutilización y memoria suficiente reducen los fallos.
• La tasa de fallos tiene un impacto casi lineal en el TEA.

16. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Calcula el TEA para p_TLB=0,98, p_RAM=0,999, t_mem=100 ns, t_pagefault=10 ms.
2. ¿Qué tasa de fallos de página hace que el TEA se duplique?
3. Modifica tasafallos.c para tocar las páginas en orden aleatorio. ¿Cómo cambia el tiempo?
4. Explica por qué la hiperpaginación es catastrófica.
5. Investiga cómo Linux detecta y mitiga la hiperpaginación.
6. Dibuja una gráfica del TEA en función de la tasa de fallos de página.
7. Compara el tiempo de un programa con y sin swap activo.
8. Calcula el TEA para p_RAM=0,99, 0,999 y 0,9999. ¿Cuánto cambia?
9. Explica por qué el prefetching es más efectivo que aumentar la RAM en algunos casos.
10. Investiga qué es el working set y cómo se relaciona con la hiperpaginación.