Intel x86 Assembly Language & Microarchitecture
Paginación - Direccionamiento Virtual y Memoria

Introducción

Historia

Las primeras computadoras

Las primeras computadoras tenían un bloque de memoria en el que el programador colocaba el código y los datos, y la CPU se ejecutaba en este entorno. Dado que las computadoras eran muy caras, fue desafortunado que hiciera un trabajo, detuviera y esperara a que se cargara el siguiente trabajo y luego procesara ese.

Multiusuario, multiprocesamiento

Así, las computadoras rápidamente se volvieron más sofisticadas y admitieron múltiples usuarios y / o programas simultáneamente, pero ahí fue cuando empezaron a surgir problemas con la simple idea de "un bloque de memoria". Si una computadora ejecutaba dos programas a la vez, o si ejecutaba el mismo programa para múltiples usuarios (lo que, por supuesto, habría requerido datos separados para cada usuario), entonces la administración de esa memoria se volvió crítica.

Ejemplo

Por ejemplo: si un programa fue escrito para funcionar en la dirección de memoria 1000, pero otro programa ya estaba cargado, entonces el nuevo programa no pudo cargarse. Una forma de resolver esto sería hacer que los programas funcionen con "direccionamiento relativo": no importaba dónde se cargaba el programa, simplemente hacía todo lo relacionado con la dirección de memoria en la que estaba cargado. Pero eso requería soporte de hardware.

Sofisticación

A medida que el hardware de la computadora se hizo más sofisticado, fue capaz de admitir bloques más grandes de memoria, permitiendo más programas simultáneos, y se volvió más complicado escribir programas que no interfirieran con lo que ya estaba cargado. Una referencia de memoria extraviada podría reducir no solo el programa actual, sino también cualquier otro programa en la memoria, ¡incluido el propio sistema operativo!

Soluciones

Lo que se necesitaba era un mecanismo que permitiera a los bloques de memoria tener direcciones dinámicas . De esa manera, se podría escribir un programa para trabajar con sus bloques de memorias en direcciones que reconoció, y no poder acceder a otros bloques para otros programas (a menos que alguna cooperación lo permitiera).

Segmentación

Un mecanismo que implementó esto fue la segmentación. Eso permitió que se definieran bloques de memoria de todos los tamaños diferentes, y el programa tendría que definir a qué segmento quería acceder todo el tiempo.

Problemas

Esta técnica era poderosa, pero su misma flexibilidad era un problema. Dado que los segmentos esencialmente subdividieron la memoria disponible en trozos de diferentes tamaños, entonces la administración de la memoria para esos segmentos fue un problema: asignación, desasignación, crecimiento, reducción, fragmentación: todo esto requería rutinas sofisticadas y, a veces, copias en masa para implementar.

Paginacion

Una técnica diferente dividió toda la memoria en bloques de igual tamaño, llamados "Páginas", que hicieron que las rutinas de asignación y desasignación fueran muy simples, y eliminaron el crecimiento, la reducción y la fragmentación (excepto la fragmentación interna, que es simplemente un problema de pérdida).

Direccionamiento virtual

Al dividir la memoria en estos bloques, se podrían asignar a diferentes programas según sea necesario con cualquier dirección que el programa lo necesite. Esta "asignación" entre la dirección física de la memoria y la dirección deseada del programa es muy poderosa y es la base de la gestión de memoria de todos los procesadores principales (Intel, ARM, MIPS, Power y otros) en la actualidad.

Soporte de hardware y sistema operativo

El hardware realizó la reasignación de forma automática y continua, pero requirió memoria para definir las tablas de qué hacer. Por supuesto, la limpieza asociada con esta reasignación tuvo que ser controlada por algo. El sistema operativo tendría que distribuir la memoria según sea necesario y administrar las tablas de datos requeridas por el hardware para admitir lo que los programas requerían.

Características de paginación

Una vez que el hardware pudo hacer esta reasignación, ¿qué permitió? El controlador principal era el multiprocesamiento: la capacidad de ejecutar varios programas, cada uno con su "propia" memoria, protegidos entre sí. Pero otras dos opciones incluían "datos dispersos" y "memoria virtual".

Multiprocesamiento

A cada programa se le asignó su propio "Espacio de direcciones" virtual, un rango de direcciones a las que se les podía asignar memoria física, en cualquier dirección deseada. Siempre que haya suficiente memoria física para circular (aunque vea "Memoria virtual" a continuación), se podrían admitir numerosos programas simultáneamente.

Además, esos programas no podían acceder a la memoria que no estaba asignada a su espacio de direcciones virtuales; la protección entre programas era automática. Si los programas necesitaban comunicarse, podrían pedir al sistema operativo que organice un bloque de memoria compartido, un bloque de memoria física que se asignó en dos espacios de direcciones de programas diferentes simultáneamente.

Datos escasos

Permitir un gran espacio de direcciones virtuales (4 GB es típico, para corresponder con los registros de 32 bits que típicamente tienen estos procesadores) no desperdicia memoria en sí misma, si grandes áreas de ese espacio de direcciones no se asignan. Esto permite la creación de enormes estructuras de datos donde solo algunas partes se asignan a la vez. Imagine una matriz tridimensional de 1,000 bytes en cada dirección: ¡eso tomaría normalmente mil millones de bytes! Pero un programa podría reservar un bloque de su espacio de direcciones virtuales para "retener" estos datos, pero solo asignar pequeñas secciones a medida que se rellenaban. Esto hace que la programación sea eficiente, mientras que no desperdicie memoria en datos que aún no son necesarios.

Memoria virtual

Anteriormente, utilicé el término "direccionamiento virtual" para describir el direccionamiento virtual a físico realizado por el hardware. A menudo, esto se denomina "memoria virtual", pero ese término corresponde más correctamente a la técnica de uso del direccionamiento virtual para brindar una ilusión de más memoria de la que realmente está disponible.

Funciona así:

• A medida que los programas se cargan y solicitan más memoria, el sistema operativo proporciona la memoria de lo que tiene disponible. Además de realizar un seguimiento de la memoria asignada, el sistema operativo también realiza un seguimiento de cuándo se utiliza realmente la memoria: el hardware admite el marcado de páginas usadas.
• Cuando el sistema operativo se queda sin memoria física, mira toda la memoria que ya ha entregado para la página que menos se usó, o que no se usó por más tiempo. Guarda el contenido de esa página en particular en el disco duro, recuerda dónde estaba, lo marca como "No presente" en el hardware para el propietario original, y luego pone a cero la página y se la entrega al nuevo propietario.
• Si el propietario original intenta acceder a esa página nuevamente, el hardware notifica al sistema operativo. El sistema operativo luego asigna una nueva página (¡quizás tenga que realizar el paso anterior nuevamente!), Carga el contenido de la antigua página y luego entrega la nueva página al programa original.

  El punto importante a tener en cuenta es que, como cualquier página puede asignarse a cualquier dirección y cada página tiene el mismo tamaño, entonces una página es tan buena como cualquier otra, ¡siempre que el contenido siga siendo el mismo!

• Si un programa accede a una ubicación de memoria no asignada, el hardware notifica al sistema operativo como antes. Esta vez, el SO nota que no fue una página que se había guardado, por lo que la reconoce como un error en el programa, ¡y la termina!

  Esto es realmente lo que sucede cuando su aplicación se desvanece misteriosamente en usted, tal vez con un MessageBox del sistema operativo. También es lo que (a menudo) causa una infame pantalla azul o Sad Mac: ¡el programa de buggy era en realidad un controlador de sistema operativo que accedía a la memoria y no debería!

Decisiones de paginación

Los arquitectos de hardware necesitaban tomar algunas decisiones importantes sobre la paginación, ya que el diseño afectaría directamente el diseño de la CPU. Un sistema muy flexible tendría una gran sobrecarga, que requeriría grandes cantidades de memoria solo para administrar la infraestructura de paginación en sí.

¿Qué tan grande debe ser una página?

En hardware, la implementación más sencilla de Paging sería tomar una dirección y dividirla en dos partes. La parte superior sería un indicador de a qué página acceder, mientras que la parte inferior sería el índice en la página para el byte requerido:

+-----------------+------------+
| Page index      | Byte index |
+-----------------+------------+

Sin embargo, rápidamente se hizo evidente que las páginas pequeñas requerirían vastos índices para cada programa: incluso la memoria que no estaba asignada necesitaría una entrada en la tabla que lo indicara.

Así que en su lugar se utiliza un índice de múltiples niveles. La dirección se divide en varias partes (tres se indican en el ejemplo a continuación), y la parte superior (comúnmente llamada "Directorio") se indexa en la siguiente parte y así sucesivamente hasta que se decodifique el índice de bytes final en la página final:

+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+

Eso significa que un índice de directorio puede indicar "no asignado" para una gran parte del espacio de direcciones, sin requerir numerosos índices de página.

¿Cómo optimizar el uso de las tablas de páginas?

Deberá asignarse cada acceso a la dirección que hará la CPU, por lo que el proceso virtual a físico debe ser lo más eficiente posible. Si se implementara el sistema de tres niveles descrito anteriormente, eso significaría que cada acceso a la memoria sería en realidad tres accesos: uno en el Directorio; uno en la tabla de páginas; Y luego, finalmente, los datos deseados en sí. Y si la CPU también necesita realizar tareas de limpieza, como indicar que esta página ya se ha accedido o escrito, entonces se necesitarían más accesos para actualizar los campos.

La memoria puede ser rápida, pero esto impondría una desaceleración triple en todos los accesos de memoria durante la paginación. Afortunadamente, la mayoría de los programas tienen una "localidad de alcance", es decir, si acceden a una ubicación en la memoria, es probable que los accesos futuros estén cerca. Y dado que las Páginas no son demasiado pequeñas, esa conversión de mapeo solo debería realizarse cuando se accedió a una Página nueva: no para absolutamente todos los accesos.

Pero incluso mejor sería implementar un caché de páginas de acceso reciente, no solo la más actual. El problema sería mantenerse al tanto de las páginas a las que se había accedido y de las que no: el hardware tendría que escanear a través de la caché en cada acceso para encontrar el valor almacenado en caché. Por lo tanto, la memoria caché se implementa como una memoria de contenido direccionable: en lugar de acceder a ella por dirección, se accede a ella mediante el contenido; si los datos solicitados están presentes, se ofrece, de lo contrario, se marca una ubicación vacía para que se complete. El caché maneja todo eso.

Este caché de contenido direccionable a menudo se denomina un búfer de traducción (TLB), y debe ser administrado por el sistema operativo como parte del subsistema de direccionamiento virtual. Cuando el sistema operativo modifica los directorios o las tablas de páginas, debe notificar a la TLB para actualizar sus entradas, o simplemente para invalidarlas.

80386 Paginación

Diseño de alto nivel

El 80386 es un procesador de 32 bits, con un espacio de memoria direccionable de 32 bits. Los diseñadores del subsistema de paginación señalaron que un diseño de página 4K se asignó a esos 32 bits de forma bastante ordenada: 10 bits, 10 bits y 12 bits:

+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+
 3         2 2          1 1          0  Bit
 1         2 1          2 1          0  number

Eso significaba que el índice de bytes era de 12 bits de ancho, lo que se indexaría en una página 4K. Los índices del Directorio y de la Página eran de 10 bits, que se mapearían en una tabla de 1,024 entradas, y si esas entradas de la tabla fueran de 4 bytes, eso sería 4K por tabla: ¡también una Página!

Así que eso es lo que hicieron:

• Cada programa tendría su propio Directorio, una Página con 1.024 Entradas de Página que definían cada una de las siguientes páginas: si hubiera una.
• Si existiera, esa tabla de páginas tendría 1.024 entradas de página que cada una definía donde estaba la página del último nivel, si hubiera una.
• Si existiera, entonces esa Página podría tener su Byte directamente leído.

Entrada de página

Tanto el Directorio de nivel superior como la Tabla de páginas del siguiente nivel se componen de 1,024 Entradas de página. La parte más importante de estas entradas es la dirección de lo que está indexando: una tabla de páginas o una página real. Tenga en cuenta que esta dirección no necesita los 32 bits completos, ya que todo es una página, solo los 20 bits principales son significativos. Por lo tanto, los otros 12 bits en la Entrada de página se pueden usar para otras cosas: si el siguiente nivel está incluso presente; limpieza de si la página ha sido visitada o escrita; ¡E incluso si las escrituras deberían ser permitidas!

+--------------+----+------+-----+---+---+
| Page Address | OS | Used | Sup | W | P |
+--------------+----+------+-----+---+---+
Page Address = Top 20 bits of Page Table or Page address
OS           = Available for OS use
Used         = Whether this page has been accessed or written to
Sup          = Whether this page is Supervisory - only accessible by the OS
W            = Whether this page is allowed to be Written
P            = Whether this page is even Present

Tenga en cuenta que si el bit P es 0, entonces el resto de la entrada puede tener cualquier cosa que el sistema operativo quiera poner allí, como por ejemplo, donde el contenido de la página debería estar en el disco duro.

Page Directory Base de Registro ( PDBR )

Si cada programa tiene su propio Directorio, ¿cómo sabe el hardware dónde comenzar el mapeo? Dado que la CPU solo ejecuta un programa a la vez, tiene un único Registro de control para mantener la dirección del Directorio del programa actual. Este es el Registro de Base de Directorio de Páginas ( CR3 ) A medida que el SO cambia entre diferentes programas, actualiza el PDBR con el Directorio de páginas correspondiente al programa.

Fallas de la página

Cada vez que la CPU accede a la memoria, debe asignar la dirección virtual indicada a la dirección física apropiada. Este es un proceso de tres pasos:

1. Indexe los 10 bits principales de la dirección en la página indicada por el PDBR para obtener la dirección de la tabla de páginas apropiada;
2. Indexe los siguientes 10 bits de la dirección en la Página indicada por el Directorio para obtener la dirección de la Página correspondiente;
3. Indexe los últimos 12 bits de la dirección para obtener los datos de esa página.

Debido a que los pasos 1. y 2. anteriores utilizan entradas de página, cada entrada podría indicar un problema:

• El siguiente nivel puede estar marcado "No presente";
• El siguiente nivel puede marcarse como "Sólo lectura", y la operación es una escritura;
• El siguiente nivel puede estar marcado como "Supervisor", y es el programa que accede a la memoria, no al sistema operativo.

Cuando el hardware detecta un problema de este tipo, en lugar de completar el acceso, genera un error: Interrumpir n. ° 14, el error de página. También completa algunos Registros de control específicos con la información de por qué ocurrió la falla: la dirección a la que se hace referencia; si era un acceso de Supervisor; y si fue un intento de escritura.

Se espera que el sistema operativo atrape esa falla, decodifique los registros de control y decida qué hacer. Si se trata de un acceso no válido, puede terminar el programa de fallas. Sin embargo, si se trata de un acceso a la memoria virtual, el sistema operativo debería asignar una nueva página (¡es posible que deba desocupar una página que ya esté en uso!), Llenarla con el contenido requerido (todos los ceros o el contenido anterior cargado desde el disco) ), asigne la nueva página en la tabla de páginas apropiada, márquela como presente y luego reanude la instrucción de fallas. Esta vez, el acceso avanzará con éxito, y el programa continuará sin saber que ocurrió algo especial (¡a menos que eche un vistazo al reloj!)

80486 Paginación

El subsistema de paginación 80486 era muy similar al de 80386. Era compatible con versiones anteriores, y las únicas características nuevas eran permitir el control de la memoria caché página por página; los diseñadores del sistema operativo podían marcar páginas específicas para que no se almacenaran en la caché, o usar diferentes escrituras o reescrituras Técnicas de almacenamiento en caché.

En todos los demás aspectos, es aplicable el ejemplo "80386 Paginación".

Paginación Pentium

Cuando se estaba desarrollando el Pentium, el tamaño de la memoria y los programas que se ejecutaban en ellos se hacían más grandes. El sistema operativo tenía que hacer cada vez más trabajo para mantener el subsistema de paginación solo en la cantidad de índices de páginas que debían actualizarse cuando se utilizaban grandes programas o conjuntos de datos.

Así que los diseñadores de Pentium agregaron un truco simple: pusieron un bit extra en las Entradas del Directorio de páginas que indicaban si el siguiente nivel era una Tabla de páginas (como antes), ¡o si iban directamente a una página de 4 MB! Al tener el concepto de 4 MB de páginas, el sistema operativo no tendría que crear una tabla de páginas y rellenarla con 1.024 entradas que básicamente eran direcciones de indexación 4K más altas que la anterior.

Diseño de la dirección

+-----------+----------------------+
| Dir Index | 4MB Byte Index       |
+-----------+----------------------+
 3         2 2                    0   Bit
 1         2 1                    0   number

Diseño de entrada de directorio

+-----------+----+---+------+-----+---+---+
| Page Addr | OS | S | Used | Sup | W | P |
+-----------+----+---+------+-----+---+---+
Page Addr = Top 20 bits of Page Table or Page address
OS        = Available for OS use
S         = Size of Next Level: 0 = Page Table, 1 = 4 MB Page
Used      = Whether this page has been accessed or written to
Sup       = Whether this page is Supervisory - onlly accessible by the OS
W         = Whether this page is allowed to be Written
P         = Whether this page is even Present

Por supuesto, eso tuvo algunas ramificaciones:

• La página de 4 MB tenía que comenzar en un límite de dirección de 4 MB, al igual que las páginas de 4K tenía que comenzar en un límite de dirección de 4K.
• Todos los 4 MB tenían que pertenecer a un solo programa, o ser compartidos por varios.

Esto era perfecto para el uso de periféricos de gran memoria, como adaptadores de gráficos, que tenían grandes ventanas de espacio de direcciones que necesitaban ser asignadas para que las usara el sistema operativo.

Extensión de dirección física (PAE)

Introducción

A medida que disminuían los precios de la memoria, las PC basadas en Intel podían tener más y más RAM de manera asequible, aliviando los problemas de muchos usuarios al ejecutar muchas de las aplicaciones cada vez más grandes que se producían simultáneamente. Mientras que la memoria virtual permitía que la memoria se "creara" virtualmente - el intercambio de los contenidos "antiguos" existentes en el disco duro para permitir que se almacenen los datos "nuevos" - esto ralentizó la ejecución de los programas, ya que la página "golpeando" se mantiene continuamente intercambiando datos Encendido y apagado del disco duro.

Más memoria RAM

Lo que se necesitaba era la capacidad de acceder a más RAM física, pero ya era un bus de direcciones de 32 bits, por lo que cualquier aumento requeriría registros de direcciones más grandes. ¿O sería? Al desarrollar el Pentium Pro (e incluso el Pentium M), como una interrupción hasta que se puedan producir procesadores de 64 bits, para agregar más bits de dirección física (lo que permite más memoria física) sin cambiar el número de bits de registro. Esto podría lograrse ya que las direcciones virtuales se asignaron a direcciones físicas de todos modos, todo lo que se necesitaba para cambiar era el sistema de mapeo.

Diseño

El sistema existente podría acceder a un máximo de 32 bits de direcciones físicas. Aumentar esto requiere un cambio completo de la estructura de Entrada de página, de 32 a 64 bits. Se decidió mantener la granularidad mínima en páginas 4K, por lo que la entrada de 64 bits tendría 52 bits de dirección y 12 bits de control (como la entrada anterior tenía 20 bits de dirección y 12 bits de control).

Tener una entrada de 64 bits, pero un tamaño de página de (aún) 4K, significaba que solo habría 512 entradas por tabla de página o directorio, en lugar de las 1.024 anteriores. Eso significaba que la dirección virtual de 32 bits se dividiría de manera diferente a antes:

+-----+-----------+------------+------------+
| DPI | Dir Index | Page Index | Byte Index |
+-----+-----------+------------+------------+
 3   3 2         2 2          1 1          0   Bit
 1   0 9         1 0          2 1          0   number

 DPI        = 2-bit index into Directory Pointer Table
 Dir Index  = 9-bit index into Directory
 Page Index = 9-bit index into Page Table
 Byte Index = 12-bit index into Page (as before)

Al cortar un bit del Índice de directorio y del Índice de página, se obtuvieron dos bits para un tercer nivel de asignación: llamaron a esto la Tabla de punteros del directorio de páginas (PDPT), una tabla de exactamente cuatro entradas de 64 bits que se dirigían a cuatro directorios en lugar de la anterior. uno. El PDBR ( CR3 ) ahora apuntaba al PDPT en su lugar, que, dado que CR3 era solo de 32 bits, necesitaba ser almacenado en los primeros 4 GB de RAM para accesibilidad. Tenga en cuenta que, dado que los bits bajos de CR3 se utilizan para el control, el PDPT debe comenzar en un límite de 32 bytes.

Extensión de tamaño de página (PSE)

Y, dado que las páginas de 4 MB anteriores eran una buena idea, querían poder admitir páginas grandes de nuevo. Sin embargo, esta vez, la eliminación de la última capa del sistema de niveles no produjo 10 + 12 bit 4MB Pages, sino 9 + 12 bit 2MB Pages.

PSE-32 (y PSE-40)

Dado que el modo de Extensión de Dirección Física (PAE) que se introdujo en el Pentium Pro (y Pentum M) fue un cambio en el subsistema de administración de memoria del Sistema Operativo, cuando Intel diseñó el Pentium II, decidieron mejorar el modo de página "normal" para admite los nuevos bits de dirección física del procesador dentro de las entradas de 32 bits definidas anteriormente.

Se dieron cuenta de que cuando se utilizaba una página de 4 MB, la entrada de directorio tenía este aspecto:

+-----------+------------+---------+
| Dir Index |  Unused    | Control |
+-----------+------------+---------+

Las áreas de Índice de Direccionamiento y Control de la Entrada fueron las mismas, pero el bloque de bits no utilizados entre ellos, que sería utilizado por el Índice de Página si existiera, se desperdició. ¡Así que decidieron usar esa área para definir los bits de la dirección física superior a 31 !

+-----------+------+-----+---------+
| Dir Index |Unused|Upper| Control |
+-----------+------+-----+---------+

Esto permitió que los sistemas operativos que no adoptaron el modo PAE tuvieran acceso a una RAM superior a 4 GB; con un poco de lógica adicional, podrían proporcionar grandes cantidades de RAM extra al sistema, aunque no más que los 4 GB normales de cada programa. Al principio solo se agregaron 4 bits, lo que permite un direccionamiento físico de 36 bits, por lo que este modo se denominó Extensión de tamaño de página 36 (PSE-36). En realidad no cambió el tamaño de la página, solo el direccionamiento sin embargo.

Sin embargo, la limitación de esto fue que solo se podían definir páginas de 4 MB superiores a 4 GB, no se permitían las páginas 4K. La adopción de este modo no fue amplia : se informó que era más lenta que usar PAE, y Linux nunca terminó usándolo.

Sin embargo, en procesadores posteriores que tenían incluso más bits de dirección física, tanto AMD como Intel ampliaron el área de PSE a 8 bits, lo que algunas personas denominaron "PSE-40"