Una tabla de páginas es una estructura de datos que utiliza un sistema de memoria virtual en una computadora para almacenar asignaciones entre direcciones virtuales y direcciones físicas . Las direcciones virtuales son utilizadas por el programa ejecutado por el proceso de acceso , mientras que las direcciones físicas son utilizadas por el hardware, o más específicamente, por el subsistema de memoria de acceso aleatorio (RAM). La tabla de páginas es un componente clave de la traducción de direcciones virtuales que es necesaria para acceder a los datos en la memoria. La tabla de páginas es configurada por el sistema operativo de la computadora , y puede ser leída y escrita durante el proceso de traducción de direcciones virtuales por la unidad de administración de memoria o por software o firmware de sistema de bajo nivel.
En los sistemas operativos que utilizan memoria virtual, a cada proceso se le da la impresión de que está trabajando con grandes secciones contiguas de memoria. Físicamente, la memoria de cada proceso puede estar dispersa en diferentes áreas de la memoria física o puede haberse movido ( paginado ) a un almacenamiento secundario, generalmente a una unidad de disco duro (HDD) o una unidad de estado sólido (SSD).
Cuando un proceso solicita acceso a datos en su memoria, es responsabilidad del sistema operativo asignar la dirección virtual proporcionada por el proceso a la dirección física de la memoria real donde se almacenan esos datos. La tabla de páginas es donde se almacenan las asignaciones de direcciones virtuales a direcciones físicas; cada asignación también se conoce como entrada de tabla de páginas (PTE). [1] [2]
La unidad de administración de memoria (MMU) dentro de la CPU almacena un caché de asignaciones utilizadas recientemente de la tabla de páginas del sistema operativo. Esto se denomina búfer de traducción de datos (TLB), que es un caché asociativo.
Cuando es necesario traducir una dirección virtual a una dirección física, primero se busca en la TLB. Si se encuentra una coincidencia, lo que se conoce como acierto de TLB , se devuelve la dirección física y se puede continuar con el acceso a la memoria. Sin embargo, si no hay ninguna coincidencia, lo que se denomina error de TLB , la MMU, el firmware del sistema o el controlador de errores de TLB del sistema operativo normalmente buscarán la asignación de direcciones en la tabla de páginas para ver si existe una asignación, lo que se denomina recorrido de página . Si existe una, se vuelve a escribir en la TLB, lo que se debe hacer porque el hardware accede a la memoria a través de la TLB en un sistema de memoria virtual y la instrucción que falla se reinicia, lo que también puede suceder en paralelo. La traducción posterior dará como resultado un acierto de TLB y el acceso a la memoria continuará.
La búsqueda en la tabla de páginas puede fallar, provocando un error de página , por dos motivos:
Cuando la memoria física no está llena, esta es una operación sencilla: la página se vuelve a escribir en la memoria física, la tabla de páginas y la TLB se actualizan y la instrucción se reinicia. Sin embargo, cuando la memoria física está llena, será necesario paginar una o más páginas de la memoria física para dejar espacio para la página solicitada. La tabla de páginas debe actualizarse para marcar que las páginas que estaban anteriormente en la memoria física ya no están allí y para marcar que la página que estaba en el disco ahora está en la memoria física. La TLB también debe actualizarse, incluida la eliminación de la página paginada y el reinicio de la instrucción. La página que se debe paginar es el tema de los algoritmos de reemplazo de páginas .
Algunas MMU activan una falla de página por otros motivos, independientemente de si la página reside actualmente en la memoria física y está asignada al espacio de direcciones virtuales de un proceso:
Los sistemas de tablas de páginas más simples suelen tener una tabla de marcos y una tabla de páginas. La tabla de marcos contiene información sobre qué marcos están asignados. En sistemas más avanzados, la tabla de marcos también puede contener información sobre a qué espacio de direcciones pertenece una página, información estadística u otra información de fondo.
La tabla de páginas es una matriz de entradas de la tabla de páginas.
Cada entrada de la tabla de páginas (PTE) contiene la correspondencia entre una dirección virtual de una página y la dirección de un marco físico. También hay información auxiliar sobre la página, como un bit presente, un bit sucio o modificado, espacio de direcciones o información de identificación de proceso, entre otros.
Se puede utilizar un almacenamiento secundario, como una unidad de disco duro, para aumentar la memoria física. Se pueden paginar páginas dentro y fuera de la memoria física y del disco. El bit presente puede indicar qué páginas están presentes actualmente en la memoria física o en el disco, y puede indicar cómo tratar estas diferentes páginas, es decir, si se debe cargar una página desde el disco y paginar otra página en la memoria física.
El bit sucio permite optimizar el rendimiento. Una página del disco que se pagina en la memoria física, luego se lee y, posteriormente, se pagina de nuevo no necesita volver a escribirse en el disco, ya que la página no ha cambiado. Sin embargo, si se escribió en la página después de paginarla, se activará su bit sucio, lo que indica que la página debe volver a escribirse en el almacenamiento de respaldo. Esta estrategia requiere que el almacenamiento de respaldo conserve una copia de la página después de paginarla en la memoria. Cuando no se utiliza un bit sucio, el almacenamiento de respaldo solo necesita ser tan grande como el tamaño total instantáneo de todas las páginas paginadas en cualquier momento. Cuando se utiliza un bit sucio, en todo momento existirán algunas páginas tanto en la memoria física como en el almacenamiento de respaldo.
En los sistemas operativos que no son sistemas operativos con un solo espacio de direcciones , la información del espacio de direcciones o del identificador de proceso es necesaria para que el sistema de administración de memoria virtual sepa qué páginas asociar a qué proceso. Dos procesos pueden usar dos direcciones virtuales idénticas para diferentes propósitos. La tabla de páginas debe proporcionar diferentes asignaciones de memoria virtual para los dos procesos. Esto se puede hacer asignando a los dos procesos identificadores de mapas de direcciones distintos o utilizando identificadores de proceso. Asociar los identificadores de proceso con las páginas de memoria virtual también puede ayudar en la selección de páginas para paginar, ya que las páginas asociadas con procesos inactivos, en particular los procesos cuyas páginas de código se han paginado, tienen menos probabilidades de ser necesarias de inmediato que las páginas que pertenecen a procesos activos.
Como alternativa a etiquetar las entradas de la tabla de páginas con identificadores exclusivos del proceso, la tabla de páginas puede ocupar una página de memoria virtual diferente para cada proceso, de modo que la tabla de páginas se convierta en parte del contexto del proceso. En una implementación de este tipo, la tabla de páginas del proceso puede paginarse siempre que el proceso ya no resida en la memoria.
Existen varios tipos de tablas de páginas, que están optimizadas para distintos requisitos. Básicamente, una tabla de páginas básica debe almacenar la dirección virtual, la dirección física que se encuentra "debajo" de esta dirección virtual y, posiblemente, alguna información del espacio de direcciones.
Una tabla de páginas invertida (IPT) se considera una extensión fuera del chip de la TLB que utiliza la memoria RAM normal del sistema. A diferencia de una tabla de páginas verdadera, no necesariamente puede contener todas las asignaciones actuales. El sistema operativo debe estar preparado para manejar errores, tal como lo haría con una TLB llena de software de estilo MIPS.
La tabla de páginas invertida combina una tabla de páginas y una tabla de marcos en una única estructura de datos. En su núcleo hay una tabla de tamaño fijo con un número de filas igual al número de marcos en la memoria. Si hay 4000 marcos, la tabla de páginas invertida tiene 4000 filas. Para cada fila hay 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), algunos otros datos y un medio para crear una cadena de colisiones , como veremos más adelante.
La búsqueda en todas las entradas de la estructura central del IPT es ineficiente, y se puede utilizar una tabla hash para asignar direcciones virtuales (y espacio de direcciones/información PID si es necesario) a un índice en el IPT; aquí es donde se utiliza la cadena de colisión. Esta tabla hash se conoce como tabla de anclaje hash . La función hash no suele estar optimizada para la cobertura; es más deseable la velocidad bruta. Por supuesto, las tablas hash experimentan colisiones. Debido a esta función hash elegida, podemos experimentar muchas colisiones en el uso, por lo que para cada entrada de la tabla se proporciona la VPN para verificar si es la entrada buscada o una colisión.
Para buscar una asignación, se utiliza la tabla de anclaje hash. Si no existe ninguna entrada, se produce un error de página. De lo contrario, se encuentra la entrada. Según la arquitectura, la entrada se puede colocar nuevamente en la TLB y reiniciar la referencia de memoria, o se puede seguir la cadena de colisión hasta que se agote y se produzca un error de página.
Una dirección virtual en este esquema podría dividirse en dos, siendo la primera mitad un número de página virtual y la segunda mitad el desplazamiento en esa página.
Un problema importante con este diseño es la mala localización de la caché causada por la función hash . Los diseños basados en árboles evitan esto al colocar las entradas de la tabla de páginas para páginas adyacentes en ubicaciones adyacentes, pero una tabla de páginas invertida destruye la localización 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, con la contrapartida de un aumento en la tasa de errores.
Normalmente, existe una tabla hash, contigua en la memoria física, compartida por todos los procesos. Se utiliza un identificador por proceso para desambiguar las páginas de los diferentes procesos entre sí. Es algo lento eliminar las entradas de la tabla de páginas de un proceso determinado; el sistema operativo puede evitar la reutilización de los valores del identificador por proceso para retrasar la tarea. Alternativamente, se pueden utilizar tablas hash por proceso, pero no son prácticas debido a la fragmentación de la memoria , que requiere que las tablas estén preasignadas.
Las tablas de páginas invertidas se utilizan, por ejemplo, en la arquitectura PowerPC , UltraSPARC y IA-64 . [4]
La tabla de páginas invertida mantiene una lista de asignaciones instaladas para todos los marcos en la memoria física. Sin embargo, esto podría ser bastante derrochador. En lugar de hacerlo, podríamos crear una estructura de tabla de páginas que contenga asignaciones para páginas virtuales. Esto se hace manteniendo varias tablas de páginas que cubran un bloque determinado de memoria virtual. Por ejemplo, podemos crear páginas más pequeñas de 1024 entradas y 4 KB que cubran 4 MB de memoria virtual.
Esto es útil porque, a menudo, las partes más altas y más bajas de la memoria virtual se utilizan para ejecutar un proceso: la parte superior se suele utilizar para segmentos de texto y datos, mientras que la inferior se utiliza para la pila, con memoria libre en el medio. La tabla de páginas de varios niveles puede mantener algunas de las tablas de páginas más pequeñas para cubrir solo 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 entre sí por una tabla de páginas maestra, lo que crea de manera efectiva 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 páginas secundarias y el desplazamiento en esa página.
Las tablas de páginas multinivel también se denominan "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 terminar siendo un desperdicio. Sin embargo, podemos evitar los problemas de espacio excesivo colocando la tabla de páginas en la memoria virtual y dejando que el sistema de memoria virtual administre la memoria para la tabla de páginas.
Sin embargo, parte de esta estructura de tabla de páginas lineal debe permanecer siempre residente en la memoria física para evitar fallas de página circulares y buscar una parte clave de la tabla de páginas que no esté presente en la tabla de páginas.
Se pueden implementar tablas de páginas anidadas para aumentar el rendimiento de la virtualización de hardware . Al proporcionar compatibilidad de hardware para la virtualización de tablas de páginas, se reduce en gran medida 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 .