Paginación

#

Mientras que la segmentación consistía en dividir la memoria física en partes de tamaño variable, la paginación la divide en partes del mismo tamaño.

Este método es más flexible y soluciona varios de los problemas que tenían los anteriores. Cuando un proceso necesita cierta cantidad de memoria y se la pide al sistema, este simplemente busca los primeros huecos que encuentre vacíos, y le da tantos como necesite. Para esto, el SO puede por ejemplo llevar una free list de todas las páginas vacías.

A cada página virtual utilizada (parte izquierda en la imagen) le corresponde su página física (parte derecha). En este caso las páginas virtuales 0, 4, 14 y 15 están ubicadas en las físicas de índice 10, 23, 28 y 4, respectivamente.

Tablas de paginación

#

Para acordarse de a qué página física le corresponde cada página virtual, el sistema lleva una tabla de paginación por proceso, que sirve para guardar traducciones entre páginas físicas y virtuales.

Para hacer la traducción de página virtual a física es necesario definir un VPN (Virtual Page Number) y un Offset en el espacio de direcciones del proceso. Supongamos un espacio de direcciones de 16kB como el de la imagen de arriba. Para definir una dirección específica en ese espacio de direcciones son necesarios 14 bits (\(2^{14} = 16\text{kB}\)). De esos 14 bits, si las páginas son de 1kB, vamos a necesitar 10 bits para definir un byte específico de una página cualquiera (\(2^{10} = 1\text{kB}\)), y los 4 bits restantes van a ser nuestra VPN, y van a representar la página de entre todas las del espacio de direcciones a la que queremos acceder.

Como al SO solo le importa traducir entre nuestra página virtual y la física en memoria, lo único que va a hacer en cada acceso a memoria va a ser tomar la VPN (la página a la que acceder), convertirla a un PFN (Physical Frame Number) (la página física), y hacer el acceso al byte ubicado en la posición del offset en el PFN correspondiente. De forma simplificada este sería el proceso:

Esa Address Translation que se indica en la imagen es (de momento) simplemente una consulta a la tabla de paginación.

Qué hay en una tabla de paginación?

#

En sí, una tabla de paginación no es más que una estructura de datos en memoria que guarda las asociaciones de VPN a PFN. La forma más simple de esta estructura de datos es una tabla de paginación lineal, que consiste simplemente en un array en el que cada índice corresponde a cada VPN, y cada elemento dentro de cada índice del array corresponde a la PFN. Un posible pseudocódigo básico sería así:

1
2
3
4

// Dado un VPN, devuelve el PFN correspondiente.
int consultarPFN(int VPN){
    return tablaPaginacion[VPN];
}

Además de las asociaciones VPN-PFN, por cada página específica también puede haber otros datos adicionales guardados, como bits de control que indiquen si la página es válida, está reservada, ha sido modificada, etc.

Problema: Tamaño

#

Uno de los problemas con la paginación es el tamaño de las tablas de paginación cuando son lineales, como estamos asumiendo de momento. Por poner un ejemplo, si asumimos un sistema actual de 64 bits, con direcciones virtuales de 64 bits también, y un tamaño de páginas de 4KiB ( \(2^{12}\) bytes, el que suele usarse hoy en día):

• El espacio de direcciones es de \(2^{64}\) bytes.
• Cada página ocupa 4KiB: \(2^{12}\) bytes.
• En total, el número de entradas en la tabla: \(\frac{2^{64}}{2^{12}}=2^{52}\text{ entradas.}\)

Suponiendo que cada entrada en la tabla ocupa 8 bits (también el valor estándar en 64bit), la tabla ocuparía \(8\text{ bit }\cdot\space 2^{52} = 2^{55}\text{ bytes.}\) Esto equivale a más de 36000 Terabytes únicamente para la tabla de paginación.

Por este motivo más adelante habrá que encontrar una forma de hacer más pequeñas las tablas de paginación.

Problema: (No) Velocidad

#

Otro de los principales problemas de la paginación es lo capaz que es de ralentizar el sistema. Supongamos una instrucción simple de ensamblador x86_64 como:

1

mov eax, [21]   ; Carga en el registro eax lo que hay en la dirección de memoria 21.

El sistema, para que pueda ejecutarse esta instrucción, tiene que:

• Sacar el VPN de la dirección 21, esto puede hacerse rápido.
• Consultar en memoria el PFN correspondiente al VPN (otro acceso a memoria).
• Quitar el VPN de la dirección efectiva y concatenar el PFN.
• Acceder a la dirección efectiva y meter el dato en eax.

Esto significa que para cada acceso a memoria (incluido cada fetch individual a instrucciones) tenemos que hacer necesariamente otro acceso extra a memoria, esto hace que cada instrucción sea mucho más lenta.

Translation-Lookaside Buffer (TLB)

#

Con el objetivo de hacer que la paginación sea más rápida (y viable), evitando la consulta extra a memoria, se va a necesitar una ayuda del hardware que recibe el nombre (por motivos históricos) de Translation-Lookaside Buffer o TLB, y es una parte de la MMU. Este TLB en sí no es más que una memoria caché de las traducciones de memoria (VPN -> PFN) más usadas.

Cuando un proceso solicita acceder a una dirección de memoria, el sistema comprueba primero el TLB para ver si la traducción está ahí guardada. Si lo está (TLB Hit), se evita la consulta extra a memoria, pero si no está ahí (TLB Miss), entonces se accede a la tabla de paginación (acceso a memoria extra), se guarda la traducción en el TLB, y finalmente el hardware repite la búsqueda de la traducción, que esta vez sí estará en el TLB.

Quién gestiona un TLB Miss?

#

Cuando se da la situación en la que una traducción específica no está en el TLB, hay que determinar si es el hardware o el software (SO) el que se encarga de ir a la tabla de paginación, copiar la traducción, y ponerla en el TLB. En entornos en los que se busca velocidad, lo preferible será el hardware, aunque realmente el quién lo gestiona depende completamente de la arquitectura del procesador, y el SO no tiene más remedio que adaptarse a lo que exponga la CPU.

Si el hardware ofrece una forma automática de recorrer las tablas de páginas, sería un desperdicio de rendimiento que el SO lo hiciera por software. De todas formas, aquí se comparan ambos casos.

Gestión por Hardware

#

Para que el hardware pueda gestionar un TLB Miss, hay que tener en cuenta una cosa, y es que la CPU (específicamente la MMU) tiene que poder entender la estructura de las tablas de paginación, y el SO debe limitarse a:

• Decirle dónde está en memoria la dirección base de la tabla de paginación.
• Seguir la estructura de datos estricta para la tabla de paginación que la CPU entiende.

Cuando hay un TLB Miss, la MMU toma el control de forma transparente, lee la dirección base de la tabla desde un registro del sistema, recorre la tabla en busca de la traducción, actualiza el TLB y reanuda la instrucción. Esto es mucho más rápido que hacerlo por software, con la única desventaja de que el SO está obligado a organizar sus tablas de paginación exactamente en el formato que el hardware exige.

Algunas arquitecturas que tienen gestión de TLB Miss por hardware y los registros en los que esperan la dirección base de la tabla de paginación: x86_64 (Registro CR3), ARM Modernos (Registros TTBR0_EL1/TTBR1_EL1), RISC-V Modernos (Registro satp).

Gestión por Software

#

Cuando hay un TLB Miss, la CPU simplemente lanza un hardware interrupt. El SO detiene el proceso, salta a un handler de excepciones en el kernel, busca la traducción en su tabla de paginación (que puede tener la forma que quiera el SO) y mete la entrada manualmente en el TLB.

Esto da mucha más flexibilidad al SO, pero también es mucho más lento porque implica gestionar una interrupción con cada TLB Miss.

Algunas arquitecturas que normalmente tienen gestión de TLB Miss por software: Tensilica Xtensa (Usada en ESP32), aunque es muy modificable. Cuando hay un TLB Miss, se genera un interrupt ITLB/DTLB Miss. El SO (FreeRTOS u otros) busca en la tabla y escribe en el TLB usando la instrucción wlb. Otra arquitectura de este tipo es MIPS.

Entradas y contenido.

#

De forma similar a las entradas de la tabla de paginación, una entrada del TLB está formada por un VPN, su correspondiente PFN, y varios bits de control. Entre ellos puede haber bits de protección (rwx), valid bits (que indiquen si la traducción es válida), dirty bits, ASID, etc. Más adelante se hablará de los ASID.

Respecto a las entradas, un TLB normal suele tener entre 16 y 128 entradas. El motivo por el cual son tan pocas es que el TLB es totalmente asociativo, esto significa que, cuando el procesador necesita traducir un VPN, el hardware compara ese VPN con todas las entradas del TLB al mismo tiempo (en paralelo), a través de un hardware llamado CAM (Content Addressable Memory)

El problema es que comparar una dirección específica con todas las entradas del TLB simultáneamente requiere circuitos muy complejos y consume mucha energía. Es por esto que los TLBs son tan pequeños

Problema: Context Switches

#

Al añadir los TLBs surge un problema nuevo. Cuando se hace un context switch entre un proceso y otro, las entradas del TLB del proceso anterior ya no sirven para el proceso en ejecución. Por esto mismo hay que tener cuidado de no usar una entrada del TLB de otro proceso en el que tenemos ahora.

• Una de las soluciones propuestas a esto es simplemente vaciar del todo el TLB con cada cambio de contexto, aunque esto es bastante ineficiente si los cambios de contexto se hacen muy a menudo.
• Otra solución más útil (y la usada en arquitecturas como MIPS) es mantener un ASID (Address Space Identifier) en cada entrada del TLB, que sirva para identificar a qué proceso pertenece una entrada específica del TLB. Puede darse el caso en el que dos entradas con diferente ASID mapeen al mismo PFN, por ejemplo cuando se comparte memoria entre dos procesos.

Solución: Tamaño de Tablas

#

Multi-Level Page Tables

#

El TLB solucionaba el problema de la velocidad con la paginación, ahora queda resolver el problema del tamaño. Una tabla de paginación puede hacerse muy grande cuando crece el espacio de direcciones, y además puede estar llena de entradas vacías entre las que realmente sirven.

Tras varias soluciones propuestas que no llegan a solucionar el problema (como hacer las páginas más grandes, que reintroduce la fragmentación interna), aparece el modelo de las Tablas de Paginación Multinivel. Este modelo es el que usan prácticamente todos los SO de propósito general hoy día (Windows 10/11, Linux, macOS)

Las Tablas de Paginación Multinivel funcionan convirtiendo las tablas de paginación lineales, como las habíamos asumido hasta ahora, en un modelo de árbol de directorios. El proceso es algo así:

• Se divide la tabla de paginación lineal en bloques del tamaño de una página (p.ej, 4kB). Es decir, se mete la tabla de paginación en páginas.
• Si una página de esas, que contiene un bloque de la tabla de paginación, solo contiene traducciones inválidas (ninguna traducción sirve), no se asigna memoria a esa página específica.
• Para saber cuáles de esas páginas están activas (se les ha asignado memoria) y cuales no, se mantiene una “metatabla de paginación”, o una tabla de paginación de un nivel superior, denominada Directorio de Páginas.
• Esto puede repetirse de nuevo con esta “metatabla” y crear una “meta-metatabla”. Así varias veces.
  • Los sistemas operativos actuales como Linux o Windows tienen tablas de paginación de 4 o 5 niveles.

Cada una de las tablas de nivel superior tiene un nombre, y se ordenan en función de a cuál se accede primero:

• Nivel 1: Page-Map Level 4 (PML4)
• Nivel 2: Page-Directory Pointer Table (PDPT)
• Nivel 3: Directorio de páginas.
• Nivel 4: Tabla de paginación. En sí, la que habíamos visto hasta ahora.

En la imagen se representa una tabla de 3 niveles. Los rectángulos vacíos de cada nivel son bloques de memoria no asignados. Esa es la gracia de las tablas de paginación multinivel, que por cada nivel añadido se ahorra memoria no utilizada en bloque.

Aunque un nivel adicional implica un salto extra en memoria cuando hay un TLB Miss, lo que hace que esto sea viable es el TLB que hemos visto antes.

Tablas de Paginación Invertidas

#

Otro modelo que permite ahorrar mucha más memoria es el de las tablas de paginación invertidas.

En las MLPT teníamos un árbol de tablas por cada proceso en el sistema, aquí tenemos una única tabla para todo el sistema, y funciona así:

• El sistema tiene una cantidad de RAM fija, y como el tamaño de las páginas es fijo, el número de marcos físicos (PFN’s) también lo es.
• Se mantiene un array con tantos elementos como marcos físicos hay en el sistema. Si un sistema tiene 32GB de RAM y páginas de 4kB, habrá exactamente 8.388.608 (32GB/4KB) PFNs y por tanto 8.388.608 entradas en la tabla, sin importar el número de procesos en ejecución.
• Cada entrada en la tabla se asocia con un PFN en función del índice. tabla[0] tiene los datos del PFN 0, tabla[1] los del PFN 1, y así en adelante.
• En cada entrada en la tabla se guarda el VPN correspondiente al PFN dado por el índice, y el PID/ASID del proceso al que pertenece esa traducción.

Este modelo ahorra memoria manteniendo un número fijo de entradas en la tabla. Para las 8 millones de entradas mencionadas en el caso de arriba, el sistema gastará en total (asumiendo que cada entrada son 8 bytes) únicamente \(8\text{ millones } *\space 8 \text{ byte } = \space 64\text{ MB }\) fijos.

El problema de este modelo es la velocidad, dado que al buscar una traducción no partimos del PFN, sino del VPN. En las MLPT cada nivel servía como índice para buscar el siguiente elemento, era algo lineal. Aquí tenemos una tabla indexada por PFNs, pero en cada búsqueda partimos de un VPN, no de un PFN, así que de primeras tendríamos que hacer una búsqueda lineal mucho más lenta. Para evitar esto, lo que suele hacerse es usar una tabla de hashes.

Normalmente este modelo suele usarse en sistemas en los que no importa tanto perder un poco de velocidad en caso de un TLB Miss a cambio de poder tener un ahorro extremo en uso de memoria.