Memoria virtual en serio: lo que cuesta de verdad un fallo de pagina

El primer grado fijo la forma: la direccion que ve el programa es virtual, la MMU la traduce por una tabla de paginas y una pagina que no esta en RAM provoca un fallo que la trae del disco. Eso era el mapa. Ahora recorremos la ruta, porque en los detalles vive y muere el rendimiento.

Lo primero que oculta el mapa es que la MMU no puede permitirse leer la tabla de paginas en cada acceso. Una tabla de cuatro niveles significa cuatro lecturas dependientes de RAM antes de tocar siquiera los datos, asi que cada acceso seria cinco veces mas lento. Por eso el procesador guarda una cache pequena de traducciones recientes: la TLB, tipicamente de 64 a 1536 entradas, totalmente asociativa, pegada a la tuberia. Un acierto cuesta un ciclo. Por eso un programa que toca 100 MB con buena localidad corre casi a plena velocidad aunque la tabla de paginas sea enorme: solo usa unos pocos miles de paginas distintas a la vez.

Cuando la TLB falla y la pagina no esta en memoria, toda la tuberia se detiene. El hardware recorre la tabla de paginas, ve el bit de presencia a cero y lanza un fallo. La instruccion se abandona a mitad de camino, se ejecuta el manejador, el kernel encuentra o libera un marco, lee 4 KiB del dispositivo, actualiza la tabla de paginas, instala una entrada en la TLB y vuelve para reintentar la instruccion, que ahora si funciona. El hardware hace la parte facil en nanosegundos; el software hace la parte cara en microsegundos.

TLB hit: 1 cycle
walk: 3 or 4 reads
RAM: 30 ns
SSD: 0.1 ms
HDD: 8 ms

fault rate: 1/1000
0.001 x 0.1 ms = 100 ns
30 ns -> 130 ns per accessLa escalera de costes. El SSD es lo bastante rapido para que una tasa baja de fallos sea soportable; el disco giratorio no lo es.

Cuando hace falta un marco y la memoria esta llena, algo hay que expulsar. La mejor eleccion posible, si pudieras ver el futuro, es la pagina que se usara mas tarde: la politica optima de Belady. No es implementable, pero es la regla de medir. La mejor aproximacion practica es LRU - expulsar la pagina sin usar durante mas tiempo -, y aqui esta la trampa que importa: el LRU exacto tampoco es implementable. Exige una marca de tiempo en cada acceso, es decir escribir en memoria en cada lectura, justo lo que la TLB existe para evitar. Por eso los kernels reales lo aproximan, y la aproximacion que usan es el algoritmo del reloj.

El algoritmo del reloj mantiene los marcos en una lista circular, cada uno con un bit de referencia. El hardware pone ese bit en cada acceso, y puede hacerlo gratis. Cuando hace falta un marco, la aguja avanza: si el bit esta puesto, la pagina se ha usado hace poco, asi que borra el bit y dale una segunda oportunidad; si el bit esta a cero, ha dado una vuelta entera sin que nadie la toque, asi que expulsala. La segunda oportunidad es lo ingenioso: separa las paginas tocadas una vez en una rafaga de las que de verdad pertenecen al conjunto de trabajo, a cambio de un bit y una pasada de la aguja.

for (;;) {
  frame = frames[hand];
  if (frame.ref_bit == 1) {
    frame.ref_bit = 0;
    hand = (hand + 1) % nframes;
  } else {
    evict(frame);
    break;
  }
}El algoritmo del reloj completo. La aguja recorre el circulo y da a cada pagina usada hace poco exactamente una oportunidad mas.

Ahora la propiedad que hace interesantes las politicas de reemplazo. Un algoritmo de pila es aquel en el que el conjunto de paginas residentes en N marcos siempre es un subconjunto del residente en N+1 marcos. LRU es de pila, asi que darle mas memoria nunca puede causar mas fallos. FIFO no lo es, y el reloj tampoco, y la consecuencia es la anomalia de Belady: existen secuencias de accesos en las que cuatro marcos producen mas fallos que tres. No es una curiosidad rara, es el sintoma directo de una politica que decide sin una nocion global de recencia, y por eso los kernels de produccion se preocupan por seguir la edad al estilo LRU en lugar de un simple turno circular.

reference string   1 2 3 4 1 2 5 1 2 3 4 5

3 frames           9 faults
4 frames          10 faults

FIFO    more frames -> more faults
CLOCK   more frames -> more faults
LRU     more frames -> never worse
OPT     more frames -> never worseLa cadena de referencias clasica. Bastan los cinco primeros fallos para que cuatro marcos sean peores que tres.

El conjunto de trabajo de un proceso es el conjunto de paginas que usa activamente en una ventana de tiempo. Si cabe en la memoria que se le ha dado, la tasa de fallos es baja y apenas importa. Si no cabe, el proceso tiene un problema: cada pagina que expulsa es una que volvera a necesitar pronto, asi que el siguiente acceso falla, y ese fallo expulsa otra pagina que necesitara, y asi sucesivamente.

working set: 20 MiB
5 threads: 100 MiB
RAM: 64 MiB

resident set: 12 MiB
fault -> evict -> fault -> evictUn caso concreto: cinco hilos de 20 MiB cada uno en un contenedor limitado a 64 MiB de RAM.

Esto es el thrashing, y explica el sintoma que todo el mundo ha visto y pocos saben nombrar. La maquina parece totalmente congelada: el raton se atasca, nada responde, la luz del disco esta fija. Miras el uso del procesador y no esta nada ocupado. La razon es que un proceso que falla esta bloqueado, no ejecutandose. Se queda en la cola de espera mientras trabaja el dispositivo, asi que la CPU esta ociosa, y entonces el planificador ejecuta otro proceso, que falla de inmediato en sus propias paginas, expulsa paginas del primero y tambien se bloquea. El procesador esta ocioso porque todos los hilos ejecutables esperan una lectura de 4 KiB, y el sistema va lento no porque calcule demasiado, sino porque casi no calcula nada entre dos operaciones de disco. Anadir mas procesos lo empeora, al contrario de la intuicion de que mas trabajo mantiene ocupada a la CPU.

Dos notas de hardware que cambian los numeros. Primera, paginas gigantes transparentes: el kernel puede respaldar partes de la memoria con paginas de 2 MiB en lugar de 4 KiB, lo que reduce 512 veces el numero de entradas de TLB necesarias. Para una base de datos que recorre una tabla puede ser una gran ganancia. Segunda, y en la otra direccion, puede ser una perdida: una pagina de 2 MiB debe escribirse entera, asi que un programa que ensucia 4 KiB de una pagina gigante paga 2 MiB de entrada y salida. Por eso el kernel tiene los modos always y madvise, y por eso el valor por defecto ha oscilado entre versiones.