Una breve introducción a los conceptos del sistema operativo - Memoria (III) - Estructura de la tabla de páginas para paginación
La segmentación y la paginación se discutieron anteriormente. Ahora echemos un vistazo a las estructuras de la tabla de páginas principales involucradas en la tabla de páginas.
La mayoría de los sistemas informáticos modernos admiten grandes espacios de direcciones lógicas (2^32 ~ 2^64). En este caso, la propia tabla de páginas puede ser muy grande.
Por ejemplo, supongamos que un sistema informático tiene un espacio de direcciones lógicas de 32 bits. Si el tamaño de página de su sistema es 4 KB (2 ^ 12). Entonces, el número de entradas en la tabla de páginas puede ser hasta 1 millón (2^32/ 2^12). Supongamos que una entrada tiene 4 bytes de longitud. Luego, cada proceso requiere 4 MB de direcciones físicas direccionadas para almacenar la tabla de páginas. Obviamente, no queremos asignar tantas tablas de páginas de forma contigua en la memoria.
Una forma sencilla de resolver este problema es dividir la tabla de páginas en partes más pequeñas. Hay muchas maneras de lograr este objetivo.
El método más simple es utilizar un algoritmo de paginación de dos niveles, que pagina la tabla de páginas, por ejemplo, suponiendo nuevamente un sistema con un espacio de direcciones lógicas de 32 bits y un tamaño de página de 4K. La dirección lógica se divide en un número de página de 20 bits y un desplazamiento de página de 12 bits.
Por lo tanto, la tabla de páginas de 20 bits se volverá a paginar para que la página pueda dividirse en un número de página de 10 bits y un desplazamiento de 10 bits. Por tanto, la dirección lógica se dividirá en la siguiente representación.
Donde p1 representa el índice utilizado para acceder a la tabla de páginas externa y p2 es el desplazamiento de página de la tabla de páginas interna. Método de traducción de direcciones utilizando esta estructura. Esto también se denomina tabla de páginas asignadas hacia adelante porque la traducción de direcciones se produce de afuera hacia adentro.
En este esquema de paginación, suponiendo que el sistema es de 64 bits, cuando su espacio de direcciones es 2^64 y luego se utilizan 4 KB como dirección, la tabla de páginas tendrá 2^52 entradas, luego La tabla de páginas se subdivide en paginación jerárquica de tres niveles, paginación jerárquica de cuatro niveles, etc.
Para utilizar este método de traducción de direcciones, también se denomina tabla de páginas asignadas hacia adelante.
Para reemplazar cada dirección lógica, un sistema de 74 bits requeriría paginación de 7 niveles, lo cual no es deseable para tantos accesos a memoria, por lo que la paginación jerárquica no es posible para sistemas de 64 bits. La mejor opción.
Una forma común de tratar con espacios de direcciones de más de 32 bits es utilizar una tabla de páginas hash con el número de página virtual como valor de la tabla hash. Cada entrada en una tabla de páginas con hash consta de una lista vinculada de elementos que tienen hash en ubicaciones consistentes (lo que significa que tienen colisiones hash). Cada elemento consta de tres campos: el número de página virtual, el código del marco asignado y un puntero al siguiente elemento de la lista vinculada.
El algoritmo funciona de la siguiente manera: el número de página virtual de la dirección virtual se codifica en una tabla hash. Compara el número de página virtual con el primer campo del primer elemento de la lista vinculada. Si hay una coincidencia, el código de trama correspondiente (segundo campo) se utiliza para formar la dirección física. Si no hay ninguna coincidencia, se compara con el primer campo del nodo siguiente en la lista vinculada para encontrar el número de página coincidente. El esquema se muestra en la figura:
Los números de página virtuales mencionados aquí en el libro pueden considerarse solo números de página. (Se llama número de página virtual porque, según el concepto de memoria virtual, el espacio de direcciones lógicas puede ser mayor que la dirección física, por lo que la parte adicional se llama virtual, que se mencionará en el siguiente capítulo).
Proponemos una variante de este esquema para espacios de direcciones de 64 bits.
Esta variante utiliza una tabla de páginas agrupadas similar a una tabla de páginas hash. Sin embargo, cada entrada en la tabla hash hace referencia a varias páginas, no a una sola página. Una entrada en una tabla de una sola página se puede asignar a múltiples marcos físicos. Las tablas de páginas agrupadas son particularmente útiles para espacios de direcciones escasos. Las referencias no son contiguas sino que están dispersas por todo el espacio de direcciones.
Normalmente, cada proceso tiene una tabla de páginas asociada. Hay una entrada en la tabla para cada página utilizada por el proceso (o una entrada para cada página virtual). Esta representación es más natural porque los procesos se refieren a páginas mediante direcciones virtuales.
Luego, el sistema operativo traduce estas direcciones en direcciones de memoria física.
Dado que la tabla de páginas está ordenada por dirección virtual, el sistema operativo puede calcular la posición de la entrada correspondiente en la tabla de páginas y utilizar ese valor directamente. La desventaja de este enfoque es que cada tabla de páginas contiene millones de números. Se producirán problemas de rendimiento y se necesitará una gran cantidad de memoria para guardar la información de la tabla de páginas.
Además de los dos métodos anteriores, invertir la tabla de páginas también es una forma de resolver este problema.
Echemos un vistazo preliminar a la representación de IBM RT de la tabla de páginas invertidas:
Solo hay una entrada en la tabla de páginas invertidas para cada página o marco de memoria real. Cada entrada contiene la dirección virtual de una página almacenada en una ubicación de memoria real, así como información sobre el proceso propietario de la página. El proceso es como se muestra en la figura:
La información del proceso aquí es el identificador de dirección de espacio (ASID) mencionado anteriormente. La razón principal de esto es que las tablas de páginas invertidas a menudo contienen múltiples espacios de direcciones diferentes que asignan memoria física. Cada página lógica de un proceso específico se puede asignar a un marco físico correspondiente.
Los sistemas con tablas de páginas invertidas tendrán problemas para implementar la memoria disfrutada porque se implementa asignando múltiples espacios de direcciones a la misma dirección física. Este enfoque no se puede utilizar para tablas de páginas invertidas porque solo hay una entrada de página virtual por página física y una página física no puede tener varias direcciones virtuales disfrutadas.
La gestión de la memoria en un sistema IA-32 se puede dividir en dos partes, segmentación y paginación, que funcionan de la siguiente manera: la CPU genera direcciones lógicas y las entrega a la unidad de segmentación, que Una dirección lógica genera una dirección lineal. La CPU genera direcciones lógicas y las entrega a la unidad de segmentación, que genera una dirección lineal para cada dirección lógica.
La arquitectura IA-32 permite tamaños de segmento de hasta 4 Gigabytes, con un máximo de 16K segmentos por proceso. El espacio de direcciones lógicas de un proceso se divide en dos partes.
La primera parte consta de hasta 8K segmentos que son privados para un solo proceso.
La segunda parte también consta de hasta 8K segmentos que son privados para un solo proceso. es **** para todos los procesos.
La primera parte se almacena en la tabla de descriptores locales (LTD) y la segunda parte se almacena en la tabla de descriptores globales (GDT). Cada una de sus entradas tiene 8 bytes de longitud y contiene información sobre los detalles del segmento. Por ejemplo, direcciones base de segmentos y límites de segmentos.
La dirección lógica suele ser una matriz binaria (selector, desplazamiento) y el selector es un número de 16 bits:
Entre ellos, s es el número de segmento y g es el segmento en LTD En GDT o en GDT, p es información de protección.
El proceso de direccionamiento del segmento es:
Las páginas de la arquitectura IA-32 se pueden dividir en 4K y 4M. Para páginas 4K, IA-32 utiliza un método de paginación secundario. Para conocer los métodos de representación y direccionamiento de 32 bits, consulte Algoritmo de paginación secundaria.
Para mejorar la utilización de la memoria física, las tablas de páginas del IA-32 se pueden intercambiar al disco. Por lo tanto, las entradas en el directorio de páginas tienen un bit válido para indicar si la tabla de páginas a la que apunta la entrada está en la memoria o en el disco. Si la tabla de páginas está en el disco, el sistema operativo puede pasar 31 bits adicionales para indicar la ubicación en el disco de la tabla de páginas. Luego se transfiere a la memoria según sea necesario.
A medida que los desarrolladores de software descubrieron gradualmente el límite de memoria de 4 GB de las arquitecturas de 32 bits, las extensiones de direcciones de página ampliaron el Inter para permitir el acceso a espacios de direcciones físicas superiores a 4 GB.
La introducción de la extensión de dirección de página esencialmente extiende el esquema de paginación de dos niveles a un esquema de tres niveles, donde los dos últimos dígitos se utilizan para apuntar a la tabla de punteros del directorio de páginas.
La extensión de dirección de página aumenta el espacio de direcciones de 32 a 36 bits y es compatible tanto con Linux como con Mac OS X.
X8686 es un ejemplo de extensión de dirección de página.
X86-64 admite espacios de direcciones físicas y lógicas más grandes. La compatibilidad con un espacio de direcciones de 64 bits significa que se pueden direccionar la asombrosa cantidad de 2^64 bytes de memoria. Los sistemas de 64 bits tienen la capacidad de acceder a cantidades tan grandes de memoria, pero en la práctica, actualmente están diseñados para abordar muchas menos direcciones.
Las máquinas actualmente disponibles para la arquitectura x86-64 utilizan hasta cuatro niveles de paginación y admiten direcciones virtuales de 48 bits. Su tamaño de página puede ser de 4KB, 2MB o 1G.
Aunque los chips de Intel ocupan la mayor parte del mercado, la arquitectura de los dispositivos móviles siempre ha sido ARM de 32 bits. Los iPhones y iPads actuales tienen licencia de ARM, y los teléfonos inteligentes Android utilizan procesadores ARM.
Tamaños de página admitidos por ARM:
La arquitectura ARM también admite dos niveles de TLB (caché). Hay dos micro-TLB externamente: uno para datos y otro para instrucciones. El mini-TLB también admite el identificador de espacio de direcciones de proceso (ASID). Hay un TLB maestro internamente. La traducción de direcciones comienza en la capa microTLB. Si no se encuentra, se verifica el TLB principal; si no se encuentra, se realiza una búsqueda de hardware a través de la tabla de páginas.