Recolección de basura (informática)

Colección de basura parada y copiada en una arquitectura Lisp: La memoria se divide en trabajo y gratis memoria; nuevos objetos se asignan en el primero. Cuando está lleno (depicado), la colección de basura se realiza: Todas las estructuras de datos que aún están en uso están ubicadas por localización de punteros y copiadas en lugares consecutivos en memoria libre.

Después de eso, el contenido de memoria de trabajo se descarta a favor de la copia comprimida, y el papel de trabajo y gratis la memoria se intercambia (depicted).

En informática, la recolección de basura (GC) es una forma de gestión automática de la memoria. El recolector de basura intenta recuperar la memoria que fue asignada por el programa, pero ya no se hace referencia a ella; dicha memoria se llama basura. La recolección de basura fue inventada por el informático estadounidense John McCarthy alrededor de 1959 para simplificar la gestión manual de la memoria en Lisp.

La recolección de elementos no utilizados libera al programador de la gestión manual de la memoria, donde el programador especifica qué objetos desasignar y devolver al sistema de memoria y cuándo hacerlo. Otras técnicas similares incluyen asignación de pila, inferencia de región y propiedad de memoria, y combinaciones de las mismas. La recolección de elementos no utilizados puede tomar 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 identificadores de bases de datos, las ventanas, los descriptores de archivos y los descriptores de dispositivos, normalmente no se manejan con la recolección de elementos no utilizados, sino con otros métodos (por ejemplo, destructores). Algunos de estos métodos también desasignan memoria.

Resumen

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

Aunque muchos lenguajes integran GC en su compilador y sistema de tiempo de ejecución, también existen sistemas GC post-hoc, como el conteo automático de referencias (ARC). Algunos de estos sistemas GC post-hoc no requieren recompilación. La GC Post-hoc a veces se denomina recolección de basura para distinguirla de la GC ordinaria.

Ventajas

GC libera al programador de la desasignación manual de memoria. Esto ayuda a evitar algunos tipos de errores:

• Puntos colgantes, que ocurre cuando un pedazo de memoria se libera mientras todavía hay apuntadores a ella, y uno de esos punteros es dereferenciado. Para entonces la memoria puede haber sido reasignada a otro uso, con resultados impredecibles.
• Insectos dobles gratis, que ocurre cuando el programa trata de liberar una región de memoria que ya ha sido liberada, y tal vez ya se ha asignado de nuevo.
• Ciertos tipos de filtraciones de memoria, en el que un programa falla en la memoria libre ocupada por objetos que se han vuelto inalcanzables, lo que puede llevar al agotamiento de la memoria.

Desventajas

GC utiliza recursos informáticos para decidir qué memoria liberar. Por lo tanto, la penalización por la conveniencia de no anotar manualmente la vida útil del objeto en el código fuente es una sobrecarga, lo que puede afectar el rendimiento del programa. 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 la administración de memoria explícita idealizada. Sin embargo, la comparación se realiza con un programa generado mediante la inserción de llamadas de desasignación utilizando un oráculo, implementado mediante la recopilación de seguimientos de programas que se ejecutan bajo un generador de perfiles, y el programa solo es correcto para una ejecución particular del programa. La interacción con los efectos de la jerarquía de la memoria puede hacer que esta sobrecarga sea intolerable en circunstancias que son difíciles de predecir o detectar en las pruebas de rutina. Apple adujo el impacto en el rendimiento como una razón para no adoptar la recolección de basura en iOS, a pesar de ser la característica más deseada.

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

Estrategias

Rastreo

El seguimiento de la recolección de basura es el tipo más común de recolección de basura, tanto es así que "recolección de basura" a menudo se refiere al seguimiento de la recolección de elementos no utilizados, en lugar de otros métodos, como el recuento de referencias. La estrategia general consiste en determinar qué objetos deben recolectarse como basura rastreando qué objetos son accesibles mediante una cadena de referencias desde ciertos objetos raíz, y considerar el resto como basura y recolectarlos. Sin embargo, hay una gran cantidad de algoritmos utilizados en la implementación, con características de rendimiento y complejidad muy variables.

Recuento de referencias

La recolección de basura de recuento de referencias es donde cada objeto tiene un recuento del número de referencias a él. La basura se identifica teniendo un conteo de referencia de cero. El recuento de referencias de un objeto aumenta cuando se crea una referencia a él y disminuye cuando se destruye una referencia. Cuando el conteo llega a cero, se recupera la memoria del objeto.

Al igual que con la gestión manual de la memoria, y a diferencia del seguimiento de la recolección de elementos no utilizados, el recuento de referencias garantiza que los objetos se destruyan tan pronto como se destruya 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 apuntado directamente por ellos y, por lo tanto, tiende a no tener efectos secundarios negativos significativos en el caché de la CPU y el funcionamiento de la memoria virtual.

Hay una serie de desventajas en el conteo de referencias; esto generalmente se puede resolver o mitigar con algoritmos más sofisticados:

Ciclos

Si dos o más objetos se refieren entre sí, pueden crear un ciclo por el cual ninguno será recogido como sus referencias mutuas nunca permita que sus recuentos de referencia se conviertan en cero. Algunos sistemas de recolección de basura utilizando el recuento de referencia (como el de CPython) usan algoritmos específicos de detección de ciclos para tratar este problema. Otra estrategia es utilizar referencias débiles para los "puntos traseros" que crean ciclos. Bajo recuento de referencia, una referencia débil es similar a una referencia débil bajo un recolector de basura rastreador. Es un objeto de referencia especial cuya existencia no aumenta el recuento de referencia del objeto referente. Además, una referencia débil es segura en que cuando el objeto referente se convierte en basura, cualquier referencia débil a él lapsos, en lugar de ser permitido permanecer colgando, lo que significa que se convierte en un valor predecible, como una referencia nula.

Superficie del espacio (conteo de referencia)

El recuento de referencia requiere espacio para cada objeto para almacenar su recuento de referencia. El recuento puede ser almacenado adyacente a la memoria del objeto o en una mesa lateral en algún otro lugar, pero en cualquier caso, cada objeto de referencia único requiere almacenamiento adicional para su recuento de referencia. Espacio de memoria con el tamaño de un puntero no firmado se utiliza comúnmente para esta tarea, lo que significa que 32 o 64 bits de almacenamiento de referencia deben ser asignados para cada objeto. En algunos sistemas, puede ser posible mitigar este exceso utilizando un puntero etiquetado para almacenar el recuento de referencia en áreas no utilizadas de la memoria del objeto. A menudo, una arquitectura no permite realmente que los programas accedan a la gama completa de direcciones de memoria que podrían almacenarse en su tamaño de puntero nativo; cierto número de pedazos altos en la dirección es ya sea ignorado o requerido para ser cero. Si un objeto tiene un puntero en un lugar determinado, el recuento de referencia 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 usando iOS 7, 19 bits no utilizados de este puntero de clase se utilizan para almacenar el recuento de referencia del objeto.

Velocidad (incremento/decremento)

En las implementaciones ingenuas, cada asignación de una referencia y cada referencia que caen fuera de alcance a menudo requieren modificaciones de uno o más contadores de referencia. Sin embargo, en un caso común cuando se copia una referencia de una variable de alcance exterior en una variable de alcance interno, de tal manera que la vida de la variable interna está ligada por la vida del exterior, el aumento de referencia se puede eliminar. La variable exterior "apropia" la referencia. En el lenguaje de programación C++, esta técnica se implementa fácilmente y se demuestra con el uso de const referencias. El recuento de referencia en C++ generalmente se implementa usando "puntos inteligentes" cuyos constructores, destructores y operadores de asignación gestionan las referencias. Un puntero inteligente se puede pasar por referencia a una función, que evita la necesidad de copiar-construir un nuevo puntero inteligente (que aumentaría el recuento de referencia en la entrada en la función y disminuirla en la salida). En cambio, la función recibe una referencia al puntero inteligente que se produce de manera económica. El método Deutsch-Bobrow de recuento de referencia capitaliza el hecho de que la mayoría de las actualizaciones de recuento de referencia se generan de hecho por referencias almacenadas en variables locales. No hace caso omiso de estas referencias, sólo contando referencias en el montón, pero antes de que un objeto con referencia cuenta cero se puede eliminar, el sistema debe verificar con un escaneo de la pila y registra que ninguna otra referencia a ella todavía existe. Otra disminución sustancial de la sobrecarga en las actualizaciones de contadores puede obtenerse por coalescing actualizado introducido por Levanoni y Petrank. Considere un puntero que en un intervalo dado de la ejecución se actualiza varias veces. Primero apunta a un objeto O1, entonces a un objeto O2, y así sucesivamente hasta el final del intervalo señala a algún objeto On. Un algoritmo de conteo de referencia 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 tener el recuento de referencia debidamente evaluado al final del intervalo es suficiente para 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 utiliza en un entorno multitejido, estas modificaciones (incremento y decremento) pueden necesitar ser operaciones atómicas tales como comparación y intercambio, al menos para cualquier objeto que se comparta, o potencialmente compartido entre múltiples hilos. Las operaciones atómicas son costosas en un multiprocesador, e incluso más costosas si tienen que ser emuladas con algoritmos de software. Es posible evitar este problema añadiendo los recuentos de referencia per-tread o per-CPU y sólo accediendo al recuento global de referencia cuando la referencia local cuenta convertirse o ya no son cero (o, alternativamente, utilizando un árbol binario de recuentos de referencia, o incluso renunciando a la destrucción determinista a cambio de no tener un recuento global de referencia), pero esto añade una carga significativa de memoria y por lo tanto tiende a ser útil en casos especiales (por ejemplo, Actualizar el coalescing por Levanoni y Petrank se puede utilizar para eliminar todas las operaciones atómicas del corredor de escritura. Los contadores nunca son actualizados por los hilos del programa en el curso de ejecución del programa. Sólo son modificados por el coleccionista que ejecuta como un solo hilo adicional sin sincronización. Este método se puede utilizar como mecanismo para detener el mundo para programas paralelos, y también con un colector de conteo de referencia concurrente.

No en tiempo real

Las implementaciones inactivas del recuento de referencia generalmente no proporcionan comportamiento en tiempo real, ya que cualquier asignación puntero puede potencialmente causar una serie de objetos ligados sólo por el tamaño total de memoria asignado para ser liberado recursivamente mientras que el hilo es incapaz de realizar otro trabajo. Es posible evitar este problema delegando la liberación de objetos no referenciados a otros hilos, a costa de sobrecarga adicional.

Análisis de escape

El análisis de escape es una técnica en tiempo de compilación que puede convertir asignaciones de montón en asignaciones de pila, lo que reduce la cantidad de recolección de elementos no utilizados. Este análisis determina si un objeto asignado dentro de una función es accesible fuera de ella. Si se encuentra que una asignación local de función es accesible para otra función o subproceso, se dice que la asignación "escape" y no se puede hacer en la pila. De lo contrario, el objeto puede asignarse directamente en la pila y liberarse cuando la función regresa, sin pasar por el montón y los costos de administración de memoria asociados.

Disponibilidad

En términos generales, es más probable que los lenguajes de programación de alto nivel tengan la recolección de elementos no utilizados como característica estándar. En algunos lenguajes que no tienen una recolección de elementos no utilizados integrada, se puede agregar a través de una biblioteca, como con el recolector de elementos no utilizados de Boehm para C y C++.

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

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

BÁSICO

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 cargar 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 cuerda podrían causar pausas largas debido a la recolección de basura. Del mismo modo el algoritmo de recogida de basura del intérprete BASIC de Applesoft escanea repetidamente los descriptores de cadena para la cadena que tiene la dirección más alta con el fin de compactarlo hacia la memoria alta, dando lugar a ${displaystyle O(n^{2}}$ rendimiento y pausa en cualquier lugar de unos segundos a unos minutos. Un coleccionista de basura de Applesoft BASIC de Randy Wigginton identifica un grupo de cadenas en cada paso sobre el montón, reduciendo el tiempo de recogida dramáticamente. BASIC. System, lanzado con ProDOS en 1983, proporciona un colector de basura de ventana para BASIC que es muchas veces más rápido.

Objetivo-C

Mientras que Objective-C tradicionalmente 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. Sin embargo, con el lanzamiento de 2012 de OS X 10.8, 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. Además, desde mayo de 2015, Apple incluso prohíbe el uso de la recolección de elementos no utilizados para las nuevas aplicaciones de OS X en la App Store. Para iOS, nunca se introdujo la recolección de elementos no utilizados debido a problemas en la capacidad de respuesta y el rendimiento de la aplicación; en cambio, iOS usa ARC.

Entornos limitados

La recolección de basura rara vez se usa 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. Microsoft.NET Micro Framework,.NET nanoFramework y Java Platform, Micro Edition son plataformas de software integradas que, al igual que sus primos más grandes, incluyen recolección de elementos no utilizados.

Java

Los recolectores de basura disponibles en Java JDK incluyen:

• G1
• Parallel
• Coleccionista de barrido continuo (CMS)
• Serie
• C4 (Continuamente Concurrent Compacting Collector)
• Shenandoah
• ZGC

Uso en tiempo de compilación

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 las invariantes conocidas durante la compilación.

Esta forma de recolección de elementos no utilizados se ha estudiado en el lenguaje de programación Mercury y se usó más con la introducción del contador de referencia automático (ARC) de LLVM en el ecosistema de Apple (iOS y OS X) en 2011.

Sistemas en tiempo real

Los recolectores de basura incrementales, simultáneos y en tiempo real han sido desarrollados, por ejemplo, por Henry Baker y por Henry Lieberman.

En el algoritmo de Baker, la asignación se realiza en la mitad de una única región de memoria. Cuando se llena a la mitad, se realiza una recolección de basura que mueve los objetos vivos a la otra mitad y los objetos restantes se desasignan implícitamente. El programa en ejecución (el 'mutador') debe verificar que cualquier objeto al que hace referencia esté en la mitad correcta y, si no, moverlo, mientras una tarea en segundo plano busca todos los objetos.

Los esquemas generacionales de recolección de basura 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. Se crean nuevos objetos en el "joven" generación que se recopila 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. De vez en cuando se realiza un escaneo completo.

Algunas arquitecturas informáticas de lenguaje de alto nivel incluyen soporte de hardware para la recolección de elementos no utilizados en tiempo real.

La mayoría de las implementaciones de recolectores de basura en tiempo real utilizan el rastreo. Dichos recolectores de basura en tiempo real cumplen con las estrictas restricciones de tiempo real cuando se usan con un sistema operativo en tiempo real.