Sistemas Operativos

16. Paginación

Tiempo de lectura: 26 minutos

La traducción entre direcciones virtuales y físicas puede realizarse de diversas maneras. La forma más extendida es la paginación, que no es sino un esquema de gestión de la memoria que permite que el espacio de direcciones físico de un proceso no sea continuo, evitando el problema de la fragmentación externa.

16.1. Método básico

En la paginación la memoria física se divide en bloques de tamaño fijo denominados marcos, mientras que el espacio de direcciones virtual se divide en bloques del mismo tamaño que los marcos, denominados páginas. Cuando un proceso va a ser ejecutado, sus páginas son cargadas desde el almacenamiento secundario en marcos libres de la memoria física.

Figura 16.1. Soporte del hardware para la paginación.

La paginación es una forma de reubicación de las direcciones en tiempo de ejecución donde la transformación de las direcciones virtuales en direcciones físicas se realiza de la siguiente manera (véase la Figura 16.1):

Cada dirección virtual generada por la CPU es divida en dos partes: un número de página p y un desplazamiento d.
El número de página es utilizado por la MMU para indexar la tabla de páginas, que contiene el número de marco f de cada página en la memoria física.
El número de marco f es combinado con el desplazamiento d para generar la dirección física que va a ser enviada por el bus de direcciones hacia la memoria.

El tamaño de las páginas —y el de los marcos— viene definido por el hardware y normalmente es un número entero potencia de 2 que puede variar entre 512 bytes y 16 MiB, dependiendo de la arquitectura. Es decir, si el espacio de direcciones es de 2^m y el tamaño de página es de 2ⁿ, los m - n bits de mayor orden de las direcciones virtuales indican el número de página, mientras que los n bits de menor orden indican el desplazamiento (véase la Figura 16.2).

Figura 16.2. Descomposición de las direcciones virtuales en paginación.

Por ejemplo, en muchos sistemas operativos el tamaño de página es de 4 KiB, por lo que el desplazamiento n necesita:

\$n = log_2 4096 = 12\ "bits"\$

Si las direcciones virtuales son de 32 bits, eso deja para el número de página p:

\$p = 32 - 12 = 20\ "bits"\$

por lo que el espacio de direcciones virtual tiene 2²⁰ páginas —es decir, 1 048 576 páginas—.

16.1.1. Desde el punto de vista de los procesos

Cada página de un proceso requiere un marco. Por tanto, cuando un proceso llega al sistema:

Si el proceso requiere n páginas, el sistema operativo debe escoger n marcos. Estos marcos son tomados de la lista de marcos libres que debe mantener el sistema. Puesto que son escogidos de allí donde los haya libres, el espacio de direcciones físico puede no ser contiguo, aunque los procesos vean un espacio de direcciones virtual contiguo.
Los marcos seleccionados son asignados al proceso y cada página del proceso es cargada en uno de dichos marcos.
La tabla de páginas es actualizada de manera que en la entrada de cada página del proceso se pone el número de marco correspondiente.

Un aspecto importante de la paginación es la diferencia entre cómo ven los procesos la memoria y como es realmente la memoria física. Cada proceso ve la memoria como un espacio único que lo contiene solo a él. Sin embargo, la realidad es que el programa está disperso por la memoria física, que además puede almacenar a otros programas. Esto es posible porque en cada momento la tabla de páginas solo contiene las páginas del proceso en ejecución en la CPU.

16.1.2. Desde el punto de vista del sistema operativo

Puesto que el sistema operativo es quién gestiona la memoria física, este debe saber:

Que marcos están asignados y a que página de qué proceso o procesos.
Que marcos están disponibles.

Toda esta información generalmente se guarda en una estructura denominada la tabla de marcos, que tiene una entrada por cada marco de la memoria física.

Además, el sistema operativo debe mantener una copia de la tabla de páginas para cada proceso en el PCB, igual que mantiene una copia del contador de programa y del contenido de los registros de la CPU. Esta copia es utilizada:

Por el asignador para sustituir la tabla de páginas usada por la CPU cuando realiza un cambio de contexto. Por lo tanto, el uso de la paginación incrementa el tiempo del cambio de contexto.
Para la traducción manual de direcciones virtuales en físicas. Por ejemplo, cuando un proceso realiza una llamada al sistema para realizar una operación de E/S y proporciona una dirección como parámetro, dicha dirección debe ser traducida manualmente para producir la dirección física correspondiente, que será comunicada al hardware para realizar la operación.

16.1.3. Tamaño de las páginas

Una decisión de diseño importante es escoger el tamaño de las páginas adecuado:

Con páginas más pequeñas esperamos tener menos fragmentación interna.
Con páginas más grandes se pierde menos espacio en la tabla de páginas. No olvidemos que cuanto más pequeñas son las páginas, más páginas son necesarias y, por tanto, más entradas en la tabla de páginas se necesitan. Además, la E/S es más eficiente cuanto más datos son transferidos de cada vez.

Los tamaños de páginas típicos son 4 y 8 KiB. En un sistema de 32 bits con páginas de 4 KiB —como del que hablamos antes— el espacio de direcciones virtual tiene 1 048 576 páginas. Si se utilizan 4 bytes para cada entrada de la tabla de páginas —aunque esto también puede variar— eso significa que cada tabla de páginas ocupa 4 MiB de espacio. Mientras que con páginas de 8 KiB, la tabla de páginas ocuparía 2 MiB de espacios.

También significa que si los 4 bytes de la tabla de páginas se utilizan para guardar únicamente el número de marco, cada entrada puede direccionar a uno de 2³² —o 4 GiB— marcos de la memoria física. Si el tamaño de cada marco es de 4 KiB —dado que debe coincidir con el tamaño de las páginas— podemos determinar que el sistema es capaz de direccionar 2⁴⁴ bytes —o 16 TiB— de memoria física, aunque el espacio de direcciones virtual de cada proceso solo le da acceso a un máximo de 4 GiB.

16.2. Soporte hardware de la tabla de páginas

La implementación en hardware de la tabla de páginas puede realizarse de diversas maneras.

16.2.1. Almacenada en registros de la CPU

La tabla de páginas del proceso actual en la CPU puede alojarse dentro de la propia CPU, en unos registros destinados a tal fin.

Debido a la velocidad de los registros de la CPU, la implementación en registros es la más eficiente. Sin embargo, solo puede ser utilizado para tablas de páginas razonablemente pequeñas, ya que alojar tablas de más de 256 entradas en registros es muy costoso.

Por ejemplo, el DEC PDP-11 —para el que se diseñó el primer UNIX— es un ejemplo de sistema con esta implementación. Utilizaba un espacio de direcciones de 16 bits y un tamaño de páginas de 8 KiB, por lo que solo necesitaba 8 registros dedicados para alojar toda la tabla de páginas.

16.2.2. Almacenada en memoria

La otra opción es alojar la tabla de páginas del proceso actual en la memoria, normalmente en un formato definido por la CPU.

En los sistemas modernos se utilizan tablas de páginas de un millón de entradas o más, que difícilmente pueden alojarse en registros dentro de la CPU. Por eso, los sistemas actuales almacenan la tabla de páginas del proceso actualmente en ejecución, en la memoria. Eso permite disponer de tablas de páginas de gran tamaño, aunque a costa de necesitar dos accesos a la memoria física por cada acceso a una dirección virtual.

Para que la MMU pueda conocer la ubicación de la tabla de páginas durante la traducción de las direcciones, la CPU debe disponer de un registro —el PTBR (Page-Table Base Register)— donde se guarda la dirección de la tabla de páginas actual.

Además, esto tiene la ventaja de que el cambio de contexto es más rápido —respecto al uso de registros para almacenar la tabla de páginas— puesto que solo es necesario cargar un único registro más —el PTBR— durante el mismo.

16.2.3. TLB

La solución al retraso originado por el acceso a la tabla de páginas, cuando esta está en la memoria, pasa porque el sistema disponga de una pequeña caché de traducciones en hardware llamada TLB (Translation Look-aside Buffer).

La TLB es una memoria asociativa de alta velocidad. Cada entrada de la TLB tiene dos partes: la clave —o etiqueta— y el valor. Cuando a la TLB se le entrega un elemento, este es comparado simultáneamente con todas las claves. Si se produce alguna coincidencia, la memoria devuelve el valor de la entrada correspondiente.

Debido a la forma que tienen de operar, son rápidas pero muy caras de fabricar. Por ello, el número de entradas es bajo, normalmente entre 64 y 1024.

Uso básico de la TLB

La TLB es utiliza con la tabla de páginas de la siguiente manera:

Figura 16.3. Soporte del hardware para la paginación con TLB.

La TLB contiene unas pocas entradas de la tabla de páginas.
Cuando la CPU genera una dirección virtual, el número de página es entregado a la TLB. La TLB utiliza los números de páginas como clave, por lo que si hay alguna coincidencia, devolverá la entrada correspondiente de la tabla de páginas.
Si hay coincidencia —o acierto de TLB— el número de marco es extraído de la entrada devuelta por la TLB y es utilizado para generar la dirección física. Todo este proceso puede requerir un 10% más de tiempo que si no se hiciera la traducción de las direcciones.
Si no hay coincidencia —o fallo de TLB— es necesario acceder a la tabla de páginas para obtener la entrada correspondiente directamente de ella. Indudablemente, este acceso puede beneficiarse de la existencia de diferentes niveles de caché en el acceso a la memoria principal.
En este último caso, la entrada recuperada debe ser añadida a la TLB, por lo que sí está llena, se debe seleccionar una para ser sustituida. Los algoritmos de reemplazo utilizados van, desde elegir una aleatoriamente, hasta el LRU (Least Recently Used).

Borrado de la TLB en el cambio de contexto

Una cuestión importante es qué ocurre con las TLB cuando el sistema operativo realiza un cambio de contexto.

En general, es necesario que el asignador realice un borrado de la TLB. De lo contrario, el nuevo proceso podría utilizar las entradas de la tabla de páginas del viejo proceso, que estuvieran almacenadas en la TLB. Sin embargo, un proceso no tiene por qué utilizar todas las entradas de la TLB, por lo que sería más interesante, no tener que borrar las entradas de procesos anteriores, mientras no sean necesarias, por si estos vuelven a ser ejecutados en la CPU.

El borrado se puede evitar si cada entrada de la TLB tiene un ASID (Address-Space Identification), que no es más que un identificador único para cada proceso. En este tipo de TLB, en la clave se buscan pares (número de página, ASID), donde el primero proviene de la dirección virtual y el segundo es el ASID del proceso actual. De esta forma, si el número de página coincide, pero no el ASID, se produce un fallo de la TLB. Esto obliga a acceder a la tabla de páginas en memoria para recuperar la entrada, evitando que se lea por error la entrada de un proceso anterior.

Esta característica está presente en los procesadores DEC Alpha, MIPS y Sun UltraSPARC. Entre 2005 y 2006 también comenzó a ser incluida en algunos procesadores de la familia x86, a través de las extensiones de virtualización Intel VT y AMD Pacifica.

16.3. Tiempos de acceso a la memoria

El rendimiento de un sistema con paginación, está relacionado con el concepto de tiempo de acceso efectivo a la memoria \$T_text(em)\$, que intenta estimar el tiempo que realmente se tarda en acceder a la memoria, teniendo en cuenta mecanismos del sistema operativo como el método de paginación o la existencia de TLB.

En muchos sistemas informáticos, el tiempo de acceso a la memoria física \$T_text(m)\$ es de unos pocos nanosegundos. Por tanto, en el método de básico de paginación —con una tabla de páginas lineal— y sin TLB, el tiempo de acceso efectivo \$T_text(em)\$ es el doble del tiempo de acceso \$T_text(m)\$ a la memoria:

\$T_text(em)=2T_text(m)\$

porque es necesario acceder a la memoria en dos ocasiones:

Primero, para consultar la tabla de páginas, con el objetivo de traducir la dirección virtual en una dirección física.
Después, para realizar la operación solicitada sobre la memoria física.

Obviamente, en métodos de paginación donde hagan falta más accesos para obtener finalmente el número de marco, el tiempo de acceso efectivo será mayor.

En el caso anterior, el segundo acceso a la memoria es inevitable, porque corresponde a la operación solicitada por el proceso. Mientras que el primero puede evitarse, en ciertas ocasiones, consultado la TLB antes de acceder a la tabla de páginas. Es decir, en un sistema con TLB:

Cuando la dirección virtual NO está en la TLB: \$T_text(em)=2T_text(m) + T_text(TLB)\$, porque primero se accede a la TLB y después —como no se encuentra allí la direcció virtual— se consulta la tabla de páginas.
Cuando la dirección virtual está en la TLB: \$T_text(em)=T_text(m) + T_text(TLB)\$, porque la TLB proporciona la información necesaria para traducir la dirección, evitando la consulta posterior a la tabla de páginas.

El cálculo de \$T_text(em)\$ puede complicarse aun más si tenemos en cuenta que los sistemas suelen tener varios niveles de memoria caché. En ese caso \$T_text(m)\$ no tiene un valor determinado, sino que se estima un promedio considernado tanto el tiempo de acceso a la memoria física como a cada uno de los niveles de caché del sistema, así como la probabilidad de que la dirección de memoria a la que se quiere acceder esté disponible en alguno de dichos niveles.

El \$T_text(em)\$ del primer caso suele ser mucho mayor que el segundo porque, por lo general, $T_\mathrm{TLB} \ll T_\mathrm{m}$. Esto hace que en muchos sistemas se pueda considerar que \$T_text(em) ~~ T_text(m)\$ cuando la dirección virtual está en la TLB.

Como el tiempo de acceso efectivo \$T_text(em)\$ ahora depende de la probabilidad \$p_text(TLB)\$ de que las direcciones virtuales consultadas estén en la TLB, ya no podemos hacer el cálculo de forma determinista, sino estimar un \$T_text(em)\$ promedio para el sistema. Para ello, solo es necesario sumar el \$T_text(em)\$ para ambos casos, ponderando por la probabilidad \$p_text(TLB)\$ de que la dirección esté en la TLB o \$(1 - p_text(TLB))\$ de que no esté en la TLB, respectivamente:

\[\begin{aligned} T_\mathrm{em} &= (1-p_\mathrm{TLB})(2T_\mathrm{m} + T_\mathrm{TLB}) + p_\mathrm{TLB}(T_\mathrm{m} + T_\mathrm{TLB})\\ &= (2-p_\mathrm{TLB})T_\mathrm{m} + T_\mathrm{TLB} \end{aligned}\]

Como comentamos anteriormente, esta expresión se puede simplificar si consideramos que $T_\mathrm{TLB} \ll T_\mathrm{m}$:

\[\begin{aligned} T_\mathrm{em} &= 2(1-p_\mathrm{TLB})T_\mathrm{m} + p_\mathrm{TLB}T_\mathrm{m}\\ &= (2-p_\mathrm{TLB}) T_\mathrm{m} \end{aligned}\]

Obviamente, cuanto más se aproxima a 1 la probabilidad \$p_text(TLB)\$ de que la entrada esté en la TLB, más cerca está \$T_text(em)\$ de \$T_text(m)\$.

Para mejorar esta probabilidad:

Las TLB permiten marcar algunas entradas como insustituibles. Esto normalmente se hace con las entradas de las páginas del código y los datos del núcleo, ya que son páginas que se utilizan con muchísima frecuencia.
Si la MMU soporta páginas de mayor tamaño que el estándar, se utilizan para alojar el código y los datos del núcleo. De esta forma se minimiza el número de entradas de la TLB que utilizan, con el fin de disponer de más entradas libres para los procesos en ejecución.

En la familia x86 el tamaño de página estándar es de 4 KiB, pero también se puede disponer de páginas de 4 MiB. En x86-64 las páginas de gran tamaño son de 2 MiB, aunque algunos modelos también soportan páginas de 1 GiB.

16.4. Protección de la memoria

La protección de las páginas se consigue mediante unos bits que indican las operaciones que se pueden realizar sobre ellas. Normalmente, estos bits son almacenados en cada una de las entradas de la tabla de páginas.

16.4.1. Bits de protección

Los bits de protección pueden ser:

Solo lectura.
Lectura — Escritura. En algunos sistemas hay un bit específico para este permiso, mientras que en otros se utilizan bits separados, como: lectura, escritura y ejecución; que se pueden combinar libremente.
Solo ejecución. Que no existen en todas las plataformas. Por ejemplo, la familia x86 careció de esta característica hasta que AMD la incluyó en su arquitectura x86-64, lo que obligó a Intel a incluirla en las versiones más modernas de Pentium IV. El bit —que para ser exacto indica no ejecución— fue introducido para evitar cierto tipo de ataques de seguridad.

Durante la traducción de las direcciones, la MMU comprueba que el tipo de acceso sea válido. Si no lo es, se genera una excepción de violación de protección de memoria, dado que el acceso en un modo no autorizado se considera una instrucción privilegiada. Normalmente, el sistema operativo responde a dicha excepción terminando el proceso que la generó.

16.4.2. Bit de válido

Además de los bits de protección comentados, se suele añadir a cada entrada un bit de válido:

Cuando una página es válida, la página existe en el espacio de direcciones virtual del proceso. Es decir, que la página se puede utilizar. Otro término comúnmente utilizado, es que la página es legal.
Cuando la página es inválida, la página no existe en el espacio de direcciones virtual del proceso. Es decir, que la página no se puede utilizar. El término alternativo utilizado es que la página es ilegal.

Al igual que con los bits de protección, los intentos de acceso a una página ilegal generan una excepción.

El sistema operativo puede utilizar este bit para permitir o denegar cualquier tipo de acceso a una página. Generalmente, porque no se le ha asignado un marco de memoria física, ya que esa página no está siendo utilizada por el proceso.

Figura 16.4. Bit de válido en la tabla de páginas.

Por ejemplo, en la Figura 16.4, vemos el espacio de direcciones virtual y la tabla de páginas de un proceso de 5096 bytes en un sistema con páginas de 1 KiB. Puesto que el proceso no ocupa todo el espacio de direcciones, solo las direcciones de la 0 a la 5119 son válidas. En dicho ejemplo, podemos apreciar varios fenómenos:

Debido a la fragmentación interna, las direcciones de la 5097 a la 5119 son válidas, aunque el proceso solo ocupe hasta la 5096. Es decir, se está asignando al proceso una porción de memoria que no necesita.
Solo las páginas con datos y código del proceso son válidas. Mientras que todas las páginas con direcciones por encima de la 5119 están marcadas como ilegales.

En general, los procesos solo necesitan una porción muy pequeña de su espacio de direcciones virtual. Por ejemplo, en un sistema de 32 bits, muy pocos procesos necesitan los 3 GiB disponibles como máximo para cada proceso —el 1 GiB restante suele estar ocupado por el núcleo del sistema—. Utilizando el bit de válido, el sistema operativo no tiene que asignar marcos a páginas no utilizadas por el proceso, ahorrando mucha memoria.

En el Apartado 16.1.3, vimos que el tamaño de la tabla de páginas se puede calcular como el número máximo de páginas del espacio de direcciones virtual multiplicado por el tamaño de cada entrada de la tabla. Así, en un sistema de 32 bits con páginas de 4 KiB y 4 bytes por entrada, se necesitan 4 MiB de memoria para almacenar la tabla de páginas. Como un proceso suele ocupar muy poco de su espacio de direcciones virtual, suele ser un desperdicio de memoria crear y almacenar una tabla de páginas completa, con una entrada para cada página del espacio de direcciones.

Para evitarlo, en algunas CPU existe el registro PTLR (Page-Table Length Register) que se utiliza para indicar el tamaño actual de la tabla de páginas. Este valor es comparado por la MMU, durante la traducción de las direcciones virtuales, con el número de página de cada dirección virtual, de manera que las páginas con entradas más allá de la última almacenada en la tabla son consideradas ilegales.

Figura 16.5. Anatomía de un proceso en memoria.

En realidad, el registro PTLR no es de mucha utilidad en los sistemas operativos modernos porque, tal y como vimos en el Apartado 9.1, lo más común es que los procesos tengan un espacio de direcciones virtual disperso como el de la Figura 16.5. En ella, podemos observar, como el sistema operativo ubica los diferentes componentes del proceso de una forma particular dentro del espacio de direcciones virtual. Este esquema permite que tanto el montón —a través del mecanismo de asignación dinámica de memoria— como la pila puedan extenderse —según las necesidades de memoria que tenga el proceso— sobre la región de memoria no ocupada. Esa región también puede ser parcialmente ocupada por librerías de enlace dinámico o regiones de memoria compartida, si son necesarias durante la ejecución del proceso.

En cualquier caso, las páginas de la región no ocupada, forman parte del espacio de direcciones virtual, pero no necesitan tener asignado ningún marco de memoria física, en tanto en cuanto el proceso no las vaya a utilizar. La falta de marco es indicada por el sistema operativo utilizando el bit de válido para denegar el acceso.

16.5. Páginas compartidas

Una de las ventajas importantes de la paginación, es la posibilidad de compartir páginas entre procesos. Para conseguir esto, basta con que las páginas compartidas de los distintos procesos tengan asignadas un mismo marco. Esto permite, por ejemplo, que los procesos de un mismo programa puedan compartir las páginas de código o los datos de solo lectura con el fin de ahorrar memoria. También permite compartir las páginas de código de una librería compartida enlazada en diferentes procesos.

Compartir páginas no solo permite ahorrar memoria, pues en los sistemas operativos modernos, la comunicación entre procesos mediante memoria compartida (véase el Capítulo 11), se implementa mediante páginas compartidas.

16.6. Paginación jerárquica

Al método básico de paginación, se lo conoce como tabla de páginas lineal. Sin embargo, las CPU comúnmente, utilizan otras técnicas a la hora de estructurar la tabla de páginas. Una de las más comunes es la paginación jerárquica, utilizada en los procesadores de la familia x86 y en ARM, entre otros.

La mayor parte de los sistemas modernos soportan el uso de espacios de direcciones de gran tamaño. Por ejemplo, supongamos un sistema con un espacio de direcciones virtual de 32 bits:

tamaño del espacio de direcciones

= 2³² = 4 GiB

tamaño de página

= 2¹² = 4 KiB

número de páginas

= 2³² / 2¹² = 2^32-12 = 2²⁰ = 1 048 576 entradas

Es decir, que si el tamaño de cada entrada fuera de 4 bytes, la tabla de páginas de un proceso podría ocupar hasta 4 MiB; que debe ser alojada en una región continúa del espacio de direcciones físico, por lo que podría darse el caso de que en algún momento no hubiera un hueco contiguo lo suficientemente grande. Una forma de resolver este problema es partir la tabla de páginas, de manera que no sea necesario asignarle memoria de forma contigua.

16.6.1. Paginación jerárquica de dos niveles

La paginación jerárquica se basa en la idea de que un vector de gran tamaño puede ser mapeado en uno más pequeño, que a su vez, puede ser mapeado en un vector de menor tamaño.

Figura 16.6. Esquema de paginación jerárquica de dos niveles.

Por ejemplo, si asumimos el caso anterior de un sistema con un espacio de direcciones de 32 bits y un tamaño de página de 4 KiB, entonces podemos dividir la tabla de páginas de 1 048 576 entradas —4 MiB si cada entrada necesita 4 bytes— en 1024 porciones, cada una de las cuales cabría en un marco de 4 KiB.

Estos marcos, a su vez, pueden ser mapeados por 1024 entradas con las direcciones físicas de cada marco. Si organizamos estas 1024 entradas en un vector lineal, obtendremos una tabla de páginas externa de 4 KiB (véase la Figura 16.6).

Dado que 4 KiB es una cantidad de memoria muy pequeña, muchos sistemas operativos mantienen la tabla de páginas externa en la memoria mientras el proceso se está ejecutando. Sin embargo, ahora la tabla de páginas está dividida en marcos, que no tienen por qué ser asignados de forma contigua en la memoria. Incluso podrían ser intercambiados al disco, en caso de necesitar memoria libre.

Para tener dos niveles de 1024 entradas, solo es necesario dividir el número de página p de la dirección virtual —que tenía 2²⁰ bits— en dos números de página de 2¹⁰ bits cada uno:

Este es el método utilizado por la familia de procesadores x86.

Otra variación de la paginación jerárquica de dos niveles es la utilizada por VAX. Estos sistemas utilizaban una arquitectura de 32 bits con un tamaño de página de 512 bytes. Las direcciones virtuales eran divididas de la siguiente manera:

El espacio de direcciones de un proceso estaba dividido en 3 secciones. Los 2 bits de orden más alto s de las direcciones virtuales se utilizaban para indicar la sección. Cada sección estaba dividida en páginas de 512 bytes, por lo que los siguientes 21 bits de las direcciones virtuales p eran utilizadas para seleccionar la página concreta.

Dividiendo el espacio de direcciones de esta manera, el sistema operativo podía mantener secciones sin utilizar mientras no fueran necesarias. Esto era importante, puesto que la tabla de páginas de una sección tenía un tamaño de 8 MiB.

16.6.2. Paginación jerárquica de N niveles

En general, en la paginación jerárquica de n niveles el número de página p de cada dirección virtual es dividido en n números: { p₁, p₂, p₃, …, p_N}, donde:

p₁ se utiliza para indexar la tabla de páginas externa —también llamada directorio de páginas o tabla de páginas de nivel 0— cuya dirección conoce la CPU mediante el PTBR. La entrada obtenida de esta manera, contiene la dirección en la memoria física de una porción de la tabla de páginas en el siguiente nivel —el nivel 1—.
p₂ se utiliza para indexar la tabla de páginas de nivel 1. E, igualmente, la entrada así obtenida contiene la dirección en la memoria física de una porción de la tabla de páginas en el siguiente nivel —el nivel 2—.
El proceso continúa hasta que p_N, se utiliza para indexar la tabla de páginas de nivel N-1, con la que se obtiene el número de marco que es utilizado, finalmente, para generar la dirección física al combinarlo con el desplazamiento d de la dirección virtual.

Como se puede ver, resolver una dirección virtual necesita tantos accesos a la memoria como niveles hay en la jerarquía.

Debido a que la traducción funciona desde las tablas de páginas de nivel superior —nivel 0— hacia las de nivel inferior —nivel N - 1— a esta estructura también se la conoce como tabla de páginas directa.

Los procesadores DEC Alpha y MIPS utilizan una variante denominada tabla de páginas virtualizada. En este esquema, el último nivel de la paginación jerárquica, aunque esté en marcos separados en el espacio de direcciones físico, se mapea de manera continua en el espacio de direcciones virtual del proceso.

Así, si la consulta a la TLB falla, se indexa la tabla de páginas directamente con direcciones virtuales usando el número de página completo. Esta consulta conlleva la traducción de la dirección virtual de la entrada indexada, que puede estar en la TLB. Si no es así, se pasa a recorrer la tabla de páginas desde el nivel 0 y usando direcciones físicas.

Existen algunos procesadores que utilizan más de dos niveles. Por ejemplo, los procesadores x86-64 utilizan un esquema de 4 niveles de paginación. Cada página es de 4 KiB —como en el resto de la familia x86— pero como cada entrada en la tabla de páginas es de 8 bytes —con el fin de poder almacenar direcciones de 64 bits— en cada una caben 512 entradas, por lo que los números de página de cada nivel necesitan 9 bits. Eso significa que de las direcciones virtuales se utilizan actualmente 48 bits —resultado de multiplicar 4 niveles por 9 bits cada uno más 12 bits de desplazamiento— aunque el límite de la arquitectura para las direcciones virtuales sea de 64 bits.

16.6.3. Tiempos de acceso a la memoria

La paginación jerárquica aumenta el número de accesos necesarios para consultar la tabla de páginas. Es decir, mientras que para consultar una tabla de páginas lineal solo necesitamos un acceso a la memoria, para obtener una dirección fisica en la paginación jerárquica de n niveles necesitamos n accesos a la memoria. Por tanto, el tiempo de acceso efectivo \$T_text(em)\$ en un sistema sin TLB es:

\[T_\mathrm{em} = (n+1)T_\mathrm{m}\]

porque, además de los n accesos para consultar la tabla de páginas y obtener la dirección física, es necesario ejecutar la operación solicitada en la memoria física.

Como en el Apartado 16.3, cuando el sistema dispone de TLB, el tiempo de acceso efectivo \$T_text(em)\$ anterior corresponde al caso en el que la dirección virtual no está en la TLB. Mientras que, en caso contrario, el tiempo de acceso efectivo es \$T_text(em)=T_text(m) + T_text(TLB)\$.

Siguiendo los mismos pasos que en el Apartado 16.3, para obtener una estimación de \$T_text(em)\$ en base a la probabilidad \$p_text(TLB)\$ de que las direcciones virtuales consultadas estén en la TLB, obtenemos el siguiente resultado:

\[\begin{aligned} T_\mathrm{em} &= (1-p_\mathrm{TLB}) ((n+1)T_\mathrm{m} + T_\mathrm{TLB}) + p_\mathrm{TLB}(T_\mathrm{m} + T_\mathrm{TLB})\\ &= ((1-p_\mathrm{TLB})n+1)T_\mathrm{m} + T_\mathrm{TLB} \end{aligned}\]

Esta expresión se puede simplificar si consideramos que $T_\mathrm{TLB} \ll T_\mathrm{m}$:

\[\begin{aligned} T_\mathrm{em} &= (1-p_\mathrm{TLB})(n+1)T_\mathrm{m} + p_\mathrm{TLB}T_\mathrm{m}\\ &= (1-p_\mathrm{TLB})n+1)T_\mathrm{m} \end{aligned}\]