Sistemas Reales (VAX/VMS y Linux)

#

Aunque VAX/VMS es un sistema operativo con casi 50 años, muchas de las técnicas y métodos usados para solucionar algunos de los problemas que tenía se siguen usando hoy en día. Además, a algunos de los métodos que usaba para solucionar dichos problemas también les surgieron otros problemas nuevos, mediante los que se explican técnicas más nuevas usadas por sistemas modernos.

VAX / VMS

#

VAX/VMS fue un sistema operativo desarrollado por DEC (que ya no existe) en 1977 hecho para trabajar sobre una amplia gama de dispositivos de rendimientos muy diversos, por lo que debía intentar funcionar razonablemente bien en todos por igual. Uno de los dispositivos en los que funcionaba era el VAX-11.

En dicho VAX-11, los procesos trabajaban en un espacio de direccionamiento de 32 bits (4GB), divididos en páginas de 512 bytes. Por lo tanto, las páginas usaban un offset de 9 bits y los otros 23 correspondían al VPN. El SO usaba un modelo híbrido entre segmentación y paginación, dividiendo el espacio de direcciones de un proceso en 2 segmentos (usando los 2 bits superiores de la dirección virtual):

• P0 y P1 (Process Space, Los primeros 2GB): El espacio de usuario (Ring 3). P0 contiene código y heap, y P1 contiene el stack.
• S (System Space, Los últimos 2GB): Aquí está mapeado el Kernel del SO, protegido de los usuarios (solo accesible en modo kernel). La dirección virtual del kernel está mapeada en el mismo sitio para todos los procesos.

Además, VMS usaba tablas de paginación lineales, aunque con un matiz importante que se verá a continuación. Más adelante hablaremos de la diferencia entre P0 y P1, pero lo importante aquí es el motivo por el cuál se hace la división P/S, y es que esta división se sigue haciendo hoy en día con sistemas modernos.

Kernel mapeado

#

Supongamos que el kernel no está mapeado en el espacio de direccionamiento de un proceso. En ese caso, cuando el proceso quiere realizar una syscall, pasa lo siguiente:

• El SO toma el control y la CPU entra en modo kernel (Ring 0)
• El SO quiere acceder a la función de la syscall, pero no está en el espacio de direcciones del proceso.
• Para acceder a la función de la syscall, el SO debe ir acceder a la memoria física directamente, pero la CPU trabaja solo con direcciones virtuales, no físicas.
• Por tanto, no hay forma de acceder a la memoria física (sin ayuda del hardware) directamente, por lo que no hay forma de acceder a la syscall, incluso en modo kernel.

Para solucionar esto, muchos sistemas (Linux, VAX/VMS y otros incluidos hasta hace no tanto) optaron por reservar parte del espacio de direccionamiento del proceso y mapear el kernel ahí (todo entero o algunas partes, como las funciones de syscalls y algunas trap tables). Así, cuando es necesario ejecutar una función del SO (como una syscall), el proceso se reduce a cambiar de modo, ir a la función de la syscall y ejecutarla, y volver al modo usuario. En esencia, el kernel (o la parte de él que se mapea) actúa como una librería protegida, al servicio del proceso.

Hasta 2018, esta era la alternativa. Luego vino un problema que se mencionará más adelante que obligó a los desarrolladores a cambiarlo.

P0 y P1

#

Mientras que la técnica de mapear el kernel sí la usaban muchos sistemas, lo de dividir el espacio de usuario del usuario en dos partes (P0 y P1) era una peculiaridad de VMS, fue una necesidad impuesta por el hardware, algo que en arquitecturas modernas no es necesario hacer.

Normalmente, entre el heap y el stack hay un agujero bastante grande de memoria virtual sin usar. Con tablas de paginación multinivel, esto no era un problema: solo se reservaba memoria para lo que se usaba. En VMS, el problema es que se usaban tablas de paginación lineales. Para solucionar el problema aquí, lo que se diseñó fue crear dos tablas de páginas separadas: una para P0 y otra para P1. Usando registros base y bounds, el sistema sabía dónde acababa el heap y dónde empezaba el stack, y no creaba tabla de páginas para el espacio vacío en medio.

Tablas de paginación swappeables

#

Como VMS tenía que funcionar en sistemas que no necesariamente tuviesen mucha memoria, la solución que se implementó fue colocar las tablas de paginación de los usuarios (las de P0 y P1) dentro del espacio virtual del kernel (segmento S).

Al meter las tablas en memoria virtual en lugar de obligarlas a estar fijas en la memoria física, el kernel podía hacer swapping de las propias tablas de paginación. Esto significa que si el sistema se estaba quedando sin RAM física, el kernel de VMS podía coger la tabla de paginación de un proceso inactivo y guardarla en el disco duro.

Aunque esto era muy útil por el ahorro de memoria, también tenía una desventaja en el rendimiento. Si la tabla de páginas de un usuario (P0) estaba en la memoria virtual del kernel (S), la CPU tenía un problema cuando intentaba traducir una dirección del usuario:

• El hardware buscaba la entrada en la tabla de P0.
• Esa entrada estaba ubicada en una dirección virtual.
• Para acceder a esa dirección virtual, el hardware tenía que consultar la tabla de paginación del sistema, que sí estaba obligatoriamente en memoria física.

Una vez traducida la dirección de la tabla, sí podía leerse la entrada del usuario y acceder a la memoria física del programa. Esto significaba que era necesaria una doble traducción, que hubiese sido inviable de no ser porque ya se contaba con un TLB que agilizaba todo.

Demand Zeroing

#

Cuando un proceso solicita al sistema operativo una página nueva porque necesita más espacio, el SO debe tener en cuenta que la página que va a darle puede haber sido usada por un proceso anteriormente, y dicho proceso puede haber dejado en memoria información sensible. Por ello, lo que el sistema hace siempre antes de darle la página a un proceso es poner todos los bits a cero (Zeroing).

El zeroing se vuelve un proceso costoso si se da el caso de que al final el proceso que ha pedido la memoria ha acabado no utilizándola. Por eso, VMS usaba una técnica para “optimizar” esto.

Cuando el proceso le pedía memoria, simplemente tomaba una página y la marcaba como reservada, pero no hacía nada más. Cuando el proceso luego intentaba acceder por primera vez a esa página, se activaba un trap, el SO veía que esa página estaba marcada como demand-zero, y entonces buscaba un marco físico para esa página, ponía todo a cero y se la daba al proceso.

Copy-On-Write

#

Copy-On-Write (COW) es otra optimización que aparecía en VMS y que se usa en muchos sistemas hoy en día. De hecho, hay una vulnerabilidad del kernel de Linux descubierta en 2016 que permitía elevar privilegios, llamada DirtyCOW, que estaba basada precisamente en (una condición de carrera en) este mecanismo. El proceso consiste en lo siguiente:

Cuando el SO necesita copiar una página de un espacio de direcciones a otro (p.ej, cuando se hace un fork() y nace otro proceso que usa el mismo código), en lugar de copiarla directamente, la mapea en el espacio de direcciones del nuevo proceso y marca la página como solo lectura para ambos espacios de direcciones.

Es decir, que ambos procesos terminan teniendo acceso a la misma página física, cada uno desde su espacio de direcciones, pero con permisos de solo lectura.

Es únicamente cuando un proceso de ellos intenta escribir en la página que se activa un trap que da el control al SO. El SO entonces verá que la página está marcada como COW y la copiará, dándosela al proceso que había intentado escribir.

Linux pt.1: Direccionamiento

#

De forma similar al de VMS, el espacio de direcciones de un proceso en Linux está formado por dos partes: la parte de usuario (código, stack, heap, etc.) y la parte del kernel (código del kernel, syscalls, stack, etc., aunque con ciertos matices de seguridad que veremos más adelante).

Igual que en otros sistemas, cuando hay un context switch, únicamente cambia la parte del usuario, y el mapeo del kernel permanece igual para todos. Y, como en otros sistemas, un programa en modo usuario no puede acceder a la parte del kernel.

En Linux de 32 bit, tres cuartas partes del espacio de direcciones pertenecen al usuario (desde \(\text{0x00000000}\) hasta \(\text{0xBFFFFFFF}\)), y la otra cuarta parte (desde \(\text{0xC0000000}\) hasta \(\text{0xFFFFFFFF}\)) pertenece al kernel. En Linux de 64 bit esto funciona de forma similar, aunque los puntos de divisón son diferentes.

Direcciones del Kernel

#

En Linux, el kernel no usa un único tipo de direcciones de memoria, sino que usa dos, las direcciones lógicas y las virtuales.

Direcciones Lógicas del Kernel

#

Esta es la memoria “normal” y principal que usa el kernel. Se solicita usando la función kmalloc (en Ring 0) y se usa para almacenar estructuras vitales del sistema, como tablas de paginación o los kernel stacks de los procesos.

Esta memoria no puede swappearse, siempre tiene que estar en RAM. Además, el punto más relevante de esta memoria es que hay un mapeo directo entre las direcciones lógicas del kernel y la memoria física. Por ejemplo, la dirección lógica \(\text{0xC0000000}\) se traduce a la física \(\text{0x00000000}\), y la lógica \(\text{0xC0000123}\) se traduce a la física \(\text{0x00000123}\), y así con todas.

Este funcionamiento tiene una implicación importante. Si se reserva un bloque de memoria contiguo en el espacio de direcciones lógicas del kernel, la memoria física correspondiente también será contigua. Esto es crucial para operaciones como el DMA (Acceso Directo a Memoria), que se verá en la parte de persistencia.

Direcciones Virtuales del Kernel

#

Este segundo tipo de memoria está diseñado para solucionar problemas de espacio. Se solicita usando la función vmalloc. Esta memoria generalmente no es contigua, pero suele venir bien cuando hace falta reservar una gran cantidad de memoria que es posible que sea difícil de encontrar físicamente contigua.

Hay que tener en cuenta que tanto vmalloc como kmalloc son funciones del kernel para reservar memoria para el kernel. Cuando hace falta memoria para un usuario, el kernel puede usar kmap.

El problema de los 32 bit

#

En sistemas de 32 bits, el espacio de direcciones virtual total de un proceso es de 4GB (\(2^{32}\)). Linux lo dividía en un formato 75% (3GB) espacio de usuario y 25% (1GB) espacio del kernel, cada proceso puede usar un máximo de 3GB para sus datos.

Este modelo, cuando el sistema empieza a tener más memoria, tiene un problema.

La necesidad de una zona segura exclusiva

#

Hay que tener claro que el kernel es el que gestiona toda la RAM del sistema. Cuando un proceso de usuario pide memoria o quiere leer un archivo de disco, es el kernel el que debe acceder físicamente a la dirección física de la RAM correspondiente para hacerlo.

Para que la CPU, ejecutando el kernel, pueda interactuar con cualquier dirección física de la RAM, el kernel necesita obligatoriamente una dirección virtual que apunte a esa dirección física (porque la CPU solo funciona con direcciones virtuales).

El kernel no puede usar las direcciones virtuales del espacio de usuario (3GB Inferiores) para mapear a las físicas por seguridad y principalmente por contexto (el kernel puede estar procesando datos destinados a un proceso mientras la CPU está ejecutando otro diferente). Esto significa que el kernel debe realizar todas sus tareas administrativas usando exclusivamente su espacio virtual privilegiado (1GB Superior).

HighMem y el Rendimiento

#

La forma más eficiente que tiene el kernel para trabajar es mapear la memoria física a su espacio virtual de forma directa (dir.física = dir.virt - 0xC0000000). Si el mapeo no cambia nunca, el kernel puede acceder a la RAM con una simple suma, sin tener que modificar tablas de páginas y por tanto sin tener que invalidar el TLB. A esto se le llama LowMem y es donde funcionaba kmalloc.

El problema es que el kernel obviamente querría mapear toda la RAM física de forma permanente (como con kmalloc) para poder administrarla rápido, pero solo tiene 1GB de espacio virtual seguro para hacer esto (del cual solo puede destinar, por diseño, 896MB a mapeo directo, reservando 128 MB para emergencias). Y es imposible meter un mapeo permanente 1 a 1 de 4GB de RAM física dentro de un espacio virtual de 896MB.

Como el kernel no puede tener un mapeo directo a las direcciones de RAM que superan esos 896MB (dichas direcciones se conocen como HighMem), se ve obligado a improvisar.

Hay que tener en cuenta que LowMem y HighMem son conceptos que existen solo de cara al kernel. No hay un LowMem o HighMem para los procesos porque ellos (1) no necesitan poder gestionar toda la RAM entera como hace el kernel y (2) su espacio de direccionamiento privado es de 3GB.

Cada vez que el kernel necesita administrar (acceder a) una página física ubicada en HighMem tiene que hacer esto:

• Buscar un hueco libre en sus 128MB de reserva
• Crear un mapeo temporal en la tabla de paginación del sistema (Dir.Física HighMem <-> Dir.Virtual en los 128MB)
• Invalidar el TLB (Flush) por la modificación de la tabla de paginación, para obligar a la CPU a reconocer este nuevo mapeo temporal.
• Acceder a la dirección virtual recién mapeada (que ahora apunta a la física) y hacer lo que tenga que hacer (p.ej zeroing).
• Deshacer el mapeo de la zona del kernel, y por tanto volver a invalidar el TLB.
• Finalmente, coger esa misma dirección física ya limpia y mapearla en la tabla de páginas del proceso de usuario para “dársela”.

Cada vez que el kernel tenga que mapear memoria física en HighMem, tendrá que invalidar el TLB 2 veces y modificar la tabla de paginación del sistema. Esto hace que sea muy lento trabajar en HighMem.

La solución de los 64 bit

#

El problema de los 32 bit era que teníamos 4GB de RAM física y solo 1GB de espacio virtual para el kernel, por lo que acceder a memoria física superior a los 896MB era muy lento.

Al pasar a una arquitectura de 64 bit, el tamaño de las direcciones virtuales crece por un factor de 65536. Aunque las CPUs de 64 bits no usan los 64 bits enteros para el direccionamiento, sino que suelen usar normalmente 48, el espacio virtual total pasa de 4GB a 256TiB.

En Linux de 64 bit (x86_64), el mapa de memoria deja de ser 3GB/1GB. Ahora el espacio de 256TB se divide en dos bloques de 128TB:

• User space: Los primeros 128TB (0x0000000000000000-0xFFFF7FFFFFFFFFFF)
• Kernel space: Los últimos 128TB (0xFFFF800000000000-0xFFFFFFFFFFFFFFFF)

Ahora, si un servidor tiene instalado 1TB de RAM, el kernel simplemente coge 1TB de sus 128TB virtuales y mapea toda la RAM física como LowMem al arrancar el sistema.

Como ahora cabe toda la memoria física dentro del mapa del kernel:

• Desaparece HighMem, ya no hay memoria física que el kernel no pueda ver directamente.
• kmap() pierde su propósito, ya no hay que ir mapeando y desmapeando páginas temporales.
• vmalloc() cambia de propósito, ahora sirve exclusivamente para cuando el kernel necesita asignar un bloque grande de memoria para sí mismo y la memoria física está tan fragmentada que no hay un bloque contiguo lo suficientemente grande.

Linux pt.2: Técnicas

#

Paginación y Huge Pages

#

Una vez hemos llegado a los sistemas de 64 bit, podemos seguir viendo los métodos que usa Linux. Los sistemas actuales usan tablas de paginación multinivel de, por defecto, 4 niveles, aunque también se permite usar 5 niveles para dar soporte a todavía más memoria.

Además, varios procesadores recientes dan soporte al uso de páginas de varios tamaños, no limitados al estándar de 4KB. Hay soporte para páginas de 2MB o incluso de 1GB. A esto Linux también se ha adaptado, permitiendo que las aplicaciones usen estas páginas, denominadas huge pages.

El uso de estas Huge Pages puede ser beneficioso para el sistema cuando hay un proceso que usa mucha memoria, pues puede acabar teniendo muchas páginas pequeñas (de 4KB) y por tanto acabar llenando el TLB. Para solucionar esto, basta con darle páginas más grandes para que use menos (cuando sepamos que las va a usar).

Normalmente, en Linux, la posibilidad de usar Huge Pages se daba como opción a los procesos para que las usasen cuando ellos querían (p.ej, bases de datos), pero actualmente la cosa ha cambiado y, para ahorrar en TLB misses, el SO (si se activa la opción) se encarga de buscar automáticamente casos en los que dar Huge Pages a las aplicaciones, de forma transparente para ellas.

Page Cache

#

Por muy rápido que sea un HDD/SSD moderno, comparado con la RAM y la CPU es demasiado lento. Para reducir el costo de acceder al almacenamiento persistente, Linux usa un page cache, que consiste en usar la memoria RAM libre para guardar copias de datos que residen en el almacenamiento persistente.

En sí, el page cache es una estructura creada por el Kernel y que se guarda en la zona del kernel. Es una forma de almacenar en memoria cosas que vienen del disco. Todas las páginas del Page Cache se guardan en una tabla hash para poder encontrarlas rápidamente cuando se necesiten.

Antes, muchos SO tenían dos sistemas separados:

• Un caché para los datos del sistema de archivos (almacenamiento persistente)
• Un sistema de memoria virtual (la que se ha visto hasta ahora, la memoria que tiene reservada un proceso)

Linux, respecto a esto, tiene un Page Cache Unificado, esto significa que mete en el mismo saco a:

• Datos y metadatos tradicionales: Cuando el programa quiere leer (o escribir) en un archivo una cantidad de bytes arbitrarios y usa read() (o write()). Si el archivo no está en RAM, el sistema lo lee de disco y lo guarda en el Page Cache (que está en el espacio del kernel). Como el proceso no puede acceder a esa zona, el kernel copia esos datos desde el Page Cache hasta el buffer del programa. Aquí hay una penalización de rendimiento porque se tiene que copiar el dato de un lugar de RAM (zona kernel) a otro (zona del proceso).
• Archivos mapeados en memoria: Cuando el programa quiere mapear un archivo de disco directamente usando mmap(). Aquí el kernel carga el archivo de disco a su Page Cache (zona kernel) y permite que el proceso mapee esa página específica entera en su zona, así accede directamente. No hay copia doble. Esto es posible porque mmap() carga páginas enteras y no cantidades de bytes arbitrarias como read()/write().
• Memoria anónima: Esta memoria es simplemente la que usan los programas cuando se ejecutan, se llama anónima porque no tiene un nombre de archivo que haga referencia a los datos específicos. Son heap, stack, y demás de un proceso. No hace falta un “page cache” en sí porque por defecto esta memoria vive en memoria.

Aunque la última es diferente a las otras dos primeras, el Page Cache es unificado precisamente porque usa el mismo sistema para gestionar las tres. Esto se hace con el objetivo de que no haga falta trazar unos límites en cuanto a memoria y decir “el 60% es para memoria anónima y el 40% es para Page Cache”. Así se puede ir ajustando el uso de la memoria dinámicamente. Esto significa que, el mismo sistema, con el mismo hardware, puede ejecutar trabajo intensivo en memoria (p.ej 95% memoria anónima), o puede funcionar como servidor de archivos (95% Page Cache), sin necesidad de cambiar unos límites manualmente o de desperdiciar RAM asignada a lo otro que no esté en uso.

Además, hay que destacar que solo se meten en el Page Cache las páginas de archivos que los procesos solicitan. Si un programa pide leer una parte de un archivo, el kernel lo mete al page cache, si no lo pide, no entra. El sistema no intenta adivinar ni se intenta acordar de qué archivos suelen abrirse más.

Dirty Bit: pdflush

#

Hay hilos del kernel encargados de mirar si hay páginas en el Page Cache que han cambiado (dirty bit a 1) y de copiar los cambios al disco, uno de ellos antiguamente era pdflush. Esto puede parecer problemático, p.ej, si un usuario quiere abrir un archivo .txt en el bloc de notas, modificarlo, pero no guardar los cambios. En ese caso, el hilo del kernel copiaría a disco los datos automáticamente, no? Pues no.

Aquí hay que tener en cuenta que los editores de archivos usan read() y write() para acceder a los archivos, y esto significa que, como decíamos antes, hay una copia de los datos en la zona del usuario, y otra copia (el Page Cache) en la zona del kernel.

Cuando el usuario modifica el documento en el bloc de notas, modifica su copia local, y es únicamente cuando usa write() que se pasan los cambios al Page Cache de la zona kernel. Entonces es cuando actúa pdflush, que pasa los cambios del Page Cache al archivo de disco.

A diferencia de esto, con mmap() solo había una única copia, por lo que si el usuario modificase cualquier cosa en la página mapeada, sí se copiaría directamente al disco. Por eso los editores de archivos no usan mmap().

Aunque pdflush sirve como ejemplo conceptual, este proceso ya no existe desde hace años (2009). Ahora se usan otros

Memoria Llena: 2Q/LRU

#

Cuando el sistema se empieza a quedar sin memoria, debe decidir qué páginas sacar de memoria para liberar espacio.

Aunque ahora se usa un algoritmo diferente (MGLRU), Linux históricamente ha usado un algoritmo basado en el Clock Algorithm llamado 2Q/LRU (2 Queue) o Active/Inactive Lists, y que solucionaba algunos de los problemas del Clock Algorithm.

El Clock Algorithm trata toda la RAM como una única lista circular. La manecilla del reloj da vueltas: si el Use Bit es 1, lo pone a 0 y avanza; y si es 0, swappea la página.

El problema que tiene esto es la falta de resistencia a escaneos masivos. Si quieres ver un vídeo de 40GB, el SO irá cargando sus páginas en RAM. Al hacerlo, todos sus Use Bits se pondrán a 1, y cuando la manecilla pase por toda la memoria, pasará por encima de las páginas del vídeo, ignorándolas porque sus bits están a 1, y terminará mandando algo importante a disco, como un proceso del sistema.

Para solucionar esto, Linux dividió el reloj en dos colas separadas: la Lista Inactiva y la Lista Activa:

• Cuando una página nueva de lee del disco por primera vez, entra en la lista inactiva.
• Cuando queda poca memoria, el SO sigue el clock algorithm, pero solo en la lista inactiva.
  • Si el Use Bit de una página es 0: la página se ha leído una vez y no se ha vuelto a tocar. Se expulsa la página al disco.
  • Si el Use Bit de una página es 1: el programa ha vuelto a leer o escribir en esa página, por lo que puede ser útil. Se mueve la página a la Lista Activa.
• Si la Lista Activa se llena demasiado, se toman las páginas del final de dicha lista, se ponen sus Use Bits a 0 y se mueven a la Lista Inactiva para hacer hueco.