¿Qué sucede si un proceso necesita más páginas que el número de entradas en la tabla de páginas?

2

Tengo problemas para entender el concepto de paginación. A continuación se muestra un ejemplo simple para ilustrar mi pregunta.

Supongamos que la memoria principal tiene 128 bytes, organizada en 32 páginas de tamaño de 4 bytes cada una, y la tabla de páginas tiene 8 entradas.

Un proceso necesita 10 páginas (= 40 bytes). Como resultado, la tabla de páginas contendrá la asignación a la dirección real de 8 páginas. Para acceder a estas páginas, la parte del número de página de la dirección lógica se utilizará como índice en la tabla de páginas para obtener la dirección física. Sin embargo, con el esquema típico de usar el número de página como un índice, el proceso no podrá acceder a las páginas 9 y 10.

¿Significa que la tabla de páginas siempre debe contener tantas entradas como el número máximo de páginas posible (en este caso, 32)? ¿O la tabla de páginas tiene tuplas (número de página, número de cuadro), con el número de página mencionado explícitamente (como en TLB)? ¿Cómo se supone que se haga esto?

    
pregunta Masked Man

1 respuesta

4

En general, una tabla de páginas debe poder cubrir todo el espacio de direcciones virtuales. Sin embargo, esto no significa que cada página deba tener una entrada de tabla de páginas.

Para los sistemas de 32 bits, el medio más popular para lograrlo es utilizar una tabla de páginas jerárquica (también denominada multinivel). Con PTE de 4 bytes y 4 páginas KiB, una tabla de páginas jerárquica usaría un puntero base de tabla de páginas que apunta a una página de Entradas de directorio de páginas. Los 10 bits más significativos de la dirección se utilizan para indexar una PDE de 4 bytes. Si se establece el bit válido de la PDE, entonces el campo de dirección de la PDE apunta a una página de PTE que se indexa por los 10 bits de dirección traducidos restantes (los 12 bits menos significativos no se usan en la traducción pero son el desplazamiento dentro del página).

(Las tablas de páginas lineales usan una disposición similar donde la tabla de páginas se asigna en el espacio de direcciones virtuales, generalmente comenzando en la dirección virtual 0. La dirección virtual de la PTE deseada es traducida por el TLB. Si esto genera una falla de TLB, entonces la dirección virtual de la PTE [equivalente a un PDE] que traduce la dirección virtual de la tabla de páginas es traducida por la TLB. Si eso falla, entonces la dirección virtual de la PTE que traduce esa página directorio : esto es equivalente al puntero base de la tabla de páginas en una tabla de páginas jerárquica y, a menudo, se almacena en un registro de propósito especial. Las tablas de páginas lineales tienen la desventaja de excluir una parte de la virtual espacio de direcciones para uso ordinario, potencialmente "desperdicio" de entradas de TLB y mayor sobrecarga de pérdida de TLB variable, pero la ventaja de explotar el TLB para almacenar en memoria caché equivalentes de PDE y un soporte potencialmente más natural de páginas de traducción de tamaño variable, lo que puede reducir el overhe Un anuncio de almacenamiento en caché de equivalentes de PDE y en un espacio de direcciones más grande puede eliminar un nivel de búsqueda. La variabilidad de la sobrecarga de fallas puede gestionarse bloqueando las entradas de TLB para partes críticas de la tabla de páginas.)

Con dichas tablas, siempre que la parte válida del espacio de direcciones virtuales no sea escasa, muchas PDE se pueden marcar como no válidas; esto comprime de manera efectiva una tabla de páginas de 4 KiB que contiene PTE no válidas en los 4 bytes del PDE.

Si se hace referencia a una PDE que tiene su bit válido borrado (y, por lo tanto, no está presente la página de PTE), esto se trataría como una forma de fallo de página y la población necesaria de la subtabla (por ejemplo, para una gran [4 MiB] parte de la memoria asignada a la que nunca se ha hecho referencia, la subtabla podría estar llena de traducciones que apuntan a una página de ceros de solo lectura). Como lo ideal sería que la subtabla solo fuera intercambiada (lo que puede no ser compatible con el sistema operativo de todos modos) si las PTE todas son inválidas (no asignadas o intercambiadas), tienen una dirección virtual con su contenido en la memoria pero no tener en la memoria la subtabla que proporciona la traducción es muy poco probable. Las PDE no válidas se usan normalmente para los fragmentos del espacio de direcciones virtuales que no están asignados (es decir, un acceso generaría una excepción de violación de permiso).

En un sistema típico de 32 bits, si cada porción de 4 MiB del espacio de direcciones virtuales tuviera al menos una página válida, entonces toda la tabla de la página tendría que estar presente (salvo el intercambio de subtablas). Los sistemas comunes no asignan poca memoria, por lo que muchas subtablas no tendrían PTE válidas y se pueden representar marcando el PDE como no válido.

Otra organización de tablas de páginas, algo menos popular, es la tabla de páginas invertida (o hash). Esto utiliza una tabla hash para almacenar los PTE. Esto requiere que cada entrada (que puede incluir múltiples PTE, aunque ninguna ISA defina dicho uso) esté etiquetada con suficiente de la dirección virtual para identificar de manera única la entrada. Esto tiene la desventaja de que los conflictos de hash deben ser gestionados. (Proporcionar más de una entrada por índice / hash puede reducir la frecuencia de conflictos). Para un uso no disperso del espacio de direcciones, las tablas de páginas invertidas generalmente tienen más sobrecarga de almacenamiento y ancho de banda que las tablas de páginas jerárquicas y agregan complejidad para manejar conflictos de hash . Para patrones de acceso (inusuales) que no tienen una localidad espacial, especialmente para espacios de direcciones grandes, o comparados con tablas de páginas jerárquicas que no almacenan en caché PDE, las tablas de páginas invertidas permiten un llenado TLB más rápido ya que solo se requiere una búsqueda (suponiendo sin conflicto).

Las tablas de páginas invertidas se llaman a veces y se pueden usar como TLB de software. Actúan como TLB pero almacenados en la memoria y administrados / dimensionados por software. Al igual que un TLB, generalmente debe haber un mecanismo para manejar los errores. Dichos mecanismos son específicos del sistema operativo y pueden incluir el uso de una lista vinculada (por lo que además de la sobrecarga de etiquetas, habría un costo adicional para el siguiente puntero) y el uso de una tabla hash secundaria (víctima).

    
respondido por el Paul A. Clayton

Lea otras preguntas en las etiquetas