En informática , la gestión de memoria basada en regiones es un tipo de gestión de memoria en la que cada objeto asignado se asigna a una región . Una región, también llamada zona , arena , área o contexto de memoria , es una colección de objetos asignados que se pueden desasignar de manera eficiente todos a la vez. Al igual que la asignación de pila , las regiones facilitan la asignación y desasignación de memoria con una sobrecarga baja; pero son más flexibles, lo que permite que los objetos vivan más tiempo que el marco de la pilaen el que fueron asignados. En implementaciones típicas, todos los objetos de una región se asignan en un solo rango contiguo de direcciones de memoria, de manera similar a como se asignan típicamente los marcos de pila.
Ejemplo
Como ejemplo simple, considere el siguiente código C que asigna y luego desasigna una estructura de datos de lista vinculada:
Región * r = createRegion (); ListNode * head = NULL ; for ( int i = 1 ; i <= 1000 ; i ++ ) { ListNode * newNode = allocateFromRegion ( r , sizeof ( ListNode )); newNode -> siguiente = cabeza ; head = newNode ; } // ... // (use la lista aquí) // ... destroyRegion ( r );
Aunque requirió muchas operaciones para construir la lista vinculada, se puede desasignar rápidamente en una sola operación al destruir la región en la que se asignaron los nodos. No es necesario recorrer la lista.
Implementación
Las regiones explícitas simples son fáciles de implementar; la siguiente descripción está basada en Hanson. [1] Cada región se implementa como una lista enlazada de grandes bloques de memoria; cada bloque debe ser lo suficientemente grande para servir a muchas asignaciones. El bloque actual mantiene un puntero a la siguiente posición libre en el bloque, y si el bloque está lleno, se asigna uno nuevo y se agrega a la lista. Cuando se desasigna la región, el puntero de la siguiente posición libre se restablece al comienzo del primer bloque y la lista de bloques se puede reutilizar para la siguiente región asignada. Alternativamente, cuando se desasigna una región, su lista de bloques se puede agregar a una lista libre global desde la cual otras regiones pueden asignar posteriormente nuevos bloques. Con este esquema simple, no es posible desasignar objetos individuales en regiones.
El costo total por byte asignado de este esquema es muy bajo; casi todas las asignaciones implican solo una comparación y una actualización del puntero de la siguiente posición libre. La desasignación de una región es una operación de tiempo constante y rara vez se realiza. A diferencia de los sistemas típicos de recolección de basura , no es necesario etiquetar los datos con su tipo.
Historia y conceptos
El concepto básico de regiones es muy antiguo y apareció por primera vez en 1967 en el paquete de almacenamiento gratuito AED de Douglas T. Ross, en el que la memoria se dividía en una jerarquía de zonas; cada zona tenía su propio asignador, y una zona podía liberarse de una vez, haciendo que las zonas se pudieran utilizar como regiones. [2] En 1976, el estándar PL / I incluía el tipo de datos AREA. [3] En 1990, Hanson demostró que las regiones explícitas en C (a las que llamó arenas) podían lograr un rendimiento de tiempo por byte asignado superior incluso al mecanismo de asignación de montones más rápido conocido. [1] Las regiones explícitas fueron fundamentales en el diseño de algunos de los primeros proyectos de software basados en C, incluido el servidor HTTP Apache , que los llama grupos, y el sistema de administración de bases de datos PostgreSQL , que los llama contextos de memoria. [4] Al igual que la asignación de almacenamiento dinámico tradicional, estos esquemas no proporcionan seguridad en la memoria ; es posible que un programador acceda a una región después de que se desasigne a través de un puntero colgante , o que se olvide de desasignar una región, provocando una pérdida de memoria .
Inferencia de región
En 1988, los investigadores comenzaron a investigar cómo usar regiones para la asignación segura de memoria al introducir el concepto de inferencia de región , donde la creación y desasignación de regiones, así como la asignación de expresiones de asignación estáticas individuales a regiones particulares, es insertada por el compilador en tiempo de compilación. El compilador puede hacer esto de tal manera que puede garantizar que no se produzcan fugas ni punteros colgantes.
En un trabajo temprano de Ruggieri y Murtagh, [5] se crea una región al comienzo de cada función y se desasigna al final. Luego, utilizan el análisis de flujo de datos para determinar la vida útil de cada expresión de asignación estática y la asignan a la región más joven que contiene toda su vida útil.
En 1994, este trabajo fue generalizado en un trabajo seminal de Tofte y Talpin para apoyar el polimorfismo de tipos y funciones de orden superior en Standard ML , un lenguaje de programación funcional , utilizando un algoritmo diferente basado en la inferencia de tipos y los conceptos teóricos de tipos de regiones polimórficas y el cálculo de la región . [6] [7] Su trabajo introdujo una extensión del cálculo lambda que incluye regiones, agregando dos construcciones:
- e 1 en ρ: Calcule el resultado de la expresión e 1 y almacénelo en la región ρ;
- letregion ρ en e 2 end: Crea una región y únela a ρ; evaluar e 2 ; luego desasigne 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 desasignarse antes de r 1 ; el resultado es una pila de regiones. Además, las regiones deben desasignarse en la misma función en la que se crearon. Estas restricciones fueron relajadas por Aiken et al. [8]
Este cálculo lambda extendido estaba destinado a servir como una representación intermedia probadamente segura para la memoria para compilar programas de ML estándar en código de máquina, pero la construcción de un traductor que produciría buenos resultados en programas grandes enfrentó una serie de limitaciones prácticas que debían resolverse con nuevas análisis, incluido el tratamiento de llamadas recursivas, llamadas de cola y la eliminación de regiones que contenían un solo valor. Este trabajo se completó en 1995 [9] y se integró en el ML Kit, una versión de ML basada en la asignación regional en lugar de la recolección de basura. Esto permitió una comparación directa entre los dos en programas de prueba de tamaño mediano, produciendo resultados muy variables ("entre 10 veces más rápido y cuatro veces más lento") dependiendo de cuán "amigable para la región" fuera el programa; los tiempos de compilación, sin embargo, eran del orden de minutos. [10] Eventualmente, el ML Kit fue escalado a grandes aplicaciones con dos adiciones: un esquema para la compilación separada de módulos y una técnica híbrida que combina la inferencia de región con el rastreo de recolección de basura. [11] [12]
Generalización a nuevos entornos lingüísticos
Tras el desarrollo del Kit de AA, las regiones comenzaron a generalizarse a otros entornos lingüísticos:
- Varias extensiones del lenguaje de programación C:
- El Cyclone en dialecto C seguro , que entre muchas otras características agrega soporte para regiones explícitas, y evalúa el impacto de migrar aplicaciones C existentes para usarlas. [13] [14] [15]
- Se implementó una extensión de C llamada RC [16] que usa regiones administradas explícitamente, pero también usa el recuento de referencias en las regiones para garantizar la seguridad de la memoria al garantizar que ninguna región se libere prematuramente. [17] [18] Las regiones reducen la sobrecarga del recuento de referencias, ya que las referencias internas a las regiones no requieren que se actualicen los recuentos cuando se modifican. RC incluye un sistema de tipo estático explícito para regiones que permite eliminar algunas actualizaciones de recuento de referencias. [19]
- Una restricción de C denominada Control-C limita los programas para usar regiones (y solo una región a la vez), como parte de su diseño para garantizar estáticamente la seguridad de la memoria. [20]
- Las regiones se implementaron para un subconjunto de Java , [21] y se convirtieron en un componente crítico de la gestión de memoria en Java en tiempo real , que las combina con tipos de propiedad para demostrar la encapsulación de objetos y eliminar las comprobaciones en tiempo de ejecución en la desasignación de regiones. [22] [23] [24] Más recientemente, se propuso un sistema semiautomático para inferir regiones en aplicaciones Java integradas en tiempo real, combinando un análisis estático en tiempo de compilación, una política de asignación de regiones en tiempo de ejecución y sugerencias para el programador. [25] [26] Las regiones son una buena opción para la computación en tiempo real porque su sobrecarga de tiempo es estáticamente predecible, sin la complejidad de la recolección de basura incremental.
- Fueron implementados para los lenguajes de programación lógica Prolog [27] [28] y Mercury [29] [30] extendiendo el modelo de inferencia de región de Tofte y Talpin para soportar retrocesos y cortes.
- La gestión de almacenamiento basada en regiones se utiliza en todo el lenguaje de programación paralelo ParaSail . Debido a la falta de punteros explícitos en ParaSail, [31] no hay necesidad de contar referencias.
Desventajas
Los sistemas que utilizan regiones pueden experimentar problemas en los que las regiones se vuelven muy grandes antes de que se desasignen y contienen una gran proporción de datos muertos; estos se denominan comúnmente "fugas" (aunque eventualmente se liberan). La eliminación de las fugas puede implicar la reestructuración del programa, por lo general mediante la introducción de nuevas regiones con una vida útil más corta. La depuración de este tipo de problema es especialmente difícil en sistemas que utilizan la inferencia de región, donde el programador debe comprender el algoritmo de inferencia subyacente o examinar la representación intermedia detallada para diagnosticar el problema. Los recolectores de basura de rastreo son más efectivos para desasignar este tipo de datos de manera oportuna sin cambios en el programa; esta fue una justificación para los sistemas híbridos de región / GC. [11] Por otro lado, el rastreo de recolectores de basura también puede exhibir filtraciones sutiles, si se retienen referencias a datos que nunca se volverán a utilizar.
La administración de memoria basada en regiones funciona mejor cuando la cantidad de regiones es relativamente pequeña y cada una contiene muchos objetos; los programas que contienen muchas regiones dispersas exhibirán fragmentación interna , lo que provocará un desperdicio de memoria y una sobrecarga de tiempo para la administración de la región. Nuevamente, en presencia de inferencia regional, este problema puede ser más difícil de diagnosticar.
Métodos híbridos
Como se mencionó anteriormente, RC usa un híbrido de regiones y recuento de referencias , lo que limita la sobrecarga del recuento de referencias, ya que las referencias internas a las regiones no requieren que los recuentos se actualicen cuando se modifican. De manera similar, algunos métodos híbridos marca-región combinan el rastreo de recolección de basura con regiones; estos funcionan dividiendo el montón en regiones, realizando un pase de barrido de marcas en el que se marcan las regiones que contienen objetos en vivo, y luego liberan las regiones no marcadas. Estos requieren una desfragmentación continua para seguir siendo efectivos. [32]
Referencias
- ↑ a b Hanson, David R. (1989). "Asignación y desasignación rápida de memoria basada en la vida de los objetos" . Software: práctica y experiencia . 20 (1): 5–12. doi : 10.1002 / spe.4380200104 . S2CID 8960945 . Archivado desde el original el 20 de octubre de 2012.
- ^ Ross, Douglas (1967). "El paquete de almacenamiento gratuito AED". Comunicaciones de la ACM . 10 (8): 481–492. doi : 10.1145 / 363534.363546 . S2CID 6572689 .
- ^ Instituto Nacional Estadounidense de Estándares, inc. (1976). Programación American National Standard Lenguaje PL / I .
- ^ 2010 Grupo de desarrollo global de PostgreSQL (1996). "Sección 41.3: Gestión de la memoria" . Documentación de PostgreSQL 8.2.15 . Consultado el 22 de febrero de 2010 .
- ^ Ruggieri, Cristina; Murtagh, Thomas P. (1988). "Análisis de por vida de objetos asignados dinámicamente" . POPL '88: Actas del 15º simposio ACM SIGPLAN-SIGACT sobre Principios de lenguajes de programación . Nueva York, NY, EE.UU .: ACM. doi : 10.1145 / 73560.73585 . Consultado el 22 de febrero de 2010 .
- ^ Tofte, Mads; Jean-Pierre Talpin (1993). A Theory of Stack Allocation in Polymorphically Typed Languages (Informe técnico). Departamento de Ciencias de la Computación, Universidad de Copenhague. 93/15. En Citeseer
- ^ Tofte, Mads ; Talpin, Jean-Pierre (1994). "Implementación del cálculo λ de llamada por valor usando una pila de regiones" . POPL '94: Actas del 21º simposio ACM SIGPLAN-SIGACT sobre Principios de lenguajes de programación . Nueva York, NY, EE.UU .: ACM. págs. 188–201. doi : 10.1145 / 174675.177855 . ISBN 0-89791-636-0. Consultado el 15 de abril de 2014 .
- ^ Aiken, Alex; Manuel Fähndrich, Raph Levien (1995). Mejor gestión de la memoria estática: mejora del análisis basado en regiones de lenguajes de orden superior (informe técnico). Departamento de EECS, Universidad de California, Berkeley. UCB / CSD-95-866. En Citeseer
- ^ Birkedal, Lars ; Tofte, Mads ; Vejlstrup, Magnus (1996). "De la inferencia de la región a las máquinas de von Neumann a través de la inferencia de representación de la región" . POPL '96: Actas del 23º simposio ACM SIGPLAN-SIGACT sobre Principios de lenguajes de programación . Nueva York, NY, EE.UU .: ACM. págs. 171-183. doi : 10.1145 / 237721.237771 . ISBN 0-89791-769-3. Consultado el 22 de febrero de 2010 .
- ^ Tofte, Mads; Birkedal, Lars; Elsman, Martin; Hallenberg, Niels (2004). "Una retrospectiva de la gestión de memoria basada en regiones" . Computación simbólica de orden superior . 17 (3): 245-265. doi : 10.1023 / B: LISP.0000029446.78563.a4 . ISSN 1388-3690 .
- ^ a b Hallenberg, Niels; Elsman, Martin; Tofte, Mads (2003). "Combinación de inferencia de región y recolección de basura". Avisos SIGPLAN . 37 (5): 141-152. doi : 10.1145 / 543552.512547 . ISSN 0362-1340 .
- ^ Elsman, Martin (2003). "Seguridad de recolección de basura para la gestión de memoria basada en regiones". Avisos SIGPLAN . 38 (3): 123-134. CiteSeerX 10.1.1.57.8914 . doi : 10.1145 / 640136.604190 . ISSN 0362-1340 .
- ^ "Ciclón: Introducción a las regiones" . Manual de usuario de Cyclone . Consultado el 22 de febrero de 2010 .
- ^ Grossman, Dan; Morrisett, Greg; Jim, Trevor; Hicks, Michael; Wang, Yanling (2002). "Gestión de memoria basada en regiones en ciclón". Avisos SIGPLAN . 37 (5): 282-293. doi : 10.1145 / 543552.512563 .
- ^ Hicks, Michael; Morrisett, Greg ; Grossman, Dan (2004). "Experiencia con gestión de memoria manual segura en ciclón" . ISMM '04: Actas del 4º simposio internacional sobre gestión de la memoria . Nueva York, NY, EE.UU .: ACM. págs. 73–84. doi : 10.1145 / 1029873.1029883 . ISBN 1-58113-945-4. Consultado el 22 de febrero de 2010 .
- ^ Gay, David (1999). "RC - Gestión de memoria segura basada en regiones para C" . Página de inicio de David Gay . Intel Labs Berkeley. Archivado desde el original el 26 de febrero de 2009 . Consultado el 22 de febrero de 2010 .
- ^ Gay, David ; Aiken, Alex (1998). "Gestión de memoria con regiones explícitas" . PLDI '98: Actas de la conferencia ACM SIGPLAN 1998 sobre diseño e implementación de lenguajes de programación . Nueva York, NY, EE.UU .: ACM. págs. 313–323. doi : 10.1145 / 277650.277748 . ISBN 0-89791-987-4. Consultado el 22 de febrero de 2010 .
- ^ Gay, David Edward (2001). Gestión de la memoria con regiones explícitas (PDF) (Tesis de Doctorado en Informática). Universidad de California en Berkeley . Consultado el 20 de febrero de 2010 .
- ^ Gay, David ; Aiken, Alex (2001). "Soporte de idiomas para regiones". Avisos SIGPLAN . 36 (5): 70–80. CiteSeerX 10.1.1.650.721 . doi : 10.1145 / 381694.378815 . ISSN 0362-1340 .
- ^ Kowshik, Sumant; Dhurjati, Dinakar; Adve, Vikram (2002). "Garantizar la seguridad del código sin comprobaciones en tiempo de ejecución para sistemas de control en tiempo real" . CASOS '02: Actas de la conferencia internacional de 2002 sobre compiladores, arquitectura y síntesis para sistemas integrados . Nueva York, NY, EE.UU .: ACM. págs. 288-297. doi : 10.1145 / 581630.581678 . ISBN 1-58113-575-0. Consultado el 22 de febrero de 2010 .
- ^ Christiansen, Morten V. (1998). Gestión de memoria basada en regiones en Java (tesis de maestría en informática). Departamento de Ciencias de la Computación (DIKU), Universidad de Copenhague . Consultado el 20 de febrero de 2010 .[ enlace muerto permanente ]
- ^ Beebee, William S .; Rinard, Martin C. (2001). "Una implementación de memoria de alcance para Java en tiempo real" . EMSOFT '01: Actas del Primer Taller Internacional sobre Software Embebido . Londres, Reino Unido: Springer-Verlag. págs. 289-305. ISBN 3-540-42673-6. Consultado el 22 de febrero de 2010 .[ enlace muerto permanente ]
- ^ Sălcianu, Alexandru; Chandrasekhar Boyapati, William Beebee, Jr., Martin Rinard (2003). Un sistema de tipos para la gestión segura de la memoria basada en regiones en Real-Time Java (PDF) (Informe técnico). Laboratorio de Ciencias de la Computación del MIT. MIT-LCS-TR-869.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Boyapati, Chandrasekhar ; Salcianu, Alexandru ; Beebee, Jr., William (2003). "Tipos de propiedad para la gestión segura de la memoria basada en regiones en Java en tiempo real" . PLDI '03: Actas de la conferencia ACM SIGPLAN 2003 sobre diseño e implementación de lenguajes de programación . Nueva York, NY, EE.UU .: ACM. págs. 324–337. doi : 10.1145 / 781131.781168 . ISBN 1-58113-662-5. Consultado el 22 de febrero de 2010 .
- ^ Nahkli, Chaker ; Rippert, Christophe ; Salagnac, Guillaume ; Yovine, Sergio (2007). "Gestión eficiente de la memoria basada en regiones para sistemas integrados en tiempo real con recursos limitados" (PDF) . Actas del "Taller sobre Implementación, Compilación, Optimización de Lenguajes, Programas y Sistemas Orientados a Objetos (ICOOOLPS'2006)" . Consultado el 22 de febrero de 2010 .
- ^ Salagnac, Guillaume ; Rippert, Christophe (2007). "Gestión de memoria semiautomática basada en regiones para sistemas integrados Java en tiempo real". RTCSA '07: Actas de la 13ª Conferencia Internacional IEEE sobre aplicaciones y sistemas informáticos integrados y en tiempo real . Washington, DC, EE.UU .: IEEE Computer Society. págs. 73–80. doi : 10.1109 / RTCSA.2007.67 . ISBN 978-0-7695-2975-2.
- ^ Makholm, Henning (2000). Gestión de memoria basada en regiones en Prolog (PDF) (Tesis de Maestría en Ciencias de la Computación). Universidad de Copenhague, Dinamarca. Archivado desde el original (PDF) el 5 de junio de 2011 . Consultado el 20 de febrero de 2010 .
- ^ Makholm, Henning (2000). "Un administrador de memoria basado en regiones para prolog" . ISMM '00: Actas del 2º simposio internacional sobre gestión de la memoria . Nueva York, NY, EE.UU .: ACM. págs. 25–34. doi : 10.1145 / 362422.362434 . ISBN 1-58113-263-8. Consultado el 22 de febrero de 2010 .
- ^ Phan, Quan ; Janssens, Gerda (2007). Análisis de región estática para Mercurio . Apuntes de clase en Ciencias de la Computación: Programación lógica . Apuntes de conferencias en Ciencias de la Computación. 4670/2007. Springer Berlín / Heidelberg. págs. 317–332. doi : 10.1007 / 978-3-540-74610-2 . ISBN 978-3-540-74608-9. ISSN 1611-3349 .
- ^ Phan, Quan ; Somogyi, Zoltan (2008). "Soporte de tiempo de ejecución para la gestión de memoria basada en regiones en Mercury" . ISMM '08: Actas del 7º simposio internacional sobre gestión de la memoria . Nueva York, NY, EE.UU .: ACM. págs. 61–70. doi : 10.1145 / 1375634.1375644 . ISBN 978-1-60558-134-7. Consultado el 15 de abril de 2014 .
- ^ Taft, Tucker (2012). "Una ruta sin punteros a la programación paralela orientada a objetos" . Blog de ParaSail . Consultado el 14 de septiembre de 2012 .
- ^ Blackburn, Stephen M .; McKinley, Kathryn S. (2008). "Immix: un recolector de basura de región de marca con eficiencia de espacio, recolección rápida y rendimiento de mutador" . PLDI '08: Actas de la conferencia ACM SIGPLAN de 2008 sobre diseño e implementación de lenguajes de programación . Nueva York, NY, EE.UU .: ACM. págs. 22–32. doi : 10.1145 / 1375581.1375586 . ISBN 978-1-59593-860-2. Consultado el 15 de abril de 2014 .