Tabla de páginas

Cada entrada de la tabla de páginas (PTE) contiene la correspondencia entre la dirección virtual de una página y la dirección de un marco físico. También incluye información auxiliar sobre la página, como el bit de presencia, el bit de modificación, el espacio de direcciones o la información de identificación del proceso, entre otros datos.

El almacenamiento secundario, como un disco duro, puede utilizarse para ampliar la memoria física. Las páginas se pueden cargar y descargar tanto de la memoria física como del disco. El bit de presencia indica qué páginas se encuentran actualmente en la memoria física o en el disco, y cómo gestionarlas, es decir, si se debe cargar una página del disco y descargar otra de la memoria física.

El bit de modificación permite optimizar el rendimiento. Una página en disco que se carga en la memoria física, se lee y posteriormente se vuelve a cargar, no necesita escribirse de nuevo en el disco, ya que no ha cambiado. Sin embargo, si se escribió en la página después de cargarla, se activará su bit de modificación, lo que indica que debe escribirse de nuevo en la memoria de respaldo. Esta estrategia requiere que la memoria de respaldo conserve una copia de la página después de cargarla en la memoria. Cuando no se utiliza el bit de modificación, la memoria de respaldo solo necesita tener el tamaño total instantáneo de todas las páginas cargadas en cualquier momento. Cuando se utiliza el bit de modificación, siempre habrá algunas páginas tanto en la memoria física como en la memoria de respaldo.

En los sistemas operativos que no son de espacio de direcciones único , la información del espacio de direcciones o del ID del proceso es necesaria para que el sistema de gestión de memoria virtual sepa qué páginas asociar a cada proceso. Dos procesos pueden usar dos direcciones virtuales idénticas para diferentes propósitos. La tabla de páginas debe proporcionar asignaciones de memoria virtual diferentes para los dos procesos. Esto se puede lograr asignando identificadores de mapa de direcciones distintos a los dos procesos o utilizando ID de proceso. Asociar los ID de proceso con las páginas de memoria virtual también puede ayudar a seleccionar las páginas que se deben paginar, ya que es menos probable que las páginas asociadas con procesos inactivos, en particular aquellos cuyas páginas de código se han paginado, se necesiten de inmediato que las páginas pertenecientes a procesos activos.

Como alternativa a etiquetar las entradas de la tabla de páginas con identificadores únicos de proceso, la propia tabla de páginas puede ocupar una página de memoria virtual diferente para cada proceso, de modo que pase a formar parte del contexto del proceso. En esta implementación, la tabla de páginas del proceso se puede paginar cuando el proceso ya no reside en la memoria.

Una tabla de páginas invertida (IPT) se puede considerar como una extensión externa de la TLB que utiliza la memoria RAM del sistema. A diferencia de una tabla de páginas convencional, no necesariamente puede almacenar todas las asignaciones actuales. El sistema operativo debe estar preparado para gestionar los fallos de memoria, al igual que lo haría con una TLB basada en software al estilo MIPS.

La tabla de páginas invertida (IPT) combina una tabla de páginas y una tabla de marcos en una única estructura de datos. Su núcleo es una tabla de tamaño fijo con un número de filas igual al número de marcos en memoria. Si hay 4000 marcos, la tabla de páginas invertida tiene 4000 filas. Cada fila contiene una entrada para el número de página virtual (VPN), el número de página física (no la dirección física), otros datos y un mecanismo para crear una cadena de colisiones , como veremos más adelante.

La búsqueda en todas las entradas de la estructura IPT principal es ineficiente, por lo que se puede usar una tabla hash para asignar direcciones virtuales (y espacio de direcciones/información PID si es necesario) a un índice en la IPT; aquí es donde se utiliza la cadena de colisiones. Esta tabla hash se conoce como tabla de anclaje hash . La función hash no suele estar optimizada para la cobertura; la velocidad bruta es más deseable. Por supuesto, las tablas hash experimentan colisiones. Debido a la función hash elegida, podemos experimentar muchas colisiones durante su uso, por lo que para cada entrada en la tabla se proporciona la VPN para verificar si se trata de la entrada buscada o de una colisión.

Para buscar una asignación, se utiliza la tabla hash de anclaje. Si no existe ninguna entrada, se produce un fallo de página. En caso contrario, se encuentra la entrada. Dependiendo de la arquitectura, la entrada puede volver a colocarse en la TLB y reiniciarse la referencia de memoria, o bien se puede seguir la cadena de colisiones hasta que se agote y se produzca un fallo de página.

En este esquema, una dirección virtual podría dividirse en dos partes: la primera sería un número de página virtual y la segunda, el desplazamiento dentro de esa página.

Un problema importante de este diseño es la escasa localidad de caché causada por la función hash . Los diseños basados ​​en árboles evitan esto colocando las entradas de la tabla de páginas para páginas adyacentes en ubicaciones contiguas, pero una tabla de páginas invertida destruye la localidad espacial de referencia al dispersar las entradas por todas partes. Un sistema operativo puede minimizar el tamaño de la tabla hash para reducir este problema, aunque esto conlleva un aumento en la tasa de fallos.

Normalmente, existe una tabla hash contigua en la memoria física, compartida por todos los procesos. Se utiliza un identificador por proceso para diferenciar las páginas de cada proceso. Eliminar las entradas de la tabla de páginas de un proceso determinado es algo lento; el sistema operativo puede evitar reutilizar los identificadores por proceso para retrasar esta tarea. Como alternativa, se pueden usar tablas hash por proceso, pero resultan poco prácticas debido a la fragmentación de la memoria , que requiere la preasignación de las tablas.

Las tablas de páginas invertidas se utilizan, por ejemplo, en las arquitecturas PowerPC , UltraSPARC e IA-64 . ^{[ 4 ]}

La tabla de páginas invertida mantiene un listado de las asignaciones instaladas para todos los marcos en la memoria física. Sin embargo, esto puede resultar bastante ineficiente. En su lugar, podríamos crear una estructura de tabla de páginas que contenga asignaciones para páginas virtuales. Esto se logra manteniendo varias tablas de páginas que cubren un bloque determinado de memoria virtual. Por ejemplo, podemos crear  páginas más pequeñas de 4 KB con 1024 entradas que cubran 4  MB de memoria virtual.

Esto resulta útil, ya que a menudo se utilizan las partes superior e inferior de la memoria virtual para ejecutar un proceso: la parte superior se usa generalmente para segmentos de texto y datos, mientras que la inferior se usa para la pila, con memoria libre entre ambas. La tabla de páginas multinivel puede conservar algunas tablas de páginas más pequeñas para cubrir únicamente las partes superior e inferior de la memoria, y crear nuevas solo cuando sea estrictamente necesario.

Ahora, cada una de estas tablas de páginas más pequeñas está vinculada mediante una tabla maestra, creando así una estructura de datos en forma de árbol . No es necesario que haya solo dos niveles, sino posiblemente varios. Por ejemplo, una dirección virtual en este esquema podría dividirse en tres partes: el índice en la tabla de páginas raíz, el índice en la tabla de subpáginas y el desplazamiento dentro de esa página.

Las tablas de páginas multinivel también se conocen como "tablas de páginas jerárquicas".

Se mencionó que crear una estructura de tabla de páginas que contuviera asignaciones para cada página virtual en el espacio de direcciones virtuales podría resultar ineficiente. Sin embargo, podemos evitar los problemas de espacio excesivo colocando la tabla de páginas en la memoria virtual y permitiendo que el sistema de memoria virtual administre la memoria para dicha tabla.

Sin embargo, parte de esta estructura lineal de la tabla de páginas debe permanecer siempre residente en la memoria física para evitar fallos de página circulares y buscar una parte clave de la tabla de páginas que no esté presente en ella.

Se pueden implementar tablas de páginas anidadas para mejorar el rendimiento de la virtualización de hardware . Al brindar soporte de hardware para la virtualización de tablas de páginas , se reduce considerablemente la necesidad de emulación. Para la virtualización x86 , las opciones actuales son la función Extended Page Table de Intel y la función Rapid Virtualization Indexing de AMD .