stringtranslate.com

Gestión de memoria basada en regiones

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 reasignar o desasignar de manera eficiente todos a la vez. Los asignadores de memoria que utilizan gestiones basadas en regiones a menudo se denominan asignadores de área y, cuando funcionan simplemente "golpeando" un solo puntero, como asignadores de golpe .

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 y permiten que los objetos duren más que el marco de pila en el que fueron asignados. En las implementaciones típicas, todos los objetos de una región se asignan en un único rango contiguo de direcciones de memoria, de manera similar a cómo se asignan normalmente 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 enlazada :

Región * r = createRegion (); ListNode * head = NULL ; for ( int i = 1 ; i <= 1000 ; i ++ ) { ListNode * newNode = allocateFromRegion ( r , sizeof ( ListNode )); newNode -> next = head ; head = newNode ; } // ... // (use la lista aquí) // ... destroyRegion ( r );

Aunque se requieren muchas operaciones para construir la lista enlazada, se puede desasignar rápidamente en una sola operación destruyendo 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 se basa en el trabajo de Hanson. [1] Cada región se implementa como una lista enlazada de grandes bloques de memoria; cada bloque debe ser lo suficientemente grande como 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 anexar a una lista libre global desde la cual otras regiones pueden asignar nuevos bloques más tarde. Con cualquiera de los casos de 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 se realiza en raras ocasiones. A diferencia de los sistemas de recolección de basura típicos , no es necesario etiquetar los datos con su tipo.

Historia y conceptos

El concepto básico de regiones es muy antiguo, apareciendo por primera vez en 1967 en el AED Free Storage Package de Douglas T. Ross, en el que la memoria se dividió en una jerarquía de zonas; cada zona tenía su propio asignador, y una zona podía liberarse de una sola vez, lo que hacía que las zonas se pudieran usar como regiones. [2] En 1976, el estándar PL/I incluyó el tipo de datos AREA. [3] En 1990, Hanson demostró que las regiones explícitas en C (a las que llamó arenas [ aclaración necesaria ] ) podían lograr un rendimiento de tiempo por byte asignado superior incluso al mecanismo de asignación de montón 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 las llama grupos, y el sistema de gestión de bases de datos PostgreSQL , que las llama contextos de memoria. [4] Al igual que la asignación de montón tradicional, estos esquemas no proporcionan seguridad de memoria ; Es posible que un programador acceda a una región después de haberla desasignado a través de un puntero colgante , o que olvide desasignar una región, lo que provoca una pérdida de memoria .

Inferencia de región

En 1988, los investigadores comenzaron a investigar cómo utilizar regiones para la asignación segura de memoria introduciendo 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, son insertadas por el compilador en tiempo de compilación. El compilador puede hacer esto de tal manera que puede garantizar que no se produzcan punteros colgantes ni fugas.

En un trabajo inicial 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 del flujo de datos para determinar una duración de vida para cada expresión de asignación estática y la asignan a la región más reciente que contiene toda su duración de vida.

En 1994, este trabajo se generalizó en un trabajo seminal de Tofte y Talpin para respaldar el polimorfismo de tipos y las 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 los tipos de regiones polimórficas y el cálculo de regiones. [6] [7] Su trabajo introdujo una extensión del cálculo lambda que incluía regiones, agregando dos construcciones:

e 1 en ρ: Calcular el resultado de la expresión e 1 y almacenarlo en la región ρ;
sea ​​la región ρ en e 2 fin: Crea una región y vincúlala a ρ; evalúa 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 crean. Estas restricciones fueron relajadas por Aiken et al. [8]

Este cálculo lambda extendido tenía como objetivo servir como una representación intermedia demostrablemente segura para la memoria para compilar programas ML estándar en código de máquina, pero la creación de un traductor que produjera buenos resultados en programas grandes se enfrentó a una serie de limitaciones prácticas que tuvieron que resolverse con nuevos análisis, incluyendo el manejo 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 de regiones 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 qué tan "amigable con la región" era el programa; los tiempos de compilación, sin embargo, fueron del orden de minutos. [10] El ML Kit finalmente se escaló a aplicaciones grandes con dos adiciones: un esquema para la compilación separada de módulos y una técnica híbrida que combina la inferencia de regiones con el rastreo de la recolección de basura. [11] [12]

Generalización a nuevos entornos lingüísticos

Tras el desarrollo de ML Kit, las regiones comenzaron a generalizarse a otros entornos lingüísticos:

[27] El propósito declarado de estos es mejorar la integración segura con bibliotecas nativas para evitar fugas de memoria de JVM y reducir el riesgo de corrupción de memoria de JVM por código nativo. [28]

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 inactivos; estos problemas se denominan comúnmente "fugas" (aunque finalmente se liberan). La eliminación de las fugas puede implicar la reestructuración del programa, normalmente 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 inferencia de regiones, donde el programador debe comprender el algoritmo de inferencia subyacente o examinar la representación intermedia verbosa para diagnosticar el problema. Los recolectores de basura de rastreo son más eficaces 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, los recolectores de basura de rastreo también pueden presentar fugas sutiles, si se conservan referencias a datos que nunca se volverán a utilizar.

La gestió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 generará un desperdicio de memoria y una sobrecarga de tiempo para la gestión de regiones. Nuevamente, en presencia de inferencia de regiones, este problema puede ser más difícil de diagnosticar.

Métodos híbridos

Como se mencionó anteriormente, RC utiliza un híbrido de regiones y conteo de referencias , lo que limita la sobrecarga del conteo de referencias ya que las referencias internas a las regiones no requieren que se actualicen los conteos cuando se modifican. De manera similar, algunos métodos híbridos de marca-región combinan la recolección de basura de rastreo con regiones; estos funcionan dividiendo el montón en regiones, realizando un pase de barrido de marcas en el que se marcan todas las regiones que contienen objetos activos y luego liberando todas las regiones sin marcar. Estos requieren una desfragmentación continua para seguir siendo efectivos. [34]

Referencias

  1. ^ ab Hanson, David R. (1989). "Asignación y desasignación rápida de memoria basada en la duración 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.
  2. ^ Ross, Douglas (1967). "El paquete de almacenamiento gratuito de AED". Comunicaciones de la ACM . 10 (8): 481–492. doi : 10.1145/363534.363546 . S2CID  6572689.
  3. ^ Instituto Nacional Estadounidense de Estándares (1976). Lenguaje de programación estándar nacional estadounidense PL/I .
  4. ^ 2010 PostgreSQL Global Development Group (1996). "Sección 41.3: Gestión de memoria". Documentación de PostgreSQL 8.2.15 . Consultado el 22 de febrero de 2010 .{{cite web}}: CS1 maint: nombres numéricos: lista de autores ( enlace )
  5. ^ Ruggieri, Cristina; Murtagh, Thomas P. (1988). "Análisis de la duración de 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 .
  6. ^ Tofte, Mads; Jean-Pierre Talpin (1993). Una teoría de la asignación de pila en lenguajes de tipado polimórfico (informe técnico). Departamento de Ciencias de la Computación, Universidad de Copenhague. 93/15.En Citeseer
  7. ^ Tofte, Mads ; Talpin, Jean-Pierre (1994). "Implementación del cálculo λ de llamada por valor tipificado utilizando 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. pp. 188–201. doi : 10.1145/174675.177855 . ISBN 0-89791-636-0. Recuperado el 15 de abril de 2014 .
  8. ^ 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 Ingeniería Eléctrica y Computacional, Universidad de California, Berkeley. UCB/CSD-95-866.En Citeseer
  9. ^ Birkedal, Lars; Tofte, Mads ; Vejlstrup, Magnus (1996). "De la inferencia de regiones a las máquinas de von Neumann a través de la inferencia de representación de regiones". 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. Recuperado el 22 de febrero de 2010 .
  10. ^ Tofte, Mads; Birkedal, Lars; Elsman, Martin; Hallenberg, Niels (2004). "Una retrospectiva sobre la gestión de memoria basada en regiones". Higher Order Symbolic Computing . 17 (3): 245–265. doi : 10.1023/B:LISP.0000029446.78563.a4 . ISSN  1388-3690.
  11. ^ ab 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.
  12. ^ 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. 
  13. ^ "Cyclone: ​​Introducción a las regiones". Manual del usuario de Cyclone . Consultado el 22 de febrero de 2010 .
  14. ^ Grossman, Dan; Morrisett, Greg; Jim, Trevor; Hicks, Michael; Wang, Yanling (2002). "Gestión de memoria basada en regiones en Cyclone". Avisos SIGPLAN . 37 (5): 282–293. doi :10.1145/543552.512563.
  15. ^ Hicks, Michael; Morrisett, Greg ; Grossman, Dan (2004). "Experiencia con la gestión manual segura de la memoria en Cyclone". 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. Recuperado el 22 de febrero de 2010 .
  16. ^ Gay, David (1999). «RC - Gestión segura de memoria 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 .
  17. ^ 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. Recuperado el 22 de febrero de 2010 .
  18. ^ Gay, David Edward (2001). Gestión de memoria con regiones explícitas (PDF) (tesis de doctorado en Ciencias de la Computación). Universidad de California en Berkeley . Consultado el 20 de febrero de 2010 .
  19. ^ Gay, David; Aiken, Alex (2001). "Soporte lingüístico para regiones". Avisos SIGPLAN . 36 (5): 70–80. CiteSeerX 10.1.1.650.721 . doi :10.1145/381694.378815. ISSN  0362-1340. 
  20. ^ 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". CASES '02: Actas de la conferencia internacional de 2002 sobre compiladores, arquitectura y síntesis para sistemas embebidos . Nueva York, NY, EE. UU.: ACM. págs. 288–297. doi :10.1145/581630.581678. ISBN. 1-58113-575-0. Recuperado el 22 de febrero de 2010 .
  21. ^ Christiansen, Morten V. (1998). Gestión de memoria basada en regiones en Java (tesis de maestría en Ciencias de la Computación). Departamento de Ciencias de la Computación (DIKU), Universidad de Copenhague . Consultado el 20 de febrero de 2010 .[ enlace muerto permanente ]
  22. ^ Beebee, William S.; Rinard, Martin C. (2001). "Una implementación de memoria con alcance para Java en tiempo real". EMSOFT '01: Actas del primer taller internacional sobre software integrado . Londres, Reino Unido: Springer-Verlag. págs. 289–305. ISBN. 3-540-42673-6. Recuperado el 22 de febrero de 2010 .[ enlace muerto permanente ]
  23. ^ Sălcianu, Alexandru; Chandrasekhar Boyapati, William Beebee, Jr., Martin Rinard (2003). Un sistema de tipos para la gestión segura de memoria basada en regiones en Java en tiempo real (PDF) (Informe técnico). Laboratorio de Ciencias de la Computación del MIT. MIT-LCS-TR-869.{{cite tech report}}: CS1 maint: varios nombres: lista de autores ( enlace )
  24. ^ Boyapati, Chandrasekhar; Salcianu, Alexandru; Beebee, William Jr. (2003). "Tipos de propiedad para la gestión segura de 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. Recuperado el 22 de febrero de 2010 .
  25. ^ Nahkli, Chaker; Rippert, Christophe; Salagnac, Guillaume; Yovine, Sergio (2007). "Gestión eficiente de memoria basada en regiones para sistemas embebidos en tiempo real con recursos limitados" (PDF) . Actas del "Taller sobre implementación, compilación y optimización de lenguajes, programas y sistemas orientados a objetos (ICOOOLPS'2006)" . Consultado el 22 de febrero de 2010 .
  26. ^ Salagnac, Guillaume; Rippert, Christophe (2007). "Gestión de memoria basada en regiones semiautomática para sistemas integrados Java en tiempo real". RTCSA '07: Actas de la 13.ª Conferencia internacional IEEE sobre sistemas y aplicaciones de computación integrada 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.
  27. ^ "Segmentos y arenas de memoria". Oracle.
  28. ^ Cimadamore, Maurizio. "JEP 454: API de memoria y funciones externas". OpenJDK.
  29. ^ 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 .
  30. ^ Makholm, Henning (2000). "Un administrador de memoria basado en regiones para prolog". ISMM '00: Actas del 2º simposio internacional sobre administración de memoria . Nueva York, NY, EE. UU.: ACM. págs. 25–34. doi :10.1145/362422.362434. ISBN 1-58113-263-8. Recuperado el 22 de febrero de 2010 .
  31. ^ Phan, Quan; Janssens, Gerda (2007). Programación lógica . Apuntes de clase sobre informática. Vol. 4670/2007. Springer Berlin / Heidelberg. págs. 317–332. doi :10.1007/978-3-540-74610-2. ISBN. 978-3-540-74608-9. ISSN  1611-3349.
  32. ^ Phan, Quan; Somogyi, Zoltan (2008). "Soporte en 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 memoria . Nueva York, NY, EE. UU.: ACM. págs. 61–70. doi :10.1145/1375634.1375644. ISBN 978-1-60558-134-7. Recuperado el 15 de abril de 2014 .
  33. ^ Taft, Tucker (2012). "Un camino sin punteros hacia la programación paralela orientada a objetos". Blog de ParaSail . Consultado el 14 de septiembre de 2012 .
  34. ^ Blackburn, Stephen M.; McKinley, Kathryn S. (2008). "Immix: un recolector de basura de región de marca con eficiencia espacial, 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. Recuperado el 15 de abril de 2014 .