Empiezo con éste una serie de artículos, traducidos de los originales de M.Tim Jones (mtj@mtjones.com) y que se pueden encontrar en el servicio de documentación técnica de IBM. Algunos de ellos ya tienen algunos meses de antigüedad, lamentablemente los he descubierto recientemente a partir del último publicado, pero los voy a ir traduciendo en el orden cronológico de publicación intentando traducir uno cada semana.

Puesto que muchas veces la designación técnica de algunos elementos y algoritmos descritos en estos artículos suele ser la inglesa, sin que exista una traducción válida, adjuntaré a cada traducción literal que haga de estos conceptos el nombre original en inglés.

Y una vez expuestos estos dos puntos, empiezo con el cuerpo del artículo original.

 

Anatomía del asignador de losas (slab allocator) de Linux

[artículo original]

Un buen rendimiento del sistema operativo depende en parte de la habilidad del propio sistema para gestionar eficientemente los recursos. En los viejos tiempos, los gestores de pila (heap memory managers) eran la norma, pero el rendimiento se veia afectado por la fragmentación y la necesidad de reasignar memoria. Hoy, el núcleo de Linux® usa un método que fue originado en Solaris pero que ha sido usado en sistemas empotrados durante algún tiempo ya, asignando memoria como objetos basándose en su tamaño. Éste artículo explora las ideas tras el asignador de losas (slab allocator) y examina sus interfaces y sus usos.

Gestión de memoria dinámica

 

El objetivo de la gestión de memoria es proveer de un método por el cual la memoria pueda ser compartida de manera dinámica entre una variedad de usuarios para una variedad de propósitos. El método de gestión de memoria usado debería cumplir las dos siguientes premisas:

  • Minimizar la cantidad de tiempo requerido para gestionar la memoria
  • Maximizar la memoria disponible para uso general (minimizando la sobrecarga de gestión)

La gestión de memoria es, en última instancia, una suma nula de compensaciones. Se puede desarrollar un algortimo que use poca memoria para la gestión, pero al que le lleve mucho tiempo gestionar la memoria disponible. También se puede desarrollar un algoritmo que gestione la memoria muy eficientemente pero que use un poco más de memoria. Finalmente, los requisitos de una aplicación particular nos llevan al balance de compensaciones.

Los primeros gestores de memoria usaban una estrategia de asignación basada en pila. En éste método, un bloque grande de memoria (llamado pila) es usado para proveer memoria a los fines de cada usuario. Cuando los usuarios necesitan un bloque de memoria, hacen una petición de una determinada cantidad. El gestor de la pila mira en la memoria disponible (usando algún algoritmo particular) y devuelve el bloque. Algunos de los algoritmos usados en esta búsqueda son del tipo primer-ajuste (first-fit), en los que el bloque devuelto es el primero que se encuentre y que satisface la petición, o bien del tipo mejor-ajuste (best-fit), en los que el bloque devuelto es el que mejor se ajuste a la petición. Cuando los usuarios han terminado con la memoria, devuelven el bloque a la pila.

El problema principal con esta estrategia de asignación basada en pila es la fragmentación. A medida que se van asignando bloques de memoria, son devueltos en diferente orden y en diferentes instantes. Esto tiende a dejar agujeros en la pila haciendo necesario más tiempo para gestionar eficientemente la memoria libre. Éste algoritmo tiende a ser eficiente en consumo de memoria (ya que asigna exactamente lo que es necesario), pero requiere más tiempo para gestionar la pila.

Otra aproximación, llamada asignación de memoria del amigo (buddy memory allocation), es una técnica de memoria rápida que divide la memoria en un número de particiones potencia-de-2 y trata de asignar las peticiones de memoria usando una aproximación del tipo mejor-ajuste. Cuando la memoria es liberada por el usuario, el bloque amigo es chequeado para ver si alguno de sus vecinos colindantes han sido también liberados. Si es asi, los bloques son combinados para minimizar la fragmenteación. Éste algoritmo tiende a ser un poco más eficiente en tiempo pero puede desperdiciar memoria debido a la aproximación de mejor-ajuste.

Éste artículo se centra en la gestión de memoria del núcleo de Linux y, en particular, en los mecanismo provistos gracias a la asignación de losas (slab allocation).

La caché de losas (slab cache)

El asignador de losas usado en Linux se basa en un algoritmo originalmente creado por Jeff Bonwick para el sistema operativo SunOS. El asignador de Jeff gira en torno al cacheado de objetos. Dentro de un núcleo, una considerable cantidad de memoria es asignada para un conjunto finito de objetos tales como descriptores de ficheros y otras estructuras comunes. Jeff vió que la cantidad de tiempo requerido para inicializar un objeto ordinario en el núcleo excedía la cantidad de tiempo requerido para asignarlo y liberarlo. Su conclusión fue que, en lugar de retornar la memoria de vuelta al contenedor global, él hizo que la memoria siguiera inicializada para el propósito previsto. Por ejemplo, si la memoria había sido asignada para un exclusor mútuo (mutex), la función de inicialización (mutex_init) sólo necesita ser ejecutada una vez cuando la memoria es asignada por primera vez al exclusor mútuo. Subsiguientes asignaciones de la memoria no necesitarian ejecutar la inicialización porque ya se encontraria en el estado deseado desde la liberación previa y la llamada al destructor.

El asignador de losas de Linux usa estas ideas y otras para construir un asignador de memoria que es eficiente tanto en espacio como en tiempo.

La figura 1 ilustra el alto nivel de organización de las estructuras de losas. En el nivel más alto está la cadena de caché ( cache_chain), que es una lista enlazada de las cachés de losas. Esto es útil para los algoritmos de mejor-ajuste que buscan una caché que mejor se ajuste al tamaño de la asignación deseada (iterado sobre la lista). Cada elemento de la cache_chain es un puntero a una estructura kmem_cache (lo que llamamos una caché). Esto define un contenedor de objetos de un tamaño fijo para gestionar.

Figura 1. Las principales estructuras del asignador de losas

Las principales estructuras del asignador de losas

Cada caché contiene una lista de losas (slabs), que son bloques de memoria contiguos (típicamente páginas). Existen 3tres tipos de losas:

slabs_full
Losas que son asignadas completamente.
slabs_partial
Losas que son parcialmente asignadas.
slabs_empty
Losas que están vacías, o que son objetos no asignados.

Evidentemente las losas en la lista slabs_empty son los primeros candidatos para la recolecta (reaping). Este es el proceso por el cual la memoria usada por las losas es devuelta al sistema operativo para otros usos.

Cada losa en su lista es un bloque de memoria contiguo (una o más páginas contiguas) que es dividido en objetos. Estos objetos son los elementos fundamentales que se asignan y liberan de una caché en particular. Fijese en que la losa es la minima asignación posible del asignador de losas, así que si necesita crecer, ésta es la cantidad mínima en que crecerá. Típicamente, múltiples objetos son asignados en cada losa.

 

A medida que los objetos son asignados y liberados de una losa, la losa individual se puede mover entre las listas de losas. Por ejemplo, cuando todos los objetos son consumidos dentro de una losa, se mueve de la lista slabs_partial hacia la lista slabs_full. Cuando una losa está llena y un objeto es liberado, se mueve de la lista slabs_full hacia la lista slabs_partial. Cuando todos los objetos son liberados, se mueve desde la lista slabs_partial hasta la lista slabs_empty.

Motivación a favor de las losas

El asignador de caché de losas proveé una serie de beneficios sobre los esquemas tradicionales de gestión de memoria. Primero, los núcleos normalmente esperan múltiples asignaciones de los mismos pequeños objetos a lo largo del tiempo de vida del sistema. El asignador de caché de losas dispone de esto gracias al cacheado de objetos de tamaños similares, evitando de este modo el problema de la fragmentación que suele ocurrir. El asignador de losas también soporta la inicialización de objetos comunes, evitando así la necesidad de inicializar repetidamente un objeto para un mismo propósito. Finalmente, el asignador de losas soporta alineación y coloreado de caché por hardware, lo que permite a objetos en diferentes cachés ocupar las mismas lineas de caché para un incremento del uso de la caché y un mejor rendimiento.

 

 

Nota del traductor. A partir de éste punto, el artículo incluye código fuente y ejemplos prácticos sobre el código del slab caché allocator, lo que hace complicada y algo inútil su traducción. Teniendo en cuenta que la teoría ya ha sido expuesta y que lo importante para entender el concepto ya ha sido traducido, entiendo que si a alguien le interesa el resto sobre el código fuente, por favor se remita al artículo original, ya que la diferencia entre ese y como lo pueda yo traducir aquí será mínima y por tanto un esfuerzo inútil para mí. Espero de todas maneras que esta traducción le sirva a alguien para entender y tener claro el concepto del gestor de memoria usado por Linux.