Tablas multinivel y tablas invertidas

1. El problema: una tabla plana no cabe

Con un espacio virtual de 2⁴⁸ bytes (256 TiB) y páginas de 4 KiB, se necesitan 2³⁶ entradas (unas 68.000 millones). Cada entrada ocupa 8 bytes, así que la tabla ocuparía 512 GiB — más que la RAM de cualquier equipo.

Además, la mayoría del espacio virtual está sin usar (huecos enormes entre código, heap y pila), por lo que la mayoría de las entradas estarían vacías. Una tabla plana desperdicia memoria masivamente.

2. Tablas multinivel

La solución es dividir la tabla en niveles: una tabla de primer nivel (directorio) cuyas entradas apuntan a tablas de segundo nivel, y así sucesivamente. Solo se crean las tablas de niveles inferiores para las regiones del espacio virtual que se usan.

Esto es como un árbol: la raíz cubre todo el espacio virtual, pero las ramas solo se crean donde hay datos. Un proceso típico usa solo unas pocas decenas de MiB, por lo que solo necesita unas pocas tablas de hoja.

Tabla multinivel es una estructura jerárquica de tablas de páginas, donde cada nivel divide el espacio virtual en bloques más pequeños, y solo se crean las entradas y tablas necesarias.

3. Los cuatro niveles de x86-64

En x86-64 (con páginas de 4 KiB), la dirección virtual de 48 bits se divide en 4 niveles de 9 bits cada uno, más 12 bits de desplazamiento:

Cada tabla ocupa 4096 bytes (512 entradas × 8 bytes). Un proceso típico usa: 1 tabla PML4, 1-2 PDPT, unas pocas PD, y decenas de PT. Total: unas decenas de KiB en lugar de 512 GiB.

Los 16 bits superiores de la dirección virtual (48-63) son de extensión de signo (canonical form): deben ser copia del bit 47.

4. Traducción con tablas multinivel

La MMU traduce la dirección en 4 pasos:

1. PML4: usa los 9 bits más altos (47-39) para indexar el PML4. La entrada da la dirección base de una tabla PDPT.
2. PDPT: usa los siguientes 9 bits (38-30) para indexar la PDPT. La entrada da la base de una tabla PD.
3. PD: usa los siguientes 9 bits (29-21). La entrada da la base de una tabla PT (o, si es página grande, el marco directamente).
4. PT: usa los siguientes 9 bits (20-12). La entrada da el marco físico.
5. Desplazamiento: los 12 bits bajos (11-0) se concatenan al marco para formar la dirección física.

Cada paso requiere un acceso a memoria (leer la tabla). Con 4 niveles, son 4 accesos antes de acceder a la RAM. La TLB (tema 24) reduce esto a 1 acceso en el caso común.

5. Tablas invertidas

La tabla invertida (inverted page table) tiene una entrada por marco físico, no por página virtual. Cada entrada guarda qué proceso y qué página virtual ocupan ese marco. El número de entradas es el número de marcos (pequeño), pero buscar una página virtual requiere recorrer toda la tabla (o usar un hash).

• Ventaja: la tabla es pequeña (proporcional a la RAM, no al espacio virtual).
• Inconveniente: la búsqueda es lenta (O(n) o hash).
• Uso: arquitecturas con espacio virtual grande y RAM relativamente pequeña (PowerPC, IA-64).

6. Tablas con hash

Para acelerar la búsqueda en tablas invertidas, se usa una tabla hash: la clave es (proceso, página virtual) y el valor es el índice en la tabla invertida. Esto da búsqueda O(1) en promedio.

• Ventaja: tabla pequeña y búsqueda rápida.
• Inconveniente: colisiones (se resuelven con listas enlazadas o sondeo).
• Uso: sistemas con muchos procesos y espacio virtual grande.

7. Ejemplo numérico

Dirección virtual de 48 bits: 0x00007F3A2C001234. Tamaño de página 4 KiB. Descomposición:

La MMU indexa cada tabla con el índice correspondiente. Si todas las entradas están presentes, el marco final se concatena con el desplazamiento 0x234 para formar la dirección física.

8. Experimento en C

El programa siguiente descompone una dirección virtual de 48 bits en sus 4 niveles:

#include <stdio.h>
#include <stdint.h>

int main(void)
{
    uint64_t v = 0x00007F3A2C001234ULL;
    uint64_t pml4 = (v >> 39) & 0x1FF;
    uint64_t pdpt = (v >> 30) & 0x1FF;
    uint64_t pd   = (v >> 21) & 0x1FF;
    uint64_t pt   = (v >> 12) & 0x1FF;
    uint64_t off  = v & 0xFFF;

    printf("virtual = 0x%016lX\\n", v);
    printf("PML4    = 0x%03lX (%lu)\\n", pml4, pml4);
    printf("PDPT    = 0x%03lX (%lu)\\n", pdpt, pdpt);
    printf("PD      = 0x%03lX (%lu)\\n", pd, pd);
    printf("PT      = 0x%03lX (%lu)\\n", pt, pt);
    printf("offset  = 0x%03lX\\n", off);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o multinivel multinivel.c
$ ./multinivel
virtual = 0x00007F3A2C001234
PML4    = 0x0FF (255)
PDPT    = 0x1D1 (465)
PD      = 0x151 (337)
PT      = 0x000 (0)
offset  = 0x234offset  = 0x234

9. Probar con un simulador

Este simulador descompone una dirección virtual de 48 bits en sus 4 niveles y muestra los índices.

10. En Linux

Linux usa tablas multinivel de 4 niveles (5 en sistemas con 5-level paging, para 57 bits de dirección virtual). Las herramientas para inspeccionar:

$ cat /proc/cpuinfo | grep -i 'address sizes'
address sizes   : 46 bits physical, 48 bits virtual

• address sizes: bits de dirección física y virtual.
• Con 5-level paging (kernel 4.14+), el espacio virtual pasa a 57 bits.
• /proc/PID/pagemap: expone la traducción (restringido).

11. Resumen

• Una tabla plana no cabe para espacios virtuales grandes (512 GiB para 256 TiB).
• Las tablas multinivel dividen la tabla en niveles, creando solo las entradas necesarias.
• x86-64 usa 4 niveles (PML4, PDPT, PD, PT), cada uno con 9 bits.
• Las tablas invertidas tienen una entrada por marco físico; las tablas con hash las aceleran.
• La traducción multinivel requiere 4 accesos a memoria (mitigado por la TLB).

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Descompón la dirección 0x0000123456789ABC en sus 4 niveles usando el simulador.
2. Calcula cuántas tablas se necesitan para un proceso que usa 10 MiB con páginas de 4 KiB.
3. Explica por qué las tablas multinivel ahorran memoria.
4. Compara las tablas multinivel con las invertidas: ¿qué ventaja tiene cada una?
5. Investiga cómo funciona el 5-level paging en Linux.
6. Implementa en C la descomposición de una dirección de 48 bits en 4 niveles.
7. Dibuja el árbol de tablas para un proceso con 3 páginas en regiones distintas.