por Dario Alejandro Alpern
Hola. Mi nombre es Dario Alpern y hoy vamos a ver paginación en procesadores de 32 bits.
La memoria virtual es una característica del sistema operativo que permite que cada proceso tenga su propio espacio de direccionamiento independiente, lo que permite aislar las aplicaciones entre sí, mediante el método de la protección por paginación.
En este esquema, se subdivide el espacio direccionable del procesador en páginas iguales. En procesadores Intel, la longitud de las páginas es de 4 KB. Como se puede ver, hay una zona de memoria no paginada. Esta zona pertenece al sistema operativo y contiene código y datos que deben estar presentes todo el tiempo en la memoria del sistema. Por ejemplo, los manejadores de interrupción deben estar siempre en RAM.
A la derecha se observa el almacenamiento externo, que puede ser un disco rígido o actualmente SSD, que es la sigla en inglés de disco de estado sólido, implementado con memoria flash. También se subdivide en páginas de 4 KB.
Aquí se puede ver como el sistema operativo carga las páginas de diferentes procesos en memoria. En este caso cargamos tres páginas, pero en la realidad, como el tamaño de los programas se mide en megabytes, se cargan miles de páginas en memoria por cada proceso.
En la mayoría de los sistemas operativos, los procesos arrancan siempre en la misma dirección lineal (o virtual, como se la conoce en otros procesadores).
Vamos a suponer como se muestra en el diagrama que la página 1 comienza en la dirección lineal 0x00400000, la página 2 comienza en la dirección lineal 0x00401000 y la página 3 comienza en la dirección lineal 0x00402000.
Se puede ver que a la misma dirección lineal, le puede corresponder varias direcciones físicas. Recordemos que las direcciones físicas son aquellas que salen por el bus de direcciones hacia la memoria externa al procesador.
En el diagrama se ve lo que ocurre cuando el sistema operativo debe cargar en memoria el tercer programa, correspondiente a una planilla de cálculo.
Se puede observar que no hay suficiente memoria RAM. Lo que ocurre en ese caso es que se usa el almacenamiento externo para enviar las páginas menos recientemente utilizadas y de esa manera hacer espacio para cargar el nuevo programa.
Cuando el procesador necesite ejecutar o bien leer o escribir datos de una página descargada en el almacenamiento externo, no hay una traducción entre dirección lineal y dirección fisica de RAM. Entonces el procesador va a generar una excepción de fallo de página, que es la excepción 14, y el sistema operativo deberá recargar esa página en memoria física, mandando otra página a almacenamiento externo si está llena la memoria.
Si bien el almacenamiento externo permite correr más procesos, es muy lento enviar las páginas al medio externo y luego de nuevo a la RAM del sistema. Por eso normalmente se limita el área de almacenamiento externo al doble del tamaño de la RAM del sistema.
Como el sistema operativo carga las páginas en el primer espacio libre que encuentra, se puede ver que es posible que una instrucción se encuentre en zonas disjuntas de RAM, como en el caso de la segunda instrucción, donde el último byte se encuentra en una dirección física completamente diferente que los dos primeros bytes.
Está claro que la unidad de paginación debe ser capaz de traducir rápidamente entre las direcciones lineales, que fueron las generadas por el linker y las direcciones físicas, que es donde el procesador va a encontrar el código y los datos en la memoria.
El diagrama que se ve acá corresponde a la paginación como se implementó originalmente en el procesador 80386.
La dirección lineal se divide en tres campos: los diez bits más significativos corresponden al índice del directorio de páginas, los diez bits siguientes corresponden al índice de la tabla de páginas y por último los 12 bits menos significativos representan el offset dentro de la página.
Tanto el directorio de páginas como las tablas de páginas son tablas que inicializa el sistema operativo y que lee el procesador para poder realizar la traducción.
El procesador usa el registro CR3 como puntero a la dirección física del directorio de páginas. Esta tabla tiene 1024 entradas de 4 bytes cada uno y debe comenzar en una dirección física múltiplo de 4 KB, es decir que los 12 bits menos significativos de la dirección física que corresponda al primer byte del directorio debe ser 000.
Cada entrada del directorio se subdivide en dos campos: la base son los 20 bits más significativos y los atributos los 12 bits menos significativos. La base indica la dirección física donde comienza la tabla de páginas. Como la tabla de páginas también comienza en una dirección física múltiplo de 4 KB, entonces los 12 bits menos significativos de esa dirección no tienen información porque siempre valen 000 y sólo se usan los 20 bits más significativos de la dirección física, que es lo que se carga en el campo base. El campo atributos indica cómo se comportan las páginas.
Como se ve en el diagrama, a la dirección física de inicio del directorio apuntado por CR3, se suma el índice que se encuentra en los bits 31 a 22 de la dirección lineal, multiplicado por 4, que es la longitud de cada entrada en el directorio.
De allí se obtiene el puntero al inicio de la tabla de páginas y se repite el proceso sumando el índice que se encuentra en los bits 21 a 12 de la dirección lineal, multiplicado por 4.
Ahí se obtiene la dirección física inicial de la página. El offset dentro de la página no se traduce, entonces los bits 11 a 0 de la dirección lineal siempre coinciden con los bits 11 a 0 de la dirección física.
A continuación veremos cuáles son los atributos que se encuentran en las tablas de paginación.
El bit 8 es el bit global. Este bit solo es válido para la tabla de páginas y si el bit 7 del registro de control CR4 denominado PGE (Page Global Enable) vale 1. Cuando se modifica el valor del registro CR3 apuntamos a un directorio de páginas diferente, lo que significa que las traducciones de direcciones lineales a direcciones físicas cambia completamente. Debido a ello, el procesador borra la TLB, que es una tabla interna que almacena las últimas traducciones hechas. Sin embargo, no se borran las traducciones que corresponden a páginas globales.
En bit 7 es el de tamaño de página (PS o Page Size en inglés). Este bit solo es válido para el directorio de páginas y si el bit 4 del registro de control CR4 denominado PSE (Page Size Enable) vale 1. Cuando PS vale cero, el campo base de la entrada de directorio apunta a una tabla de páginas, y si vale uno, el campo base apunta a una página grande de 4 MB. En este caso, los bits 21 a 0 de la dirección lineal corresponden al offset dentro de la página grande.
El bit 6 indica si algún byte de la página se escribió. Esto sirve para optimizar la copia a almacenamiento externo, que no hace falta si la página no fue modificada.
El bit 5 indica si la página fue accedida.
Cuando el bit 4 vale cero, indica que el caché está habilitado para la página. Cuando vale uno, no se usa el caché para la página.
Si el caché está habilitado, el bit 3 indica la política de escritura que se utiliza. Si vale cero, se utiliza write-back, mientras que si vale uno, se usa write-through.
En el caso de la RAM, hay que poner ambos bits a cero para que se use el caché, que es mucho más rápido que la RAM. Si tuviéramos un hardware mapeado a memoria, como un termómetro por ejemplo, se debe deshabilitar el caché en esa página para forzar que la lectura se haga siempre desde el termómetro.
Si el bit 2 vale 1 indica que la página corresponde al usuario (CPL = 3) y si es cero, al supervisor (CPL < 3).
El bit 1 es el permiso de escritura. Si el vale 1 se puede escribir en memoria.
Si el bit 0 vale uno, la página existe en memoria.
Cuando el atributo del directorio no coincide con el de la tabla de páginas, se toma el más restrictivo de los dos:
Si uno es presente y otro es no presente, el procesador elige no presente.
Si uno tiene habilitación de escritura y otro sólo lectura, se elige sólo lectura.
En el caso del atributo usuario/supervisor, como el usuario no puede acceder a una página con atributo supervisor, entonces supervisor es más restrictivo que usuario, por lo tanto, si uno tiene atributo usuario y el otro supervisor, se elige supervisor.
Aquí se puede observar si el procesador puede leer o escribir dependiendo de los atributos usuario/supervisor y habilitación de escritura y el código que está corriendo: si es usuario o supervisor.
Se puede observar que el código de usuario no puede leer ni escribir páginas de supervisor. Tampoco puede escribir en páginas de usuario de solo lectura.
Cuando corre el supervisor, el comportamiento depende del indicador Write Protect, que es bit 16 del registro de control CR0. Cuando Write Protect vale cero, el supervisor puede leer y escribir en cualquier página presente, sin importar el valor de los atributos usuario/supervisor ni el de habilitación de escritura.
Si Write Protect vale 1, El procesador solo tiene en cuenta el atributo de habilitación de escritura. Si el atributo está encendido, el supervisor puede leer o escribir en la página. En caso contrario sólo puede leer.
Veremos un ejemplo para afianzar los conceptos.
Suponiendo que el directorio de páginas se encuentra en la dirección física 0x00100000 y las tablas de páginas a continuación, indicar el valor de CR3 y las direcciones con el contenido a escribir en las tablas para que a la dirección lineal 0xAA234889 le corresponda la dirección física 0x44522889. Todas las páginas son de supervisor y de lectura/escritura.
Como sabemos que los 12 bits menos significativos de las direcciones lineales no se traducen, primero comprobamos que esto ocurra. Ambas direcciones terminan con los tres nibbles menos significativos en 889, así que está bien.
En base a lo indicado en el enunciado, como el directorio comienza en la dirección física 0x00100000, este es el valor a cargar en el registro CR3.
A la izquierda se ve el mapa de memoria como indica el enunciado: el directorio a partir de la dirección física 0x00100000 y las tablas de paginación a continuación.
A la derecha se puede ver como queda el directorio para que las bases apunten a las diferentes tablas de páginas. Para los atributos, seleccionamos supervisor, entonces el bit 2 debe valer cero, permiso de escritura, entonces el bit 1 debe valer uno y finalmente página presente, por lo que el bit 0 también vale uno. De esta manera el atributo queda con el valor 3.
Lo primero que debemos hacer es convertir la dirección lineal de hexadecimal a binario. Esto es sencillo porque los números hexadecimales siempre se corresponden con cuatro bits. En la conversión separé los bits en grupos de cuatro para facilitar la traducción.
Luego separamos la parte alta en rojo, que corresponde al índice del directorio y la parte baja en azul, que corresponde al índice de la tabla de páginas.
Una vez obtenidos ambos índices en hexadecimal, podemos ver qué dirección del directorio se debe modificar y qué dato hay que escribir.
Como cada elemento del directorio tiene 4 bytes, multiplicamos el índice por 4 para obtener el offset dentro del directorio. A este valor le sumamos la dirección física de inicio del directorio. Así obtenemos la dirección 0x00100AA0.
El contenido a escribir tiene dos partes: la base que es lo que deberemos hallar, y el atributo, que vale 3 como ya habíamos comentado.
La base es igual a la dirección física de la tabla de pagínas número 0x2A8. Las tablas de páginas están almacenadas una a continuación de la otra a partir de la dirección 0x00101000. Como el tamaño de cada tabla es 0x1000, sumaremos a la dirección física de la tabla de páginas cero, que es 0x00101000, el número de la tabla de página 0x2A8 por la longitud de cada tabla de páginas, que es 0x1000. Al resultado le sumaremos 3, que es el atributo. El resultado es 0x003A9003.
Con respecto a la dirección de la tabla a escribir y su contenido, a la dirección física del inicio de la tabla de página que es 0x003A9000, le sumamos el índice de la tabla de páginas que es 0x234 por 4, que es la longitud de cada entrada de la tabla de páginas. El resultado es 0x003A98D0.
El contenido a escribir es la base de la página, que es 0x44522000 más el atributo que vale 3. El resultado es 0x44522003.
El Pentium Pro, lanzado en el mercado a fines de 1995, fue el primer procesador de Intel de la serie x86 con más de 32 bits de bus de direcciones. Este procesador podía direccionar 64 GB con sus 36 bits de bus de direcciones.
Como las direcciones lineales seguían siendo de 32 bits, tuvieron que cambiar el esquema para acceder a direcciones físicas de más de 32 bits. La siguiente potencia de 2 es 64 bits. De esta manera, todas las entradas de las tablas de paginación tienen una longitud de 64 bits, es decir de 8 bytes.
Como las tablas siempre tienen 4 KB de longitud, la cantidad de entradas se reduce a la mitad, es decir, 512 entradas.
De esta manera, ahora los índices tienen 9 bits en vez de 10. En el diagrama se puede observar que tanto el índice del directorio de páginas como el índice de la tabla de páginas tienen 9 bits cada uno. Como sobran 2 bits, se agregó una tabla adicional de 4 elementos llamado puntero a directorio de páginas.
El registro CR3 apunta ahora al puntero a directorio de páginas. Como el registro CR3 tiene 32 bits, la dirección física del puntero de directorio de páginas debe estar por debajo de los 4 GB. Además debe estar alineado a múltiplo de 32 bytes.
Dentro de las tablas, los atributos ocupan los bits 63 a 56 y 11 a 0. El resto corresponde a la base.
Este sistema es incompatible con el anterior y se habilita poniendo a uno el bit 5 del registro de control CR4 denominado PAE (Physical Address Extension).
Aquí se pueden ver las diferencias más significativas en la paginación según si PAE está activo o no.
Cuando PAE, que es el bit 5 de CR4 vale uno, hay tres niveles de paginación. Si vale cero, hay dos.
Cuando PAE está habilitado, las entradas de las tablas de paginación tienen 64 bits, en caso contrario, 32 bits.
Cuando PAE está habilitado, las páginas grandes, aquellas con el atributo Page Size a 1 en el directorio de páginas, ocupan 2 MB, en caso contrario ocupan 4 MB.
Cuando PAE está habilitado, también están habilitadas las páginas grandes, pero PSE (Page Size Enable) que es el bit 4 de CR4, debe estar a cero.
Con PAE activado, se agrega el atributo de no ejecución, que se ubica en el bit 63. Si la página está marcada como de no ejecución, ocurrirá una excepción de fallo de página si se intenta ejecutar una instrucción obtenida de dicha página.
Aquí se muestra el código de error que ingresa en la pila cuando el procesador llama al manejador de la excepción de fallo de página. Además, el procesador pone en el registro CR2 la dirección lineal que causó el fallo de página.
El bit 0 indica si el fallo se dio por página presente o no.
El bit 1 indica si el fallo ocurrió durante una escritura, si está a uno, o durante una lectura, si el bit está a cero.
El bit 2 está encendido si la falla ocurrió con CPL = 3, correspondiente al usuario. Vale cero si CPL < 3, que corresponde al supervisor.
El bit 3 se enciende si las entradas de directorio o de tabla de páginas tienen un "1" en un campo reservado. Esto solo puede ocurrir si PSE o PAE valen uno.
Cuando está encendido el bit 4, indica que la falla ocurrió por intentar ejecutar una instrucción. Esto solo puede ocurrir si el atributo de no ejecución está activado.
Cuando PAE está desactivado, para traducir de direcciones lineales a direcciones físicas, el procesador debe leer dos direcciones de memoria, una correspondiente al directorio y otra de la tabla de páginas. Esto ralentizaría enormemente la ejecución de los programas ya que haría falta tres accesos a memoria por cada acceso que requiera el programa.
Para solucionar este inconveniente, dentro de la unidad de paginación, el procesador tiene una memoria caché completamente asociativa que almacena las últimas traducciones.
La memoria asociativa compara el dato de entrada, en este caso la dirección lineal proveniente de la unidad de segmentación con todas las direcciones lineales que se encuentren activas en el TLB en el mismo ciclo de reloj. Si hay coincidencia, el TLB devuelve la dirección física y los atributos de la página que corresponden con esa dirección lineal.
Si no se encuentra la dirección lineal en el TLB, el procesador deberá leer las tablas de paginación que se encuentran en memoria externa para poder realizar la traducción a memoria física.
En el diagrama se puede ver el TLB cuyo tamaño depende del procesador. Por ejemplo, en el 80386, la TLB original tenía 32 entradas.
En procesadores más modernos, hay una TLB por tamaño de página. Así, hay un TLB para páginas de 4 KB y otra para páginas de 2 MB y 4 MB.
Tanto las direcciones lineales como las físicas no incluyen los bits de offsets de página. Es decir que tienen 20 bits si PAE = 0.
Tanto la dirección física como los atributos de pagína se cargan en la TLB cuando se realiza la primera traducción de esa dirección lineal.
Los atributos de caché contienen información que indican si la entrada es válida, o cuándo liberar la traducción si la TLB se llena, usando la política LRU (Least Recently Used en inglés).
Existen dos maneras de borrar la TLB: escribiendo el registro CR3 o utilizando la instrucción INVLPG.
Cuando se modifica el valor del registro CR3 apuntamos a un directorio de páginas diferente, lo que significa que las traducciones de direcciones lineales a direcciones físicas cambia completamente. Debido a ello, el procesador borra la TLB. Sin embargo, no se borran las traducciones que corresponden a páginas globales, que se podrían usar para apuntar a la zona no paginada.
La instrucción INVLPG sirve para borrar la traducción que se refiera a la posición de memoria indicada por dicha instrucción. En este caso no importa el valor del atributo global.
Aquí se muestran los pasos necesarios para activar la unidad de paginación.
Primero se deben preparar las tablas de paginación asegurando que el código que contenga la habilitación de la unidad de paginación esté en identity mapping, lo que significa que las direcciones lineales y las físicas coinciden.
Después debemos asegurarnos que el flag de interrupción esté apagado mediante la instrucción CLI.
A continuación habilitaremos o no PAE en base al tipo de paginación que necesitemos. Por ejemplo, si necesitamos acceder más allá de los 4 GB, entonces PAE debe estar activado.
Luego cargamos en el registro CR3 el puntero a la dirección física del directorio de páginas si PAE no está habilitado o al puntero de directorio de páginas si lo está.
Si PAE no está habilitado pero necesitamos pagínas grandes de 4 MB, deberemos activar PSE.
Finalmente habilitaremos la paginación activando el bit 31 de CR0.
Espero que les haya sido de interés. Hasta luego.