En programación de computadoras , rastrear la recolección de basura es una forma de administración automática de la memoria que consiste en determinar qué objetos deben ser desasignados ("recolectados de basura") rastreando qué objetos son accesibles por una cadena de referencias de ciertos objetos "raíz", y considerando el descansar como "basura" y recogerlos. El seguimiento 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 seguimiento de la recolección de basura, en lugar de otros métodos como el recuento de referencias , y hay una gran cantidad de algoritmos utilizados en la implementación.
Accesibilidad de un objeto
De manera informal, un objeto es accesible si es referenciado por al menos una variable en el programa, ya sea directamente o mediante referencias de otros objetos accesibles. Más precisamente, se puede acceder a los objetos solo de dos formas:
- Un distinguido conjunto de raíces: objetos que se supone que son alcanzables. Por lo general, estos incluyen todos los objetos a los que se hace referencia desde cualquier lugar de la pila de llamadas (es decir, todas las variables y parámetros locales en las funciones que se invocan actualmente) y cualquier variable global .
- Cualquier cosa a la que se haga referencia desde un objeto alcanzable es en sí misma accesible; más formalmente, la accesibilidad es un cierre transitivo .
La definición de accesibilidad de "basura" no es óptima, en la medida en que la última vez que un programa usa un objeto podría ser mucho antes de que ese objeto caiga fuera del ámbito del entorno. A veces se hace una distinción entre basura sintáctica , aquellos objetos que el programa no puede alcanzar, y basura semántica , esos objetos que el programa nunca volverá a utilizar. Por ejemplo:
Objeto x = nuevo Foo (); Objeto y = nueva barra (); x = nuevo Quux (); / * En este punto, sabemos que el objeto Foo * originalmente asignado a x nunca será * accedido: es basura sintáctica. * /si ( x . comprobar_algo ()) { x . hacer_algo ( y ); } Sistema . salir ( 0 ); / * En el bloque anterior, y * podría * ser basura semántica; * pero no lo sabremos hasta que x.check_something () devuelva * algún valor, si es que regresa. * /
Se puede demostrar fácilmente que el problema de identificar con precisión la basura semántica es parcialmente decidible : un programa que asigna un objeto X , ejecuta un programa de entrada arbitrario P y usa X si y solo si P termina requeriría un recolector de basura semántica para resolver la detención. problema . Aunque los métodos heurísticos conservadores para la detección de basura semántica siguen siendo un área de investigación activa, esencialmente todos los recolectores de basura prácticos se centran en la basura sintáctica. [ cita requerida ]
Otra complicación con este enfoque es que, en lenguajes con tipos de referencia y tipos de valor sin caja , el recolector de basura necesita de alguna manera poder distinguir qué variables en la pila o campos en un objeto son valores regulares y cuáles son referencias: en la memoria, un número entero y una referencia pueden parecerse. El recolector de basura necesita saber si tratar el elemento como una referencia y seguirlo, o si es un valor primitivo. Una solución común es el uso de punteros etiquetados .
Referencias fuertes y débiles
El recolector de basura solo puede reclamar objetos que no tengan referencias que los apunten directa o indirectamente desde el conjunto raíz. Sin embargo, algunos programas requieren referencias débiles , que deberían ser utilizables mientras exista el objeto, pero no deberían prolongar su vida útil. En las discusiones sobre referencias débiles, las referencias ordinarias a veces se denominan referencias fuertes . Un objeto es elegible para la recolección de basura si no hay referencias fuertes (es decir, ordinarias) a él, aunque todavía pueda haber algunas referencias débiles a él.
Una referencia débil no es simplemente un puntero al objeto que no le importa a un recolector de basura. El término generalmente se reserva para una categoría administrada correctamente de objetos de referencia especiales que son seguros de usar incluso después de que el objeto desaparece porque caducan a un valor seguro (generalmente null
). Una referencia insegura que no es conocida por el recolector de basura simplemente permanecerá colgando al continuar refiriéndose a la dirección donde residía anteriormente el objeto. Esta no es una referencia débil.
En algunas implementaciones, las referencias débiles se dividen en subcategorías. Por ejemplo, Java Virtual Machine proporciona tres formas de referencias débiles, a saber , referencias suaves , [1] referencias fantasmas , [2] y referencias débiles regulares. [3] Un objeto referenciado suavemente solo es elegible para reclamación, si el recolector de basura decide que el programa tiene poca memoria. A diferencia de una referencia suave o una referencia débil regular, una referencia fantasma no proporciona acceso al objeto al que hace referencia. En cambio, una referencia fantasma es un mecanismo que permite al recolector de basura notificar al programa cuando el objeto referenciado se ha vuelto fantasma alcanzable . Un objeto es alcanzable fantasma, si todavía reside en la memoria y es referenciado por una referencia fantasma, pero su finalizador ya se ha ejecutado. De manera similar, Microsoft.NET proporciona dos subcategorías de referencias débiles, [4] a saber, referencias débiles largas (pistas de resurrección) y referencias débiles cortas.
Colecciones débiles
También se pueden diseñar estructuras de datos que tengan características de seguimiento débiles. Por ejemplo, las tablas hash débiles son útiles. Al igual que una tabla hash normal, una tabla hash débil mantiene una asociación entre pares de objetos, donde cada par se entiende como una clave y un valor. Sin embargo, la tabla hash en realidad no mantiene una referencia sólida sobre estos objetos. Se produce un comportamiento especial cuando la clave, el valor o ambos se convierten en basura: la entrada de la tabla hash se elimina espontáneamente. Existen más refinamientos, como tablas hash que solo tienen claves débiles (las referencias de valor son referencias ordinarias y fuertes) o solo valores débiles (las referencias de clave son fuertes).
Las tablas hash débiles son importantes para mantener asociaciones entre objetos, de modo que los objetos involucrados en la asociación aún pueden convertirse en basura si ya no hay nada en el programa que se refiera a ellos (aparte de la tabla hash asociada).
El uso de una tabla hash regular para tal propósito podría conducir a una "pérdida de memoria lógica": la acumulación de datos accesibles que el programa no necesita y no usará.
Algoritmo basico
Los recopiladores de rastreo se denominan así porque recorren el conjunto de trabajo de la memoria. Estos recolectores de basura realizan la recolección en ciclos. Es común que los ciclos se activen cuando no hay suficiente memoria libre para que el administrador de memoria satisfaga una solicitud de asignación. Sin embargo, los ciclos a menudo pueden ser solicitados por el mutador directamente o ejecutarse en un horario. El método original implica una marca y un barrido ingenuo en el que todo el conjunto de memoria se toca varias veces.
Marcar y barrer ingenuo
En el método ingenuo de marcar y barrer, cada objeto en la memoria tiene una bandera (típicamente un solo bit) reservada para uso exclusivo de recolección de basura. Esta bandera siempre se borra , excepto durante el ciclo de recolección.
La primera etapa es la etapa de marca que hace un recorrido de árbol de todo el "conjunto de raíces" y marca cada objeto al que apunta una raíz como "en uso". Todos los objetos a los que apuntan esos objetos, y así sucesivamente, también se marcan, de modo que se marcan todos los objetos a los que se puede acceder a través del conjunto raíz.
En la segunda etapa, la etapa de barrido , se escanea toda la memoria de principio a fin, examinando todos los bloques libres o usados; los que no están marcados como "en uso" no son accesibles desde ninguna raíz, y su memoria se libera. Para los objetos que fueron marcados en uso, la bandera en uso se borra, preparándose para el siguiente ciclo.
Este método tiene varias desventajas, la más notable es que todo el sistema debe suspenderse durante la recolección; no se puede permitir ninguna mutación del conjunto de trabajo. Esto puede hacer que los programas se 'congelen' periódicamente (y generalmente de manera impredecible), haciendo que algunas aplicaciones en tiempo real y de tiempo crítico sean imposibles. Además, se debe examinar toda la memoria de trabajo, gran parte de ella dos veces, lo que podría causar problemas en los sistemas de memoria paginada .
Marcado tricolor
Debido a estos problemas de rendimiento, la mayoría de los recolectores de basura de seguimiento modernos implementan alguna variante de la abstracción de marcado de tres colores , pero los recolectores simples (como el recolector de marca y barrido ) a menudo no hacen que esta abstracción sea explícita. El marcado tricolor funciona como se describe a continuación.
Se crean tres conjuntos: blanco , negro y gris :
- El conjunto blanco, o conjunto condenado , es el conjunto de objetos que son candidatos a que su memoria sea reciclada.
- El conjunto negro es el conjunto de objetos de los que se puede demostrar que no tienen referencias salientes a los objetos del conjunto blanco y que son accesibles desde las raíces. Los objetos del conjunto negro no son candidatos para la colección.
- El conjunto gris contiene todos los objetos accesibles desde las raíces pero que aún no se han escaneado en busca de referencias a objetos "blancos". Dado que se sabe que se puede acceder a ellos desde las raíces, no se pueden recolectar como basura y terminarán en el conjunto negro después de ser escaneados.
En muchos algoritmos, inicialmente el conjunto negro comienza vacío, el conjunto gris es el conjunto de objetos a los que se hace referencia directamente desde las raíces y el conjunto blanco incluye todos los demás objetos. Cada objeto en la memoria está en todo momento exactamente en uno de los tres conjuntos. El algoritmo procede de la siguiente manera:
- Elija un objeto del conjunto gris y muévalo al conjunto negro.
- Mueva cada objeto blanco al que hace referencia al conjunto gris. Esto asegura que ni este objeto ni ningún objeto al que haga referencia puedan ser recolectados como basura.
- Repita los dos últimos pasos hasta que el conjunto gris esté vacío.
Cuando el conjunto gris está vacío, el escaneo está completo; los objetos negros son accesibles desde las raíces, mientras que los objetos blancos no lo son y pueden ser recolectados como basura.
Dado que todos los objetos a los que no se puede acceder inmediatamente desde las raíces se agregan al conjunto blanco, y los objetos solo pueden moverse de blanco a gris y de gris a negro, el algoritmo conserva un invariante importante: ningún objeto negro hace referencia a objetos blancos. Esto asegura que los objetos blancos se puedan liberar una vez que el conjunto gris esté vacío. Esto se llama invariante tricolor . Algunas variaciones del algoritmo no conservan este invariante, pero utilizan una forma modificada para la que se mantienen todas las propiedades importantes.
El método tricolor tiene una ventaja importante: se puede realizar "sobre la marcha", sin detener el sistema durante períodos de tiempo significativos. Esto se logra marcando los objetos a medida que se asignan y durante la mutación, manteniendo los distintos conjuntos. Al monitorear el tamaño de los conjuntos, el sistema puede realizar la recolección de basura periódicamente, en lugar de según sea necesario. Además, se evita la necesidad de tocar todo el conjunto de trabajo en cada ciclo.
Estrategias de implementación
Moverse vs no moverse
Una vez que se ha determinado el conjunto inalcanzable, el recolector de basura puede simplemente liberar los objetos inalcanzables y dejar todo lo demás como está, o puede copiar algunos o todos los objetos alcanzables en una nueva área de memoria, actualizando todas las referencias a esos objetos como necesario. Estos se denominan recolectores de basura "no móviles" y "móviles" (o, alternativamente, "no compactantes" y "compactadores"), respectivamente.
Al principio, un algoritmo en movimiento puede parecer ineficaz en comparación con uno que no se mueve, ya que parecería que se requiere mucho más trabajo en cada ciclo. Pero el algoritmo de movimiento genera varias ventajas de rendimiento, tanto durante el ciclo de recolección de basura como durante la ejecución del programa:
- No se requiere ningún trabajo adicional para recuperar el espacio liberado por los objetos muertos; toda la región de la memoria desde la que se movieron los objetos alcanzables puede considerarse espacio libre. Por el contrario, un GC inmóvil debe visitar cada objeto inalcanzable y registrar que la memoria que ocupaba está disponible.
- Del mismo modo, los nuevos objetos se pueden asignar muy rápidamente. Dado que las grandes regiones contiguas de memoria suelen estar disponibles mediante un GC en movimiento, se pueden asignar nuevos objetos simplemente incrementando un puntero de "memoria libre". Una estrategia sin movimiento puede, después de algún tiempo, conducir a un montón muy fragmentado , requiriendo una consulta costosa de "listas libres" de pequeños bloques de memoria disponibles para asignar nuevos objetos.
- Si se utiliza un orden transversal apropiado (como cdr-first para los contratos de lista ), los objetos se pueden mover muy cerca de los objetos a los que hacen referencia en la memoria, lo que aumenta la posibilidad de que se ubiquen en la misma línea de caché o página de memoria virtual . . Esto puede acelerar significativamente el acceso a estos objetos a través de estas referencias.
Una desventaja de un recolector de basura móvil es que solo permite el acceso a través de referencias administradas por el entorno de recolección de basura y no permite la aritmética de punteros . Esto se debe a que cualquier puntero a objetos se invalidará si el recolector de basura mueve esos objetos (se convierten en punteros colgantes ). Para la interoperabilidad con el código nativo, el recolector de basura debe copiar el contenido del objeto en una ubicación fuera de la región de memoria recolectada de basura. Un enfoque alternativo es anclar el objeto en la memoria, evitando que el recolector de basura lo mueva y permitiendo que la memoria se comparta directamente con punteros nativos (y posiblemente permitiendo la aritmética de punteros). [5]
Copiar frente a marcar y barrer frente a marcar y no barrer
Los recolectores no solo difieren en si se mueven o no se mueven, sino que también se pueden clasificar por cómo tratan los conjuntos de objetos blancos, grises y negros durante un ciclo de recolección.
El enfoque más sencillo es el colector de semiespacio , que data de 1969. En este colector móvil, la memoria se divide en "desde el espacio" y "al espacio" del mismo tamaño. Inicialmente, los objetos se asignan en "al espacio" hasta que se llena y se activa un ciclo de recolección. Al comienzo del ciclo, el "al espacio" se convierte en el "desde el espacio" y viceversa. Los objetos accesibles desde el conjunto raíz se copian del "desde el espacio" al "al espacio". Estos objetos se escanean a su vez y todos los objetos a los que apuntan se copian en "al espacio", hasta que todos los objetos alcanzables se copian en "al espacio". Una vez que el programa continúa con la ejecución, los nuevos objetos se asignan nuevamente en el "espacio a" hasta que se llena de nuevo y se repite el proceso.
Este enfoque es muy simple, pero dado que solo se usa un semiespacio para asignar objetos, el uso de memoria es el doble en comparación con otros algoritmos. La técnica también se conoce como detener y copiar . El algoritmo de Cheney es una mejora del colector semiespacio.
Un recolector de basura de marca y barrido guarda un poco o dos con cada objeto para registrar si es blanco o negro. El conjunto gris se mantiene como una lista separada o usando otro bit. A medida que se recorre el árbol de referencia durante un ciclo de recopilación (la fase de "marca"), el recopilador manipula estos bits. Luego, un "barrido" final de las áreas de memoria libera los objetos blancos. La estrategia de marca y barrido tiene la ventaja de que, una vez que se determina el conjunto condenado, se puede seguir una estrategia de recolección en movimiento o sin movimiento. Esta elección de estrategia se puede realizar en tiempo de ejecución, según lo permita la memoria disponible. Tiene la desventaja de "hinchar" los objetos en una pequeña cantidad, ya que cada objeto tiene un pequeño costo de memoria oculta debido a la lista / bit extra. Esto se puede mitigar un poco si el recopilador también maneja la asignación, ya que entonces podría usar bits no utilizados en las estructuras de datos de asignación. O bien, esta "memoria oculta" se puede eliminar mediante el uso de un puntero etiquetado , intercambiando el costo de la memoria por el tiempo de la CPU. Sin embargo, la marca y el barrido es la única estrategia que coopera fácilmente con los asignadores externos en primer lugar.
Un recolector de basura de marcar y no barrer , como el de marcar y barrer, guarda un poco con cada objeto para registrar si es blanco o negro; el conjunto gris se mantiene como una lista separada o usando otro bit. Aquí hay dos diferencias clave. En primer lugar, el blanco y negro significan cosas diferentes a las que tienen en el coleccionista de marcas y barridos. En un colector "marcar y no barrer", todos los objetos alcanzables son siempre negros. Un objeto se marca en negro en el momento en que se asigna y permanecerá negro incluso si se vuelve inalcanzable. Un objeto blanco es memoria no utilizada y puede asignarse. En segundo lugar, la interpretación del bit blanco y negro puede cambiar. Inicialmente, el bit negro / blanco puede tener el sentido de (0 = blanco, 1 = negro). Si una operación de asignación falla en encontrar alguna memoria disponible (blanca), eso significa que todos los objetos están marcados como usados (negro). A continuación, se invierte el sentido del bit negro / blanco (por ejemplo, 0 = negro, 1 = blanco). Todo se vuelve blanco. Esto rompe momentáneamente la invariante de que los objetos alcanzables son negros, pero inmediatamente sigue una fase de marcado completo, para marcarlos de nuevo en negro. Una vez hecho esto, toda la memoria inalcanzable es blanca. No es necesaria ninguna fase de "barrido".
La estrategia de marcar y no barrer requiere la cooperación entre el asignador y el recolector, pero es increíblemente eficiente en el espacio ya que solo requiere un bit por puntero asignado (que la mayoría de los algoritmos de asignación requieren de todos modos). Sin embargo, esta ventaja está algo mitigada, ya que la mayoría de las veces, grandes porciones de memoria se marcan incorrectamente en negro (se usan), lo que dificulta devolver los recursos al sistema (para que los usen otros asignadores, subprocesos o procesos) en tiempos de bajo uso de memoria.
Por lo tanto, la estrategia de marcar y no barrer puede verse como un compromiso entre las ventajas y desventajas de la marca y el barrido y las estrategias de detener y copiar .
GC generacional (GC efímero)
Se ha observado empíricamente que en muchos programas, los objetos creados más recientemente son también los que tienen más probabilidades de volverse inalcanzables rápidamente (lo que se conoce como mortalidad infantil o hipótesis generacional ). Un GC generacional (también conocido como GC efímero) divide los objetos en generaciones y, en la mayoría de los ciclos, colocará solo los objetos de un subconjunto de generaciones en el conjunto blanco inicial (condenado). Además, el sistema de tiempo de ejecución mantiene el conocimiento de cuándo las referencias cruzan generaciones al observar la creación y sobrescritura de referencias. Cuando se ejecuta el recolector de basura, es posible que pueda usar este conocimiento para demostrar que algunos objetos en el conjunto blanco inicial son inalcanzables sin tener que atravesar todo el árbol de referencia. Si se mantiene la hipótesis generacional, esto da como resultado ciclos de recolección mucho más rápidos y, al mismo tiempo, se recuperan la mayoría de los objetos inalcanzables.
Para implementar este concepto, muchos recolectores de basura generacionales usan regiones de memoria separadas para diferentes edades de objetos. Cuando una región se llena, se trazan los objetos que contiene, utilizando las referencias de las generaciones anteriores como raíces. Esto generalmente da como resultado que la mayoría de los objetos de la generación se recopilen (según la hipótesis), dejándolo para que se utilice para asignar nuevos objetos. Cuando una colección no recopila muchos objetos (la hipótesis no se cumple, por ejemplo, porque el programa ha calculado una gran colección de objetos nuevos que quiere retener), algunos o todos los objetos supervivientes a los que se hace referencia desde la memoria anterior las regiones se promueven a la siguiente región más alta y, a continuación, toda la región se puede sobrescribir con objetos nuevos. Esta técnica permite una recolección de basura incremental muy rápida, ya que la recolección de basura de solo una región a la vez es todo lo que se requiere normalmente.
El carroñero de generación clásico de Ungar tiene dos generaciones. Divide a la generación más joven, llamada "nuevo espacio", en un gran "edén" en el que se crean nuevos objetos y dos "espacios de supervivientes" más pequeños, el espacio de supervivientes pasados y el espacio de supervivientes futuros. Los objetos de la generación anterior que pueden hacer referencia a objetos en un nuevo espacio se mantienen en un "conjunto recordado". En cada búsqueda, los objetos en el nuevo espacio se rastrean desde las raíces en el conjunto recordado y se copian en el futuro espacio de superviviente. Si el espacio de los futuros supervivientes se llena, los objetos que no encajan son promovidos al espacio antiguo, un proceso llamado "tenencia". Al final de la búsqueda, algunos objetos residen en el espacio del futuro superviviente, y el eden y el espacio del superviviente pasado están vacíos. Luego, se intercambian el espacio de sobrevivientes futuros y el espacio de sobrevivientes pasados y el programa continúa, asignando objetos en eden. En el sistema original de Ungar, eden es 5 veces más grande que cada espacio de superviviente.
La recolección de basura generacional es un enfoque heurístico y es posible que algunos objetos inalcanzables no se recuperen en cada ciclo. Por lo tanto, ocasionalmente puede ser necesario realizar una marca completa y barrer o copiar la recolección de basura para recuperar todo el espacio disponible. De hecho, los sistemas en tiempo de ejecución para lenguajes de programación modernos (como Java y .NET Framework ) suelen utilizar algún híbrido de las diversas estrategias que se han descrito hasta ahora; por ejemplo, la mayoría de los ciclos de recolección pueden considerar solo unas pocas generaciones, mientras que ocasionalmente se realiza un marcado y barrido, y aún más raramente se realiza una copia completa para combatir la fragmentación. Los términos "ciclo menor" y "ciclo mayor" se utilizan a veces para describir estos diferentes niveles de agresión de los recolectores.
Stop-the-world versus incremental versus concurrente
Los recolectores de basura simples de detener el mundo detienen por completo la ejecución del programa para ejecutar un ciclo de recolección, lo que garantiza que no se asignen nuevos objetos y que los objetos no se vuelvan inaccesibles repentinamente mientras el recolector se está ejecutando.
Esto tiene la desventaja obvia de que el programa no puede realizar ningún trabajo útil mientras se está ejecutando un ciclo de recolección (a veces llamado "pausa embarazosa" [6] ). Por lo tanto, la recolección de basura Stop-the-world es principalmente adecuada para programas no interactivos. Su ventaja es que es más sencillo de implementar y más rápido que la recolección de basura incremental.
Los recolectores de basura incrementales y simultáneos están diseñados para reducir esta interrupción intercalando su trabajo con la actividad del programa principal. Los recolectores de basura incrementales realizan el ciclo de recolección de basura en fases discretas, con la ejecución del programa permitida entre cada fase (y algunas veces durante algunas fases). Los recolectores de basura concurrentes no detienen la ejecución del programa en absoluto, excepto quizás brevemente cuando se escanea la pila de ejecución del programa. Sin embargo, la suma de las fases incrementales tarda más en completarse que una pasada de recolección de basura por lotes, por lo que estos recolectores de basura pueden producir un rendimiento total menor.
Es necesario un diseño cuidadoso con estas técnicas para garantizar que el programa principal no interfiera con el recolector de basura y viceversa; por ejemplo, cuando el programa necesita asignar un nuevo objeto, el sistema en tiempo de ejecución puede necesitar suspenderlo hasta que se complete el ciclo de recolección, o notificar de alguna manera al recolector de basura que existe un nuevo objeto accesible.
Punteros internos y precisos frente a conservadores
Algunos recopiladores pueden identificar correctamente todos los punteros (referencias) en un objeto; estos se denominan recolectores precisos (también exactos o exactos ), siendo el opuesto un recolector conservador o parcialmente conservador . Los coleccionistas conservadores asumen que cualquier patrón de bits en la memoria podría ser un puntero si, interpretado como un puntero, apuntaría a un objeto asignado. Los recolectores conservadores pueden producir falsos positivos, donde la memoria no utilizada no se libera debido a una identificación incorrecta del puntero. Esto no siempre es un problema en la práctica, a menos que el programa maneje una gran cantidad de datos que fácilmente podrían identificarse erróneamente como un puntero. Los falsos positivos son generalmente menos problemáticos en sistemas de 64 bits que en sistemas de 32 bits porque el rango de direcciones de memoria válidas tiende a ser una pequeña fracción del rango de valores de 64 bits. Por lo tanto, es poco probable que un patrón arbitrario de 64 bits imite un puntero válido. También puede ocurrir un falso negativo si los punteros están "ocultos", por ejemplo, utilizando una lista enlazada XOR . El hecho de que un colector preciso sea práctico generalmente depende de las propiedades de seguridad de tipo del lenguaje de programación en cuestión. Un ejemplo para el que se necesitaría un recolector de basura conservador es el lenguaje C , que permite que los punteros tecleados (no vacíos) se conviertan en punteros sin tipear (vacíos) y viceversa.
Un problema relacionado concierne a los punteros internos o punteros a campos dentro de un objeto. Si la semántica de un lenguaje permite punteros internos, entonces puede haber muchas direcciones diferentes que pueden referirse a partes del mismo objeto, lo que complica determinar si un objeto es basura o no. Un ejemplo de esto es el lenguaje C ++ , en el que la herencia múltiple puede hacer que los punteros a los objetos base tengan direcciones diferentes. En un programa muy optimizado, es posible que el puntero correspondiente al objeto en sí se haya sobrescrito en su registro, por lo que dichos punteros internos deben escanearse.
Actuación
El rendimiento de los recolectores de basura de seguimiento, tanto la latencia como el rendimiento, depende significativamente de la implementación, la carga de trabajo y el entorno. Las implementaciones ingenuas o el uso en entornos con mucha memoria restringida, especialmente los sistemas integrados, pueden dar como resultado un rendimiento muy deficiente en comparación con otros métodos, mientras que las implementaciones sofisticadas y el uso en entornos con mucha memoria pueden dar como resultado un rendimiento excelente. [ cita requerida ]
En términos de rendimiento, el seguimiento por su naturaleza requiere una sobrecarga de tiempo de ejecución implícita , aunque en algunos casos el costo amortizado puede ser extremadamente bajo, en algunos casos incluso menor que una instrucción por asignación o colección, superando la asignación de pila. [7] La gestión manual de la memoria requiere sobrecarga debido a la liberación explícita de memoria, y el recuento de referencias tiene sobrecarga por incrementar y disminuir los recuentos de referencia y comprobar si el recuento se ha desbordado o ha caído a cero. [ cita requerida ]
En términos de latencia, los recolectores de basura simples de detener el mundo pausan la ejecución del programa para la recolección de basura, lo que puede suceder en momentos arbitrarios y tomar un tiempo arbitrario, lo que los hace inutilizables para la computación en tiempo real , especialmente los sistemas integrados, y no se ajustan bien a los sistemas interactivos. uso, o cualquier otra situación en la que la baja latencia sea una prioridad. Sin embargo, los recolectores de basura incrementales pueden proporcionar garantías estrictas en tiempo real, y en sistemas con tiempo de inactividad frecuente y suficiente memoria libre, como computadoras personales, la recolección de basura se puede programar para tiempos de inactividad y tener un impacto mínimo en el rendimiento interactivo. La administración de memoria manual (como en C ++) y el conteo de referencias tienen un problema similar de pausas arbitrariamente largas en caso de desasignar una estructura de datos grande y todos sus elementos secundarios, aunque estos solo ocurren en momentos fijos, no dependiendo de la recolección de basura. [ cita requerida ]
- Asignación de montón manual
- buscar el bloque mejor / primer ajuste de tamaño suficiente
- mantenimiento de lista gratuito
- Recolección de basura
- localizar objetos alcanzables
- copiar objetos accesibles para coleccionistas en movimiento
- barreras de lectura / escritura para recolectores incrementales
- busque el mejor bloque o el primer ajuste y el mantenimiento de lista gratuito para colectores que no se muevan
Es difícil comparar los dos casos directamente, ya que su comportamiento depende de la situación. Por ejemplo, en el mejor de los casos para un sistema de recolección de basura, la asignación solo incrementa un puntero, pero en el mejor de los casos para la asignación manual del montón, el asignador mantiene listas libres de tamaños específicos y la asignación solo requiere seguir un puntero. Sin embargo, esta segregación de tamaño suele causar un alto grado de fragmentación externa, lo que puede tener un impacto adverso en el comportamiento de la caché. La asignación de memoria en un lenguaje recolectado de basura se puede implementar usando la asignación de montón detrás de escena (en lugar de simplemente incrementar un puntero), por lo que las ventajas de rendimiento enumeradas anteriormente no se aplican necesariamente en este caso. En algunas situaciones, sobre todo en los sistemas integrados , es posible evitar tanto la recolección de basura como la sobrecarga de administración del montón mediante la preasignación de grupos de memoria y el uso de un esquema ligero y personalizado para la asignación / desasignación. [8]
Es más probable que la sobrecarga de las barreras de escritura se note en un programa de estilo imperativo que frecuentemente escribe punteros en estructuras de datos existentes que en un programa de estilo funcional que construye datos solo una vez y nunca los cambia.
Algunos avances en la recolección de basura pueden entenderse como reacciones a problemas de rendimiento. Los primeros coleccionistas eran coleccionistas de stop-the-world, pero el rendimiento de este enfoque distraía en las aplicaciones interactivas. La recolección incremental evitó esta interrupción, pero a costa de una menor eficiencia debido a la necesidad de barreras. Las técnicas de recolección generacional se utilizan con recolectores incrementales y de parada del mundo para aumentar el rendimiento; la compensación es que parte de la basura no se detecta como tal durante más tiempo de lo normal.
Determinismo
- El seguimiento de la recolección de basura no es determinista en el momento de la finalización del objeto. Un objeto que se vuelve elegible para la recolección de basura generalmente se limpiará eventualmente, pero no hay garantía de cuándo (o incluso si) sucederá. Este es un problema para la corrección del programa cuando los objetos están vinculados a recursos que no son de memoria, cuya liberación es un comportamiento del programa visible externamente, como cerrar una conexión de red, liberar un dispositivo o cerrar un archivo. Una técnica de recolección de basura que proporciona determinismo a este respecto es el recuento de referencias .
- La recolección de basura puede tener un impacto no determinista en el tiempo de ejecución, al introducir potencialmente pausas en la ejecución de un programa que no están correlacionadas con el algoritmo que se está procesando. En el seguimiento de la recolección de basura, la solicitud para asignar un nuevo objeto a veces puede regresar rápidamente y en otras ocasiones desencadenar un ciclo de recolección de basura prolongado. En el recuento de referencias, mientras que la asignación de objetos suele ser rápida, disminuir una referencia no es determinista, ya que una referencia puede llegar a cero, lo que desencadena la recursividad para disminuir los recuentos de referencias de otros objetos que contiene ese objeto.
Recolección de basura en tiempo real
Si bien la recolección de basura generalmente no es determinista, es posible usarla en sistemas duros en tiempo real. Un recolector de basura en tiempo real debería garantizar que, incluso en el peor de los casos, dedicará una cierta cantidad de recursos computacionales a los subprocesos mutantes. Las restricciones impuestas a un recolector de basura en tiempo real generalmente se basan en el trabajo o en el tiempo. Una restricción basada en el tiempo se vería así: dentro de cada ventana de tiempo de duración T , se debería permitir que los subprocesos mutadores se ejecuten al menos durante el tiempo Tm . Para el análisis basado en el trabajo, MMU (utilización mínima del mutador) [9] se usa generalmente como una restricción en tiempo real para el algoritmo de recolección de basura.
Una de las primeras implementaciones de recolección de basura en tiempo real para la JVM se basó en el algoritmo Metronome , [10] cuya implementación comercial está disponible como parte de IBM WebSphere Real Time . [11] Otro algoritmo dura la recolección de basura en tiempo real es Staccato, disponible en el IBM 's J9 JVM , que también proporciona escalabilidad para grandes arquitecturas multiprocesador, mientras que traer varias ventajas sobre metrónomo y otros algoritmos que, por el contrario, requieren hardware especializado . [12]
Ver también
- Eliminación de código muerto
Referencias
- ^ "Clase SoftReference " . Ed. Estándar de la plataforma Java ™. 7 . Oracle . Consultado el 25 de mayo de 2013 .
- ^ "Clase PhantomReference " . Ed. Estándar de la plataforma Java ™. 7 . Oracle . Consultado el 25 de mayo de 2013 .
- ^ "Clase WeakReference " . Ed. Estándar de la plataforma Java ™. 7 . Oracle . Consultado el 25 de mayo de 2013 .
- ^ "Referencias débiles" . .NET Framework 4.5 . Microsoft . Consultado el 25 de mayo de 2013 .
- ^ "Copiar y fijar" . Msdn2.microsoft.com . Consultado el 9 de julio de 2010 .
- ^ Steele, Guy L. (septiembre de 1975). "Recolección de basura compactadora multiprocesamiento". Comunicaciones de la ACM . 18 (9): 496. doi : 10.1145 / 361002.361005 .
- ^ Appel, Andrew W. (17 de junio de 1987). "La recolección de basura puede ser más rápida que la asignación de pilas" . Cartas de procesamiento de información . 25 (4): 275-279. CiteSeerX 10.1.1.49.2537 . doi : 10.1016 / 0020-0190 (87) 90175-X .
- ^ "Asignación de memoria en sistemas embebidos" . Eros-os.org . Consultado el 29 de marzo de 2009 .
- ^ Cheng, Perry; Blelloch, Guy E. (22 de junio de 2001). "Un recolector de basura paralelo en tiempo real" (PDF) . Avisos ACM SIGPLAN . 36 (5): 125-136. doi : 10.1145 / 381694.378823 .
- ^ "El metrónomo: un enfoque más simple para la recolección de basura en sistemas en tiempo real" (PDF) .
- ^ "Java en tiempo real, parte 4: recolección de basura en tiempo real" .
- ^ McCloskey, Bill; Bacon, David F .; Cheng, Perry; Grove, David (22 de febrero de 2008). "Staccato: un recolector de basura compactador en tiempo real paralelo y concurrente para multiprocesadores" (PDF) . Consultado el 11 de marzo de 2014 .