Jerarquía de memoria y almacenamiento

1. El dilema: rápida, grande y barata

En el tema 5 dibujamos la memoria como un único bloque, y en el tema 6 vimos que la CPU ejecuta miles de millones de instrucciones por segundo, casi todas con algún acceso a datos. Para no frenarla, la memoria ideal tendría tres propiedades:

• Rápida: que entregue cada dato en el tiempo de una instrucción.
• Grande: que quepan todos los programas y todos los datos.
• Barata: que el equipo se pueda pagar.

Esa memoria no existe. Las tecnologías disponibles obligan a elegir: las más rápidas necesitan más circuitos por cada bit, así que son caras y ocupan mucho espacio; las más baratas y densas son lentas. Además, las rápidas pierden su contenido al quedarse sin energía.

La solución no es elegir una, sino combinarlas: poca memoria muy rápida, bastante memoria de velocidad media y muchísimo almacenamiento lento, organizados de modo que lo que más se usa esté en la parte rápida.

2. La jerarquía

El resultado se conoce como jerarquía de memoria. Cada nivel es más lento, más grande y más barato por byte que el que tiene encima:

La tabla siguiente pone cifras a la pirámide. Son órdenes de magnitud de un equipo personal actual; los valores exactos cambian con cada modelo.

Las unidades de la columna central esconden la magnitud del salto: un nanosegundo (ns) es la milmillonésima parte de un segundo; un microsegundo (µs) son mil nanosegundos; un milisegundo (ms), un millón. Entre el primer nivel y el último hay siete órdenes de magnitud.

3. Las distancias, a escala humana

Cifras como «100 nanosegundos» no dicen nada a la intuición. Para apreciarlas, estiremos el tiempo de manera que un acceso a la caché L1, de un nanosegundo, dure un segundo. Todo lo demás se estira en la misma proporción:

Visto así, se entiende por qué los sistemas operativos están diseñados alrededor de la entrada y salida. Si pedir un dato al disco equivale a esperar meses, la CPU no puede quedarse mirando: tiene que ocuparse de otra cosa mientras tanto. Y evitar un solo acceso al disco, aunque cueste miles de instrucciones, es siempre un buen negocio. Las dos ideas —la multiprogramación y las cachés— nacen de esta tabla.

4. El principio de localidad

Tener poca memoria rápida solo sirve si lo que el programa necesita está en ella casi siempre. Que eso ocurra no es suerte, sino una regularidad observada en prácticamente todos los programas:

El principio de localidad dice que, durante un intervalo corto, un programa usa una porción pequeña de sus instrucciones y de sus datos, y que esa porción cambia lentamente.

Tiene dos formas:

• Localidad temporal: lo que se usó hace un momento se volverá a usar pronto. Las instrucciones de un bucle se ejecutan una y otra vez; un contador se lee y se modifica en cada vuelta.
• Localidad espacial: si se usó una dirección, pronto se usarán las vecinas. Las instrucciones se ejecutan una detrás de otra; los elementos de un arreglo se recorren en orden; los campos de una estructura están juntos.

La localidad es la razón de ser de toda caché, palabra que designa una idea general y no un componente concreto: guardar en un lugar rápido una copia de los datos de un lugar lento que se usaron recientemente, con la expectativa de volver a necesitarlos. Cuando el dato buscado está en la caché se habla de acierto (hit); cuando no está y hay que ir al nivel lento, de fallo (miss).

Encontraremos esta misma idea en todos los niveles: en el procesador, en el kernel, en la biblioteca de C, en los navegadores y en los servidores. Cambia el tamaño; el principio es el mismo.

5. La caché de la CPU

Entre los registros y la RAM, los procesadores tienen una memoria intermedia muy rápida integrada en el mismo chip. Guarda copias de las zonas de RAM usadas recientemente. Funciona así:

1. Cuando la CPU necesita el contenido de una dirección, busca primero en la caché.
2. Si está (acierto), lo obtiene en uno o pocos nanosegundos.
3. Si no está (fallo), lo trae de la RAM, lo que tarda del orden de cien veces más, y lo guarda en la caché desplazando algo más antiguo.

Hay un detalle decisivo en el paso 3: la caché no trae un byte, sino un bloque completo de bytes contiguos, llamado línea de caché, normalmente de 64 bytes. Es una apuesta por la localidad espacial: si el programa pidió una dirección, probablemente pida enseguida las siguientes, y ya estarán allí.

La caché se organiza a su vez en niveles: L1, pequeña y rapidísima, propia de cada núcleo y dividida en una parte para instrucciones y otra para datos; L2, mayor y algo más lenta; y L3, mucho mayor, compartida por todos los núcleos. Linux muestra su tamaño:

$ lscpu | grep -i cache
L1d cache:                128 KiB (4 instances)
L1i cache:                128 KiB (4 instances)
L2 cache:                 1 MiB (4 instances)
L3 cache:                 6 MiB (1 instance)

$ getconf LEVEL1_DCACHE_LINESIZE # tamaño de la línea de caché, en bytes
64

La salida se lee así: hay cuatro cachés L1 de datos (L1d) y cuatro de instrucciones (L1i), una por núcleo, de 32 KiB cada una; cuatro cachés L2 de 256 KiB; y una única L3 de 6 MiB para todo el procesador.

6. La caché en un experimento

El siguiente programa suma todos los elementos de una matriz de 4096 × 4096 enteros dos veces: la primera recorriéndola por filas y la segunda por columnas. Las dos sumas hacen exactamente las mismas operaciones sobre los mismos datos; solo cambia el orden.

#include <stdio.h>
#include <time.h>

#define N 4096

static int matriz[N][N];                 /* 64 MiB */

static double segundos(void)
{
    struct timespec t;

    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}

int main(void)
{
    long suma = 0;
    double inicio;

    for (int i = 0; i < N; i++)          /* cargar valores */
        for (int j = 0; j < N; j++)
            matriz[i][j] = 1;

    inicio = segundos();
    for (int i = 0; i < N; i++)          /* recorrido por filas */
        for (int j = 0; j < N; j++)
            suma += matriz[i][j];
    printf("Por filas:    %.3f s  (suma %ld)\n", segundos() - inicio, suma);

    suma = 0;
    inicio = segundos();
    for (int j = 0; j < N; j++)          /* recorrido por columnas */
        for (int i = 0; i < N; i++)
            suma += matriz[i][j];
    printf("Por columnas: %.3f s  (suma %ld)\n", segundos() - inicio, suma);

    return 0;
}

$ gcc -Wall -Wextra -g matriz.c -o matriz
$ ./matriz
Por filas:    0.041 s  (suma 16777216)
Por columnas: 0.287 s  (suma 16777216)

El resultado es el mismo y el tiempo no: el recorrido por columnas tarda varias veces más. La proporción exacta depende del procesador, pero la diferencia aparece siempre. La explicación está en cómo guarda C una matriz y en la línea de caché:

• C almacena las matrices fila por fila: en memoria, matriz[0][0] está junto a matriz[0][1], y al final de la fila 0 empieza la fila 1.
• Por filas, el programa avanza por direcciones consecutivas. Cada línea de caché de 64 bytes contiene 16 enteros, así que, de cada 16 accesos, uno falla y los 15 siguientes aciertan. Además, el procesador detecta el patrón y va trayendo las líneas siguientes por adelantado.
• Por columnas, cada acceso está 4096 enteros más allá que el anterior, es decir, a 16 KiB de distancia. Cada uno cae en una línea de caché distinta, y cuando el programa vuelve a pasar cerca, esa línea ya fue desplazada. Casi todos los accesos fallan y hay que ir a la RAM.

El primer recorrido tiene buena localidad espacial; el segundo, ninguna. Es la tabla de la sección 3 convertida en una medición.

7. Discos rígidos y de estado sólido

Por debajo de la RAM están los dispositivos de almacenamiento, que conservan los datos sin energía. Hay dos tecnologías, con comportamientos muy distintos:

Pese a sus diferencias, ambos se presentan ante el sistema operativo de la misma forma: como una larga secuencia de bloques numerados de tamaño fijo, normalmente 512 o 4096 bytes. Solo se puede leer o escribir un bloque entero. Todo lo demás —archivos, directorios, nombres— lo construye el sistema operativo encima.

$ lsblk -d -o NAME,ROTA,SIZE,MODEL
NAME    ROTA   SIZE MODEL
nvme0n1    0 476,9G SAMSUNG MZVLB512HAJQ-000L7
sda        1   1,8T WDC WD20EZRZ-00Z5HB0

La columna ROTA indica si el dispositivo es giratorio: 1 para un disco rígido, 0 para un SSD. El kernel usa ese dato para decidir cómo ordenar los pedidos que envía a cada uno. En una máquina virtual o en WSL verás discos virtuales.

8. La caché de disco del kernel

Entre la RAM y el disco hay un salto de mil a cien mil veces, mucho mayor que entre la caché de la CPU y la RAM. Aplicar aquí la idea de caché rinde todavía más, y en este nivel quien la aplica es el sistema operativo.

El kernel de Linux mantiene en memoria RAM una copia de los bloques de disco leídos o escritos recientemente. Se la llama caché de páginas (page cache) o caché de disco. Cuando un programa pide leer un archivo, el kernel mira primero ahí; solo si los datos no están los pide al dispositivo. El programa no hace nada especial: sigue llamando a read.

El efecto se mide con facilidad. Creamos un archivo de 512 MiB, le pedimos al kernel que vacíe su caché y lo leemos dos veces seguidas:

$ dd if=/dev/urandom of=grande.bin bs=1M count=512 status=none

$ sync                                          # asegurar que todo esté en disco
$ echo 3 | sudo tee /proc/sys/vm/drop_caches    # vaciar la caché de disco
3

$ time cat grande.bin > /dev/null               # primera lectura: desde el disco
real	0m0.612s
user	0m0.004s
sys	0m0.170s

$ time cat grande.bin > /dev/null               # segunda lectura: desde la RAM
real	0m0.085s
user	0m0.001s
sys	0m0.084s

$ rm grande.bin

El mismo comando, sobre el mismo archivo, tarda varias veces menos la segunda vez, porque los datos ya no vienen del dispositivo. Con un disco rígido la diferencia sería de decenas de veces. Vaciar la caché es inofensivo: el sistema solo queda momentáneamente más lento, hasta que vuelve a llenarla.

La caché de disco explica una duda muy frecuente al mirar la memoria de un sistema Linux:

$ free -h
               total        used        free      shared  buff/cache   available
Mem:            15Gi       4.2Gi       1.1Gi       412Mi        10Gi        10Gi
Swap:          2.0Gi          0B       2.0Gi

La columna free muestra poca memoria libre, y sin embargo el sistema no tiene ningún problema. La memoria que ningún programa necesita no se deja vacía: el kernel la usa como caché de disco, y aparece en buff/cache. Si un programa pide memoria, el kernel descarta parte de esa caché al instante y se la entrega. Por eso la cifra que importa es available, la memoria realmente disponible para programas nuevos. La memoria sin usar es memoria desperdiciada.

9. Volátil y persistente

La línea punteada de la pirámide separa dos mundos. Por encima, todo se pierde al cortarse la energía; por debajo, se conserva. Esa frontera tiene una consecuencia práctica que el sistema operativo debe gestionar con cuidado.

Para ganar velocidad, la caché de disco también interviene en las escrituras. Cuando un programa escribe en un archivo, el kernel copia los datos a su caché en RAM y devuelve el control enseguida; la escritura real en el dispositivo se hace más tarde, agrupada con otras. Durante ese intervalo, que puede durar varios segundos, los datos «guardados» existen únicamente en memoria volátil.

$ grep -E '^(Dirty|Writeback):' /proc/meminfo
Dirty:              1284 kB
Writeback:             0 kB

Dirty es la cantidad de datos modificados en memoria que todavía no llegaron al disco. Si se corta la energía en ese momento, se pierden. De aquí salen varias prácticas que quizá conozcas sin saber su motivo:

• Por eso hay que apagar el sistema ordenadamente y expulsar una memoria USB antes de retirarla: en ambos casos se espera a que las escrituras pendientes terminen.
• El comando sync pide al kernel que escriba ahora todo lo pendiente.
• Un programa que no puede permitirse perder datos, como una base de datos, usa la llamada al sistema fsync para exigir que un archivo concreto quede escrito antes de continuar. Paga ese tiempo a cambio de la garantía.

Es un ejemplo claro del equilibrio entre rendimiento y seguridad que vimos en el tema 2, y uno de los problemas centrales del curso sobre sistemas de archivos.

10. El camino inverso: el intercambio

La caché de disco usa la RAM para acelerar el disco. El sistema operativo también hace lo contrario: usa el disco para ampliar la RAM.

Cuando la memoria se agota, el kernel puede tomar zonas de memoria que algún programa no usa desde hace tiempo, copiarlas a un área reservada del disco y reutilizar esa RAM para otra cosa. Si el programa vuelve a necesitar esos datos, el kernel los trae de vuelta. Esa técnica es el intercambio (swap), y el área de disco que utiliza aparece en la segunda línea de free.

$ swapon --show
NAME      TYPE SIZE USED PRIO
/swap.img file   2G   0B   -2

El intercambio permite ejecutar más programas de los que caben en la memoria física, y de nuevo se apoya en la localidad: en un momento dado, cada programa usa solo una parte de su memoria. Pero tiene un precio evidente a la luz de la tabla de la sección 3. Cada dato que hay que recuperar del disco cuesta miles de veces más que uno que está en RAM. Si el sistema tiene tan poca memoria que debe intercambiar continuamente, pasa más tiempo moviendo datos que ejecutando programas, una situación llamada hiperpaginación (thrashing), y todo se vuelve desesperadamente lento.

El mecanismo que hace posible el intercambio es la memoria virtual, que presentamos en el tema 27.

11. Quién gestiona cada nivel

Cada frontera de la jerarquía tiene un responsable distinto, y conviene saber cuál es para entender dónde interviene el sistema operativo y dónde no:

La columna de la derecha resume el mérito del diseño. Un programa trabaja con dos ideas sencillas —variables en memoria y archivos en disco— y toda la maquinaria que hace que eso funcione con rapidez queda oculta. Es otra de las abstracciones del tema 2.

12. Consecuencias para quien programa

Que la jerarquía sea invisible no significa que dé igual cómo se escriba el código. Algunas reglas prácticas se desprenden directamente de este tema:

• Recorre los datos en el orden en que están en memoria. Es la lección de matriz.c. Los arreglos contiguos suelen ser más rápidos que las estructuras con elementos dispersos, aunque sobre el papel hagan las mismas operaciones.
• Lee y escribe archivos en bloques grandes. Pedir los datos de a un byte multiplica las llamadas al sistema. El programa copiar.c del tema 2 usaba un bloque de 4096 bytes por esa razón.
• La segunda vez siempre es más rápida. Al medir el rendimiento de un programa que usa archivos, ten presente si los datos ya están en la caché de disco. Comparar una primera ejecución con una segunda lleva a conclusiones equivocadas.
• «Escrito» no significa «a salvo». Si tu programa no puede perder datos ante un corte de energía, debe pedirlo explícitamente con fsync.
• Mira available, no free. Un sistema Linux sano tiene casi toda su memoria ocupada.

La propia biblioteca de C aplica la misma idea. printf no hace una llamada al sistema por cada carácter: acumula el texto en una zona de memoria y lo envía de una vez. Es una caché más, situada un nivel por encima, cuyo objetivo es evitar una operación costosa: el cruce al kernel. La estudiamos en el tema 15.

13. Resumen

• No existe una memoria rápida, grande y barata a la vez, así que las computadoras combinan varias en una jerarquía.
• De arriba abajo: registros, caché de la CPU, RAM, SSD y disco rígido. Cada nivel es más lento, más grande y más barato que el anterior.
• Entre los extremos hay siete órdenes de magnitud: si la caché L1 tardara un segundo, un disco rígido tardaría meses.
• La jerarquía funciona gracias al principio de localidad: los programas usan, en cada momento, una porción pequeña de sus instrucciones y datos.
• Una caché guarda en un nivel rápido copias de datos de un nivel lento. La de la CPU la gestiona el procesador y trabaja con líneas de 64 bytes.
• El orden en que un programa recorre sus datos puede cambiar varias veces su velocidad.
• El kernel usa la RAM libre como caché de disco, y el disco como extensión de la RAM mediante el intercambio.
• Los niveles superiores son volátiles. Los datos escritos en un archivo pueden estar durante segundos solo en memoria.

14. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta matriz.c en tu equipo y calcula cuántas veces más lento es el recorrido por columnas. Luego cambia N a 512 y repite: ¿por qué la diferencia casi desaparece? Compara el tamaño de la matriz con el de tus cachés.
2. Compila matriz.c con gcc -O2 y vuelve a medir. ¿Cambian los tiempos? ¿Cambia la proporción?
3. Repite el experimento de la sección 8 mirando free -h antes de la primera lectura y después de la segunda. ¿En cuánto aumentó buff/cache?
4. Ejecuta grep -E '^(Dirty|Writeback):' /proc/meminfo, luego crea un archivo grande con dd y repite el grep enseguida. Ejecuta sync y míralo otra vez.
5. Con lscpu, anota los tamaños de tus cachés L1d, L2 y L3 por núcleo. ¿Cuántos enteros de 4 bytes caben en la L1 de datos?