Elementos de diseño del sistema de Memoria Virtual de FreeBSD

Antes de avanzar con el diseño real dediquemos un poco de tiempo a la necesidad de mantener y modernizar cualquier base de código de larga duración. En el mundo de la programación, los algoritmos tienen a se más importantes que el código y es precisamente debido a las raíces académicas de BSD que una gran parte de la atención se puso desde el comienzo en el diseño algorítmico. Prestar más atención al diseño generalmente lleva a una base de código limpio y flexible que puede ser modificado fácilmente, extendido o reemplazado a lo largo del tiempo. Aunque BSD es considerado por alguna gente como un sistema operativo"viejo", aquellos de nosotros que trabajamos en él solemos verlo más como una base de código"madura" la cual tiene varios componentes modificados, extendidos, o reemplazados con código moderno. Ha evolucionado, y FreeBSD está a la vanguardia independientemente de cómo de viejo sea parte del código. Es importante hacer esta distinción y que mucha gente pasa por alto. El mayor error que puede cometer un programador es no aprender de la historia, y es precisamente este error el que han cometido muchos otros sistemas operativos modernos. Windows NT® es el mejor ejemplo, y las consecuencias han sido nefastas. Linux también comete este error hasta cierto punto—lo suficiente para que nosotros la gente de BSD hagamos pequeñas bromas de vez en cuando, por lo menos. El problema de Linux es simplemente la falta de experiencia y de una historia contra la que comparar ideas, un problema que está siendo tratado rápidamente por la comunidad Linux de la misma forma que ha sido tratado en la comunidad BSD—mediante el desarrollo continuo de código. La gente de Windows NT®, por otro lado, repiten los mismos errores solucionados por UNIX® hace décadas y pasan años arreglándolos. Una y otra vez. Sufren un caso severo de "no diseñado aquí" y "siempre tenemos la razón porque nuestro departamento de marketing así lo dice". Tengo poca tolerancia hacia cualquiera que no puede aprender de la historia.

Mucha de la aparente complejidad del diseño de FreeBSD, especialmente en el subsistema de Memoria Virtual/Intercambio, es un resultado directo de tener que resolver serios problemas de rendimiento que ocurren bajo condiciones variadas. Estos problemas no se deben aun mal diseño algorítmico sino que surgen de factores ambientales. En cualquier comparación directa entre plataformas, estos problemas se hacen más evidentes cuando los recursos del sistema empiezan a sufrir estrés. Como describo en el subsistema de Memoria Virtual/Intercambio de FreeBSD el lector siempre debería tener en mente dos puntos:

Cualquier base de código que sobrevivirá y será mantenible durante años debe por lo tanto ser diseñada adecuadamente desde el comienzo incluso si tiene algo de coste en rendimiento. Hace veinte años la gente todavía discutía si la programación en ensamblador era mejor que programar en un lenguaje de alto nivel porque producía código que era diez veces más rápido. Hoy, la falibilidad de ese argumento es obvio — de modo paralelo al diseño algorítmico y la generalización de código.

La mejor manera de empezar describiendo el sistema de Memoria Virtual de FreeBSD is mirarlo desde la perspectiva de un proceso de usuario. Cada proceso de usuario ve una espacio de direcciones de Memoria Virtual único, privado y contiguo que contiene diversos tipos de objetos de memoria. Estos objetos tienen diversas características. Código de programa y datos de programa son de forma efectiva un solo fichero mapeado en memoria (el fichero binario que se está ejecutando), pero el código del programa es de solo lectura mientras que los datos de programa son copy-on-write. El BSS del programa es sólo memoria asignada y rellenada con ceros bajo demanda, llamada rellenado de página cero bajo demanda. Ficheros arbitrarios pueden ser mapeados en memoria en el espacio de direcciones también, que es como funciona el mecanismo de librerías compartidas. Dichos mapeos pueden requerir modificaciones para permanecer privados al proceso que los realiza. La llamada al sistema fork añade una nueva dimensión a al problema de la gestión de la Memoria Virtual a añadir a la complejidad ya existente.

Una página de datos binarios de un programa (que es una página copy-on-write básica) ilustra esta complejidad. Un programa binario contiene una sección de datos preinicializados que es inicialmente mapeado directamente por el fichero del programa. Cuando un programa se carga en el espacio de direcciones de Memoria Virtual del proceso, este área es inicialmente mapeado en memoria y respaldado por el programa binario mismo, permitiendo al sistema de Memoria Virtual liberar/reutilizar la página y después cargarla de nuevo desde el binario. Sin embargo, en el momento en que un proceso modifica estos datos, el sistema de Memoria Virtual debe hacer una copia privada para ese proceso. Puesto que la copia privada ha sido modificada, el sistema de Memoria Virtual podría no ser capaz de liberarla, porque no hay forma de restaurarla posteriormente.

Notarás inmediatamente que lo que originalmente era un simple mapeo de un fichero se ha convertido en algo más complejo. Los datos pueden ser modificados página a página mientras que el mapeo de ficheros engloba varias páginas a la vez. La complejidad aumenta más cuando un proceso se bifurca. Cuando un proceso se bifurca, el resultado son dos procesos—cada uno con su propio espacio de direcciones privado que incluye cualquier modificación hecha por el proceso original antes de la llamada a fork(). Sería tonto para el sistema de Memoria Virtual hacer una copia completa de los datos en el momento de llamar a fork() porque es bastante posible que al menos uno de los dos procesos solamente necesite leer de esa página a partir de este momento, permitiendo así que se use la página original. Lo que era una página privada se ha convertido en una página copy-on-write de nuevo, puesto que cada proceso (padre y hijo) espera que sus propias modificaciones personales después del fork permanezcan privadas para ellos y que afecten al otro.

FreeBSD gestiona todo esto con un modelo de Objetos de Memoria Virtual en capas. El fichero del programa binario original termina siendo la capa de Objetos de Memoria Virtual más baja. Una capa copy-on-write se sitúa encima de ella para mantener aquellas páginas que han sido copiadas del fichero original. Si el programa modifica una página de datos que pertenece al fichero original el sistema de Memoria Virtual recibe un fallo de página y hace una copia de la página en la capa superior. Cuando un proceso bifurca, se empujan nuevas capas de Objetos de Memoria Virtual. Esto puede cobrar más sentido con un ejemplo bastante básico. Un fork() es una operación común para cualquier sistema *BSD, así que este ejemplo considerará un programa que arranca, y bifurca. Cuando el proceso arranca, el sistema de Memoria Virtual crea una capa de objetos, llamémosla A:

A representa el fichero—las páginas pueden ser paginadas hacia o desde el medio físico del fichero según sea necesario. Paginar desde el disco es razonable para un programa, pero en realidad no queremos paginar de vuelta y sobrescribir el ejecutable. Por tanto, el sistema de Memoria Virtual crea una segunda capa, B, que estará respaldada físicamente por espacio de intercambio:

En la primera escritura a una página después de esto, se crea una nueva página en B, y su contenido es inicializado desde A. Todas las páginas en B pueden ser paginadas a o desde el dispositivo de intercambio. Cuando el programa bifurca, el sistema de Memoria Virtual crea dos capas de objetos nuevas—C1 para el padre, y C2 para el hijo—que descansan sobre B:

En este caso, digamos que una página en B es modificada por el proceso padre original. El proceso recibirá un fallo de copy-on-write y duplicará la página en C1, dejando la página original en B sin tocar. Ahora, digamos que la misma página en B es modificada por el proceso hijo. El proceso recibirá un fallo de copy-on-write y duplicará la página en C2. La página original en B está ahora completamente oculta ya que tanto C1 como C2 tienen una copia y B podría teóricamente ser destruida si no representa un fichero "real"; sin embargo, este tipo de optimización no es trivial de hacer porque es muy fina. FreeBSD no hace esta optimización. Ahora, supón (como suele ser el caso) que el proceso hijo hace un exec(). Su espacio de direcciones actual es habitualmente remplazado por un nuevo espacio de direcciones que representa un nuevo fichero. En este caso, la capa C2 es destruida:

En este caso, el número de hijos de B ha bajado a uno, y todos los accesos a B van ahora a través de C1. Esto significa que B y C1 pueden colapsarse juntas. Cualquier página en B que también existe en C1 se borran de B durante el colapso. Por lo tanto, incluso aunque la optimización en el paso anterior no se pudo hacer, podemos recuperar las páginas muertas bien cuando el proceso sale o cuando llama a exec().

Este modelo crea un número de problemas potenciales. El primero es que puedes terminar con una pila de Objetos de Memoria Virtual relativamente profunda que puede tener un coste de tiempo de escaneo y de memoria cuando recibes un fallo. Capas muy profundas pueden ocurrir cuando los procesos se bifurcan y se bifurcan de nuevo (en el padre o en el hijo). El segundo problema es que puedes terminar con páginas muertas, inaccesibles en lo profundo de la pila de Objetos de Memoria Virtual. En nuestro último ejemplo si tanto los el proceso padre como el hijo modifican la misma página, ambos obtienen su propia copia privada de la página y la página original en B ya no es accesible por nadie. Esa página en B puede ser liberada.

FreeBSD soluciona el problema de capas profundas con una optimización especial llamada "Caso de Todo Sombreado". Este caso ocurre si C1 o C2 generan suficientes fallos COW como para sombrear (ocultar) todas las páginas en B. Digamos que C1 lo consigue. C1 puede ahora puentear B completamente, así que en lugar de tener C1→B→A y C2→B→A ahora tenemos C1→A y C2→B→A. Pero mira lo que ha pasado también—ahora B tiene sólo una referencia (C1), así que podemos colapsar B y C2 juntas. El resultado final es que B se borra completamente y tenemos C1→A y C2→A. Habitualmente el caso es que B contendrá un gran número de páginas y ni C1 ni C2 serán capaces de ocultarla completamente. Si bifurcamos de nuevo y creamos un conjunto de capas D, sin embargo, es mucho más probable que una de las capas de D eventualmente sea capaz de ocultar el conjunto mucho menor representado por C1 o C2. La misma optimización funcionará en cualquier punto del grafo y el resultado total de esto es que incluso en una máquina con muchas bifurcaciones las pilas de Objetos de Memoria Virtual tienen a no ser mucho más profundas de 4. Esto es verdad tanto para el padre como para los hijos y es así tanto si el padre hace la bifurcación como si los hijos bifurcan en cascada.

El problema de la página muerta todavía existe en el caso en el que C1 o C2 no ocultan completamente B. Debido a otras optimizaciones este caso no es demasiado problema y simplemente permitimos que haya páginas muertas. Si el sistema se queda sin memoria las intercambiará a disco, utilizando un poco de espacio de intercambio, pero eso es todo.

La ventaja del modelo de Objetos de Memoria Virtual es que fork() es extremadamente rápido, ya que no se necesita realizar una copia real de datos. La desventaja es que puedes construir un conjunto de capas de Objetos de Memoria Virtual relativamente complejo que haga un poco más lento el manejo de fallos de página, y que tienes que gastar memoria en la gestión de las estructuras de los Objetos de Memoria Virtual. Las optimizaciones que hace FreeBSD demuestran que reducen los problemas lo suficiente de forma que pueden ser ignorados, eliminando prácticamente la desventaja.

Las páginas de datos privadas se crean como páginas copy-on-write o rellenas con ceros. Cuando se hace un cambio, y por lo tanto una copia, el objeto de respaldo original (normalmente un fichero) ya no puede ser utilizado para guardar una copia de la página cuando el sistema de Memoria Virtual necesita reutilizarla para otros fines. Aquí es donde aparece el Intercambio. El Intercambio se asigna para crear almacenamiento de respaldo para memoria que de otra forma no la tendría. FreeBSD asigna la estructura de gestión del intercambio para un Objeto de Memoria Virtual solo cuando se necesita realmente. Sin embargo históricamente, la estructura de gestión del intercambio ha tenido problemas:

De esa lista se hace evidente que había mucho margen de mejora. Para FreeBSD 4.X, reescribí completamente el subsistema de intercambio:

No realicé el paso final de tener un "puntero de anotaciones para las asignaciones" que recorrería una porción del espacio de intercambio según se hicieran las asignaciones para así garantizar asignaciones contiguas o al menos localidad de referencia, pero aseguré que esa condición no podría darse.

Como el sistema de Memoria Virtual usa toda la memoria disponible para cachear disco, normalmente hay pocas páginas que estén realmente libres. El sistema de Memoria Virtual depende de su habilidad para adecuadamente escoger las páginas que no están en uso para reutilizarlas en nuevas asignaciones. Seleccionar las páginas óptimas para liberar es posiblemente la función más importante que cualquier sistema de Memoria Virtual puede realizar porque si la elección no es buena, el sistema de Memoria Virtual puede verse forzada a recuperar páginas de disco innecesariamente, degradando seriamente el rendimiento del sistema.

¿Cuánto trabajo extra estamos dispuestos a sufrir en el camino crítico para evitar liberar la página equivocada? Cada decisión errónea que hacemos costará cientos de miles de ciclos de CPU y una parada notable de los procesos afectados, así que estamos dispuestos a soportar una cantidad significativa de trabajo extra para estar seguros que se escoge la página adecuada. Por esto es por lo que FreeBSD tiende a superar en rendimiento a otros sistemas cuando se estresan los recursos de memoria.

El algoritmo que determina la página libre se construye en base al histórico de uso de las páginas de memoria. Para adquirir este histórico, el sistema se aprovecha de la característica del bit de página utilizada que la mayoría del hardware de tablas de página posee.

En cualquier caso, el bit de página utilizada se blanquea y en algún momento posterior el sistema de Memoria Virtual se encuentra con la página de nuevo y ve que el bit de página utilizada ha sido marcado. Esto indica que la página todavía se está utilizando activamente. Si el bit está blanqueado eso indica que la página no se usa activamente. Mediante el chequeo periódico de este bit, se desarrollo (en forma de contador) un histórico de uso . Cuando posteriormente el sistema de Memoria Virtual necesita liberar algunas páginas, examinar este histórico se convierte en la piedra de toque para determinar la mejor página candidata para reutilizar.

Para esas plataformas que no tienen esta característica, el sistema en realidad emula un bit de página utilizada. Desmapea o protege una página, forzando un fallo de página si ésta es accedida de nuevo. Cuando se maneja el fallo de página, el sistema simplemente marca la página como usada y desprotege la página de forma que puede ser utilizada. Aunque realizar este fallo de página tan solo para determinar si una página está siendo usada puede parecer una proposición cara, es mucho menos cara que reutilizar la página para otro propósito para darse cuenta después de que otro proceso la necesita y tener que ir al disco.

FreeBSD utiliza varias colas de páginas para refinar aún más la selección de páginas a reutilizar así como para determinar cuando se deben llevar las páginas sucias a su almacenamiento de respaldo. Puesto que las tablas de páginas en FreeBSD son entidades dinámicas, cuesta virtualmente nada desmapear una página del espacio de direcciones de cualquier proceso que la esté usando. Cuando se ha escogido una página candidata basándose en el contador de página utilizada, esto es precisamente lo que se hace. El sistema debe distinguir entre páginas limpias que pueden en teoría ser liberadas en cualquier momento, y páginas sucias que deben ser escritas primero en el almacenamiento de respaldo antes de ser reutilizadas. Cuando se encuentra una página candidata se mueve a la cola inactiva si está sucia, o a la cola de caché si está limpia. In algoritmo separado que se bajas en el ratio de páginas sucias respecto de las limpias determina cuándo se tienen que escribir a disco las páginas sucias de la cola inactiva. Una vez hecho esto, las páginas escritas se mueven de la cola inactiva a la cola de caché. En este punto, las páginas en la cola de caché todavía pueden ser reactivadas por un fallo de Memoria Virtual con un coste relativamente bajo. Sin embargo, las páginas de la cola de caché se consideran como "inmediatamente liberables" y serán reutilizadas de modo LRU (Usada Menos Recientemente) cuando el sistema necesita asignar nueva memoria.

Es importante señalar que el sistema de Memoria Virtual de FreeBSD intenta separar páginas limpias y sucias para expresar la razón de evitar la escritura innecesaria de páginas sucias (que come ancho de banda de E/S), y tampoco mueve de forma gratuita páginas entre distintas colas de páginas cuando el sistema de memoria no está bajo estrés. Este es el motivo por el que verás algunos sistemas con contadores de cola de caché muy bajos y contadores de cola de páginas activa altos cuando se ejecuta el comando systat -vm. Según el sistema de Memoria Virtual va sufriendo más estrés, hace un gran esfuerzo por mantener varias colas de páginas en los niveles que determina que son más efectivos.

Durante años ha circulado una leyenda urbana acerca de que Linux hacía un mejor trabajo que FreeBSD evitando escribir en intercambio, pero de hecho esto no es cierto. Lo que ocurría en realidad era que FreeBSD estaba llevando a intercambio de forma proactiva páginas no utilizadas para hacer sitio para más caché de disco mientras que Linux estaba manteniendo las páginas sin utilizar y dejando menos memoria disponible para la caché y para páginas de procesos. No sé si esto sigue siendo cierto a día de hoy.

Realizar un fallo de Memoria Virtual no es costoso y la página subyacente ya está cargada y simplemente puede ser mapeada en el proceso, pero puede ser costoso si hay muchas de ellas de forma regular. Un buen ejemplo de esto es ejecutar un programa como ls(1) o ps(1) una y otra vez. Si el programa binario está mapeado en la memoria pero no lo está en la tabla de páginas, entonces todas las páginas que serán accedidas por el programa generarán un fallo cada vez que el programa se ejecute. Esto es innecesario cuando las páginas en cuestión ya están en la Caché de Memoria Virtual, de modo que FreeBSD intentará pre-poblar las tablas de páginas de un proceso con aquellas páginas que ya están en la Caché de Memoria Virtual. Algo que FreeBSD no hace todavía es un pre-copy-on-write de ciertas páginas al hacer exec. Por ejemplo, si ejecutas el programa ls(1) mientras ejecutas vmstat 1 notarás que siempre produce un cierto número de fallos de página, incluso cuando lo ejecutas una y otra vez. Estos son fallos de página de rellenados de ceros, no fallos de código de programa (que ya han sido pre-fallados). Realizar una pre-copia de páginas en un exec o fork es un área en el que ser sujeto de más estudio.

Un gran porcentaje de los fallos de página que se producen son fallos de rellenado de ceros. Habitualmente puedes verlo observando la salida del comando vmstat -s. Esto ocurre cuando un proceso accede a páginas de su área de BSS. Se espera que el área de BSS esté inicializada a cero pero el sistema de Memoria Virtual no se molesta en asignar ninguna memoria en absoluto hasta el momento en el que el proceso accede de verdad. Cuando se produce un fallo el sistema de Memoria Virtual no solo debe asignar una nueva página, tiene que inicializarla a cero también. Para optimizar la operación de rellenado de ceros el sistema de Memoria Virtual tiene la capacidad de pre-inicializar páginas a cero y marcarlas como tal, y solicitar páginas pre-inicializadas a cero cuando ocurre un fallo de rellenado de ceros. La pre-inicialización a cero ocurren cuando la CPU está ociosa pero el número de páginas que el sistema pre-inicializa a cero está limitado para evitar destrozar las cachés de memoria. Este es un ejemplo excelente de cómo añadir complejidad al sistema de Memoria Virtual para optimizar el camino crítico.

Las optimizaciones de la tabla de páginas constituyen la parte más controvertida del diseño de la Memoria Virtual de FreeBSD y ha mostrado cierta tensión con la llegada de uso serio de mmap(). Creo que esto en realidad es una característica de la mayor parte de los BSDS aunque no estoy seguro de cuándo se introdujo por primera vez. Hay dos optimizaciones principales. La primar es que las tablas de páginas hardware no contienen un estado persistente sino que pueden descartarse en cualquier momento con solo un pequeño sobre coste en la gestión. La segunda es que cada entrada en la tabla de páginas activas en el sistema tiene una estructura pv_entry que lo gobierna la cual está enlazada a la estructura vm_page. FreeBSD puede simplemente iterar sobre esos mapeos que se sabe que existen mientras Linux tiene que comprobar todas las tablas de páginas que podrían contener un mapeo específico para ver si es así, lo que puede provocar un sobre coste de O(n^2) en algunas situaciones. Por esto FreeBSD tiene a tomar mejores decisiones sobre qué páginas reutilizar o intercambiar cuando la memoria está bajo estrés, resultando en un mejor rendimiento bajo carga. Sin embargo, FreeBSD requiere ajustes del núcleo para acomodar situaciones con grandes espacios de direcciones compartidos como los que pueden darse en sistemas nuevos porque podría agotar las estructuras pv_entry.

Tanto Linux como FreeBSD necesitan trabajar en este área. FreeBSD trata de maximizar la ventaja de un modelo de mapeo activo potencialmente disperso (no todos los procesos necesitan mapear todas las páginas de una biblioteca compartida por ejemplo), mientras que Linux trata de simplificar sus algoritmos. FreeBSD en general tiene la venta del rendimiento a costa de gastar algo más de memoria extra, pero FreeBSD se desmorona en el caso donde un fichero grande está compartido de forma masiva entre cientos de procesos. Linux, por otro lado, se desmorona en el caso donde muchos procesos mapean pocas porciones de la misma biblioteca compartida y también se ejecuta de forma no-óptima cuando intenta determinar si una página puede ser reutilizada o no.

Terminaremos con las optimizaciones de coloreado de páginas. El coloreado de páginas es una optimización de rendimiento diseñada para asegurar que el acceso a páginas contiguas en memoria virtual hacen el mejor uso posible de la caché del procesador. Hace mucho tiempo (es decir, más de 10 años) las cachés de los procesadores solían mapear memoria virtual en lugar de memoria física. Esto produjo un gran número de problemas que incluyen tener que limpiar la caché en cada cambio de contexto en algunos casos, y problemas con los alias de datos en la caché. De hecho, si no tienes cuidado, páginas contiguas en memoria virtual podrían terminar utilizando la misma página en la caché del procesador—llevando a desechar prematuramente datos cacheables y reduciendo el rendimiento de la CPU. Esto es cierto incluso en cachés asociativas multi direccionales (aunque el efecto se mitiga algo).

El código de asignación de memoria de FreeBSD implementa optimizaciones de coloreado de páginas, lo que significa que el código se asignación de memoria intentará localizar páginas libres que son contiguas desde el punto de vista de la caché. Por ejemplo, si la página 16 de memoria física está asignada a la página 0 de la memoria virtual del proceso y la caché puede mantener 4 páginas, el código de coloreado de páginas no asignará la página 20 de memoria física a la página 1 de la memoria virtual de un proceso. En su lugar, asignaría la página 21 de memoria física. El código de coloreado de páginas intenta evitar la asignación de la página 20 porque esto mapea sobre la misma memoria cacheada que la página 16 y resultaría en un cacheo no óptimo. Este código añade una significativa complejidad al subsistema de asignación de memoria de la Memoria Virtual como puedes imaginar, pero el resultado merece la pena. El Coloreado de Páginas hace que la memoria de la Memoria Virtual sea tan determinista como la memoria física en términos de rendimiento de caché.

La Memoria Virtual en lo sistemas operativos modernos deben afrontar diversas situaciones de forma eficiente y para muchos patrones de uso distintos. La aproximación modular y algorítmica que históricamente ha tomado BSD nos permite estudiar y entender la implementación actual así como reemplazar piezas de código relativamente grandes de forma también relativamente limpia. Ha habido una serie de mejoras en el sistema e Memoria Virtual de FreeBSD en los últimos años, y el trabajo continua.