.. Introducción a la importancia de la recolección de basura y sus
principales técnicas, con sus ventajas y desventajas. También se da
un breve recorrido sobre el estado del arte.
- ESTADO: SIN EMPEZAR
+ ESTADO: TERMINADO
+
.. _ref_gc:
============================================================================
+
.. _ref_gc_intro:
Introducción
-
.. _ref_gc_classic:
Algoritmos clásicos
[PHP081]_.
-
.. _ref_gc_rc_example:
Ejemplo
}
-
Luego se cambia una referencia (en vez de eliminarse) realizándose la
operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador
de referencias de ``h5`` para evitar confundirlo accidentalmente con
-
.. _ref_gc_mark_sweep:
Marcado y barrido
+.. _ref_gc_copy:
-Copia/Semi-espacio
+Copia de semi-espacio
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-TODO
+Este algoritmo consiste en hacer una partición del *heap* en 2 mitades
+o *semi-espacios*, llamados usualmente *Fromspace* y *Tospace*. El primero se
+utiliza para alocar nuevas celdas de forma lineal, asumiendo un *heap*
+contiguo, incrementando un puntero (ver figura :vref:`fig:gc-copy`). Esto se
+conoce como *pointer bump allocation* y es, probablemente, la forma más
+eficiente de alocar memoria (tan eficiente como alocar memoria en el *stack*).
+
+.. fig:: fig:gc-copy
+
+ Estructura del *heap* de un recolector con copia de semi-espacios.
+
+ .. aafig::
+ :aspect: 0.7
+ :scale: 1.4
+
+ zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
+
+ /---+"Fromspace" /---+"Tospace"
+ | |
+ V_______________________________V_______________________________
+ | XXXX X XXX aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+ | XXXX X XXX aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+ | XXXX X XXX aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+ |~~~~~~~~~~~~~~~A~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ |
+ | | | XX "Fromspace usado"
+ \---+"libre"
+ | | ZZ "Fromspace basura"
+
+ |/ "longitud del semi-espacio" |/ AA "Fromspace libre"
+ +- - - - - - - - - - - - - - - -+
+ /| /| BB "Tospace"
+
+
+La segunda mitad (*Tospace*) permanece inutilizada hasta que se agota el
+espacio en el *Fromspace*; en ese momento comienza el proceso de recolección
+de basura que consiste en recorrer el grafo de conectividad, copiando las
+celdas *vivas* del *Fromspace* al *Tospace* de manera contigua, como si
+estuvieran alocando por primera vez. Como la posición en memoria de las celdas
+cambia al ser movidas, es necesario actualizar la dirección de memoria de
+todas las celdas *vivas*. Para esto se almacena una dirección de memoria de
+redirección, *forwarding address*, en las celdas que mueven. La *forwarding
+address* sirve a su vez de marca, para no recorrer una celda dos veces (como
+se explica en :ref:`ref_gc_intro_mark`). Cuando se encuentra una celda que ya
+fue movida, simplemente se actualiza la referencia por la cual se llegó a esa
+celda para que apunte a la nueva dirección, almacenada en la *forwarding
+address*. Una vez finalizado este proceso, el *Fromspace* y *Tospace*
+invierten roles y se prosigue de la misma manera (todo lo que quedó en el
+viejo *Fromspace* es *basura* por definición, por lo que se convierte el
+*Tospace*).
+
+A continuación se presenta una implementación sencilla de los servicios
+provistos por este tipo de recolectores. Cabe destacar que este tipo de
+recolectores deben estar íntimamente relacionados con el *low level
+allocator*, ya que la organización del *heap* y la forma de alocar
+memoria es parte fundamental de este algoritmo. Se asume que ya hay dos áreas
+de memoria del mismo tamaño destinadas al *Fromspace* y *Tospace*, y la
+existencia de 4 variables: ``fromspace`` (que apunta a la base del
+*Fromspace*), ``tospace`` (que apunta a la base del *Tospace*), ``spacesize``
+(que contiene el tamaño de un semi-espacio) y ``free`` (que apunta al lugar
+del *Fromspace* donde comienza la memoria libre). También vale aclarar que
+este algoritmo soporta inherentemente celdas de tamaño variable, por lo que
+los servicios ``alloc()`` y ``new()`` [#gccopynew]_ reciben como parámetro el
+tamaño de la celda a alocar::
+
+ function alloc(size) is
+ if free + size > fromspace + spacesize
+ return null
+ else
+ cell = free
+ free = free + size
+ return cell
+
+ function new(size) is
+ cell = alloc(size)
+ if cell is null
+ collect()
+ cell = alloc(size)
+ if cell is null
+ throw out_of_memory
+ return cell
+
+ function collect() is
+ free = tospace
+ foreach r in root_set
+ r = copy(r)
+ fromspace, tospace = tospace, fromspace
+
+ function copy(cell) is
+ if cell.forwarding_address is null
+ cell.forwarding_address = free
+ free = free + cell.size
+ foreach child in cell
+ child = copy(child)
+ return cell.forwarding_address
+ else
+ return cell.forwarding_address
+
+.. [#gccopynew] Notar que ``new()`` es igual que en el marcado y barrido con
+ la salvedad de que en este caso toma como parámetro el tamaño de la celda.
+
+Esta técnica tiene nombres variados en inglés: *semi-space*, *two-space*
+o simplemente *copying collector*. En este documento se denomina "copia de
+semi-espacio" porque los otros nombres son demasiado generales y pueden
+describir, por ejemplo, algoritmos donde no hay copia de celdas o donde no hay
+2 semi-espacios (como se verá en :ref:`ref_gc_art`).
+
+Al igual que el :ref:`ref_gc_mark_sweep` este algoritmo es :ref:`indirecto
+<ref_gc_direct>`, :ref:`no incremental <ref_gc_inc>` y :ref:`stop-the-world
+<ref_gc_concurrent>`. Las diferencias con los esquemas vistos hasta ahora son
+evidentes. La principal ventaja sobre el marcado y barrido (que requiere una
+pasada sobre el *live set*, el marcado, y otra sobre el *heap* entero, el
+barrido) es que este método require una sola pasada y sobre las celdas vivas
+del *heap* solamente. La principal desventaja es copia memoria, lo que puede
+ser particularmente costoso, además de requerir, como mínimo, el doble de
+memoria de lo que el *mutator* realmente necesita. Esto puede traer en
+particular problemas con la memoria virtual y el caché, por la pobre localidad
+de referencia.
+
+Por lo tanto los recolectores de este tipo pueden ser convenientes por sobre
+el marcado y barrido cuando se espera que el *live set* sea muy pequeño luego
+de una recolección. En estos casos el trabajo realizado por este tipo de
+recolectores puede ser considerablemente menor que el del marcado y barrido.
+Y por el contrario, si el *working set* es pequeño, al ser *compactado* en
+memoria puede mejorar la localidad de referencia (si el *working set* es
+grande se corre el riesgo de que la localidad de referencia empeore al
+moverse las celdas).
+
+
+Ejemplo
+^^^^^^^
+
+A continuación se presenta un sencillo ejemplo del algoritmo. Se parte de una
+estructura simple con 4 celdas en el *Fromspace* (que incluye un pequeño ciclo
+para mostrar que este algoritmo tampoco tiene inconvenientes para
+recolectarlos). Asumimos que ya no queda lugar en el *Fromspace* por lo que
+comienza la ejecución de ``collect()``. Se comienza por el *root set* que
+apunta a ``h3``, por lo tanto ésta es movida al *Tospace* primero, dejando una
+*forwarding address* a la nueva ubicación (ver figura
+:vref:`fig:gc-copy-ex-1`).
+
+.. fig:: fig:gc-copy-ex-1
+
+ Ejemplo de recolección con copia de semi-espacios (parte 1).
+
+ .. subfig::
+
+ Estructura inicial del *heap*. El *Fromspace* está complete y se inicial
+ la recolección.
+
+ .. aafig::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "Fromspace" |
+ | /--------------------------------\ |
+ | | /--------\ /------\ | |
+ | | | | | | | |
+ | ______|_V________|__V______|___________V______ |
+ | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
+ | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
+ | ~~~~~~~~~|~~~~~~~~~~A~~~~~~~A~~~~~~~~~~~~~~~~~ |
+ | h1 | h2 | h3 | h4 |
+ | \----------/ | |
+ | \----+"root set" |
+ | |
+ | |
+ | |
+ | ______________________________________________ |
+ | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+ | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+ | A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
+ | | |
+ | \----+"free" |
+ | "Tospace" |
+ +--------------------------------------------------+
+
+ .. subfig::
+
+ Se sigue la referencia del *root set*, copiando ``h3`` al *Tospace*
+ y dejando una *forwarding address*.
+
+ .. aafig::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "Fromspace" |
+ | /--------------------------------\ |
+ | | /--------\ /------\ | |
+ | | | | | | | |
+ | ______|_V________|__V______|___________V______ |
+ | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
+ | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
+ | ~~~~~~~~~|~~~~~~~~~~A~~~~~~~|A~~~~~~~~~~~~~~~~ |
+ | h1 | h2 | h3 || h4 |
+ | \----------/ || |
+ | +\----+"root set" |
+ | / |
+ | /-------------------------+ |
+ | | h3 |
+ | V_____________________________________________ |
+ | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+ | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+ | ~~~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
+ | | |
+ | \----+"free" |
+ | "Tospace" |
+ +--------------------------------------------------+
+
+
+A continuación se copian las *hijas* de ``h3``, en este caso sólo ``h2``, que
+se ubica en el *Tospace* a continuación de ``h3``, dejando nuevamente su
+``forwarding address`` en la celda original. Al proceder recursivamente, se
+procede a copiar ``h1`` al *Tospace*, dejando una vez más la *forwarding
+address* en la celda original y procediendo con las hijas. Aquí podemos
+observar que al seguirse la referencia :math:`h1 \to h2`, como ``h2`` ya había
+sido visitada, solamente se actualiza la referencia apuntando a la nueva
+ubicación de ``h2`` pero no se vuelve a copiar la celda (ver figura
+:vref:`fig:gc-copy-ex-2`).
+
+.. fig:: fig:gc-copy-ex-2
+
+ Ejemplo de recolección con copia de semi-espacios (parte 2).
+
+ .. subfig::
+
+ Se sigue :math:`h3 \to h2`, copiando ``h2`` al *Tospace* y dejando una
+ *forwarding address*.
+
+ .. aafig::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "Fromspace" |
+ | /--------------------------------\ |
+ | | /--------\ /------\ | |
+ | | | | | | | |
+ | ______|_V________|__V______|___________V______ |
+ | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
+ | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
+ | ~~~~~~~~~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~ |
+ | h1 | h2 || h3 || h4 |
+ | \----------/+ || |
+ | / +\----+"root set" |
+ | +-----------+ / |
+ | /------+------------------+ |
+ | | h3 | h2 |
+ | V______V______________________________________ |
+ | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+ | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+ | ~~|~~~~~~A~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
+ | | | | |
+ | \------/ \----+"free" |
+ | "Tospace" |
+ +--------------------------------------------------+
+
+ .. subfig::
+
+ Se sigue :math:`h2 \to h1`, copiando ``h1``. Luego :math:`h1 \to h2`
+ pero ``h2`` no se copia, sólo se actualiza la referencia con la
+ *forwarding address*.
+
+ .. aafig::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "Fromspace" |
+ | /--------------------------------\ |
+ | | /--------\ /------\ | |
+ | | | | | | | |
+ | ______|_V________|__V______|___________V______ |
+ | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
+ | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
+ | ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~ |
+ | h1 | | h2 || h3 || h4 |
+ | \-+----------/+ || |
+ | +-----+ / +\-----+"root set" |
+ | +-------+---+ / |
+ | /------+-------+----------+ |
+ | | h3 | h2 | h1 |
+ | V______V_______V______________________________ |
+ | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
+ | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
+ | ~~|~~~~~~A~|~A~~|~A~~~~A~~~~~~~~~~~~~~~~~~~~~~ |
+ | | | | | | | | |
+ | \------/ | \--/ | \----+"free" |
+ | "Tospace" \------/ |
+ +--------------------------------------------------+
+
+
+Se termina de copiar recursivamente las hijas de ``h1`` al copiar ``h4`` que
+resulta la última celda (sin hijas). Finalmente se invierten los roles de los
+semi-espacios y se actualiza la referencia del *root set* para que apunte a la
+nueva ubicación de ``h3``, como se muestra en la figura
+:vref:`fig:gc-copy-ex-3`.
+
+.. fig:: fig:gc-copy-ex-3
+
+ Ejemplo de recolección con copia de semi-espacios (parte 3).
+
+ .. subfig::
+
+ Se sigue :math:`h1 \to h4` copiando `h4`` al *Tospace* y dejando una
+ *forwarding address*.
+
+ .. aafig::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "Fromspace" |
+ | /--------------------------------\ |
+ | | /--------\ /------\ | |
+ | | | | | | | |
+ | ______|_V________|__V______|___________V______ |
+ | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
+ | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
+ | ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~|~~~~~ |
+ | h1 | | h2 || h3 || h4 \----\ |
+ | \-+----------/+ || | |
+ | +-----+ / +----/\---+"root set" | |
+ | +-------+---+ / | |
+ | /------+-------+-----+ /--------------------/ |
+ | | h3 | h2 | h1 | h4 |
+ | V______V_______V________V_____________________ |
+ | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+ | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+ | ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~ |
+ | | | | | | | | | | |
+ | \------/ | \--/ | \------/ \----+"free" |
+ | "Tospace" \------/ |
+ +--------------------------------------------------+
+
+ .. subfig::
+
+ Se finaliza la recolección, se intercambian los roles de los
+ semi-espacios y se actualiza la referencia del *root set*.
+
+ .. aafig::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "Tospace" |
+ | |
+ | |
+ | |
+ | ______________________________________________ |
+ | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
+ | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
+ | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
+ | |
+ | |
+ | |
+ | /---+"root set" |
+ | | |
+ | | h3 h2 h1 h4 |
+ | V______________________________________________ |
+ | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+ | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+ | ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~ |
+ | | | | | | | | | | |
+ | \------/ | \--/ | \------/ \---+"free" |
+ | "Fromspace" \------/ |
+ +--------------------------------------------------+
Estado del arte
----------------------------------------------------------------------------
-.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
- ejemplos.
+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.
-TODO
+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]_.
-Clasificación
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+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).
-La cantidad de clasificaciones que pueden hacerse respecto a algoritmos de
-recolección de basura son muy grandes. Muchas de estas clasificaciones se
-superponen entre sí, habiendo algoritmos que aplican muchas técnicas a la
-vez o recolectores híbridos que aplican una técnica para algún tipo de
-objeto y otra para otros.
-A continuación se enumeran las clasificaciones más importantes que se
-pudieron observar en la investigación sobre el `estado del arte`_.
.. _ref_gc_direct:
-Directa / indirecta
-^^^^^^^^^^^^^^^^^^^
+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 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 (dejando de lado el :ref:`problema de
-los ciclos <ref_gc_rc_cycles>`). Esto permite reclamar una celda
-instantáneamente cuando el *mutator* deja de hacer referencia a ella. Este
-tipo de recolectores son, inherentemente :ref:`incrementales <ref_gc_inc>`.
+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:`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
+<ref_gc_inc>`.
Por el contrario, los recolectores **indirectos** normalmente no
interfieren con el *mutator* en cada actualización del grafo de
la información de conectividad desde cero para determinar qué celdas son
*basura*.
-Estas son las dos grandes familias de recolectores, también conocidos como
-`conteo de referencias`_ (directa) y *traicing garbage collection*
-(indirecta).
+Esta es la madre de toda clasificación, también conocidos como :ref:`conteo de
+referencias <ref_gc_rc>` (directa) y *traicing garbage collection*
+(indirecta). Prácticamente todos los recolectores menos el :ref:`conteo de
+referencias <ref_gc_rc>` están dentro de esta última categoría (como por
+ejemplo, el :ref:`marcado y barrido <ref_gc_mark_sweep>` y :ref:`copia de
+semi-espacio <ref_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).
+
.. _ref_gc_inc:
-Incremental
-^^^^^^^^^^^
+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 en tiempo total de recolección).
+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 `conteo de referencias`_. 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*
-aloca 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.
+básica es el :ref:`conteo de referencias <ref_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* aloca 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
+<ref_gc_direct>` se utiliza la :ref:`abstracción tricolor
+<ref_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 la eficiencia de los recolectores incrementales disminuye
considerablemente cuando el *mutator* actualiza muy seguido el grafo 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]_,
+
+
.. _ref_gc_concurrent:
-Concurrente / *stop-the-world*
-^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+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* (*parar
+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.
+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
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.
-
-
-Cloning
+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]_.
-1. Instrumentar el *mutator* de forma tal de que informe al recolector cada
- vez que cambia el grafo de conectividad, de manera que pueda re-escanear
- el sub-grafo que afectado por el cambio.
+.. [#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.
-2. Tomar una foto de la memoria y escanear esa foto estática en vez de la
- memoria original, de forma que cualquier cambio en del *mutator* no
- afecte la vista de la memoria del recolector.
+Todos los :ref:`algoritmos clásicos <ref_gc_classic>` que se han citado son
+del tipo *stop-the-world*.
-Ambos métodos tienen ventajas y desventajas. El primero no necesita hacer
-una copia costosa de la memoria, pero existe la posibilidad de que el
-recolector nunca pueda escanear el grafo de conectividad completo, si el
-*mutator* modifica el grafo más rápido de lo que el recolector lo escanea.
-Si bien hay formas de evitar esto, es usual que el trabajo de recolección
-se vea considerablemente incrementado por la cantidad de veces que hay que
-re-escanear el grafo. El segundo método puede ser costoso por las copias
-necesarias (aunque esto puede ser mitigado empleando alguna forma de *COW*
-[#gccow]_) y existe la posibilidad de que no se recuperen celdas que el
-*mutator*
-.. [#gccow] *COW* (del inglés *Copy On Write* o *copiar al escribir*) es
- una técnica muy utilizada para disminuir las copias innecesarias,
- evitando hacer la copia hasta que haya una modificación. Mientras no
- hayan modificaciones no es necesario realizar una copia porque todos los
- interesados verán la misma información. Esta técnica es utilizada por el
- *kernel* de Linux_ por ejemplo, para que varias instancias de un mismo
- proceso puedan compartir la memoria.
+.. _ref_gc_free_list:
+Lista de libres / *pointer bump allocation*
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Boehm, H., and M. Weiser, "Garbage Collection in an Uncooperative
-Environment", Software Practice & Experience, September 1988, pp. 807-820.
-http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/preprint.pdf
-(http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/)
+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:`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 alocar 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. :ref:`ref_gc_mark_sweep` en general usa este
+esquema, al igual que :ref:`ref_gc_rc`.
+
+Otro forma de organizar el *heap* es utilizándolo como una especie de *stack*
+en el cual para alocar simplemente se incrementa un puntero. Este esquema es
+simple y eficiente, si el recolector puede mover celdas (ver
+:ref:`ref_gc_moving`); de otra manera alocar 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 :ref:`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 alocan páginas completas (similar a las regiones) y dentro de
+cada página se alocan 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 <ref_dgc_actual>`).
+
+
+
+.. _ref_gc_moving:
+
+Movimiento de celdas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Boehm, H., "Space Efficient Conservative Garbage Collection", Proceedings
-of the ACM SIGPLAN '93 Conference on Programming Language Design and
-Implementation, SIGPLAN Notices 28, 6 (June 1993), pp. 197-206.
-http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi93.ps.Z
+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 <ref_gc_free_list>`, ya que *compacta* todas
+las celdas *vivas* al comienzo del *heap* luego de una recolección,
+permitiendo este esquema para alocar 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
+<ref_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 <ref_gc_free_list>` y que es sencillo
+implementar recolectores :ref:`generacionales <ref_gc_part>` sobre estos.
+
+De los algoritmos clásicos sólo la :ref:`copia de semi-espacios <ref_gc_copy>`
+mueve celdas, el :ref:`conteo de referencias <ref_gc_rc>` y :ref:`marcado
+y barrido <ref_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 <ref_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]_.
+
+
+
+.. _ref_gc_conserv:
+
+Recolectores conservativos vs precisos
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Boehm, H., A. Demers, and S. Shenker, "Mostly Parallel Garbage Collection",
-Proceedings of the ACM SIGPLAN '91 Conference on Programming Language
-Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 157-164.
-http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi91.ps.Z
+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:`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 comunmente 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:`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
+conservativismo son el :ref:`recolector actual de D <ref_dgc_actual>`
+y [BLAC08]_.
+
+
+
+.. _ref_gc_part:
+
+Recolección particionada
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-Implementación de Bohem GC
-http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html
+Otra forma de reducir la cantidad de pausas y la cantidad de trabajo realizado
+por el recolector en general es particionando el *heap* 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 particionando el *heap* en un área
+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]_. Basandose 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 monitorear 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 particionar 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 inecesario 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 principale ineficiencias
+y complejidades del esquema generacional.
-Interfaz de Bohem GC
-http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html
.. include:: links.rst
projects / z.facultad / 75.00 / informe.git / blobdiff