linux - significa - ubuntu para i686

¿Por qué el tamaño de página de Linux(x86) 4 KB, cómo se calcula? (6)

Introducción

El primer procesador Intel que admitió la técnica de memoria virtual de paginación fue el Intel 80386 . El procesador soporta un solo tamaño de página, 4 KB. Desde su lanzamiento en 1985, tenemos que volver a ese período de tiempo para comprender por qué Intel eligió ese tamaño de página en particular.

Atlas fue la primera computadora que admitió la paginación con un tamaño de página de 3 KB y tuvo una profunda influencia en el diseño de la memoria virtual y la investigación relacionada motivada. El sistema fue diseñado entre 1958-1962. Es interesante observar que el tamaño de página compatible con el 80386 es algo similar al tamaño de página compatible con el Atlas, aunque el 80386 se diseñó unos 20 años después y las computadoras (y las cargas de trabajo que ejecutaron) han evolucionado radicalmente durante ese período de ¡hora! De hecho, muchas computadoras de ese período utilizaron tamaños de página que oscilan entre 0,5 y 5 KB. En ese momento, los investigadores dedicaron una gran cantidad de esfuerzo al estudio de sistemas de memoria virtual (paginación y segmentación).

Una de las grandes preguntas fue: ¿Cuál es el tamaño de página óptimo? Se publicó una gran cantidad de trabajos en los años 60 y 70 que intentan estudiar y comprender el impacto del tamaño de la página en el rendimiento de las aplicaciones y recomiendan o proporcionan pautas sobre cómo elegir un tamaño de página. Ciertamente hay una serie de artículos que nunca fueron publicados. Que yo sepa, esto incluye el documento de Intel que dice "... Por lo tanto, el tamaño de la página debe ser de 4 KB". Pero los factores que influyen o interactúan con el tamaño de la página y el proceso de elegir un tamaño de página (o varios tamaños de página para esa materia) son bien conocidos, que es lo que discutiré en esta respuesta a un nivel básico. También explicaré en particular por qué un tamaño de página de 4 KB es razonable.

El problema del tamaño de página

En el método de paginación, la memoria física se organiza como una secuencia de regiones contiguas de memoria, llamadas marcos de página, que son del mismo tamaño (que es la característica definitoria de la paginación ¹ ). Cada marco de página puede asignarse a una porción de igual tamaño de un espacio de direcciones virtuales, llamada página virtual.

Supongamos que una página consta de N bytes ² (lo que implica que un marco de página también tiene un tamaño de N bytes por definición) y considera un espacio de direcciones virtuales que consta de P páginas (es decir, los números de página son {0, 1, 2, ..., P - 1} y el número total de direcciones virtuales es N * P ). Supongamos también que el espacio de direcciones físicas consiste en marcos de página F (es decir, los números de marco de página son {0, 1, 2, ..., F - 1} y el número total de direcciones físicas es N * F ).

Dada una dirección virtual VA , se requiere un mecanismo (un dispositivo de mapeo ) para determinar la dirección física, PA , se asigna o se debe presentar un error de página en caso de que no se haya asignado. El dispositivo de mapeo usa una estructura de datos (la tabla de páginas) almacenada en algún lugar para realizar el mapeo. Debería haber una entrada en esa tabla para cada página virtual asignada que describa cómo se asigna la página y potencialmente algunos atributos adicionales (como los atributos de protección). El diseño de la entrada de la tabla de páginas, como verá, interactúa con el tamaño de la página. Discutiré el diseño de la entrada de la tabla de páginas en Intel 80386 más adelante.

El tamaño de una dirección virtual es log ₂ ( N * P ) y el tamaño de una dirección física es log ₂ ( N * F ). Algunos bits de VA representarían el desplazamiento dentro de la página, mientras que los otros bits representarían el número de página, lo que identifica la página utilizando el dispositivo de mapeo.

¿Cuántas opciones tenemos para el tamaño de la página? Bueno, puede ser tan poco como un byte hasta N * P o N * F , el que sea más pequeño. Eso es un montón de opciones.

Es conveniente que el tamaño de página sea una potencia de 2

Una dirección virtual, VA , es equivalente a un par de números de página y desplazamiento, ( PN , OFF ). El proceso de traducción debe ser lo más eficiente posible. Es conveniente para los programadores ³ que los bytes dentro de una página sean contiguos en el espacio de direcciones. De esta manera, las direcciones de los elementos dentro de una estructura de datos de múltiples bytes se pueden calcular con aritmética simple en una sola dirección, lo que constituiría la dirección base de la estructura de datos. Esto se puede lograr utilizando los bits de registro ₂ ( N ) menos significativos (redondeados) de una dirección virtual para representar el desplazamiento y el resto de los bits para representar el número de página.

Si N no es una potencia de 2, habrá algunos bits que se compartirán entre el desplazamiento y el número de página, dependiendo de los valores de estos bits. Al hacer N una potencia de 2, tal complicación no existe. Por lo tanto, sería conveniente utilizar tamaños de página con una potencia de 2. Todos los procesadores reales que admiten la paginación utilizan tamaños de página con una potencia de dos (aunque la unidad de direccionabilidad puede no ser de 8 bits), lo cual tiene sentido. Pero para ser honesto, no está claro si esto realmente importa. Usando la tecnología actual, si N es una potencia de 2 puede no tener un impacto medible en el rendimiento o cualquier otra métrica de interés. De hecho, en el futuro, a medida que se necesiten tamaños de página cada vez más grandes, puede suceder que algún tamaño de página que no sea una potencia de 2 sea mejor. Pero hasta ahora, esto no ha sucedido. El punto que trato de señalar aquí es que la opción de diseño de hacer que el tamaño de la página no sea una potencia 2 no debe descartarse automáticamente. Creo que esta es una buena oportunidad de investigación en futuros sistemas de memoria virtual.

De todos modos, teniendo en cuenta que la elección de páginas de 4 KB se realizó en los años 80, se demostró que tales variaciones extremadamente pequeñas en el tamaño de las páginas (tanto teóricamente como experimentalmente) tenían poca importancia. Así triunfó la conveniencia de los tamaños de página de potencia de 2. Esto reduce el número de tamaños de página para considerar exponencialmente. Pero todavía tenemos una buena gama de opciones.

Favorecer los tamaños de página más pequeños

Dado que el dispositivo de mapeo funciona a nivel de páginas, la unidad de asignación desde la perspectiva del sistema operativo es una página virtual ⁴ . Incluso si una aplicación necesita asignar solo 1 byte, aún debe indicar al sistema operativo que asigne una página virtual completa para ese 1 byte. Este problema se llama fragmentación interna . Cada aplicación (o tal vez incluso cada componente de una aplicación) tiene su propio espacio de direcciones virtuales desde el cual asigna memoria en porciones de tamaño de página. Se espera de cada aplicación que no use una sola página para un solo objeto que asigna, sino que asigne tantos objetos como sea posible desde la misma página antes de que asigne más páginas. Sin embargo, debido a que los atributos de la página funcionan a nivel de las páginas, la misma aplicación puede usar múltiples administradores de memoria en modo de usuario (como cuando se usan múltiples tiempos de ejecución de C / C ++), y es difícil para la aplicación compartir partes de las páginas que no están usando con otras aplicaciones, la fragmentación interna puede ocurrir en muchas páginas del sistema. El uso de tamaños de página más pequeños puede ayudar a reducir la cantidad de memoria física desperdiciada (para todo el sistema) y virtual (por proceso).

Además, las aplicaciones suelen pasar por varias fases a lo largo de su vida útil, donde presentan diferentes requisitos de memoria en diferentes fases. Si el tamaño de la página es, digamos, de 16 KB, pero muchas aplicaciones pueden requerir solo menos de 10 KB para muchas de sus fases, entonces se perderá mucha memoria física, lo que puede llevar a situaciones de falta de memoria que podrían tener se evitó si se admitieran tamaños de página más pequeños, como 8 o 4 KB.

Los tamaños de página más pequeños son preferibles para manejar los errores de página de copia en escritura, ya que cuanto más pequeña es la página, tomaría menos tiempo crear una copia de la misma. Para tamaños de página extremadamente pequeños, esto puede no hacer ninguna diferencia medible, dependiendo del ancho de banda del bus de memoria.

Las cantidades típicas de memoria física disponibles en las computadoras en los años 70 estaban en el rango de 10 o 100 de KB. No tendría sentido tener tamaños de página de cientos de KB o más. De hecho, los conjuntos de aplicaciones de trabajo en ese momento eran típicamente solo unas pocas decenas de KB. Por lo tanto, es improbable que incluso los tamaños de página tan pequeños como 16 KB sean prácticos porque solo un par de páginas pueden consumir toda la memoria física disponible. El tamaño de la página debe ser coherente con la cantidad de memoria física. Por supuesto, este argumento puede aplicarse a los sistemas actuales (no tendría sentido tener páginas de 128 GB, por ejemplo).

Por lo tanto, considerando los tamaños de los conjuntos de trabajo y la disponibilidad de memoria física de los 70 y principios de los 80 , el tamaño de la página debe ser una potencia de 2 en el rango 2 ⁰ -2 ¹⁴ . Genial, ahora solo tenemos 15 opciones para elegir.

Favorecer tamaños de página más grandes

También podemos argumentar que los tamaños de página más grandes son mejores. Para el mismo conjunto de trabajo, los tamaños de página más pequeños implican un número mayor de páginas por aplicación, lo que requeriría entradas de la tabla de páginas para permitir la traducción. Esto requiere fundamentalmente tablas de páginas más grandes independientemente de la estructura de las tablas de páginas (aunque la sobrecarga exacta depende del diseño de la propia entrada de tabla de páginas, que trataré más adelante). Imagine tener, por ejemplo, páginas de 4 bytes y conjuntos de trabajo típicos de decenas de KB. Entonces, la mayor parte de la memoria física se asignaría para contener las tablas de páginas, no los datos. La búsqueda de tablas de páginas para el almacenamiento en segundo lugar conduce a fallas de doble página para referencias de memoria individuales, lo que sería absolutamente terrible para el rendimiento. Tal diseño es obviamente ridículo.

Esencialmente, el tamaño de la página no debe ser (mucho) más pequeño que el tamaño de conjunto de trabajo más pequeño posible que pueda ser. Esto elimina inmediatamente las páginas de tamaños 2 ⁰ -2 ⁶ , y nos deja 8 opciones. Los artículos de los años 70 y principios de los 80 que estudian el tamaño de las páginas estudian principalmente solo estas 8 opciones.

Hay otra razón que hace que las páginas de mayor tamaño sean ventajosas. Uno de los beneficios de la memoria virtual es poder usar de manera transparente el almacenamiento secundario además de la memoria principal para almacenar datos volátiles. Sin embargo, los dispositivos de almacenamiento secundario son mecánicos y funcionan mejor con transferencias a granel. Esto es más una pauta realmente y no debemos descartar ningún tamaño de página todavía. Existen dispositivos con diferentes diseños y características y, eventualmente, la ventaja de rendimiento de las transferencias masivas se saturará en algún momento. Pero ciertamente es algo que se debe tener en cuenta al medir el impacto de los tamaños de página en el rendimiento. Si el tipo de aplicaciones que se consideran muestran una pequeña localidad espacial, los tamaños de página más pequeños seguirían siendo preferibles porque la copia de bytes adicionales desde o hacia el disco no es exactamente gratis.

La localidad espacial de referencia fomenta el uso de ciertos tamaños de página. Para tamaños de página muy pequeños, es muy probable que todos los bytes de la página se utilicen en un período de tiempo reducido. A medida que aumenta el tamaño de una página, aumenta el número de bytes que tienen menos probabilidades de ser utilizados. Sin embargo, para páginas muy grandes, todo el conjunto de trabajo puede caber dentro de un pequeño número de páginas, independientemente de la localidad. Por lo tanto, para minimizar el número de fallas de página, el tamaño de la página debe ser demasiado pequeño o demasiado grande, pero no en el medio. Pero en última instancia, esto varía de una aplicación a otra. Los paradigmas de programación emergentes, como la programación orientada a objetos y la programación funcional, y las técnicas como el multihilo pueden reducir la localidad espacial debido al uso extensivo de estructuras vinculadas y la forma en que las diferentes aplicaciones interactúan entre sí. Los tamaños de página más grandes son preferibles para reducir el número de fallas de página. Sin embargo, los tamaños de página más pequeños pueden ser mejores para la memoria compartida entre varias aplicaciones para reducir la fragmentación interna de las páginas compartidas. También se ha demostrado experimentalmente que el número de marcos de página que se pueden mantener en la memoria principal está correlacionado con el número de fallas de página, favoreciendo tamaños de página más pequeños.

La necesidad de los TLB fue bien reconocida en ese momento. Intel los llamó cachés de página en sus patentes (no estoy seguro de si Intel fue el primero en usar ese término). Los TLB rápidos son muy importantes porque la traducción de direcciones está en la ruta crítica de ejecución de instrucciones. Para hacerlos lo más rápido posible, deben hacerse pequeños, pero luego solo pueden almacenar en caché un pequeño número de entradas de tabla de páginas. Esto motiva el uso de tamaños de página más grandes.

En la búsqueda del tamaño de página óptimo, resulta que no hay uno. En ese momento se sabía que existe la necesidad de admitir varios tamaños de página. De hecho, el sistema Multics diseñado en 1965 admitía páginas de 64 o 1.024 palabras (una palabra tiene un tamaño de 36 bits). Los tamaños de página en el rango 2 ⁷ -2 ¹⁴ se mostraron óptimos tanto empíricamente como teóricamente en diferentes escenarios. Intel debe haber observado que las páginas de 4 KB resultan en el mejor rendimiento promedio para las aplicaciones que sus clientes usaron en los años 80. Para las computadoras y aplicaciones de hoy en día, las pequeñas diferencias en el tamaño de las páginas no hacen mucha diferencia como solía ser en los años 70 y 80.

El diseño de la entrada de la tabla de páginas del Intel 80386

El diseño de la entrada del directorio de la página y la entrada de la tabla de la página se tratan en detalle en una patent Intel. Esto es importante porque el tamaño de la entrada de la tabla de páginas y la estructura general de la tabla de páginas se tuvieron en cuenta en muchos estudios sobre el tamaño de la página porque todos interactúan entre sí. Prefiero no discutir esto con más detalle para mantener la respuesta corta.

El tamaño de la página del futuro cercano

Intel recibió una patent un par de meses que aparentemente propone un sistema con un tamaño de página predeterminado de 64 KB, pero que al mismo tiempo admite páginas de 4 KB (y otros tamaños de página IA-32e) para compatibilidad con versiones anteriores. Cito de la patente:

Como resultado del soporte de la asignación de la página de 64 KB en las subpáginas de 4 KB, VA64 admite directamente todas las operaciones definidas actualmente en páginas de 4 KB, incluidos los bits de protección independientes por página de 4 KB y las asignaciones de direcciones arbitrarias alineadas de 4 KB. VA64 también admite la administración de páginas del kernel del sistema operativo en límites de 4 KB, incluso cuando el kernel del sistema operativo asigna memoria en unidades de 64 KB. Como resultado del soporte de páginas grandes, VA64 admite todas las divisiones del rango de direcciones virtuales en páginas que admite un sistema de paginación existente, como el sistema de paginación IA-32e de Intel Corporation. Por lo tanto, VA64 es compatible con aplicaciones y dispositivos de hardware que funcionan con un kernel del sistema operativo Windows® de 4 KB, mientras que también se aprovechan al máximo las páginas de 64 KB cuando se pueden usar páginas de 64 KB.
Las capacidades de VA64 pueden ser adoptadas gradualmente por el kernel del sistema operativo, en lugar de requerir que todas sean compatibles con la primera generación de kernel con capacidad para VA64. Por ejemplo, un kernel de sistema operativo compatible con VA64 podría comenzar asignando todas las páginas a los tamaños actuales (por ejemplo, 4 KB / 2 GB / 1 TB en el sistema de paginación IA-32e de Intel Corporation), pero cambiando a un nuevo formato de tabla de páginas. Después del cambio en el formato de la tabla de páginas, el kernel del sistema operativo podría modificarse para asignar memoria virtual en unidades de 64 KB y cambiar para almacenar páginas de 64 KB en su lista gratuita. Luego, el kernel del sistema operativo podría comenzar a usar páginas de 64 KB siempre que la alineación y las protecciones lo permitan, y agregar soporte para otras capacidades VA64.

No sé nada más sobre el sistema de paginación VA64 que no sea lo que está escrito en la patente. No hay nada en él en ningún lugar en Internet. Supongo que nos enteraremos más pronto.

Referencias seleccionadas

Denning, PJ (1970). Memoria virtual Encuestas de computación ACM, volumen 2, número 3, 153-189.

Gelenbe, E., Tiberio, P., y Boekhorst, JCA (1973). Tamaño de página en sistemas de paginación por demanda . Acta Informática, 3 (1), 1-23.

Alanko, TO, y Verkamo, AI (1983). Segmentación, paginación y tamaños de página óptimos en memoria virtual . Evaluación de desempeño, 3 (1), 13-33.

Corbató, FJ, y Vyssotsky, VA (1965). Introducción y visión general del sistema Multics . En las Actas del 30 de noviembre al 1 de diciembre de 1965, se celebró una conferencia informática conjunta, parte I (pp. 185-196).

Notas al pie

(1) En realidad, el tamaño de una sola página virtual puede ser múltiple del tamaño de un marco de página, pero no vayamos allí.

(2) Podemos generalizar la formulación y usar el término "palabra" para referirnos a la unidad de memoria más pequeña y accesible en lugar de byte, pero eso no es importante aquí.

(3) Tal vez no programadores, dependiendo del lenguaje de programación, sino compiladores, enlazadores, ensambladores y herramientas que funcionan con código binario.

(4) Ciertamente, es posible diseñar un sistema que admita el uso de paginación y no paginación al mismo tiempo, por lo que potencialmente soporta múltiples unidades de asignación, pero no vayamos allí.

El tamaño de página de memoria predeterminado del kernel de Linux en la arquitectura x86 era de 4 KB, me pregunto cómo se calculó eso y por qué.

Agrego esta respuesta / comentario porque el cálculo de sleepsort es muy interesante, tengo que agregarlo a mi página web (mencionando la fuente, por supuesto). Una respuesta (posible) a la pregunta de cómo puede calcular el tamaño de página mediante programación puede encontrarse here . La forma en que se calcula según lo mencionado por sleepsort es muy interesante. Hice lo mismo para x86_64 y el resultado no fue el que esperaba. Sin embargo, una lectura adicional sobre la administración de memoria x86_64 encontré que para inteligencia de 64 bits, no se usan 16 bits, déjenos 48 bits para que los calculemos. 9 bits para las ramas del árbol de memoria, cada una de las otras 9 bits, aquí en otras 9 para las ramas y finalmente 9 bits para las hojas de la última rama. Entonces 48 - 36 = 12 bits para cada dirección en la página de memoria. 2 ^ 12 = 4096 como se mencionó anteriormente por sleepsort. Me pregunto cuántos de los que pasa esta arquitectura es 3 o 4 (si alguien puede explicarlo) siguiendo el cálculo de Sleepsort:

2^x * 2^x * 2^x * 2^x * 2^y = 2^48 4x + y = 48 this time we have 8 bytes for each address (8 bytes * 8 bits / byte = 64 bits) 2^y / 2^3 = 2^x y - 3 = x filled in in previous equation: 4(y - 3) + y = 48 4y - 12 + y = 48 5y = 60 y = 12 because 2^y represents the pagesize, the size = 2^12 = 4096 bytes

Déjame con la pregunta "¿qué pasa con esas páginas enormes en Linux"?

Conseguí esto del artículo de wikipedia y cito:

El tamaño de la página suele estar determinado por la arquitectura del procesador.

Revisa el artículo de abajo:

http://en.wikipedia.org/wiki/Page_(computer_memory)

El diseño del tamaño de página normal de 4 KB de la arquitectura de 32 bits es realmente muy interesante :)

Y me gustaría agregar una respuesta adicional para demostrar por qué es razonable.

x86 utiliza ''2-pass'' para traducir direcciones de memoria virtual en direcciones de memoria física.

Así que asuma que tanto el directorio de páginas como la tabla de páginas contienen entradas, y el tamaño de la página es bytes Para hacer pleno uso de la dirección, tenemos:

Cada entrada en el directorio / tabla de páginas consume 4 bytes (32 bits), por lo tanto:

Así y = 12, y el tamaño de la página en bytes será = = 4KB.

¿Y qué pasa con ''1-pass''? Esto es interesante porque lógicamente podemos usar una sola tabla de páginas para la búsqueda de direcciones.

Supongamos que el directorio de la página contiene entradas, asignando una dirección a la página correspondiente, y el tamaño de la página es bytes

Una vez más, para hacer pleno uso de direcciones, necesitamos:

Obtenemos y = 17, y el tamaño de la página es = = 128KB.

De todos modos, esto funciona "lógicamente". Si presentamos TLB , un tamaño de memoria tan grande será un diaster: las páginas de memoria serán difíciles de encajar en TLB, y el diseño no será eficiente.

También podemos argumentar que, en la versión ''2-pass'', el directorio de la página y la tabla de la página pueden tener diferentes tamaños. Sin embargo, esto significa que usaremos un directorio de páginas más grandes, que ocupará más de una página de memoria. Lamentablemente, cada vez que se genera un nuevo proceso de usuario, para su propio directorio de páginas, el sistema operativo tiene que asignar páginas sucesivas, lo que no es elegante por su diseño.

El tamaño de página predeterminado se fija según lo que admite la MMU (unidad de administración de memoria) de la CPU. En el modo protegido de 32 bits, x86 admite dos tipos de páginas:

los normales, 4 KiB
enormes, 4 mib

No todos los procesadores x86 admiten páginas grandes. Uno necesita tener una CPU con capacidades de extensión de tamaño de página (PSE). Esto excluye los procesadores pre-Pentium. Prácticamente todas las CPUs x86 de la generación actual lo implementan.

4 KiB es también la granularidad de la página popuplar en otras arquitecturas. Se podría argumentar que este tamaño proviene de la división de una dirección virtual de 32 bits en dos índices de 10 bits en directorios / tablas de página y los 12 bits restantes dan el tamaño de página de 4 KiB.

Eso depende de la arquitectura del procesador .

El tamaño de página predeterminado es 4 KB en muchas arquitecturas. Generalmente se puede aumentar (a veces mucho, como 1 GB de AMD64) cambiando al modo de página grande . Esto permite que la tabla de páginas sea más pequeña, lo que puede resultar en mejoras de rendimiento.