Recolección de basura (informática)

En informática , la recolección de basura ( GC ) es una forma de gestión automática de memoria . ^[2] El recolector de basura intenta recuperar la memoria que fue asignada por el programa, pero que ya no está referenciada; dicha memoria se llama basura . La recolección de basura fue inventada por el científico informático estadounidense John McCarthy alrededor de 1959 para simplificar la gestión manual de la memoria en Lisp . ^[3]

La recolección de basura libera al programador de realizar una gestión manual de la memoria , donde el programador especifica qué objetos desasignar y devolver al sistema de memoria y cuándo hacerlo. ^[4] Otras técnicas similares incluyen la asignación de pila , la inferencia de región y la propiedad de la memoria, y combinaciones de las mismas. La recolección de basura puede ocupar una proporción significativa del tiempo de procesamiento total de un programa y, como resultado, afectar el rendimiento .

Los recursos distintos de la memoria, como los sockets de red , los manejadores de bases de datos , las ventanas , los descriptores de archivos y los descriptores de dispositivos, no suelen ser manejados por la recolección de basura, sino por otros métodos (por ejemplo, los destructores ). Algunos de estos métodos también desasignan memoria.

Esta sección necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes confiables en esta sección. El material sin fuentes puede ser cuestionado y eliminado. ( Julio de 2014 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Muchos lenguajes de programación requieren recolección de basura, ya sea como parte de la especificación del lenguaje (por ejemplo, RPL , Java , C# , D , ^[5] Go y la mayoría de los lenguajes de script ) o de manera efectiva para la implementación práctica (por ejemplo, lenguajes formales como el cálculo lambda ). ^[6] Se dice que estos son lenguajes de recolección de basura . Otros lenguajes, como C y C++ , fueron diseñados para su uso con administración manual de memoria, pero tienen implementaciones de recolección de basura disponibles. Algunos lenguajes, como Ada , Modula-3 y C++/CLI , permiten que tanto la recolección de basura como la administración manual de memoria coexistan en la misma aplicación mediante el uso de montones separados para objetos recolectados y administrados manualmente. Aún otros, como D , son de recolección de basura pero permiten al usuario eliminar objetos manualmente o incluso deshabilitar la recolección de basura por completo cuando se requiere velocidad. ^[7]

Aunque muchos lenguajes integran el GC en su compilador y sistema de ejecución , también existen sistemas de GC post-hoc , como el conteo automático de referencias (ARC). Algunos de estos sistemas de GC post-hoc no requieren recompilación. ^[8]

Esta sección no cita ninguna fuente . Por favor, ayude a mejorar esta sección añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado . ( Abril de 2021 ) ( Aprenda cómo y cuándo eliminar este mensaje )

GC libera al programador de la tarea de desasignar memoria manualmente, lo que ayuda a evitar algunos tipos de errores : ^[9]

• Punteros colgantes , que se producen cuando se libera un fragmento de memoria mientras todavía hay punteros hacia él y uno de esos punteros se desreferencia . Para entonces, la memoria puede haber sido reasignada a otro uso, con resultados impredecibles. ^[10]
• Errores de doble liberación , que ocurren cuando el programa intenta liberar una región de memoria que ya ha sido liberada, y quizás ya ha sido asignada nuevamente.
• Ciertos tipos de fugas de memoria , en las que un programa no logra liberar la memoria ocupada por objetos que se han vuelto inalcanzables , lo que puede provocar el agotamiento de la memoria. ^[11]

GC utiliza recursos informáticos para decidir qué memoria liberar. Por lo tanto, la penalización por la conveniencia de no anotar la duración de los objetos manualmente en el código fuente es la sobrecarga , que puede perjudicar el rendimiento del programa. ^[12] Un artículo revisado por pares de 2005 concluyó que GC necesita cinco veces más memoria para compensar esta sobrecarga y funcionar tan rápido como el mismo programa utilizando una gestión de memoria explícita idealizada. Sin embargo, la comparación se realiza con un programa generado insertando llamadas de desasignación utilizando un oráculo , implementado mediante la recopilación de rastros de programas ejecutados bajo un generador de perfiles , y el programa solo es correcto para una ejecución particular del programa. ^[13] La interacción con los efectos de la jerarquía de memoria puede hacer que esta sobrecarga sea intolerable en circunstancias que son difíciles de predecir o detectar en pruebas de rutina. El impacto en el rendimiento fue dado por Apple como una razón para no adoptar la recolección de basura en iOS , a pesar de ser la característica más deseada. ^[14]

El momento en que se recolecta la basura puede ser impredecible, lo que da como resultado bloqueos (pausas para cambiar/liberar memoria) dispersos a lo largo de una sesión . Los bloqueos impredecibles pueden ser inaceptables en entornos de tiempo real , en el procesamiento de transacciones o en programas interactivos. Los recolectores de basura incrementales, concurrentes y en tiempo real abordan estos problemas, con diferentes compensaciones.

El rastreo de la recolección de basura es el tipo más común de recolección de basura, tanto que "recolección de basura" a menudo se refiere al rastreo de la recolección de basura, en lugar de otros métodos como el conteo de referencias . La estrategia general consiste en determinar qué objetos deben ser recolectados como basura rastreando qué objetos son accesibles por una cadena de referencias desde ciertos objetos raíz, y considerando el resto como basura y recolectándolos. Sin embargo, hay una gran cantidad de algoritmos utilizados en la implementación, con características de complejidad y rendimiento muy variables.

La recolección de basura por conteo de referencias es cuando cada objeto tiene un recuento de la cantidad de referencias a él. La basura se identifica por tener un recuento de referencias de cero. El recuento de referencias de un objeto se incrementa cuando se crea una referencia a él y se decrementa cuando se destruye una referencia. Cuando el recuento llega a cero, se recupera la memoria del objeto. ^[15]

Al igual que con la gestión manual de memoria, y a diferencia del seguimiento de la recolección de basura, el conteo de referencias garantiza que los objetos se destruyan tan pronto como se destruye su última referencia y, por lo general, solo accede a la memoria que se encuentra en cachés de CPU , en objetos que se liberarán o directamente apuntados por estos y, por lo tanto, tiende a no tener efectos secundarios negativos significativos en el funcionamiento de la memoria caché de la CPU y la memoria virtual .

El recuento de referencias tiene varias desventajas; por lo general, esto se puede solucionar o mitigar mediante algoritmos más sofisticados:

Ciclos

Si dos o más objetos se refieren entre sí, pueden crear un ciclo por el cual ninguno será recolectado ya que sus referencias mutuas nunca dejan que sus recuentos de referencia se vuelvan cero. Algunos sistemas de recolección de basura que utilizan el recuento de referencias (como el de CPython ) utilizan algoritmos específicos de detección de ciclos para lidiar con este problema. ^[16] Otra estrategia es usar referencias débiles para los "retropunteros" que crean ciclos. Bajo el recuento de referencias, una referencia débil es similar a una referencia débil bajo un recolector de basura de rastreo. Es un objeto de referencia especial cuya existencia no incrementa el recuento de referencias del objeto referente. Además, una referencia débil es segura en el sentido de que cuando el objeto referente se convierte en basura, cualquier referencia débil a él caduca , en lugar de permitir que permanezca colgando, lo que significa que se convierte en un valor predecible, como una referencia nula.

Espacio de arriba (recuento de referencia)

El recuento de referencias requiere que se asigne espacio para que cada objeto almacene su recuento de referencias. El recuento puede almacenarse adyacente a la memoria del objeto o en una tabla auxiliar en algún otro lugar, pero en cualquier caso, cada objeto con recuento de referencias requiere almacenamiento adicional para su recuento de referencias. El espacio de memoria con el tamaño de un puntero sin signo se utiliza comúnmente para esta tarea, lo que significa que se deben asignar 32 o 64 bits de almacenamiento de recuento de referencias para cada objeto. En algunos sistemas, puede ser posible mitigar esta sobrecarga utilizando un puntero etiquetado para almacenar el recuento de referencias en áreas no utilizadas de la memoria del objeto. A menudo, una arquitectura en realidad no permite que los programas accedan a la gama completa de direcciones de memoria que podrían almacenarse en su tamaño de puntero nativo; se ignora una cierta cantidad de bits altos en la dirección o se requiere que sea cero. Si un objeto tiene de manera confiable un puntero en una ubicación determinada, el recuento de referencias se puede almacenar en los bits no utilizados del puntero. Por ejemplo, cada objeto en Objective-C tiene un puntero a su clase al comienzo de su memoria; En la arquitectura ARM64 que utiliza iOS 7 , se utilizan 19 bits no utilizados de este puntero de clase para almacenar el recuento de referencia del objeto. ^{[17] [18]}

Sobrecarga de velocidad (incremento/disminución)

En implementaciones ingenuas, cada asignación de una referencia y cada referencia que cae fuera del ámbito a menudo requieren modificaciones de uno o más contadores de referencia. Sin embargo, en un caso común cuando una referencia se copia de una variable de ámbito externo a una variable de ámbito interno, de modo que la duración de la variable interna está limitada por la duración de la variable externa, el incremento de la referencia se puede eliminar. La variable externa "posee" la referencia. En el lenguaje de programación C++, esta técnica se implementa y demuestra fácilmente con el uso de constreferencias. El conteo de referencias en C++ generalmente se implementa utilizando " punteros inteligentes " ^[19] cuyos constructores, destructores y operadores de asignación administran las referencias. Un puntero inteligente se puede pasar por referencia a una función, lo que evita la necesidad de copiar y construir un nuevo puntero inteligente (que aumentaría el conteo de referencias al ingresar a la función y lo disminuiría al salir). En cambio, la función recibe una referencia al puntero inteligente que se produce de manera económica. El método Deutsch-Bobrow de conteo de referencias aprovecha el hecho de que la mayoría de las actualizaciones del conteo de referencias se generan de hecho por referencias almacenadas en variables locales. Ignora estas referencias, solo cuenta las referencias en el montón, pero antes de que se pueda eliminar un objeto con un recuento de referencias cero, el sistema debe verificar con un escaneo de la pila y registrar que aún no existe otra referencia a él. Se puede obtener una disminución sustancial adicional en la sobrecarga de las actualizaciones de contadores mediante la fusión de actualizaciones introducida por Levanoni y Petrank . ^{[20] [21]} Considere un puntero que en un intervalo dado de la ejecución se actualiza varias veces. Primero apunta a un objeto O1, luego a un objeto O2, y así sucesivamente hasta que al final del intervalo apunta a algún objeto On. Un algoritmo de conteo de referencias normalmente ejecutaría rc(O1)--, rc(O2)++, rc(O2)--, rc(O3)++, rc(O3)--, ..., rc(On)++. Pero la mayoría de estas actualizaciones son redundantes. Para que el recuento de referencias se evalúe correctamente al final del intervalo, es suficiente realizar rc(O1)--y rc(On)++. Levanoni y Petrank midieron una eliminación de más del 99% de las actualizaciones de contadores en puntos de referencia típicos de Java.

Requiere atomicidad

Cuando se utilizan en un entorno multiproceso , estas modificaciones (incremento y decremento) pueden necesitar ser operaciones atómicas como compare-and-swap , al menos para cualquier objeto que sea compartido, o potencialmente compartido entre múltiples subprocesos. Las operaciones atómicas son costosas en un multiprocesador, y aún más costosas si tienen que ser emuladas con algoritmos de software. Es posible evitar este problema agregando recuentos de referencia por subproceso o por CPU y solo accediendo al recuento de referencia global cuando los recuentos de referencia locales se vuelven o ya no son cero (o, alternativamente, usando un árbol binario de recuentos de referencia, o incluso renunciando a la destrucción determinista a cambio de no tener un recuento de referencia global en absoluto), pero esto agrega una sobrecarga de memoria significativa y, por lo tanto, tiende a ser útil solo en casos especiales (se usa, por ejemplo, en el recuento de referencia de los módulos del kernel de Linux). La coalescencia de actualizaciones de Levanoni y Petrank ^{[20] [21]} se puede usar para eliminar todas las operaciones atómicas de la barrera de escritura. Los contadores nunca son actualizados por los subprocesos del programa durante la ejecución del programa. Solo son modificados por el recopilador, que se ejecuta como un único subproceso adicional sin sincronización. Este método se puede utilizar como un mecanismo de parada del mundo para programas paralelos y también con un recopilador de recuento de referencias concurrentes.

No en tiempo real

Las implementaciones ingenuas del conteo de referencias generalmente no brindan un comportamiento en tiempo real, porque cualquier asignación de puntero puede potencialmente hacer que una cantidad de objetos limitada solo por el tamaño total de memoria asignada se liberen de manera recursiva mientras el subproceso no puede realizar otro trabajo. Es posible evitar este problema delegando la liberación de objetos no referenciados a otros subprocesos, a costa de una sobrecarga adicional.

El análisis de escape es una técnica de tiempo de compilación que puede convertir asignaciones de montón en asignaciones de pila , reduciendo así la cantidad de recolección de basura que se debe realizar. Este análisis determina si un objeto asignado dentro de una función es accesible fuera de ella. Si se descubre que una asignación local de función es accesible para otra función o subproceso, se dice que la asignación "se escapa" y no se puede realizar en la pila. De lo contrario, el objeto se puede asignar directamente en la pila y liberar cuando la función regresa, evitando el montón y los costos de administración de memoria asociados. ^[22]

En términos generales, es más probable que los lenguajes de programación de alto nivel tengan la recolección de basura como una característica estándar. En algunos lenguajes que carecen de recolección de basura incorporada, se puede agregar a través de una biblioteca, como en el caso del recolector de basura Boehm para C y C++.

La mayoría de los lenguajes de programación funcional , como ML , Haskell y APL , tienen la recolección de basura incorporada. Lisp es especialmente notable por ser el primer lenguaje de programación funcional y el primer lenguaje en introducir la recolección de basura. ^[23]

Otros lenguajes dinámicos, como Ruby y Julia (pero no Perl  5 o PHP antes de la versión 5.3, ^[24] que utilizan el conteo de referencias), JavaScript y ECMAScript también tienden a utilizar GC. Los lenguajes de programación orientados a objetos como Smalltalk , RPL y Java suelen proporcionar recolección de basura integrada. Las excepciones notables son C++ y Delphi , que tienen destructores .

BASIC y Logo han utilizado a menudo la recolección de basura para tipos de datos de longitud variable, como cadenas y listas, para no sobrecargar a los programadores con detalles de gestión de memoria. En el Altair 8800 , los programas con muchas variables de cadena y poco espacio de cadena podían causar largas pausas debido a la recolección de basura. ^[25] De manera similar, el algoritmo de recolección de basura del intérprete de Applesoft BASIC escanea repetidamente los descriptores de cadena en busca de la cadena que tenga la dirección más alta para compactarla hacia una memoria alta, lo que resulta en un mejor rendimiento ^[26] y pausas en cualquier momento desde unos pocos segundos hasta unos pocos minutos. ^[27] Un recolector de basura de reemplazo para Applesoft BASIC por Randy Wigginton identifica un grupo de cadenas en cada paso sobre el montón, lo que reduce drásticamente el tiempo de recolección. ^[28] BASIC.SYSTEM, lanzado con ProDOS en 1983, proporciona un recolector de basura con ventanas para BASIC que es mucho más rápido. ^[29]${\displaystyle O(n^{2})}$

Aunque tradicionalmente Objective-C no tenía recolección de basura, con el lanzamiento de OS X 10.5 en 2007 Apple introdujo la recolección de basura para Objective-C  2.0, utilizando un recolector de tiempo de ejecución desarrollado internamente. ^[30] Sin embargo, con el lanzamiento de OS X 10.8 en 2012 , la recolección de basura quedó obsoleta en favor del contador de referencia automático (ARC) de LLVM que se introdujo con OS X 10.7 . ^[31] Además, desde mayo de 2015 Apple incluso prohibió el uso de la recolección de basura para nuevas aplicaciones de OS X en la App Store . ^{[32] [33]} Para iOS , la recolección de basura nunca se ha introducido debido a problemas en la capacidad de respuesta y el rendimiento de la aplicación; ^{[14] [34]} en su lugar, iOS utiliza ARC. ^{[35] [36]}

La recolección de basura rara vez se utiliza en sistemas integrados o en tiempo real debido a la necesidad habitual de un control muy estricto sobre el uso de recursos limitados. Sin embargo, se han desarrollado recolectores de basura compatibles con muchos entornos limitados. ^[37] Microsoft .NET Micro Framework , .NET nanoFramework ^[38] y Java Platform, Micro Edition son plataformas de software integrado que, al igual que sus primos mayores, incluyen la recolección de basura.

Los recolectores de basura disponibles en los JDK de Java incluyen:

• G1
• Paralelo
• Recopilador de barrido de marcas concurrente (CMS)
• De serie
• C4 (Colector Compactador Continuamente Concurrente) ^[39]
• Shenandoah
• ZGC

La recolección de basura en tiempo de compilación es una forma de análisis estático que permite reutilizar y recuperar la memoria en función de invariantes conocidas durante la compilación.

Esta forma de recolección de basura se ha estudiado en el lenguaje de programación Mercury , ^[40] y vio un mayor uso con la introducción del contador de referencia automático (ARC) de LLVM en el ecosistema de Apple (iOS y OS X) en 2011. ^{[35] [36] [32]}

Se han desarrollado recolectores de basura incrementales, concurrentes y en tiempo real, por ejemplo, por Henry Baker y por Henry Lieberman . ^{[41] [42] [43]}

En el algoritmo de Baker, la asignación se realiza en cualquiera de las mitades de una región de memoria. Cuando se llena a la mitad, se realiza una recolección de basura que mueve los objetos activos a la otra mitad y los objetos restantes se desasignan implícitamente. El programa en ejecución (el "mutador") tiene que comprobar que cualquier objeto al que hace referencia esté en la mitad correcta y, si no, moverlo a la otra mitad, mientras que una tarea en segundo plano busca todos los objetos. ^[44]

Los esquemas de recolección de basura generacional se basan en la observación empírica de que la mayoría de los objetos mueren jóvenes. En la recolección de basura generacional, se mantienen dos o más regiones de asignación (generaciones), que se mantienen separadas en función de la edad del objeto. Los objetos nuevos se crean en la generación "joven" que se recolecta regularmente y, cuando una generación está llena, los objetos a los que todavía se hace referencia desde regiones más antiguas se copian en la siguiente generación más antigua. Ocasionalmente, se realiza un análisis completo.

Algunas arquitecturas informáticas de lenguajes de alto nivel incluyen soporte de hardware para la recolección de basura en tiempo real.

La mayoría de las implementaciones de recolectores de basura en tiempo real utilizan rastreo . ^{[ cita requerida ]} Dichos recolectores de basura en tiempo real cumplen con estrictas restricciones de tiempo real cuando se utilizan con un sistema operativo en tiempo real. ^[45]

• Destructor (programación informática)
• Eliminación dinámica de código muerto
• Puntero inteligente
• Compresión de memoria virtual

• Jones, Richard; Hosking, Antony; Moss, J. Eliot B. (16 de agosto de 2011). Manual de recolección de basura: el arte de la gestión automática de la memoria . Serie de estructuras de datos y algoritmos aplicados de CRC. Chapman y Hall / CRC Press / Taylor & Francis Ltd. ISBN 978-1-4200-8279-1.(511 páginas)
• Jones, Richard; Lins, Rafael (12 de julio de 1996). Recolección de basura: algoritmos para la gestión automática de la memoria dinámica (1.ª edición). Wiley . ISBN 978-0-47194148-4.(404 páginas)
• Schorr, Herbert; Waite, William M. (agosto de 1967). "Un procedimiento eficiente e independiente de la máquina para la recolección de basura en varias estructuras de lista" (PDF) . Comunicaciones de la ACM . 10 (8): 501–506. doi :10.1145/363534.363554. S2CID  5684388. Archivado (PDF) desde el original el 22 de enero de 2021.
• Wilson, Paul R. (1992). "Técnicas de recolección de basura en procesadores monoprocesadores". Gestión de memoria . Apuntes de clase en informática. Vol. 637. Springer-Verlag . Págs. 1–42. CiteSeerX  10.1.1.47.2438 . Doi : 10.1007/bfb0017182. ISBN. 3-540-55940-X. {{cite book}}: |journal=ignorado ( ayuda )
• Wilson, Paul R.; Johnstone, Mark S.; Neely, Michael; Boles, David (1995). "Asignación dinámica de almacenamiento: una revisión crítica y de estudio". Memory Management . Lecture Notes in Computer Science. Vol. 986 (1.ª ed.). págs. 1–116. CiteSeerX  10.1.1.47.275 . doi :10.1007/3-540-60368-9_19. ISBN 978-3-540-60368-9. {{cite book}}: |journal=ignorado ( ayuda )

El Wikilibro Gestión de memoria tiene una página sobre el tema: Recolección de basura

• La referencia de gestión de memoria
• Los conceptos básicos de la recolección de basura
• Ajuste de la recolección de basura de la máquina virtual HotSpot de Java SE 6
• TinyGC: una implementación independiente de la API de BoehmGC
• Implementación de recolección de basura conservadora para lenguaje C
• MeixnerGC: un recolector de basura incremental de marcado y barrido para C++ que utiliza punteros inteligentes