Este artículo ha sido consultado en 546 ocasiones.

Prólogo

Mientras que la gestión de memoria virtual (en adelante VMM, de Virtual Memory Management) en Linux 2.2 tiene un rendimiento decente para muchos tipos de cargas, tiene varios problemas. La primera parte de este documento contiene una descripción de como la VMM de Linux 2.2 trabaja y un análisis de porque tiene un mal comportamiento en algunas situaciones.

La manera de la que gran parte de este comportamiento ha sido solucionado en el kernel Linux 2.4 está descrita en la segunda parte de este documento. Debido a que Linux 2.4 estaba en un periodo de congelación de código mientras estas mejoras fueron implementadas, solo se han integrado las soluciones bien conocidas. Muchas de las ideas usadas son derivadas de principios usados en otros sistemas operativos, principalmente porque sabemos que funcionan y tenemos un buen conocimiento del porqué, haciendolas indicadas para la integración en el código base de Linux durante el periodo de congelación del código.

Gestión de memoria en Linux 2.2

La gestión de memoria en Linux 2.2 parece estar centrada en la simplicidad y en la baja sobrecarga. Mientras que esto funciona bastante bien en la práctica para la mayoria de los sistemas, tiene algunos puntos débiles y fracasa en algunos escenarios.

La memoria en Linux está unificada, esto significa que toda la memoria está en la misma lista libre y puede ser asignada a cualquiera de los siguientes almacenes de memoria (memory pools) segun se necesite. La mayoria de estos almacenes pueden crecer y disminuir bajo demanda. Normalmente la mayoria de la memoria de un sistema sera asignada a páginas de datos de procesos y a los page cache y buffer caché.

• El slab cache: Este es el almacen de heap dinámico del kernel. Esta memoria no se puede llevar a swap, pero se puede reclamar una vez que todos los objetos en una area (normalmente del tamaño de una pagina) no sean usados.

• El page cache: Este cache se usa para cachear datos de archivos para mmap() y read() y esta indexado por parejas de (ínodo, índice). En este cache no existen datos sucios; cuando un programa escribe a una página, los datos sucios se copian al buffer cache, desde donde los datos son escritos al disco.

• El buffer cache: Este caché esta indexado por parejas (dispositivo bloque, numero de bloque) y se usa para cachear los dispositivos de disco "raw", inodos, directorios y otros metadatos del sistema de archivos. Tambien se usa para realizar I/O en el disco en nombre del page cache y los otros caches. Para las lecturas del disco el page cache evita este caché y para sistemas de archivos de red ni siquiera se usa.

• El inode cache: Este caché reside en el slab cache y contiene informacion sobre los archivos cacheados en el sistema. Linux 2.2 no puede reducir este cache, sino que por su reducido tamaño necesita reclamar entradas individuales.

• El dentry cache: Este caché contiene la información del nombre y directorio de una manera independiente del sistema de archivos, y se usa para buscar archivos y directorios. Este caché crece y disminuye dinámicamente segun se requiera.

• Memoria compartida SYSV: El espacio de memoria que contiene el segmento de memoria compartida SYSV se gestiona bastante parecido al page cache, pero tiene su propia infraestructura para hacer cosas.

• Memoria virtual mapeada de un proceso: Esta memoria se administra en las tablas de páginas del proceso.  Los procesos pueden tener mapeados page cache o segmentos de memoria compartida SYSV, en cuyo caso esas páginas son gestionadas tanto en las tablas de páginas como en las estructuras de datos usadas para el page cache o el código de memoria compartida, respectivamente.

Reemplazo de páginas en Linux 2.2

Aqui se explica como trabaja el reemplazo de páginas en Linux 2.2. Cuando la memoria cae por debajo de un cierto límite se despierta el demonio de pageout kswapd. Dicho demonio debería ser capaz de mantener la suficiente memoria libre - pero si no lo es, los procesos de los usuarios terminarán llamando al mismo código de pageout.

El principal bucle de pageout esta en la funcion try_to_free_pages, que comienza liberando slabs no usados del almacen de memoria del kernel. Despues de eso, llama a las siguientes funciones en un bucle, pidiendolas a cada una de ellas que examinen una pequeña parte de su parte de memoria hasta que se haya liberado suficiente memoria.

• shrink_mmap es un algorritmo de reloj clásico, que da vueltas por todas las páginas fisicas, limpiando los referenced bits, encolando las paginas que esten dirty (sucias) y viejas, y liberando las páginas que estén viejas y limpias . Sin embargo, la principal desventaja que tiene comparado con un algoritmo de reloj, es que no puede liberar páginas que estan en uso por un programa o un segmento de memoria compartida. Esas páginas necesitan ser desmapeadas primero por swap_out.

• shm_swap escanea los segmentos de memoria compartida SYSV, moviendo a swap aquellas páginas que no han sido referenciadas recientemente y que no estan mapeadas en ningun proceso.

• swap_out examina la memoria virtual de todos los procesos en el sistema, desmapeando páginas que no han sido referenciadas recientemente, empezando a moverlas a swap y colocando dichas paginas en el page cache.

• shrink_dcache_memory reclama entradas del cache de nombres del VFS. Esta memoria no es reusable directamente, pero tan pronto como una página entera de estas entradas no esté usada  podemos reclamar esa página.

Se consigue algo de balanceo entre estas funciones llamandolas en un bucle, empezando por pedirlas a cada una de ellas que examinen un poco de su memoria, ya que cada una de estas funciones acepta un argumento de prioridad que las indica el porcentaje de memoria a examinar. Si no se ha liberado suficiente memoria en el primer bucle, la prioridad se incrementa y se llaman otra vez las funciones. La idea que hay detras de este esquema es que cuando un almacen de memoria se está usando mucho, no renunciara a sus recursos fácilmente y automáticamente recaera en uno de los otros almacenes de memoria. Sin embargo, este esquema confía en que cada uno de los diferentes espacios de memoria reaccionan de manera similar al argumento de prioridad bajo diferentes condiciones de memoria. Esto en la realidad no funciona porque los almacenes de memoria tienen, para empezar, diferentes propiedades.

Problemas con el reemplazo de memoria de Linux 2.2

• El balanceado entre el desalojo (evicting) de páginas del file cache, el desalojo de páginas de proceso sin usar, y el desalojo de páginas de los segmentos de memoria compartida . Si la presión de memoria es la "justa", shrink_mmap siempre logra liberar paginas del cache y un proceso que haya estado todo el dia inactivo esta todavia en memoria. Esto puede ocurrir incluso en un sistema con un cache de sistema de archivos muy ocupado, pero solo con la fase lunar correcta.

• El reemplazo NRU simple[Nota] no puede identificar con exactitud el conjunto de trabajo contra los  acessos fortuitos a páginas, y puede llevar a fallos de página extra. Esto no daña notablemente a la mayoria de los tipos de cargas, pero tiene un gran impacto en algunos tipos de cargas y puede solucionarse facilmente, principalmente porque se sabe que el reemplazo LFU usado en kernels mas antiguos funciona.

• Debido al simple algoritmo de reloj de shrink_mmap, algunas veces las paginas limpias, accedidas pueden ser desalojadas antes que las sucias y viejas. Con un caché de archivos relativamente pequeño que consista básicamente de datos sucios, por ejemplo desempacar una bola .tar, es posible que las páginas sucias vacien los buffers (limpios) de metadatos que se necesitan para escribir al disco. Existen otras cuantas excepciones con divertidas variaciones.

• El sistema reacciona malamente a cargas variables de VM o a picos de carga despues de un periodo sin actividad en la VM. Ya que kswapd, el demonio de pageout, solamente escanea cuando el sistema esta bajo en memoria, el sistema puede acabar en un estado en el cual algunas páginas han sido referenciadas en los ultimos 5 segundos, mientras otras páginas lo fueron hace 20 minutos. Esto significa que en un pico de carga el sistema no tiene pistas sobre cuales son las paginas correctas para desalojar de la memoria, esto puede llevar a una tormenta de swap, donde se desalojan las páginas incorrectas y casi inmediatamente despues se vuelven a fallar y reintroducir, llevando al demonio de pageout a otra pagina aleatoria, etc....

• Bajo cargas muy pesadas, el reemplazo NRU de páginas simplemente no encaja. Se necesita un vaciado y limpieza de paginas mas cuidadoso y mejor balanceado. En realidad con la fragilidad del entorno de trabajo de Linux 2.2 este objetivo no es alcanzable.

El hecho de que shrink_mmap sea un algoritmo de reloj simple y que se fie de otras funciones para hacer liberables a las paginas mapeadas de procesos lo hace altamente impredicible. Añade eso al bucle de balanceo en try_to_free_pages y tendrás un subsistema de VM que es extremamente sensible a cambios de ultimo minuto en el código y una bestia frágil cuando se refiere al mantenimiento o (escalofrío) afinamiento.

Cambios en Linux 2.4

En Linux 2.4, una parte substancial del esfuerzo de desarrollo se ha empleado en cosas como hacer al subsistema de VM enteramente fine-grained para sistemas SMP y soporte de máquinas con mas de 1GB de RAM. Los cambios  al código de pageout solo se hicieron en la ultima fase de desarrollo, y son, por ello, algo conservadores y solamente emplean métodos bien conocidos para enfrentarse a los problemas que aparecieron con el reemplazo de páginas de Linux 2.2. Antes de que empecemos con los cambios de el reemplazo de páginas, primero vamos a ver una vista rápida de otros cambios de el subsistema de VM de linux 2.4:

• Bloqueo SMP mas fine-grained. La escalabilidad en el subsistema VM ha mejorado mucho para tipos de cargas donde múltiples CPUs estan leyendo o escribiendo el mismo archivo simultaneamente; por ejemplo, cargas de trabajo de un servidor web o ftp. Esto no tiene ningun influencia real en el código de reemplazo de páginas.

• Unificación del buffer-cache y del page-cache. Mientras en Linux 2.2 el page cache usaba el buffer-cache para escribir sus datos, necesitando una copia extra de los datos y doblando los requerimientos de memoria para algunas cargas de trabajo; en Linux 2.4 las páginas sucias del page cache simplemente se añaden tanto en el buffer cache como en el page cache. El sistema hace IO de disco directamente a y desde  la página del page cache. El buffer cache todavía se mantiene separadamente para metadatos del sistema de archivos y el cacheado de dispositivos de bloque raw . Nótese que el cache ya fue unificado para las lecturas en Linux 2.2, Linux 2.4 simplemente completa la unificación.

• Soporte de sistemas con hasta 64GB de RAM (en x86). Previamente el kernel linux tenía toda la memoría fisica mapeada directamente en el espacio de direcciones virtuales del kernel, que limitaba la cantidad de memoria soportada a ligeramente por debajo de 1GB. Para Linux 2.4 el kernel tambien soporta memoria adicional (la asi llamada "memoria alta" o highmem), que no puede usarse para esctructuras de datos del kernel sino solamente para el page cache y la memoria de los procesos de usuario. Para hacer IO en esas páginas se mapean temporalmente en el espacio de direcciones virtual del kernel y los datos se copian a o desde un búffer  de rebote en la "memoria baja".

  Al mismo tiempo la zona de memoria para DMA ISA (0 - 16MB) se ha separado tambien en una zona de páginas separada. Esto significa que los grandes sistemas x86 terminan teniendo 3 zonas de memoria, que necesitan balancear su memoria libre de manera que podamos continuar asignando estructuras de datos del kernel y búffers ISA DMA. La lógica de las zonas de memoria esta lo suficientemente generalizada tambien para trabajar para sistemas NUMA.

• La memoria compartida SYSV se ha quitado y reemplazado con un simple sistema de archivos de memoria que usa el page cache para todas sus funciones. Soporta ambas semánticas POSIX SHM y SYSV SHM y puede ser usado tambien como sistema de archivos de memoria que se puede llevar a swap (tmpfs).

Ya que los cambios al código de reemplazo de páginas tuvo lugar despues de todos esos cambios y en el periodo(un año y medio largo)  de congelación de código del kernel Linux 2.4, los cambios se han conservado bastante conservadores. Por la otra parte, hemos intentado areglar tantos problemas del reemplazo de páginas de Linux 2.2 como nos ha sido posible. Aqui está una vista rápida de los cambios al reemplazo de páginas: serán descritos con mas detalle abajo.

• Page aging,(en adelante envejecimiento de páginas) que estaba presente en los kernels 1.2 y 2.0 y en FreeBSD ha sido reintroducido en la VM. Sin embargo, se han hecho unos cuantos pequeños cambios para evitar algunos artefactos del envejecimiento basado en páginas virtuales.

• Se ha separado el envejecimiento y vaciado de páginas para evitar el desalojo de las páginas "equivocadas" debido a interacciones de los mismos. Hay listas de páginas activas e inactivas.
• El vaciado de páginas se ha optimizado para evitar demasiada intereferencia por el writeout IO en el IO de lecturas de disco mas crítico.
• Envejecimiento de páginas de fondo controlado durante periodos de pequeña o nula actividad de la VM para conervar al sistema en un estado en el que puede enfrentarse fácilmente con picos de carga.
• El IO secuencial se detecta; hacemos vaciado temprano en las páginas que ya han sido usadas y recompensamos al IO secuancial con un readahead mas agresivo.

Cambios del reemplazo de páginas de Linux 2.4 en detalle

El desarrollo de los cambios en el reemplazo de páginas en Linux 2.4 fue influenciado principalmente por dos factores. En primer logar los malos comportamientos de el reemplazo de páginas de Linux 2.2 tenían que arrreglarse. Usando solamente estrategias bien conocidas porque el desarrollo de Linux 2.4 había entrado ya en el estado de "congelacion de código". En segundo lugar el reemplazo de páginas tenía que ser mas predecible y facil de entender que en Linux 2.2 porque el afinar el reemplazo de páginas en Linux 2.2 se estaba mereciendo la etiqueta de proverbio "sútil y fácil de deprimir". Esto significa que solo se integraron las lideas de VM que estaban bien entendidas y tenían pocas interacciones con el resto del sistema. Muchas ideas fueron tomadas de otros sistemas operativos libremente disponibles y de la literatura.

Envejecimiento de páginas

El envejecimiento de páginas fue el primer paso para hacer irse el mal comportamiento-limite de Linux 2.2, funciona razonablemente bien en Linux 1.2, Linux 2.0 y FreeBSD. El envejecimiento de páginas nos permite hacer una distinción mucho mas fina entre las páginas que queremos conservar en memoria y las páginas que queremos mandar a swap que el envejecimiento NRU de Linux 2.2.

El envejecimiento de páginas en esos Sistemas operativos trabaja de la siguiente forma: conservamos un contador (llamado age "edad" en Linux, o act_count en FreeBSD) para cada páginas física que indica como es de deseable conservar esa página en la memoria. Cuando escaneamos la memoria buscando páginas a vaciar, incrementamos la edad de la página (añadiendo una constante) cuando encontramos que la página fue accedida y decrementamos la edad de la página cuando encontramos que la página no fue accedida. Cuando la edad de la página (o act_count) llega a cero, la página es una candidata para el desalojo.

Sin embargo, se sabes que en algunas situaciones el envejecimiento de páginas LFU[Nota] de Linux 2.0 tiene demasiada sobrecarga de CPU y se ajusta a los cambos de carga muy lentamente. Mas aun, la investigación[Smaragdis, Kaplan, Wilson] ha mostrado que la "recencia" (de reciente) de acceso es un criterio mas importante para el reemplazo de páginas que la frecuencia.

Estos dos problemas estan solventados haciendo una declinación exponencial de la edad de la página (dividir por dos en vez de substraer unas constante) cuando encontramos que una página no fue accedida, resultando en un reemplazo de páginas que es mas cercano a LRU[Nota] que a LFU. Esto reduce la sobrecarga de CPU del envejecimiento de páginas drasticamente en algunos casos, sin embargo no se ha observado ningun cambio notable en el comportamiento del swap..

Otro artefacto viene del escaneo de las direcciones virtuales. En Linux 1.2 y 2.0 el sistema reduce la edad de la página cuando ve que la página no ha sido accedida desde la tabla de páginas que esta escaneando actualmente, ignorando completamente el hecho de que la página podría haber sido accedida desde otras tablas de páginas. Esto puede dar una penalidad severa en las páginas fuertemente compartidas, como la librería de C.

Este problema se arregla simplemente no haciendo "disminuciones" de la edad de los escaneos de las páginas virtuales, sino solamente del escaneo basado en páginas fisicas de la lista activa. Si encontramos páginas que no han sido referenciadas, presentes en las tablas de páginas pero no en la lista activa, simplemente seguimos la ruta de mandara al swap para añadir está página al swap cache y la lista activa asi podremos reducir la edad de esta página y mandarla a swap tan pronto como la edad de la página llegue a cero.

Múltiples listas de páginas

Se han arreglado las malas interacciones entre el envejecimiento y el vaciado de páginas, donde las páginas referenciadas y limpias eran liberadas antes que las viejas y sucias, conservando las páginas que son candidatas para el desalojo separadas de las páginas que queremos conservar en memoria (edad de la página cero vs no-cero). Separamos las paginas poniendolas en varias listas de páginas y teniendo algoritmos separados que tratan cada lista.

Las páginas que (todavía) no son candidatas para el desalojo están en las tablas de páginas de los procesos, en la lista activa o en ambas. El envejecimiento de páginas ocurre en esas páginas, con la función refill_inactive() balanceando entre el escaneo de las tablas de páginas y el escaneo de la lista activa.

Cuando la edad de una página llega a cero, debido a una combinación de escaneo de pageout y que la página no esta siendo usada activamente, la página se mueve a la lista inactive_dirty. Las páginas de esta lista no están mapeadas en las tablas de páginas de ningún proceso y están, o pueden volverse, reclamables. Las páginas en esta lista están manejadas por la función page_launder(), que vacia las páginas sucias al disco y mueve las paginas limpias a la lista inactive_clean.

A diferencia de las listas active e inactive_dirty, la lista inactive_clean no es global, sino que es "por zona de memoria". Las páginas en estas listas pueden ser inmediatamente reusadas por el código de asignación de páginas y cuentan como páginas libres. Estas páginas tambien pueden ser falladas de nuevo hacia donde vinieron, ya que los datos todavía están ahi. En BSD esto se llamaría la cola "cache".

Lista inactiva dimensionadadinámicamente

Ya que hacemos envejecimiento de páginas para seleccionar que páginas evitar, tener una lista inactiva dimensionada estáticamente (como tiene FreeBSD) no tiene mucho sentido. De hecho, cancelaría alguno de los efectos de hacer envejecimiento de páginas en primer lugar: ¿porque perder tanto esfuerzo seleccionando que páginas evitar[Dillon] cuando puedes conservar como mucho un 33% de las páginas que se puede mandar a swap en la lista inactiva? ¿Por qué hacer un envejecimiento de páginas cuidadoso cuando el 33% de tus páginas terminan siendo candidatas para el desalojo a la misma prioridad y has deshecho efectivamente el envejecimiento para ese 33% de páginas que son candidatas para el desalojo?

Por otra parte, tener montones de páginas inactivas para elegir cuando haces desalojo de páginas significa que tienes mas posibilidades de evitar el writeout IO o hacer mejor clustering de IO. Tambien te da como un buffer para gestionar  asignaciones debido a fallos de página, etc.

Tanto un tamaño grande y pequeño para la lista de páginas inactive tiene sus beneficios. En Linux 2.4 hemos elegido un sistema a mitad de tierra permitiendo al sistema variar el tamaño de la lista inactiva dinámicamente dependiendo de la actividad de la VM, con un limite superior artificial para asegurarnos de que el sistema siempre preserva cierta informacion de envejecimiento.

Linux 2.4 conserva flotando una media de la cantidad de páginas desalojadas por segundo y da a la lista inactive y la lista free combinadas al "objetivo libre" más este número medio de robos de páginas por segundo. Esto segundo no nos da solamente suficiente tiempo para hacer todo tipo de optimizaciones de vaciados de página, sino que es lo suficientemente pequeño para conservar la distribución del envejecimiento de páginas intacto, permitiendonos hacer buenas elecciones de qué páginas desalojar y que páginas conservar.

Vaciado de página optimizado

Escribir las páginas de la lista inactiva según las vamos encontrando en la lista inactive_dirty puede destruir totalmente el rendimiento de las lecturas en un sistema a causa de las búsquedas de disco extras hechas. Una solución mejor es retrasar el writeout de las páginas sucias y dejarlas que se acumulen hasta que podamos hacer un clustering de IO mejor de manera que estas páginas pueden escribirse al disco con menos busquedas de disco e interferir menos en el rendimiento de las lecturas.

Debido al desarrollo de los cambios que ocurrieron en la congelación de código, el sistema tiene una implementación simple de lo que ocurre en FreeBSD 4.2. Mientras haya suficientes páginas inactivas limpias alrededor, las seguimos moviendo a la lista inactive_clean y nunca nos preocupamos de sincronizar las páginas sucias. Nótese que esto afecta tanto a las páginas limpias como a las páginas que han sido escritas al disco por el demonio update (que manda los datos del sistema de archivos al disco periodicamente).

Esto significa que bajo cargas donde los datos estan medio escritos podemos evitar escribir las páginas sucias inactivas la mayoría del tiempo, dándonos mucho mejores latencias al liberar páginas y permitiendo a las lecturas secuenciales continuar sin que se requiera mover la cabeza del disco todo el tiempo. Solamente bajo cargas donde muchas páginsa estan siendo ensuciadas rápidamente el sistema sufre un poco de sincronizar los datos sucios irregularmente.

Otra alternativa habría sido la estrategía usada en FreeBSD 4.3, donde las páginas sucias consiguen estar en la lista inactiva mas tiempo que las páginas limpias pero son sincronizadas antes de que las páginas limpias se acaben. Esta estrategia da un IO de pageout mas consistente en FreeBSD durante cargas de mucha escritura. Sin embargo, un gran factor causante de las irregularidades en las escrituras de páginas por la estrategia de arriba bien podría ser causada por el gran objetivo de la lista inactiva en FreeBSD (No está enteramente claro que haría esta estrategia mas complicada cuando se use una lista inactiva dimensionada dinamicamente en Linux 2.4, es por ello por lo que Linux 2.4 usa la estrategia de desalojo de páginas mejor entendida de desalojar las páginas inactivas limpias primero y solamente despues de esas se va a empezar a sincronizar las sucias.

Envejecimiento de páginas de fondo

En muchos sistemas el modo de operación normal es que despues de un periodo de tiempo de relativa actividad un pico de carga ocurre y el sistema tiene que luchar con eso lo mejor posible. Linux 2.2 tiene el problema de que, con la falta de una lista de páginas inactivas, no está claro del todo que páginas deberian desalojarse cuando viene una demanda de memoria repentina.

Linux 2.4 es mejor en este aspecto, con los candidatos hábilmente separados en la lista inactiva. Sin embargo, la lista inactiva podría tener cualquier tamaño en el momento en el que la presiñón de VM cae. Nos gustaría tener al sistema en un estado predecible cuando la presión de la VM es baja. Para conseguir esto, Linux hace un escaneo de fondo de las páginas, intentando conseguir una buena cantidad de páginas en la lista inactiva, pero sin escanear agresivamente de manera que solamente las páginas verdaderamente dormidas terminarán en la lista inactiva y la sobrecarga del escaneo estará baja.

Drop behind

EL IO secuencial no tiene solamente readahead, sino tambien su complemento natural: el drop behind. Despues de que el programa que este haciendo el IO secuencial acabe con una página, decrementamos su prioridad fuertemente de manera que sera uno de los primeros candidatos para el desalojado. Esto no solamente protege a los procesos ejecutandose de ser desalojados rápidamente por el IO secuencial, sino que previene que el IO secuencial compita con los pageouts y los pageins de otros procesos que se esten ejecutando, lo que reduce el número de busquedas del disco y permite que el IO secuencial proceda a una mayor velocidad. Actualmente el readahead y el drop behind solamente funcionan para read() y write(); las filas mmap()eadas y la memoria anonima respaldada por swap no está soportadas.

Conclusiones

Ya que el subsistema de VM de Linux 2.4 esta siendo afinado todavía, es demasiado pronto para mostrar numeros sobre el rendimiento. Sin embargo, los resultados iniciales parecen indicar que Linux 2.4 tiene mejor rendimiento que Linux 2.2 sobre el mismo hardware.

Los reportes de los usuarios indican que en las típicas máquinas de escritorio ha mejorado mucho, aunque el afinado de la nueva VM solamente ha comenzado. Los números para los servidores parecen ser tambien mejores, pero eso tambien podría estar atribuido al hecho de que la unificación del page cache y del buffer cache está completa.

Una gran diferencia entre la VM de Linux 2.4 y la VM en Linux 2.2 es que la nueva VM es bastante menos sensible a los cambios profundos. Mientras en Linux 2.2 un cambio sutil en la lógica de el flushing de páginas podía trastornar el reemplazo de páginas, en Linux 2.4 es posible afinar los varios aspectos de la VM con resultados predecibles y pocos efectos secundarios en el resto de la VM.

Puede tomarse el rendimiento sólido y la insensibilidad relativa a cambios profundos en el entorno como un signo de que la VM de Linux 2.4 no es simplemente unconjunto de arreglos simples para los problemas experienciados en Linux 2.2, sino tambien una buena base para un desarrollo en un futuro.

Problemas pendientes

La VM de Linux 2.4 contiene soluciones fáciles de implementar y obvias de verificar para algunos problemas conocidos  de los que sufre Linux 2.2. Un numero de problemas son o muy profundos para implementarlos durante la congelación del código o tendrán demasiado impacto en el código. La lista completa de items por hacer puede encontrarse en la pçagina de Linux-MM [Linux-MM]; aqui están los mas importantes:

• Prevención de deadlock con poca memoría: con la llegada del sistemas de archivs con journaling y  delayed-allocation es posible que el sistema necesite asignar memoria para liberar memoria; mas precisamente, para escribir datos de manera que la memoria pueda ser liberable. Para eliminar esta posibilidad de deadlock, necesitamos limitar el numero de las transacciones salientes a un número sin peligro, posiblemente permitiendo indicar a cada una de las funciones de vaciado cuanta memoria podría necesitar y guardar un registro de esos valores. Nótese que ocurre el mismo problema con el swap a traves de red.
  

• Control de carga: no importa como sea de bueno el código de reemplazo de páginas, siempre habra un punto en el que los sistemas empezaran a hacer thrashing hasta la muerte. Implementar un sistema de control de carga simple, puede conservar el sistema vivo durante la dura sobrecarga y permite al sistema hacer el suficiente trabajo para devolverla a un estado sano, donde los procesos se suspenden en un sistema round-robin  cuando la carga de paginación es muy alta.

• Limites y garantías del RSS: en algunas situaciones es deseable controlar la cantidad de memoria física que puede consumir un proceso (el conjunto de trabajo residente, "resident set size", RSS). Con el escaneo de páginas del subsistema de VM de Linux basado en direcciones virtuales implementar ulimits RSS y garantias  minimas de RSS es trivial. Ambos ayudan a proteger los procesos bajo carga pesada y permiten al administrador controlar mejor el uso de recursos de memoria.

• Balanceo de VM: en Linux 2.4, el balanceo entre el desalojo de páginas de cache, memoria anónima respaldada por swap, y los caches de inodos y dentry es esencialmente la misma que en Linux 2.2. Mientras que esto funciona bien para la mayoría de los casos hay algunos escenarios posibles donde algunos caches explusan a los otros usuarios de la memoria, llevando a un rendimiento del sistema no optimo. Merecería la pena intentar mejorar el algoritmo de balanceo para conseguir mejor rendimiento en situaciones "no estandares".

• Readahead unificado: actualmente readahead y drop-behind solo funcionan para read() y write(). Idealmente debería funcionar con archivos mmap()eados y memoria anónima tambien. Tener el mismo conjunto de algoritmos para read()/write(), mmap () y la memoria anónima respaldada por swap simplificará el código y hará que las mejoras de readahead y drop behind esten disponibles inmediatamente en todo el sistema.

Reconocimientos

Al autor le gustaría agradecer, en ningún orden en particular, a: Stephen Tweedie, por cuidar de la gestión de memoria en Linux 1.2, 2.0 y 2.2 y tambien por ayudar con este documento; Matt Dillon, por tomarse el tiempo para explicar la lógica detrás de cada pequeña parte de la VM de FreeBSD; Conectiva Inc, quien tiene empleado al autor para hackear el kernel de Linux y por la maravillosa panda de probadores de #kernelnewbies[Kernelnewbies] y a cualquiera que haya ayudado a rreglar los bugs en la VM de Linux 2.4.

Bibliografía

de CastroRodrigo S. de Castro
Linux 2.4 Virtual Memory Overview (2001)
http://linuxcompressed.sourceforge.net/vm24/DillonMatthew Dillon
Design Elements of the FreeBSD VM System (2000)
http://www.daemonnews.org/200001/freebsd_vm.htmlKernelnewbiesKernelnewbies
http://kernelnewbies.org/Linux-MMThe Linux Memory Management home page
http://linux-mm.org/ Smaragdis, Kaplan, WilsonYannis Smaragdakis, Scott F. Kaplan and Paul R. Wilson
EELRU: Simple and Effective Adaptive Page Replacement,
SIGMETRICS '99
http://www.cs.amherst.edu/~sfkaplan/papers/index.html NotaHay documentación sobre algoritmos de reemplazo de páginas practicamente en cualquier parte. Los tres algoritmos usados en este documento son:

• NRU: Not Recently Used, traducido como "no usado recientemente", escaneamos la memoria y vaciamos cada página que no se haya accedido desde la última vez que la escaneamos.
• LRU: vaciamos aquellas páginas que no hayan sido accedidas durante el mayor tiempo.
• LFU: vaciamos aquellas páginas que hayan sido accedidas menos frecuentemente en tiempos recientes.

Sobre este documento ...

Reemplazo de páginas en la gestión de memoria de Linux 2.4

Este documento fue generado usando el traductor LaTeX2HTML Version 99.2beta8 (1.42)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

Los argumentos de la linea de comando fueron:
latex2html -split 0 linux24-vm.la

La traducción fue iniciada por Rik van Riel en 2001-06-27
La traducción a español fue realizada por Diego Calleja

UNIX trabaja muy distinto. Mejor que tener tareas del kernel sirviendo las peticiones de un proceso, el proceso entra por si mismo a Espacio de Kernel. Esto significa, mejor que tener el proceso esperando "fuera" del kernel, este entra al kernel por si mismo (i.e. el proceso comenzara a ejecutar codigo de kernel por si mismo).

Esto puede sonar como un recipiente para un desastre, pero la capacidad del proceso de entrar a espacio de kernel esta estrictamente crontrolado (requiere soporte de hardware). Por ejemplo, en x86, un proceso entra a espacio de kernel a traves de llamadas de sistema - puntos bien conocidos a los cuales el proceso debe invocar para entrar al kernel.

Cuando un proceso invoca una llamada de sistema, el hardware es cambiado a configuraciones de kernel (por ejemplo, en x86, entre otras cosas, el nivel de proteccion esta establecido a ring 0 en vez de ring 3). En este punto, el proceso estara ejecutando codigo de la imagen del kernel. Tiene poder completo para hacer estragos en este punto, no como cuando estuvo en espacio de usuario. Ademas, el proceso no es mas pre-emptible.

Pre-emptibilidad

Los procesos en espacio de usuario son pre-emptibles - esto significa que los procesos pueden tomar la CPU arbitrariamente. Asi es como funcionan las multitarea pre-emptive: la rutina de scheduling peridocamente suspendera el proceso actual en ejecucion, y posiblemente schedule otra tarea para correr esa CPU. Esto significa teoricamente, que un proceso puede estar en la situacion donde este nunca devuelve la CPU. En relialidad el codigo de scheduling tiene interes en la viabilidad y tratara de dar la CPU a cada proceso con un nivel debil de viabilidad, pero no hay garantias.

En contraste, toda tarea (todos los objetos schedulables son referidos como "tareas" para claridad) corriendo en espacio de kernel No puede ser pre-empted. Esto significa que la CPU nunca sera scheduled away de la tarea. Este hecho es complicado por dos aspectos :

Interrupciones

A menos que se hayan deshabilitado las interrupciones (y algunas interrupciones no pueden ser deshabilitadas), una interrupcion puede ocurrir que durante la cual temporalmente interrumpira la tarea en ejecucion. Esto puede pasar en tareas en ambos espacios, de usuario y de kernel. La diferencia es que aqui, para tareas en espacio de kernel, la interrupcion garantiza retorno de la CPU a la tarea tarde o temprano. Para tareas en espacio de usuario, la interrupcion puede causar que otra tarea sea scheduled en la CPU, y puede tambien puede que se ejecuten otras tareas, - aqui en espacio de usuario la tarea debe ser escogida de nuevo por el scheduler. Por supuesto que esta no es la explicacion completa (como es usual) - Primero, hay subsistemas en espacio de kernel que pueden registrar codigo para ser ejecutado al volver de una interrupcion, tal como bottom halves y los tasklets. Esto no cambia el hecho de que, sin embargo, de que el scheduler no estara envuelto en la interrupcion de una tarea en espacio de kernel. Segundo, las interrupciones pueden interrumpir interrupciones - un ejemplo saliente es la arquitectura ARM, donde las interrupciones rapidas (FIQs) tienen prioridad mas alta de hardware que las interrupciones normales (IRQs). Por eso de hecho de una FIQ puede retornar a otro manejador de interrupciones. Tarde o temprano a traves, de la interrupcion original se completara y returnara la CPU a la tarea en espacio de kernel.

Multi-tarea co-operativa

Ya hemos dicho que una tarea en espacio de kernel space no puede tener la CPU scheduled away desde esta. Sin embargo, puede escoger ser schedule() con proposito (y por razones de latencia toda buena llamada de sistema hace esto usualmente). Notese que el termino "con proposito" es un poco engañoso - ya que actualmente significa que una tarea en espacio de kernel, lleno de propositos incluye codigo que puede causar que pase un scheduling. Por ejemplo una tarea puede establecer la politica SCHED_YIELD, entonces se llama volunariamente a la rutina para darle la CPU. Pero tambien puede causar un schedule() to happen usando rutinas que puedan dormir. Un ejemplo comun es kmalloc(), la cual duerme cuando es llamada con una prioridad GFP_KERNEL.

La diferencia aqui pienso es que el codigo en espacio de kernel "sabe" que esto puede causar que ocurra un schedule, por eso tiene la oportunidad de mantener o retener la CPU si quiere. Una tarea en espacio de usuario no tiene oportunidad de eleccion de escoger en el asunto. Una consecuencias esta descrita mas abajo en la seccion "Scheduling y Locks".

Contextos de usuario e hilos del kernel

Recuerda, para el scheduler y para el kernel en grande, todo objecto que sea schedulable (i.e. cualquiera que pueda ser escogido por la rutina schedule()) es conocido como tarea. No se hace distinction entre alguno de esos objectos, por eso usualmente son llamados procesos, LWPs, hilos del kernel , fibras, hilos, etc. son todos solo tareas para el kernel, cada uno de ellos con sus propias caracteristicas particulares. Esto es una gran ganancia en terminos de limpieza de kernel -no hay razon real para separarlos fuera de caso.

Estas caracteristicas particulares estan pensadas interesantemente . Por ejemplo algunas tareas pueden tener mapeos de memoria y pila en espacio de usuario - un ejemplo tipico es un proceso que esta en espacio de usuario. El termino contexto de procesoes usado para referirse a una de esas tareas que se ejecutan en espacio de kernel - ellas tienen de mapeos de espacio, y los (posiblemente temporales) mapeos de kernel y pila. En este contexto se tiene sentido de la copia desde/hacia memoria de usuario.

Una vez mas, lo que a veces se conoce como "hilos del kernel" o "fibras" no se tratan diferente a las otras tareas. Ellas pueden tener mapeos de memoria en espacio de usuario solo como procesos "normales". La unica caracateristica distinguida aqui es el codigo que se ejecuta por los hilos de kernel, que vienen del kernel o de la imagen de un modulo, mejor que desde las imagenes de procesos binarios.

El termino contexto de interrrupcion se usa usualmente para denotar al codigo que actualmente se ejecuta como resultado de una interrupcion de hardware. Esto rodea bottom divide en dos, ISRs, softirqs, y tasklets. Aqui no hay tarea asociada tal como de menos significado para el schedule (y de hecho panicking bug). Esto tambien significa que no puedes dormir aqui, esto implica un schedule.

Algoritmo para Scheduling

El scheduler tiene un problema - hay una contradiccion entre latencia/igualdad (permitiendo que cada tarea se ejecute tan pronto como sea posible) y el costo del cambio de contexto (las operaciones necesarias para cambiar una tarea por otra). Que se asigne demasiado tiempo a una tarea significa que los procesos tendrar que esperar mas por la CPU - esto no es bueno si uno de los procesos esta tratando de brindar facilidades interactivas, por ejemplo. Hacer demasiados cambios usualmente se toma demasiado tiempo en este proceso, dejando menos CPU para hacer algo util en el momento. Cada tarea pre-emptible es ubicada en un periodo de tiempo - un pequeñisimo periodo de tiempo durante el cual se puede ejecutar. La Interrupcion temporizador es invocada peridicamente y esta decidira si la tarea deberia ser pre-empted en favor de otra tarea en la lista de ejecución (la lista de ejecucion es una lista que tiene todas las tareas que estan listas para ejecutarse). Adicionalmente, en el scheduling puede ocurrir cuando sea pedido por el codigo del kernel, y tambien despues que finalizan las llamadas a sistema, en la ruta de retorno de la llamada de sistema del codigo de kernel a espacio de usuario. Mas detalles: aqui.

Algún código

Scheduling y Locking

Ya hemos mencionado que las tareas del kernel no pueden ser pre-empted a menos de que ellas escogan perimitirlo, en puntos bien conocidos (tal como kmalloc() llamada de prioridad GFP_KERNEL). Pero en sistemas SMP, esto aun significa que muchas tareas pueden ejecutarse en espacio de kernel al mismo tiempo (ademas se necesita protección adicional contra interrupciones, igual en sistemas ARRIBA).

Una consecuencia obia es que las tareas necesitan ser "sincronizadas", i.e. recursos compartidos deben darse exclusivamente a una tarea alterando esos resultados. La falta de sincronización adecuada de recursos compartidos se conoce como "condicion de carrera" - llamada de la nocion de que una tarea "esta en carrera" con otra en acceso al recurso. Esto es imparcialmente obio algo malo. Unos de los mecanismos de sincronizacion es el spinlock. Esta es simplemente es una estructura de datos la cual es adquirida automaticamente, y solo puede ser matenida por una sola tarea al tiempo. El spinlock es ya adquirido sobre (la sección de codigo que modifica el recurso compartido de un "estado conocido" a otro). Si la tarea trata de adquirir un spinlock ya ocupado (con spin_lock(&lock) o funcion similar) este "girara", i.e. ejecuta un pequeño bucle hasta que se lanza el spinlock .
Esto es por que es una mala idea (lee: ilegal) llamar a una funcion que puede dormir mientras un spinlock: Mantendras la CPU para otra tarea que puede tratar de aquirir el mismo spinlock. Esto puede facilmente direcciona a un deadlock donde tienes una tarea A esperando por un spinlock entonces este puede dejar libre un recurso necesitado por la tarea B, la cual actualmente mantiene el spinlock que quiere la tarea A.(Adicionalmente el scheduling con un spinlock ya adquirido significa que los apuntadores rotos pueden seguirse cuando se manipula la lista de ejecucion (runqueue)).
Pero, escuche que preguntas, seguramente esto es usualmente necesario para dormir mientras aun se manrtiene la exclusion mutual en alguna estructura de datos ? y en efecto, es. El metodo que generalmente se usa aqui es el semaforo. Hay mucho esfuerzo de diferentes locking primitives, tal como los tipos atomic_t. Lee el documento sobre el kernel-locking en Documentation/DocBook/ en las fuentes del arbol del kernel para mas informacion sobre esto. Algo menor que notar es que el big kernel lock (BKL), usado por lock_kernel() y unlock_kernel(), no es un spinlock normal. Puedes dormir con el BKL ya adquirido, y este se liberara cuando se realize un schedule.

Glossario

Pre-emptible
Una tarea es pre-emptible si la CPU puede ser scheduled y deja de ejecutarse y pasa a otra tarea del proceso. Esto es diferente a una interrupción, donde la interrupcion usa temporalmente la CPU.
Espacio de kernel
Es el codigo que se ejecuta el cual proviene de una imagen de Kernel o de una imagen de un módulo. Esto código tiene permisos completos para hacer lo que el quiera (en x86, el codigo esta en ring 0). Esta puede ser una tarea o una interrupcion invocada. Si es una tarea, no es pre-emptible. El acceso a memoria en espacio de usuario usualmente requiere que los datos sean copidados.
Espacio de Usuario
El codigo ejecutable que proviene de la imagen de un proceso normal. Este se ejecuta en nivel de ring 3 en x86 y tienen derechos limitados. Esta protegido para no afectar a otros procesos o la direccion de espacio del kernel y no tiene acceso directo al hardware (a menos que sea otorgado por el kernel explicitamente).
Contexto de proceso
Codigo ejecutable del kernel por parte de un proceso. El codigo puede schedule (durmiendo, o explicitamente) pero aun no es pre-emptible.

*** Correcciones a moz@compsoc.man.ac.uk.

Última actualización: 2007-04-29 10:57:00-05