Hispanopedia Wiki
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 , 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 bajo nivel del sistema.
Función de la tabla de páginas
En los sistemas operativos que utilizan memoria virtual, cada proceso tiene la impresión de estar 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 ( paginada ) a un almacenamiento secundario, normalmente a un disco duro (HDD) o a 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 donde se almacenan esos datos. La tabla de páginas es donde se almacenan las asignaciones de direcciones virtuales a direcciones físicas, y cada asignación también se conoce como entrada de la tabla de páginas (PTE). [ 1 ] [ 2 ]
El proceso de traducción
La unidad de gestión de memoria (MMU) dentro de la CPU almacena una caché de asignaciones utilizadas recientemente de la tabla de páginas del sistema operativo. Esto se denomina búfer de traducción anticipada (TLB), que es una caché asociativa.
When a virtual address needs to be translated into a physical address, the TLB is searched first. If a match is found, which is known as a TLB hit, the physical address is returned and memory access can continue. However, if there is no match, which is called a TLB miss, the MMU, the system firmware, or the operating system's TLB miss handler will typically look up the address mapping in the page table to see whether a mapping exists, which is called a page walk. If one exists, it is written back to the TLB, which must be done because the hardware accesses memory through the TLB in a virtual memory system, and the faulting instruction is restarted, which may happen in parallel as well. The subsequent translation will result in a TLB hit, and the memory access will continue.
Translation failures
The page table lookup may fail, triggering a page fault, for two reasons:
- The lookup may fail if there is no translation available for the virtual address, meaning that virtual address is invalid. This will typically occur because of a programming error, and the operating system must take some action to deal with the problem. On modern operating systems, it will cause a segmentation fault signal being sent to the offending program.
- The lookup may also fail if the page is currently not resident in physical memory. This will occur if the requested page has been moved out of physical memory to make room for another page. In this case the page is paged out to a secondary store located on a medium such as a hard disk drive (this secondary store, or "backing store", is often called a swap partition if it is a disk partition, or a swap file, swapfile or page file if it is a file). When this happens the page needs to be taken from disk and put back into physical memory. A similar mechanism is used for memory-mapped files, which are mapped to virtual memory and loaded to physical memory on demand.
When physical memory is not full this is a simple operation; the page is written back into physical memory, the page table and TLB are updated, and the instruction is restarted. However, when physical memory is full, one or more pages in physical memory will need to be paged out to make room for the requested page. The page table needs to be updated to mark that the pages that were previously in physical memory are no longer there, and to mark that the page that was on disk is now in physical memory. The TLB also needs to be updated, including removal of the paged-out page from it, and the instruction restarted. Which page to page out is the subject of page replacement algorithms.
Algunas MMU provocan un fallo de página por otros motivos, independientemente de si la página reside o no en la memoria física y está asignada al espacio de direcciones virtuales de un proceso:
- Intentar escribir cuando la tabla de páginas tiene el bit de solo lectura activado provoca un fallo de página. Esto es habitual en la implementación de la copia en escritura de muchos sistemas operativos ; también puede ocurrir cuando se escribe en una ubicación desde la que el proceso tiene permiso para leer, pero en la que no tiene permiso para escribir, en cuyo caso se envía una señal al proceso.
- Intentar ejecutar código cuando la tabla de páginas tiene el bit NX (bit de no ejecución) activado provoca un fallo de página. Esto puede ser utilizado por un sistema operativo, en combinación con el bit de solo lectura, para proporcionar una función de escritura XOR Ejecutar que detiene ciertos tipos de exploits. [ 3 ]
Datos de la tabla de marcos
Los sistemas de tablas de páginas más sencillos suelen mantener 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 el espacio de direcciones al que pertenece una página, información estadística u otra información de contexto.
Datos de la tabla de páginas
La tabla de páginas es una matriz de entradas de tabla de páginas.
Entrada de tabla de página
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.
Tipos de tabla de página
Existen varios tipos de tablas de páginas, optimizadas para diferentes requisitos. Básicamente, una tabla de páginas básica debe almacenar la dirección virtual, la dirección física subyacente a esta dirección virtual y, posiblemente, información sobre el espacio de direcciones.
Tablas de páginas invertidas
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.
Buscar en todas las entradas de la estructura IPT principal es ineficiente, y 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 usa la cadena de colisiones. 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 durante 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.
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 ]
Tablas de páginas multinivel
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".
Tablas de páginas virtualizadas
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.
Tablas de páginas anidadas
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 .
Véase también
Referencias
Lecturas adicionales
- Andrew S. Tanenbaum , Sistemas operativos modernos , ISBN 0-13-031358-0
- A. Silberschatz , PB Galvin, G. Gagne, Conceptos de sistemas operativos , ISBN 0-471-69466-5
- Sistemas Operativos: Tres Piezas Fáciles , por Remzi H. Arpaci-Dusseau y Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Capítulos relevantes: Espacios de direcciones, Traducción de direcciones, Introducción a la paginación , TLB, Tablas de páginas avanzadas.
- Tutorial de memoria virtual del CNE, Centro para el Nuevo Ingeniero, Universidad George Mason, Tablas de páginas
- "El arte del ensamblador, 6.6 Memoria virtual, protección y paginación" . Archivado del original el 18 de febrero de 2012.
- "Manuales para desarrolladores de software de las arquitecturas Intel 64 e IA-32" . Intel. 18 de enero de 2018.
- "Manual del desarrollador de software de la arquitectura AMD64" . AMD. Archivado del original el 13 de marzo de 2010.
Enlaces externos
- Referencia de gestión de memoria
- Memoria virtual
- Gestión de la memoria
- Memoria de computadora
