Una tabla de páginas es una estructura de datos utilizada por 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 la configura el sistema operativo de la computadora y puede ser leída y escrita durante el proceso de traducción de direcciones virtuales mediante la unidad de administración de memoria o mediante software o firmware del 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 secciones de memoria grandes y contiguas. 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 la tabla de páginas (PTE). [1] [2]
La unidad de administración de memoria (MMU) dentro de la CPU almacena un caché de las asignaciones utilizadas recientemente de la tabla de páginas del sistema operativo. Esto se denomina búfer de búsqueda de traducción (TLB), que es un caché asociativo.
Cuando es necesario traducir una dirección virtual a una dirección física, primero se busca el TLB. Si se encuentra una coincidencia, lo que se conoce como acierto 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 un paseo de página . Si existe uno, se vuelve a escribir en el TLB, lo que debe hacerse porque el hardware accede a la memoria a través del TLB en un sistema de memoria virtual y la instrucción errónea se reinicia, lo que también puede ocurrir en paralelo. La traducción posterior dará como resultado un acierto de TLB y el acceso a la memoria continuará.
La búsqueda de 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 el TLB se actualizan y se reinicia la instrucción. 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. Es necesario actualizar la tabla de páginas 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. El TLB también debe actualizarse, incluida la eliminación de la página paginada y reiniciar la instrucción. Qué página eliminar es el tema de los algoritmos de reemplazo de páginas .
Algunas MMU desencadenan un error 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 mantener una tabla de marco y una tabla de páginas. La tabla de cuadros contiene información sobre qué cuadros están mapeados. En sistemas más avanzados, la tabla de marco 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 asignación 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 ID de proceso, entre otros.
El almacenamiento secundario, como una unidad de disco duro, se puede utilizar para aumentar la memoria física. Las páginas se pueden paginar dentro y fuera de la memoria física y del disco. El bit presente puede indicar qué páginas están actualmente presentes 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 buscar otra página en la memoria física.
El bit sucio permite optimizar el rendimiento. Una página en el disco que se pagina en la memoria física, luego se lee y posteriormente se pagina nuevamente 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 haberla paginado, se establecerá su bit sucio, lo que indica que la página se debe volver a escribir en el almacén de respaldo. Esta estrategia requiere que el almacén de respaldo conserve una copia de la página después de paginarla en la memoria. Cuando no se utiliza un bit sucio, el almacén de respaldo sólo 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 almacén de respaldo.
En los sistemas operativos que no son sistemas operativos de espacio de direcciones único , el espacio de direcciones o la información de identificación del proceso es necesario para que el sistema de administración de memoria virtual sepa qué páginas asociar a qué proceso. Dos procesos pueden utilizar 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 mapa de direcciones distintos o utilizando ID de proceso. Asociar ID de proceso con páginas de memoria virtual también puede ayudar en la selección de páginas para paginar, ya que es menos probable que las páginas asociadas con procesos inactivos, particularmente procesos cuyas páginas de códigos se han paginado, se necesiten inmediatamente que las páginas que pertenecen a procesos activos.
Como alternativa a etiquetar las entradas de la tabla de páginas con identificadores únicos de proceso, la tabla de páginas en sí 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 tal implementación, la tabla de páginas del proceso se puede paginar siempre que el proceso ya no resida en la memoria.
Existen varios tipos de tablas de páginas, que están optimizadas para diferentes requisitos. Esencialmente, una tabla de páginas básica debe almacenar la dirección virtual, la dirección física que está "debajo" de esta dirección virtual y posiblemente alguna información del espacio de direcciones.
Es mejor considerar una tabla de páginas invertida (IPT) como una extensión fuera del chip del TLB que utiliza la 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 un TLB lleno de software estilo MIPS.
El IPT combina una tabla de páginas y una tabla de marco en una estructura de datos. En esencia, hay una tabla de tamaño fijo con un número de filas igual al número de fotogramas en la memoria. Si hay 4000 marcos, la tabla de páginas invertidas 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 colisión , como veremos más adelante.
Buscar en todas las entradas de la estructura central del IPT es ineficiente, y se puede usar una tabla hash para asignar direcciones virtuales (e información del espacio de direcciones/PID si es necesario) a un índice en el IPT; aquí es donde se usa la cadena de colisión. Esta tabla hash se conoce como tabla de anclaje hash . La función hash generalmente no está optimizada para la cobertura; la velocidad bruta es más deseable. 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 en la tabla se proporciona la VPN para verificar si es la entrada buscada o una colisión.
Al 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. Dependiendo de la arquitectura, la entrada se puede volver a colocar en el TLB y se reinicia la referencia de memoria, o se puede seguir la cadena de colisiones 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 localidad de 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 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, con la compensación de una mayor tasa de errores.
Normalmente hay una tabla hash, contigua en la memoria física, compartida por todos los procesos. Se utiliza un identificador por proceso para eliminar la ambigüedad de las páginas de 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 valores de identificador por proceso para retrasar este problema. Alternativamente, se pueden usar 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 invertidas mantiene una lista de las asignaciones instaladas para todos los marcos en la memoria física. Sin embargo, esto podría ser un gran desperdicio. En lugar de hacerlo, podríamos crear una estructura de tabla de páginas que contenga asignaciones para páginas virtuales. Se realiza manteniendo varias tablas de páginas que cubren un determinado bloque de memoria virtual. Por ejemplo, podemos crear páginas más pequeñas de 4 KB de 1024 entradas que cubran 4 MB de memoria virtual.
Esto es útil ya que a menudo las partes superiores e inferiores de la memoria virtual se utilizan para ejecutar un proceso: la parte superior se utiliza a menudo para segmentos de texto y datos, mientras que la inferior para la pila, con memoria libre en el medio. La tabla de páginas multinivel puede conservar algunas de las tablas de páginas más pequeñas para cubrir sólo las partes superior e inferior de la memoria y crear otras nuevas sólo cuando sea estrictamente necesario.
Ahora, cada una de estas tablas de páginas más pequeñas está vinculada entre sí mediante una tabla de páginas maestra, creando efectivamente una estructura de datos de árbol . No es necesario que haya sólo 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 la página raíz, el índice en la tabla de subpáginas 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. Pero podemos solucionar 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 de la tabla de páginas.
Sin embargo, parte de esta estructura de tabla de páginas lineal siempre debe permanecer residente en la memoria física para evitar errores 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 soporte de hardware para la virtualización de tablas de páginas, la necesidad de emular se reduce considerablemente. Para la virtualización x86, las opciones actuales son la función de tabla de páginas extendida de Intel y la función de indexación de virtualización rápida de AMD .