Memoria virtual

📐 Fundamento

Idea base. Dividir la memoria virtual y la física en bloques de tamaño fijo (típicamente 4 KB), llamados páginas (virtual) y marcos (físico).

• Página virtual: unidad del espacio del proceso.
• Marco físico: unidad de la RAM.

Cada dirección virtual se compone de:

• Número de página (VPN): índice en la tabla.
• Desplazamiento (offset): dentro de la página.

Para una dirección de 32 bits con páginas de 4 KB ($2^{12}$):

| 31 ............ 12 | 11 ........ 0 |
|        VPN          |    offset    |
       20 bits          12 bits

Tabla de páginas. El kernel mantiene, por cada proceso, una tabla que mapea VPN → marco físico (PFN). Cuando el proceso accede a una dirección virtual:

1. MMU extrae el VPN.
2. Consulta la tabla → obtiene el PFN.
3. Combina PFN + offset → dirección física real.
4. Accede a RAM.

Todo esto en hardware, en cada acceso. Tu programa nunca lo "ve".

dirección virtual:    | VPN | offset |
                          ↓ traducción por MMU
dirección física:     | PFN | offset |

Tabla de páginas — entrada típica:

Si un acceso intenta escribir una página marcada read-only, page fault → el kernel toma el control y decide qué hacer (bloquear el proceso, copy-on-write, etc.).

📐 Fundamento

El problema. Una tabla plana sería enorme. En 64 bits hay $2^{52}$ páginas; una tabla con $2^{52}$ entradas no cabe en ninguna parte.

Solución: tablas multinivel. La VPN se subdivide en partes, cada una indexa un nivel.

| 47 ... 39 | 38 ... 30 | 29 ... 21 | 20 ... 12 | 11 ... 0 |
   PML4        PDPT        PD          PT          offset

x86-64 usa 4 niveles (PML4, PDPT, PD, PT). Cada nivel solo se materializa cuando se usa — un proceso pequeño tiene tablas chicas.

Costo: cada acceso requeriría 5 lecturas a memoria (4 niveles + el dato). Inaceptable. La solución: caché.

TLB (Translation Lookaside Buffer)

La TLB es una caché en hardware (dentro de la CPU) que guarda traducciones recientes VPN → PFN. Tamaños típicos: 64–4096 entradas.

Ciclo de un acceso:

1. CPU extrae VPN.
2. Consulta TLB.
   • Hit: PFN listo en 1 ciclo. Acceso continúa.
   • Miss: hay que recorrer la tabla (4 accesos a memoria), después se carga la TLB.

Hit rate típico: >99%. Eso es lo que permite que la paginación sea viable.

Cuándo la TLB se vacía:

• Cambio de proceso (otro espacio de direcciones — distinta tabla).
• Cambio explícito (al modificar la tabla).

TLB shootdown. En multinúcleo, si el SO modifica una tabla, tiene que invalidar la TLB de los otros núcleos donde el proceso pueda haber corrido. Es caro pero necesario.

Páginas grandes (huge pages, 2 MB o 1 GB en x86): cada entrada cubre más memoria, así una sola entrada de TLB sirve para más. Útil para servidores con datasets enormes (bases de datos, JVM con heaps de cientos de GB).

📐 Fundamento

Page fault: la MMU encuentra que la página accedida no está en RAM (bit "presente" = 0). Levanta una excepción y el control salta al kernel.

Tipos de page fault:

1. Minor (soft). La página está en memoria pero no mapeada en la tabla del proceso, o requiere copy-on-write. Se resuelve en microsegundos.
2. Major (hard). La página está en disco (swap) o nunca se cargó. El kernel debe traerla. Costa milisegundos — mil veces más lento que un acceso normal.
3. Inválido. Acceso a una dirección no mapeada. El kernel mata el proceso (SIGSEGV). Ese es el famoso segfault que veías en C.

Demanda paginada (demand paging). Estrategia clave: no cargar páginas hasta que se necesiten. Cuando lanzás firefox, el kernel no copia los 200 MB del binario a RAM al inicio; solo configura las tablas y deja todas las páginas marcadas "no presente". El primer acceso a cada página dispara un page fault que la trae.

Resultado: los programas arrancan rápido, ocupan poca memoria al inicio y solo lo que realmente usan se carga.

Comando para ver page faults:

$ ps -o pid,min_flt,maj_flt,cmd -p $$
  PID  MINFL  MAJFL CMD
12345  12421      8 bash

minflt = minor faults, majflt = major (los caros).

📐 Fundamento

Cuando se llena la RAM y el SO necesita más, swappea: mueve páginas inactivas al espacio de swap (un archivo o partición en disco). La RAM queda libre para lo que está en uso.

Ciclo:

1. Hay presión de memoria — se necesita un marco libre.
2. El SO elige una víctima (página a evacuar).
3. Si la página está dirty (modificada), la escribe a swap. Si está limpia (sólo lectura del binario), se descarta — se puede recuperar leyendo del binario original.
4. Marca la entrada de la tabla como "no presente".
5. Asigna ese marco al solicitante.

Después, cuando el proceso original quiera acceder, page fault → el SO trae la página de vuelta de swap → reconfigura tabla → reanuda.

Costo. Si el disco es HDD, ~10 ms por page-in. SSD: ~0.1 ms. RAM directa: ~0.0001 ms. Aún con SSD, swap es 1000× más lento que RAM. Si el sistema swappea mucho, está trasheando y la pantalla se vuelve melaza.

Ver swap en Linux:

$ free -h
              total        used        free      shared  buff/cache   available
Mem:          7.7Gi       2.4Gi       3.1Gi       320Mi       2.2Gi       4.9Gi
Swap:         2.0Gi          0B       2.0Gi

Swap: 0B used = bien, no estás swappeando. Si used crece, mirar qué proceso lo causa.

📐 Fundamento

Cuando hay que liberar un marco, ¿cuál página desalojás? La mejor decisión rebaja drásticamente el número de page faults.

Óptimo (Belady)

Desalojar la página que no se va a usar por más tiempo en el futuro. Imposible en la práctica (no sabemos el futuro), pero útil como referencia teórica.

FIFO

Desalojar la más antigua (la que llegó primero). Simple, pero ignora si se sigue usando.

Anomalía de Belady: con FIFO, más marcos NO siempre dan menos faults. Caso clásico que demuestra que FIFO está mal.

LRU (Least Recently Used)

Desalojar la menos recientemente usada. Aproxima el óptimo bajo el principio de localidad (lo que se usó recientemente, probablemente se vuelva a usar).

Problema: implementar LRU exacto requeriría actualizar timestamps en cada acceso. Imposible al ritmo de la CPU.

Aproximaciones de LRU:

• Bit de referenced. El hardware lo activa al acceder; el SO lo limpia periódicamente. Páginas con bit=0 son candidatas a desalojo.
• Algoritmo del reloj (clock). Páginas en un anillo. Un puntero las recorre. Si bit=1, lo limpia y avanza. Si bit=0, esa es la víctima.

Working set / WSClock

Toma en cuenta no solo cuándo se usó, sino qué conjunto de páginas está usando activamente cada proceso. Linux usa una variante de esto.

Comparación

Considerá la secuencia de páginas: $1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5$ con 3 marcos disponibles.

Lección: la diferencia entre algoritmos es real pero modesta. Lo que realmente baja faults es agregar más RAM.

Linux real

Linux usa una variante de two-list LRU: una lista "activa" (recientes) y una "inactiva" (víctimas candidatas). Las páginas se mueven entre listas según uso. Está combinado con kswapd, un proceso de kernel que va liberando páginas en background antes que se sature.

📐 Fundamento

Segmentación es una alternativa (o complemento) a la paginación. La memoria se divide en segmentos de tamaño variable, con significado lógico: segmento de código, de datos, de pila, de heap.

Ventaja: mapea la estructura del programa.

Desventaja: segmentos de tamaño variable causan fragmentación externa — espacios chicos entre segmentos que no sirven a nadie.

x86 (16 y 32 bits) usaba segmentación + paginación combinadas. x86-64 prácticamente eliminó segmentación: solo quedan los segmentos cs, ds, ss que casi siempre apuntan al mismo espacio plano. La paginación ganó.

Hoy "segmento" se usa más coloquialmente: el segmento de texto (código), el de datos, etc. Son regiones lógicas dentro del espacio paginado del proceso.