ESTADO: TERMINADO
-.. _ref_gc:
+.. _gc:
Recolección de basura
============================================================================
-.. _ref_gc_intro:
+.. _gc_intro:
Introducción
----------------------------------------------------------------------------
-.. _ref_gc_intro_mark:
+.. _gc_intro_mark:
Recorrido del grafo de conectividad
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. _ref_gc_intro_tricolor:
+.. _gc_intro_tricolor:
Abstracción tricolor
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Muchos algoritmos utilizan tres colores para realizar el marcado. El tercer
color, gris generalmente, indica que una celda debe ser visitada. Esto
-permite algoritmos :ref:`concurrentes <ref_gc_concurrent>`
-e :ref:`incrementales <ref_gc_inc>`, además de otro tipo de optimizaciones.
+permite algoritmos :ref:`concurrentes <gc_concurrent>`
+e :ref:`incrementales <gc_inc>`, además de otro tipo de optimizaciones.
Entonces, lo que plantea esta abtracción es una nueva partición del heap al
momento de marcar, esta vez son 3 porciones: blanca, gris y negra.
-.. _ref_gc_intro_services:
+.. _gc_intro_services:
Servicios
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cambio en la conectividad del grafo, la eliminación de una arista
(análogo a :math:`update(ref, null)` pero sin proporcionar información
sobre la arista a eliminar). Esto es generalmente útil solo en
- :ref:`conteo de referencias <ref_gc_rc>`. Para otros recolectores puede
+ :ref:`conteo de referencias <gc_rc>`. Para otros recolectores puede
significar que el usuario asegura que no hay más referencias a esta
celda, es decir, análogo a eliminar el conjunto de aristas
:math:`\big\lbrace (v, w) \in A , v \in Live \thickspace set , w \in
-.. _ref_gc_classic:
+.. _gc_classic:
Algoritmos clásicos
----------------------------------------------------------------------------
-.. _ref_gc_rc:
+.. _gc_rc:
Conteo de referencias
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Se trata del algoritmo más antiguo de todos, implementado por primera vez
por `John McCarthy`_ para Lisp_ a finales de 1950. Se trata de un método
-:ref:`directo <ref_gc_direct>` e :ref:`incremental <ref_gc_inc>` por
+:ref:`directo <gc_direct>` e :ref:`incremental <gc_inc>` por
naturaleza, ya que distribuye la carga de la recolección de basura durante
toda la ejecución del programa, cada vez que el *mutator* cambia la
conectividad de algún nodo del grafo de conectividad.
-.. _ref_gc_rc_cycles:
+.. _gc_rc_cycles:
Ciclos
^^^^^^
[PHP081]_.
-.. _ref_gc_rc_example:
+.. _gc_rc_example:
Ejemplo
^^^^^^^
-.. _ref_gc_mark_sweep:
+.. _gc_mark_sweep:
Marcado y barrido
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consiste en realizar la recolección en 2 fases: marcado y barrido. La primera
fase consiste en el proceso de marcar el grafo de conectividad del *heap* para
descubrir qué celdas son alcanzables desde el *root set*, tal y como se
-describió en :ref:`ref_gc_intro_mark`.
+describió en :ref:`gc_intro_mark`.
Una vez marcadas todas las celdas, se sabe que las celdas *blancas* son
*basura*, por lo tanto el paso que queda es el *barrido* de estas celdas,
free(cell)
El algoritmo ``mark_sweep()`` es exactamente igual al presentado en
-:ref:`ref_gc_intro_mark`. Es preciso notar que la fase de barrido
+:ref:`gc_intro_mark`. Es preciso notar que la fase de barrido
(``sweep_phase()``) debe tener una comunicación extra con el *low level
allocator* para poder obtener todas las celdas de memoria que existen en el
*heap*.
A diferencia del conteo de referencias, este algoritmo es :ref:`indirecto
-<ref_gc_direct>` y :ref:`no incremental <ref_gc_inc>`, ya que se realiza un
+<gc_direct>` y :ref:`no incremental <gc_inc>`, ya que se realiza un
recorrido de todo el *heap* de forma espaciada a través de la ejecución del
programa. En general el *mutator* sufre pausas considerablemente mayores (en
promedio) que con el conteo de referencias, lo que puede ser problemático para
aplicaciones con requerimientos rígidos de tiempo, como aplicaciones
*real-time*. Debido a la percepción de las pausas grandes, este tipo de
-colectores se conocen como :ref:`stop-the-world <ref_gc_concurrent>` (o
+colectores se conocen como :ref:`stop-the-world <gc_concurrent>` (o
*detener el mundo*).
Una ventaja fundamental sobre el conteo de referencias es la posibilidad de
-.. _ref_gc_copy:
+.. _gc_copy:
Copia de semi-espacio
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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
+se explica en :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*
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`).
+2 semi-espacios (como se verá en :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
+Al igual que el :ref:`gc_mark_sweep` este algoritmo es :ref:`indirecto
+<gc_direct>`, :ref:`no incremental <gc_inc>` y :ref:`stop-the-world
+<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
-.. _ref_gc_art:
+.. _gc_art:
Estado del arte
----------------------------------------------------------------------------
-.. _ref_gc_direct:
+.. _gc_direct:
Recolección directa / indirecta
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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
+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
-<ref_gc_inc>`.
+<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
-<ref_gc_inc>` que a veces necesitan instrumentar el *mutator* pero no para
+<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 alocar memoria pero no hay
más memoria libre conocida disponible y el recolector se encarga de generar
*basura*.
Esta es la madre de toda clasificación, también conocidos como :ref:`conteo de
-referencias <ref_gc_rc>` (directa) y *traicing garbage collection*
+referencias <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>`).
+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
-.. _ref_gc_inc:
+.. _gc_inc:
Recolección incremental
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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 <ref_gc_rc>`. Otros recolectores
+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* aloca memoria. En general para hacer esto es también necesario
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
+<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 la eficiencia de los recolectores incrementales disminuye
-.. _ref_gc_concurrent:
+.. _gc_concurrent:
Recolección concurrente / paralela / *stop-the-world*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Para lograr que un recolector sea concurrente generalmente el mecanismo es
similar al necesario para hacer un :ref:`recolector incremental
-<ref_gc_inc>`: hay que instrumentar al *mutator* para que informe al
+<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.
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 <ref_gc_classic>` que se han citado son
+Todos los :ref:`algoritmos clásicos <gc_classic>` que se han citado son
del tipo *stop-the-world*.
-.. _ref_gc_free_list:
+.. _gc_free_list:
Lista de libres / *pointer bump allocation*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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,
+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
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`.
+muchas otras ineficiencias. :ref:`gc_mark_sweep` en general usa este
+esquema, al igual que :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
+: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`.
+puntero). El clásico ejemplo de esta familia es :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.
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:`recolector actual de D <dgc_actual>`).
-.. _ref_gc_moving:
+.. _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 <ref_gc_free_list>`, ya que *compacta* todas
+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 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
+<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*
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.
+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 <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
+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 <ref_gc_copy>` pero suele poder proveer una mayor localidad 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
-.. _ref_gc_conserv:
+.. _gc_conserv:
Recolectores conservativos vs precisos
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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
+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
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`).
+: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>`
+conservativismo son el :ref:`recolector actual de D <dgc_actual>`
y [BLAC08]_.
-.. _ref_gc_part:
+.. _gc_part:
Recolección particionada
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
projects / z.facultad / 75.00 / informe.git / commitdiff