La administración de memoria basada en regiones es una forma de administrar la memoria en la que cada objeto creado en la memoria se asigna a una "región" específica.
Una región, también llamada zona, arena [1] , región o contexto de memoria, es un conjunto de objetos asignados que se pueden desasignar de manera eficiente al mismo tiempo. De forma similar a la gestión de memoria basada en pilas , la gestión de memoria basada en regiones facilita la asignación y desasignación de memoria, lo que permite que se realice con una sobrecarga mínima. Pero, en comparación con la pila, la gestión de la memoria mediante regiones puede ser más flexible: permiten que los objetos vivan más tiempo que cuando se colocan en un marco de pila. En implementaciones típicas, todos los objetos en la misma región se asignan en el mismo rango contiguo de direcciones de memoria, de forma similar a cómo se asignan normalmente los marcos de pila.
En comparación con la asignación de memoria basada en pilas, la administración de memoria basada en regiones permite una forma más natural de implementar la asignación de memoria en la programación paralela. Además, las regiones facilitan mucho el trabajo con la virtualización y diversas técnicas de optimización del rendimiento de la memoria, simplificando la tarea de mover simultáneamente todos los objetos pertenecientes a una misma región a la memoria con acceso más rápido o más lento [2] .
Como ejemplo simple, considere el siguiente código C que asigna y luego libera una estructura de datos como una lista enlazada :
Región * r = crearRegión (); NodoLista * cabeza = NULL ; para ( int yo = 1 ; yo <= 1000 ; yo ++ ) { ListNode * newNode = allocateFromRegion ( r , sizeof ( ListNode )); nuevoNodo -> siguiente = cabeza ; cabeza = nuevoNodo ; } // ... // (use la lista aquí) // ... destroyRegion ( r );Aunque se necesitaron muchas operaciones para crear la lista vinculada, se puede destruir rápidamente en una operación, liberando el área donde se colocaron los elementos de la lista. No es necesario escanear la lista y eliminar sus elementos individualmente.
Las regiones explícitas simples son fáciles de implementar; la siguiente descripción se basa en un artículo de David Hanson [ 3 ] . Cada región se implementa como una lista enlazada de grandes bloques de memoria; cada bloque debe ser lo suficientemente grande para asignar memoria para muchos objetos dentro de él. La estructura de datos de la región contiene un puntero a la siguiente posición libre dentro del bloque y, si el bloque está lleno, el sistema de administración de memoria asigna un nuevo bloque y lo agrega a la lista. Cuando se libera una región, el siguiente puntero de posición libre se restablece al comienzo del primer bloque y la lista completa de bloques ya creados se puede reutilizar para cambiar la posición de los objetos dentro de la región. En una implementación alternativa, cuando se libera una región, la lista de bloques asignados a ella puede devolverse a la lista libre global, desde la cual otras regiones pueden asignar nuevos bloques posteriormente. Sin embargo, dentro de un esquema tan simple, no es posible liberar memoria individualmente de objetos específicos dentro de un bloque.
La sobrecarga por byte asignado es muy baja para este esquema. Casi todos los episodios de asignación de memoria implican solo comparar y actualizar el puntero a la siguiente posición libre. Las únicas excepciones son aquellos episodios en los que se agota la memoria del bloque y el administrador de memoria debe adjuntar un nuevo bloque a la región. Liberar una región es una operación de tiempo fijo que rara vez se realiza. A diferencia de los sistemas típicos de recolección de basura , la administración de datos basada en regiones no necesita marcar cada objeto de datos con su tipo .
El concepto mismo de regiones es muy antiguo. Se implementó por primera vez en 1967 en el paquete de almacenamiento gratuito AED de Douglas Ross , en el que la memoria se dividía en una jerarquía de zonas. Para cada una de las zonas, la disciplina de gestión de memoria podría configurarse individualmente. Cada una de las zonas podría liberarse mediante una operación común. Así, en este paquete de software, Ross implementó por primera vez el concepto de gestión de memoria basada en regiones prácticamente [4] . En 1976 , el tipo de datos AREA se incluyó en el estándar de lenguaje PL/I para la gestión de grupos de estructuras de datos [5] . En 1990, Hanson demostró que las regiones explícitamente definidas en C (a las que llamó arenas) en la gestión de la memoria pueden proporcionar un rendimiento, medido como el tiempo empleado por byte asignado, que supera incluso al mecanismo de asignación de montón más rápido conocido [3] . Las regiones explícitas desempeñaron un papel importante en el desarrollo de una serie de proyectos de software basados en C, incluido Apache HTTP Server , donde se denominan grupos, y PostgreSQL , donde se denominan contextos de memoria [6] . Al igual que la asignación de almacenamiento dinámico tradicional, estos esquemas no brindan seguridad de acceso a la memoria ; un programador puede acceder a una región de la memoria después de que se haya liberado a través de un enlace pendiente u olvidarse de liberar la región, lo que resulta en una fuga de memoria .
En 1988, los científicos comenzaron a explorar cómo usar regiones para la asignación segura de memoria, introduciendo el concepto de inferencia de región . Como parte de esta técnica, el compilador inserta en el código en la etapa de compilación las directivas para asignar y liberar regiones, así como los objetos individuales ubicados en la memoria que están vinculados estáticamente a una región en particular. El compilador sabe cómo hacer esto de tal manera que puede garantizar la ausencia de punteros colgantes y pérdidas de memoria. En sus primeros trabajos, Ruggieri y Murtagh exploraron una variante de esta técnica en la que se crea una región cuando se ejecuta cada función y se libera cuando finaliza [7] . Al hacerlo, utilizaron el análisis de flujo de datos para determinar la vida útil de cada objeto de memoria asignado estáticamente y luego asignar ese objeto para la asignación a la región más joven por el tiempo de creación que contiene objetos con esa vida útil. En 1994, este trabajo se resumió en el trabajo original de Tofte y Talpin, quienes ampliaron la técnica propuesta por Ruggieri y Murtagh para admitir el polimorfismo de tipos y funciones de orden superior en el lenguaje de programación funcional Standard ML . El trabajo de Tofte y Talpin usó un algoritmo diferente basado en la inferencia de tipos y los conceptos teóricos de tipos de regiones y cálculo de regiones [8] [9] . Propusieron una extensión del cálculo lambda, incluyendo regiones como una entidad especial. De hecho, agregaron las siguientes dos construcciones al cálculo lambda:
e 1 en ρ: calcular el resultado de la expresión e 1 y almacenarlo en la región ρ; letregion ρ in e2 end: crea una región y vincúlala a ρ; calcule e 2 , luego libere la región.Debido a esta estructura sintáctica, las regiones están "anidadas", lo que significa que si r 2 se crea después de r 1 , también debe liberarse antes de r 1 . El resultado es una "pila" de regiones. Además, las regiones deben ser liberadas en la misma función en que fueron creadas. Las restricciones fueron relajadas en parte por Aiken y otros [10] .
Este cálculo lambda extendido estaba destinado a servir como una representación intermedia demostrablemente segura para la memoria para compilar programas de ML estándar en código de máquina. Sin embargo, la creación de un traductor que pudiera dar buenos resultados para programas grandes se topó con una serie de limitaciones prácticas. Tuvieron que resolverse utilizando un nuevo análisis, incluido el trabajo con llamadas recursivas, llamadas recursivas de cola y la eliminación de regiones que contienen solo un valor de la representación intermedia generada. Este trabajo se completó en 1995 [11] . Sus resultados fueron utilizados por ML Kit, una versión de ML cuyo manejo de memoria se basaba en regiones, en lugar de recolección de elementos no utilizados. El advenimiento del ML Kit permitió una comparación directa entre las dos compilaciones de programas de prueba de tamaño mediano, lo que arrojó resultados muy diferentes ("10 veces más rápido y cuatro veces más lento") dependiendo de cuán "apto para la región" sea un programa de prueba en particular. fue [12] . ML Kit finalmente se amplió para aplicaciones grandes. Se implementaron dos adiciones en él: compilación separada de módulos y una técnica híbrida que combina la deducción de los límites de la región con la recolección regular de basura. [13] [14]
Luego del desarrollo del ML Kit, se comenzaron a implementar regiones para otros lenguajes de programación:
Los sistemas que usan regiones pueden experimentar problemas en los que las regiones se vuelven muy grandes antes de que se liberen y, por lo tanto, contienen una alta proporción de datos muertos. Estas regiones generalmente se denominan "fugas de memoria" (aunque finalmente se liberan). La reparación de estas fugas puede requerir la reestructuración del programa. Por lo general, se produce agregando nuevas regiones con una vida útil más corta. La depuración de este tipo de problema es particularmente difícil en los sistemas que utilizan la inferencia de región , donde el programador debe comprender el algoritmo de inferencia subyacente al sistema o analizar la representación intermedia en detalle para diagnosticar el problema. La depuración de programas que utilizan recolectores de basura tradicionales es mucho más fácil, y la liberación oportuna de la memoria que tiene fugas se puede lograr sin reestructurar el programa, simplemente eliminando errores lógicos en su construcción. Estas consideraciones han dado lugar a sistemas híbridos que combinan la gestión de memoria basada en regiones y la recolección de basura convencional [13] . Por otro lado, al depurar programas con recolección de basura, también pueden ocurrir filtraciones si se almacenan referencias a datos que no se volverán a utilizar, y esta circunstancia tiene que ser monitoreada mucho más cuidadosamente por el programador que en un sistema con base en regiones. gestión de la memoria.
La administración de memoria basada en regiones funciona mejor cuando el número de regiones es relativamente pequeño y cada región contiene muchos objetos. Los programas que contienen muchas regiones dispersas sufrirán fragmentación interna . Esto, al final, puede conducir a la pérdida de memoria y al tiempo adicional dedicado a administrar regiones. Nuevamente, cuando se trabaja con la salida de la región, este problema puede ser más difícil de diagnosticar.
Como se mencionó anteriormente, el lenguaje RC utiliza una técnica de gestión de memoria híbrida que incluye regiones y recuento de referencias . Este enfoque reduce la sobrecarga del recuento de referencias, ya que los enlaces entre objetos dentro de una región no requieren actualizar los contadores cuando se modifican, agregan o eliminan. De manera similar, algunos métodos híbridos que utilizan el etiquetado de regiones combinan el seguimiento de accesibilidad de objetos de recolección de elementos no utilizados con regiones. Dichos métodos implican dividir el montón en regiones, realizar un pase de seguimiento que marca las regiones que contienen objetos vivos y luego liberar las regiones sin etiquetar. Este enfoque requiere una desfragmentación constante de la memoria para que sea eficaz [34] .