+La manera en que la investigación sobre recolección de basura ha crecido es
+realmente sorprendente. Hay, al menos, 2995 publicaciones sobre recolección de
+basura registradas al momento de escribir este documento [GCBIB]_. Esto hace
+que el análisis del estado del arte sea particularmente complejo y laborioso.
+
+Analizar todas las publicaciones existentes es algo excede los objetivos de
+este trabajo, por lo tanto se analizó solo una porción significativa,
+utilizando como punto de partida a [JOLI96]_.
+
+De este análisis se observó que la gran mayoría de los algoritmos son
+combinaciones de diferentes características básicas; por lo tanto se intentó
+aislar estas características que son utilizadas como bloques de construcción
+para algoritmos complejos. Ésta tampoco resultó ser una tarea sencilla debido
+a que muchos de estos bloques de construcción básicos están interrelacionados
+y encontrar una división clara para obtener características realmente atómicas
+no es trivial.
+
+La construcción de recolectores más complejos se ve alimentada también por la
+existencia de recolectores *híbridos*; es decir, recolectores que utilizan más
+de un algoritmo dependiendo de alguna característica de la memoria
+a administrar. No es poco común observar recolectores que utilizan un
+algoritmo diferente para celdas que sobreviven varias recolecciones que para
+las que mueren rápidamente, o que usan diferentes algoritmos para objetos
+pequeños y grandes, o que se comporten de forma conservativa para ciertas
+celdas y sean precisos para otras.
+
+De todas estas combinaciones resulta el escenario tan fértil para la
+investigación sobre recolección de basura.
+
+A continuación se presentan las principales clases de algoritmos
+y características básicas encontradas durante la investigación del estado del
+arte. La separación de clases y aislamiento de características no es siempre
+trivial, ya que hay ciertas clases de recolectores que están interrelacionadas
+(o ciertas características pueden estar presentes sólo en recolectores de una
+clase en particular).
+
+
+
+.. _gc_direct:
+
+Recolección directa / indirecta
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Generalmente se llama recolección **directa** a aquella en la cual el
+compilador o lenguaje instrumenta al *mutator* de forma tal que la información
+sobre el grafo de conectividad se mantenga activamente cada vez que hay un
+cambio en él. Normalmente se utiliza un contador de referencia en cada celda
+para este propósito, permitiendo almacenar en todo momento la cantidad de
+nodos que apuntan a ésta (ver :ref:`gc_rc`). Esto permite reclamar una celda
+instantáneamente cuando el *mutator* deja de hacer referencia a ella. Este
+tipo de recolectores son inherentemente :ref:`incrementales <gc_inc>`.
+
+Por el contrario, los recolectores **indirectos** normalmente no interfieren
+con el *mutator* en cada actualización del grafo de conectividad (exceptuando
+algunos :ref:`recolectores incrementales <gc_inc>` que a veces necesitan
+instrumentar el *mutator* pero no para mantener el estado del grafo de
+conectividad completo). La recolección se dispara usualmente cuando el
+*mutator* requiere asignar memoria pero no hay más memoria libre conocida
+disponible y el recolector se encarga de generar la información de
+conectividad desde cero para determinar qué celdas son *basura*.
+
+Esta es la madre de toda clasificación, también conocidos como :ref:`conteo de
+referencias <gc_rc>` (directa) y *traicing garbage collection* (indirecta).
+Prácticamente todos los recolectores menos el :ref:`conteo de referencias
+<gc_rc>` están dentro de esta última categoría (como por ejemplo, el
+:ref:`marcado y barrido <gc_mark_sweep>` y :ref:`copia de semi-espacio
+<gc_copy>`).
+
+Otros ejemplos de recolectores modernos *directos* son el recolector de basura
+de Python_ [NAS00]_ y [LINS05]_ (aunque ambos tiene un algoritmo *indirecto*
+para recuperar ciclos).
+
+
+
+.. _gc_inc:
+
+Recolección incremental
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Recolección incremental es aquella que se realiza de forma intercalada con el
+*mutator*. En general el propósito es disminuir el tiempo de las pausas
+causadas por el recolector (aunque generalmente el resultado es un mayor costo
+total de recolección en términos de tiempo).
+
+De los `algoritmos clásicos`_ el único que es incremental en su forma más
+básica es el :ref:`conteo de referencias <gc_rc>`. Otros recolectores pueden
+hacerse incrementales de diversas maneras, pero en general consta de hacer
+parte del trabajo de escanear el grafo de conectividad cada vez que el
+*mutator* asigna memoria. En general para hacer esto es también necesario
+instrumentar al *mutator* de forma tal que informe al recolector cada vez que
+cambia el grafo de conectividad, para que éste pueda marcar al sub-grafo
+afectado por el cambio como *desactualizado* y así re-escanearlo nuevamente en
+la próxima iteración. Para realizar esto en recolectores :ref:`indirectos
+<gc_direct>` se utiliza la :ref:`abstracción tricolor <gc_intro_tricolor>`;
+cuando el *mutator* cambia una referencia, se marca *gris* la celda que la
+contiene, de modo que el recolector vuelva a visitarla.
+
+En general el rendimiento de los recolectores incrementales disminuye
+considerablemente cuando el *mutator* actualiza muy seguido el grafo de
+conectividad, porque debe re-escanear sub-grafos que ya había escaneado una
+y otra vez. A esto se debe también que en general el tiempo de procesamiento
+total de un recolector incremental sea mayor que uno no incremental, aunque el
+tiempo de pausa de una recolección sea menor.
+
+Ejemplos de recolectores que se encuentran dentro de esta categoría son
+[BOEH91]_, [LINS05]_,
+
+
+
+.. _gc_concurrent:
+
+Recolección concurrente / paralela / *stop-the-world*
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Los recolectores concurrentes son aquellos que pueden correr en paralelo con
+el *mutator*. Por el contrario, aquellos que pausan el *mutator* para realizar
+la recolección son usualmente denominados *stop-the-world* (*detener el
+mundo*), haciendo referencia a que pausan todos los hilos del *mutator* para
+poder escanear el grafo de conectividad de forma consistente. Hay una tercera
+clase de colectores que si bien son *stop-the-world*, utilizan todos los hilos
+disponibles para realizar la recolección (ver figura
+:vref:`fig:gc-concurrent`).
+
+.. fig:: fig:gc-concurrent
+
+ Distintos tipos de recolectores según el comportamiento en ambientes
+ multi-hilo.
+
+ .. subfig::
+
+ *Stop-the-world*.
+
+ .. aafig::
+ :aspect: 0.7
+
+ ___________________________________________________________________
+ | |
+ | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
+ | |
+ | HH Mutator ZZ Inactivo XX Recolector |
+ |___________________________________________________________________|
+
+ .. subfig::
+
+ Paralelo.
+
+ .. aafig::
+ :aspect: 0.7
+
+ ___________________________________________________________________
+ | |
+ | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | HH Mutator ZZ Inactivo XX Recolector |
+ |___________________________________________________________________|
+
+ .. subfig::
+
+ Concurrente.
+
+ .. aafig::
+ :aspect: 0.7
+
+ ___________________________________________________________________
+ | |
+ | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | ZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZ |
+ | |
+ | HH Mutator ZZ Inactivo XX Recolector |
+ |___________________________________________________________________|
+
+
+Para lograr que un recolector sea concurrente generalmente el mecanismo es
+similar al necesario para hacer un :ref:`recolector incremental <gc_inc>`: hay
+que instrumentar al *mutator* para que informe al recolector cuando se realiza
+algún cambio en el grafo de conectividad, de forma tal que pueda volver
+a escanear el sub-grafo afectado por el cambio.
+
+Esto también trae como consecuencia el incremento en el tiempo total que
+consume el recolector, debido a la necesidad de re-escanear sub-grafos que han
+sido modificados, además de la sincronización necesaria entre *mutator*
+y recolector.
+
+¿Cúal es la idea entonces de un recolector concurrente? Una vez más, al igual
+que los recolectores incrementales, el principal objetivo es disminuir las
+largas pausas provocadas por la recolección de basura. Sin embargo, este tipo
+de algoritmos además permite hacer un mejor aprovechamiento de las
+arquitecturas *multi-core* [#gcmulticore]_ que cada vez se afirman más, ya que
+el *mutator* y el recolector pueden estar corriendo realmente en paralelo,
+cada uno en un procesador distinto. Algunos recolectores van más allá
+y permiten incluso paralelizar la recolección de basura en varios hilos
+([HUEL98]_, [LINS05]_). Otros ejemplos de recolectores concurrentes (aunque no
+ofrece paralelización del procesamiento del recolector en varios hilos) son
+[BOEH91]_, [RODR97]_.
+
+.. [#gcmulticore] Una arquitectura *multi-core* es aquella que combina dos
+ o más núcleos (*cores*) independientes que trabajan a la misma frecuencia,
+ pero dentro de un solo circuito integrado o procesador.
+
+Todos los :ref:`algoritmos clásicos <gc_classic>` que se han citado son del
+tipo *stop-the-world*.
+
+
+
+.. _gc_free_list:
+
+Lista de libres / *pointer bump allocation*
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Esta clasificación se refiere principalmente a la forma en que se organiza el
+*heap*, íntimamente relacionado al *low level allocator*. Si bien se ha dicho
+que en este trabajo no se prestará particular atención a este aspecto, en
+ciertos algoritmos es tan relevante que tampoco es sensato pasarlo por alto
+completamente.
+
+En términos generales, hay dos formas fundamentales de organizar el *heap*,
+manteniendo una lista de libres o realizando *pointer bump allocation*, como
+se explicó en :ref:`gc_copy`. La primera forma consiste, a grandes rasgos, en
+separar el *heap* en celdas (que pueden agruparse según tamaño) y enlazarlas
+en una lista de libres. Al solicitarse una nueva celda simplemente se la
+desenlaza de la lista de libres. Por otro lado, cuando el recolector detecta
+una celda *muerta*, la vuelve a enlazar en la lista de libres. Este es un
+esquema simple pero con limitaciones, entre las principales, el costo de
+asignar puede ser alto si hay muchos tamaños distintos de celda y soportar
+tamaño de celda variable puede ser complejo o acarrear muchas otras
+ineficiencias. El :ref:`marcado y barrido <gc_mark_sweep>` en general usa este
+esquema, al igual que el :ref:`conteo de referencias <gc_rc>`.
+
+Otro forma de organizar el *heap* es utilizándolo como una especie de *stack*
+en el cual para asignar simplemente se incrementa un puntero. Este esquema es
+simple y eficiente, si el recolector puede mover celdas (ver
+:ref:`gc_moving`); de otra manera asignar puede ser muy costoso si hay que
+buscar un *hueco* en el heap (es decir, deja de reducirse a incrementar un
+puntero). El clásico ejemplo de esta familia es el algoritmo visto en
+:ref:`gc_copy`.
+
+Sin embargo, entre estos dos extremos, hay todo tipo de híbridos. Existen
+recolectores basados en *regiones*, que se encuentran en un punto intermedio.
+Dentro de una región se utiliza un esquema de *pointer bump allocation* pero
+las regiones en sí se administran como una lista de libres (como por ejemplo
+[BLAC08]_). Otra variación (más común) de este esquema son los *two level
+allocators* que asignan páginas completas (similar a las regiones) y dentro de
+cada página se asignan las celdas. Ambas, páginas y celdas, se administran
+como listas de libres (ejemplos que utilizan este esquema son [BOEHWD]_ y el
+:ref:`recolector actual de D <dgc_actual>`).
+
+
+
+.. _gc_moving:
+
+Movimiento de celdas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Otra característica muy importante del recolector de basura es si mueve las
+celdas o no. En general el movimiento de celdas viene de la mano del esquema
+de :ref:`pointer bump allocation <gc_free_list>`, ya que *compacta* todas las
+celdas *vivas* al comienzo del *heap* luego de una recolección, permitiendo
+este esquema para asignar nuevas celdas, pero puede utilizarse en esquemas
+híbridos como recolectores basados en *regiones* (por ejemplo [BLAC08]_).
+
+Además los recolectores con movimiento de celdas deben ser :ref:`precisos
+<gc_conserv>`, porque es necesario tener la información completa de los tipos
+para saber cuando actualizar los punteros (de otra manera se podría escribir
+un dato de una celda que no era un puntero). Para que un recolector pueda
+mover celdas, aunque sea parcialmente, en recolectores *semi-precisos* se
+utiliza un método conocido como *pinning* (que significa algo como *pinchar
+con un alfiler*); una celda es *pinned* (*pinchada*) cuando hay alguna
+referencia no-precisa a ella, y por lo tanto no puede ser movida (porque no se
+puede estar seguro si es posible actualizar dicha referencia).
+
+La ventaja principal de los colectores con movimiento es la posibilidad de
+utilizar :ref:`pointer bump allocation <gc_free_list>` y que es sencillo
+implementar recolectores :ref:`generacionales <gc_part>` sobre estos.
+
+De los algoritmos clásicos sólo la :ref:`copia de semi-espacios <gc_copy>`
+mueve celdas, el :ref:`conteo de referencias <gc_rc>` y :ref:`marcado
+y barrido <gc_mark_sweep>` no lo hacen. Además hay otro algoritmo bastante
+básico que mueve celdas, el **marcado y compactado**. Éste no tiene
+2 semi-espacios, directamente mueve las celdas compactándolas al comienzo del
+*heap*. El algoritmo es un poco más complejo que la :ref:`copia de
+semi-espacios <gc_copy>` pero suele poder proveer una mayor localidad de
+referencia y *desperdicia* un semi-espacio que está inutilizado salgo en el
+momento de la recolección. Por ejemplo para Mono_, que antes usaba un
+recolector conservativo sin movimiento ([BOEHWD]_) se está implementando un
+recolector de este tipo [MOLAWE]_ [MOLA06]_.
+
+
+
+.. _gc_conserv:
+
+Recolectores conservativos vs precisos
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Los recolectores *conservativos* son aquellos que tienen la capacidad de poder
+lidiar con un *root set* o celdas que no tengan información de tipos asociada.
+Esto significa que el recolector no sabe donde hay punteros (o referencias) en
+una celda o raiz dada. Es decir, una ubicación particular puede ser un puntero
+o no. Esto trae una variada cantidad de problemas, como retención de celdas
+que en realidad son *basura* simplemente porque hay algún dato que coincide
+con la dirección de memoria en la que está almacenada esa celda *basura*
+[#gcflasepos]_. Además los recolectores puramente conservativos no puede mover
+celdas (ver :ref:`gc_moving`), porque no pueden arriesgarse a actualizar los
+punteros por el riesgo que existe de que sean falsos positivos.
+
+.. [#gcflasepos] Esto es lo que se conoce como un *falso positivo*, algo que
+ aparenta ser un puntero pero en realidad no lo es.
+
+Sin embargo hay ciertas circunstancias que hacen que no quede más remedio que
+el recolector sea conservativo, por ejemplo cuando se utiliza un recolector de
+basura para un lenguaje que no ha sido pensado para tener uno (como C o C++).
+
+Por el contrario, los recolectores que poseen a su disposición información
+completa sobre el tipo de la celda, y por ende información sobre cuales de sus
+campos son realmente punteros, son denominados *precisos*. Estos recolectores
+no están sujetos a estas limitaciones y por lo tanto son potencialmente más
+eficientes en cuanto a tiempo y espacio. Los lenguajes que fueron diseñados
+para tener un recolector de basura (y en especial aquellos que son de relativo
+alto nivel) en general disponen de recolectores precisos.
+
+Hay casos donde se posee información de tipos para algunas celdas solamente,
+o más comúnmente se posee información de tipos de celdas que se encuentran en
+el *heap* pero no para el *stack* y registros (por ejemplo [MOLA06]_). En
+estos casos se puede adoptar un esquema híbrido y tratar algunas referencias
+de forma conservativa y otras de forma precisa, de manera de mitigar, aunque
+sea de forma parcial, los efectos adversos de los recolectores conservativos.
+Estos recolectores son conocidos como *semi-precisos*. Los recolectores
+semi-precisos pueden mover celdas si utilizan un mecanismo de *pinning* (ver
+:ref:`gc_moving`).
+
+El ejemplo de recolector conservativo por excelencia es el recolector
+`Boehm-Demers-Wiser`_ ([BOEH88]_, [BOEH91]_, [BOEH93]_, [BOEHWD]_) aunque
+puede comportarse de forma semi-precisa si el usuario se encarga de darle la
+información de tipos (en cuyo caso el recolector deja de ser transparente para
+el usuario). Otros ejemplos de recolectores con cierto grado de precisión son
+el :ref:`recolector actual de D <dgc_actual>` y [BLAC08]_.
+
+
+
+.. _gc_part:
+
+Recolección por particiones / generacional
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Otra forma de reducir la cantidad de pausas y la cantidad de trabajo realizado
+por el recolector en general es dividiendo el *heap* en particiones de manera
+tal de recolectar solo las partes donde más probabilidad de encontrar *basura*
+haya.
+
+Entonces, si el recolector tiene algún mecanismo para identificar zonas de
+alta concentración de *basura* puede hacer la recolección solo en ese área
+donde el trabajo va a ser mejor recompensado (ver :vref:`fig:gc-part`).
+
+.. fig:: fig:gc-part
+
+ Concentración de basura en distintas particiones del *heap*.
+
+ .. aafig::
+ :aspect: 0.7
+
+ _______________________________________________________________________
+ | |
+ | +-----------------------------+ +-----------------------------+ |
+ | / Baja \ / Alta \ |
+ | + + + |
+ | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
+ | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
+ | |
+ | GG Celdas vivas ZZ Basura |
+ |_______________________________________________________________________|
+
+
+Sin embargo encontrar zonas de alta concentración no es trivial. La forma más
+divulgada de encontrar estas zonas es dividiendo el *heap* en una partición
+utilizada para almacenar celdas *jóvenes* y otra para celdas *viejas*. Una
+celda *vieja* es aquella que ha *sobrevivido* una cantidad *N* de
+recolecciones, mientras que el resto se consideran *jóvenes* (las celdas
+*nacen* jóvenes). Los recolectores que utilizan este tipo de partición son
+ampliamente conocido como recolectores **generacionales**. La *hipótesis
+generacional* dice que el área de celdas jóvenes tiene una mayor probabilidad
+de ser un área de alta concentración de basura [JOLI96]_. Basándose en esto,
+los recolectores generacionales primero intentan recuperar espacio del área de
+celdas jóvenes y luego, de ser necesario, del área de celdas viejas. Es
+posible tener varias generaciones e ir subiendo de generación a generación
+a medida que es necesario. Sin embargo en general no se obtienen buenos
+resultados una vez que se superan las 3 particiones. La complejidad que trae
+este método es que para recolectar la generación joven es necesario tomar las
+referencias de la generación vieja a la joven como parte del *root set* (de
+otra forma podrían tomarse celdas como *basura* que todavía son utilizadas por
+las celdas viejas). Revisar toda la generación vieja no es una opción porque
+sería prácticamente lo mismo que realizar una recolección del *heap* completo.
+La solución está entonces, una vez más, en instrumentar el *mutator* para que
+avise al recolector cuando cambia una referencia de la generación vieja a la
+joven (no es necesario vigilar las referencias en sentido inverso ya que
+cuando se recolecta la generación vieja se hace una recolección del *heap*
+completo).
+
+Sin embargo, a pesar de ser este el esquema más difundido para dividir el
+*heap* y realizar una recolección parcial sobre un área de alta concentración
+de basura no es la única. Otros recolectores proponen hacer un análisis
+estático del código revisando la conectividad entre los objetos según sus
+tipos (esto es posible solo en lenguajes con *tipado* estático), de manera tal
+de separar en distintas áreas grupos de tipos que no pueden tener referencias
+entre sí [HIRZ03]_. Este análisis hace que sea innecesario instrumentar el
+*mutator* para reportar al recolector cambios de referencias
+inter-particiones, sencillamente porque queda demostrado que no existe dicho
+tipo de referencias. Esto quita una de las principales ineficiencias
+y complejidades del esquema generacional.
projects / z.facultad / 75.00 / informe.git / blobdiff