============================================================================
+.. _ref_gc_intro:
+
Introducción
----------------------------------------------------------------------------
del *heap* [#gcheap]_ una vez que el programa ha dejado de hacer referencia
a ella (y por lo tanto, ha dejado de utilizarla).
+.. [#gcheap] *Heap* es un área de memoria que se caracteriza por ser
+ dinámica (a diferencia del área de memoria estática que está disponible
+ durante toda la ejecución de un programa). Un programa puede reservar
+ memoria en tiempo de ejecución según sea necesario y liberarla cuando ya
+ no la necesita. A diferencia del *stack*, la duración de la *reserva* no
+ está atada a un bloque de código.
+
A medida que el tiempo pasa, cada vez los programas son más complejos y es
más compleja la administración de memoria. Uno de los aspectos más
importantes de un recolector de basura es lograr un mayor nivel de
(como *buffer overflows* [#gcbuff]_ o *dangling pointers* [#gcdang]_) son
la causa más frecuente de problemas de seguridad [BEZO06]_.
+.. [#gcbuff] Un *buffer overflow* (*desbordamiento de memoria* en
+ castellano) se produce cuando se copia un dato a un área de memoria que
+ no es lo suficientemente grande para contenerlo. Esto puede producir que
+ el programa sea abortado por una violación de segmento, o peor,
+ sobreescribir un área de memoria válida, en cuyo caso los resultados son
+ impredecibles.
+
+.. [#gcdang] Un *dangling pointer* (*puntero colgante* en castellano) es un
+ puntero que apunta a un área de memoria inválida. Ya sea porque el
+ elemento apuntado no es el mismo tipo o porque la memoria ya ha sido
+ liberada. Al ser desreferenciado, los resultados son impredecibles, el
+ programa podría abortarse por una violación de segmento o podrían pasar
+ peores cosas si el área de memoria fue realocada para almacenar otro
+ objeto.
+
La recolección de basura nació junto a Lisp_ a finales de 1950 y en los
siguientes años estuvo asociada principalmente a lenguajes funcionales,
pero en la actualidad está presente en prácticamente todos los lenguajes de
difícil la búsqueda de errores.
-.. [#gcheap] *Heap* es un área de memoria que se caracteriza por ser
- dinámica (a diferencia del área de memoria estática que está disponible
- durante toda la ejecución de un programa). Un programa puede reservar
- memoria en tiempo de ejecución según sea necesario y liberarla cuando ya
- no la necesita. A diferencia del *stack*, la duración de la *reserva* no
- está atada a un bloque de código.
-.. [#gcbuff] Un *buffer overflow* (*desbordamiento de memoria* en
- castellano) se produce cuando se copia un dato a un área de memoria que
- no es lo suficientemente grande para contenerlo. Esto puede producir que
- el programa sea abortado por una violación de segmento, o peor,
- sobreescribir un área de memoria válida, en cuyo caso los resultados son
- impredecibles.
-.. [#gcdang] Un *dangling pointer* (*puntero colgante* en castellano) es un
- puntero que apunta a un área de memoria inválida. Ya sea porque el
- elemento apuntado no es el mismo tipo o porque la memoria ya ha sido
- liberada. Al ser desreferenciado, los resultados son impredecibles, el
- programa podría abortarse por una violación de segmento o podrían pasar
- peores cosas si el área de memoria fue realocada para almacenar otro
- objeto.
-
Conceptos básicos
celda [#gccelda]_ alocada antes que otra nunca puede ser liberada antes
que aquella.
+ .. [#gccelda] En general en la literatura se nombra a una porción de
+ memoria alocada individualmente *celda*, *nodo* u *objeto*
+ indistintamente. En este trabajo se utilizará la misma nomenclatura
+ (haciendo mención explícita cuando alguno de estos términos se
+ refiera a otra cosa, como al nodo de una lista o a un objeto en el
+ sentido de programación orientada a objetos).
+
*Heap*:
A diferencia del *stack*, el *heap* provee un área de memoria que puede
ser obtenida dinámicamente pero sin limitaciones de orden. Es el tipo de
normalmente se lo llama *mutator* (mutador).
-.. [#gccelda] En general en la literatura se nombra a una porción de
- memoria alocada individualmente *celda*, *nodo* u *objeto*
- indistintamente. En este trabajo se utilizará la misma nomenclatura
- (haciendo mención explícita cuando alguno de estos términos se refiera
- a otra cosa, como al nodo de una lista o a un objeto en el sentido de
- programación orientada a objetos).
-
+.. _ref_gc_intro_mark:
Recorrido del grafo de conectividad
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
y de esta manera tener un mejor comportamiento de la memoria virtual o del
*caché*.
+.. [#gccycle] Un ciclo es un camino donde el *vértice inicial* es el mismo
+ que el *vértice final*. Por lo tanto, los *vértices terminales* son
+ completamente arbitrarios, ya que cualquier *vértice interior* puede ser
+ un *vértice terminal*.
+
Un algoritmo simple (recursivo) de marcado *primero a lo alto* puede ser
el siguiente (asumiendo que partimos con todos los vértices sin marcar)
[#gcpseudo]_::
- mark(v)
+ function mark(v) is
if not v.marked
v.marked = true
for (src, dst) in v.edges
mark(dst)
- mark_phase()
- for r in root_set
+ function mark_phase() is
+ foreach r in root_set
mark(r)
+.. [#gcpseudo] Para presentar los algoritmos se utiliza una forma simple de
+ pseudo-código. El pseudo-código se escribe en inglés para que pueda ser
+ más fácilmente contrastado con la literatura, que está en inglés. Para
+ diferenciar posiciones de memoria y punteros de las celdas en sí, se usa
+ la misma sintaxis que C, ``r*`` denota una referencia o puntero y ``*r``
+ denota "objeto al que apunta ``r``\ ". Se sobreentiende que ``r = o``
+ siempre toma la dirección de memoria de ``o``.
+
Una vez concluido el marcado, sabemos que todos los vértices con la marca
son parte del *live set* y que todos los vértices no marcados son *basura*.
Esto es conocido también como **abstracción bicolor**, dado que en la
Puede observarse un ejemplo del algoritmo en la figura
:vref:`fig:gc-mark-1`, en la cual se marca el sub-grafo apuntando por
-``r0``. Luego se marca el sub-grafo al que apunta ``r1`` (figura
+``r0``. Luego se marca el sub-grafo al que apunta ``r1`` (ver figura
:vref:`fig:gc-mark-2`), concluyendo con el marcado del grafo completo,
dejando sin marcar solamente las celdas *basura* (en blanco).
}
-.. [#gccycle] Un ciclo es un camino donde el *vértice inicial* es el mismo
- que el *vértice final*. Por lo tanto, los *vértices terminales* son
- completamente arbitrarios, ya que cualquier *vértice interior* puede ser
- un *vértice terminal*.
-.. [#gcpseudo] Para presentar los algoritmos se utiliza una forma simple de
- pseudo-código. El pseudo-código se escribe en inglés para que pueda ser
- más fácilmente contrastado con la literatura, que está en inglés. Para
- diferenciar posiciones de memoria y punteros de las celdas en sí, se usa
- la misma sintaxis que C, ``r*`` denota una referencia o puntero y ``*r``
- denota "objeto al que apunta ``r``\ ". Se sobreentiende que ``r = o``
- siempre toma la dirección de memoria de ``o``.
-
-
-.. _ref_gc_tricolor:
+.. _ref_gc_intro_tricolor:
Abstracción tricolor
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
blanco contiene todas las celdas de memoria y los conjuntos negro y gris
están vacíos)::
- mark_phase()
- for r in root_set
+ function mark_phase() is
+ foreach r in root_set
gray_set.add(r)
while not gray_set.empty()
v = gray_set.pop()
-.. _ref_gc_services:
+.. _ref_gc_intro_services:
Servicios
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
de una capa inferior [#gclowlayer]_ y proveen servicios a una capa superior
[#gchilayer]_.
+.. [#gclowlayer] En general estos servicios están provistos directamente
+ por el sistema operativo pero también pueden estar dados por un
+ administrador de memoria de bajo nivel (o *low level allocator* en
+ inglés).
+
+.. [#gchilayer] En general estos servicios son utilizados directamente por
+ el lenguaje de programación, pero pueden ser utilizados directamente por
+ el usuario del lenguaje si éste interatúa con el recolector, ya sea por
+ algún requerimiento particular o porque el lenguaje no tiene soporte
+ diercto de recolección de basura y el recolector está implementado como
+ una biblioteca de usuario.
+
A continuación se presentan las primitivas en común que utilizan todos los
recolectores a lo largo de este documento.
usuario también.
-.. [#gclowlayer] En general estos servicios están provistos directamente
- por el sistema operativo pero también pueden estar dados por un
- administrador de memoria de bajo nivel (o *low level allocator* en
- inglés).
-.. [#gchilayer] En general estos servicios son utilizados directamente por
- el lenguaje de programación, pero pueden ser utilizados directamente por
- el usuario del lenguaje si éste interatúa con el recolector, ya sea por
- algún requerimiento particular o porque el lenguaje no tiene soporte
- diercto de recolección de basura y el recolector está implementado como
- una biblioteca de usuario.
-
-.. _ref_gc_clasic:
+.. _ref_gc_classic:
Algoritmos clásicos
----------------------------------------------------------------------------
Las primitivas implementadas para este tipo de recolector son las
siguientes (acompañadas de una implementación básica)::
- new()
+ function new() is
cell = alloc()
if cell is null
throw out_of_memory
cell.rc = 1
return cell
- del(cell)
+ function del(cell) is
cell.rc = cell.rc - 1
if cell.rc is 0
- for child* in cell.children
+ foreach child* in cell.children
del(*child)
free(cell)
- update(ref*, cell)
+ function update(ref*, cell) is
cell.rc = cell.rc + 1
del(*ref)
*ref = cell
+
.. _ref_gc_rc_cycles:
Ciclos
^^^^^^
+El conteo de referencias tiene, sin embargo, un problema fundamental:
+**falla con estructuras cíclicas**. Esto significa que siempre que haya un
+ciclo en el grafo de conectividad, hay una pérdida de memoria potencial en
+el programa. Un ciclo es un camino :math:`\underset{v \to v}{C}`, es decir,
+el *vértice inicial* es el mismo que el *vértice final*.
+
+Cuando esto sucede, las celdas que participan del ciclo tienen siempre su
+contador mayor que 0, sin embargo puede no haber ningún elemento del *root
+set* que apunte a una celda dentro del ciclo, por lo tanto el ciclo es
+*basura* (al igual que cualquier otra celda que sea referenciada por el
+ciclo pero que no tenga otras referencias externas) y sin embargo los
+contadores no son 0. Los ciclos, por lo tanto, *rompen* la invariante del
+conteo de referencia.
+
+Hay formas de solucionar esto, pero siempre recaen en un esquema que va por
+fuera del conteo de referencias puro. En general los métodos para
+solucionar esto son variados y van desde realizar un marcado del subgrafo
+para detectar nodos hasta tener otro recolector completo de *emergencia*,
+pasando por tratar los ciclos como un todo contar las referencias al ciclo
+completo en vez de a cada celda en particular.
+
+Incluso con este problema, el conteo de referencia sin ningún tipo de
+solución en cuanto a la detección y recolección de ciclos fue utilizado en
+muchos lenguajes de programación sin que su necesidad sea tan evidente. Por
+ejemplo Python_ agregó recolección de ciclos en la versión 2.0 [NAS00]_
+(liberada en octubre de 2000) y PHP_ recién agrega detección de ciclos en
+la versión 5.3 (todavía no liberada al momento de escribir este documento)
+[PHP081]_.
+
+
+
.. _ref_gc_rc_example:
Ejemplo
comienzo todas las celdas son accesibles desde el *root set* por lo tanto
son todas parte del *live set*.
-Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina
-que ``h1`` se convirtió en *basura* (figura :vref:`fig:gc-rc-rm-1`). Esto
-conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
-*live set* ya que sus contadores siguen siendo mayores a 0 (figura
-:vref:`fig:gc-rc-rm-2`).
-
.. fig:: fig:gc-rc-rm-1
h1 [ label = "h1\n1|<l> l|<r> r" ];
h2 [ label = "h2\n2|<l> l|<r> r" ];
- h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n3|<l> l|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n1|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h2:r -> h5;
h3:l -> h2;
h3:r -> h6;
+ h6:r -> h3:r;
}
h1 [ label = "h1\n1|<l> l|<r> r" ];
h2 [ label = "h2\n2|<l> l|<r> r" ];
- h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n3|<l> l|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n1|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h2:r -> h5;
h3:l -> h2;
h3:r -> h6;
+ h6:r -> h3:r;
}
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n2|<l> l|<r> r" ];
- h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n3|<l> l|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n1|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h2:r -> h5;
h3:l -> h2;
h3:r -> h6;
+ h6:r -> h3:r;
}
.. fig:: fig:gc-rc-rm-2
+ :padding: 0.5
Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n1|<l> l|<r> r" ];
- h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n3|<l> l|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n1|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h2:r -> h5;
h3:l -> h2;
h3:r -> h6;
+ h6:r -> h3:r;
}
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n1|<l> l|<r> r" ];
- h3 [ label = "h3\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n1|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h2:r -> h5;
h3:l -> h2;
h3:r -> h6;
+ h6:r -> h3:r;
}
-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
-*basura* si se elimina alguna celda que apuntaba a ésta. Luego se procede
-a decrementar el contador de ``h2`` que queda en 0, transformándose en
-*basura* (figura :vref:`fig:gc-rc-up-1`). Lo mismo pasa cuando se desciende
-a ``h4``, pero al descender a ``h5`` y decrementar el contador, éste sigue
-siendo mayor que 0 (pues ``h3`` va a apuntar a ``h5``) así que permanece en
-el *live set*. Finalmente se termina de actualizar la referencia ``h3.l``
-para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
+Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina
+que ``h1`` se convirtió en *basura* (ver figura :vref:`fig:gc-rc-rm-1`). Esto
+conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
+*live set* ya que sus contadores siguen siendo mayores a 0 (ver figura
+:vref:`fig:gc-rc-rm-2`).
.. fig:: fig:gc-rc-up-1
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n1|<l> l|<r> r" ];
- h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n2|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h3:l -> h2;
h3:l -> h5 [ style = dotted, color = black ];
h3:r -> h6;
+ h6:r -> h3:r;
}
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n1|<l> l|<r> r" ];
- h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n2|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h3:l -> h2 [ style = bold, color = black ];
h3:l -> h5 [ style = dotted, color = black ];
h3:r -> h6;
+ h6:r -> h3:r;
}
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n1|<l> l|<r> r" ];
- h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n2|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h3:l -> h2 [ style = invis ];
h3:l -> h5 [ style = dotted, color = black ];
h3:r -> h6;
+ h6:r -> h3:r;
}
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n1|<l> l|<r> r" ];
- h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
h4 [ label = "h4\n0|<l> l|<r> r" ];
h5 [ label = "h5\n2|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h3:l -> h2 [ style = invis ];
h3:l -> h5 [ style = dotted, color = black ];
h3:r -> h6;
+ h6:r -> h3:r;
}
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n1|<l> l|<r> r" ];
- h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
h4 [ label = "h4\n0|<l> l|<r> r" ];
h5 [ label = "h5\n1|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h3:l -> h5 [ style = bold, color = black ];
h3:l -> h2 [ style = invis ];
h3:r -> h6;
+ h6:r -> h3:r;
}
h1 [ label = "h1\n0|<l> l|<r> r" ];
h1 [ label = "h1\n0|<l> l|<r> r" ];
h2 [ label = "h2\n0|<l> l|<r> r" ];
- h3 [ label = "h3\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
h4 [ label = "h4\n0|<l> l|<r> r" ];
h5 [ label = "h5\n1|<l> l|<r> r" ];
h6 [ label = "h6\n1|<l> l|<r> r" ];
h3:l -> h5;
h3:l -> h2 [ style = invis ];
h3:r -> h6;
+ h6:r -> h3:r;
+
+ }
+
+
+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
+*basura* si se elimina alguna celda que apuntaba a ésta. Luego se procede
+a decrementar el contador de ``h2`` que queda en 0, transformándose en
+*basura* (ver figura :vref:`fig:gc-rc-up-1`). Lo mismo pasa cuando se
+desciende a ``h4``, pero al descender a ``h5`` y decrementar el contador,
+éste sigue siendo mayor que 0 (pues ``h3`` va a apuntar a ``h5``) así que
+permanece en el *live set*. Finalmente se termina de actualizar la
+referencia ``h3.l`` para que apunte a ``h5`` (ver figura
+:vref:`fig:gc-rc-up-2`).
+
+
+.. fig:: fig:gc-rc-cycle
+ :padding: 0.5
+
+ Eliminación de la referencia ``r1`` :math:`\to` ``h3`` (pérdida de
+ memoria debido a un ciclo).
+
+ .. subfig::
+
+ El ejecutarse ``update(r1, null)`` se visita la celda ``h3``.
+
+ .. digraph:: g4_6
+
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ edge [ color = gray40 ];
+ node [
+ shape = record,
+ width = 0,
+ height = 0,
+ style = filled,
+ fillcolor = gray25,
+ fontcolor = white
+ ];
+
+ subgraph cluster_all {
+
+ root [
+ label = "root\nset|<r0> r0|<r1> r1\n*",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1; h2; h4;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n0|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n0|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ root:r1 -> h3 [ style = bold, color = black ];
+ h2:l -> h4 [ style = invis ];
+ h2:r -> h5 [ style = invis ];
+ h3:l -> h5;
+ h3:l -> h2 [ style = invis ];
+ h3:r -> h6;
+ h6:r -> h3:r;
}
+ .. subfig::
+
+ Se decrementa el contador de ``h3`` pero sigue siendo mayor que 0 por
+ el ciclo.
+
+ .. digraph:: g5_2
+
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ edge [ color = gray40 ];
+ node [
+ shape = record,
+ width = 0,
+ height = 0,
+ style = filled,
+ fillcolor = gray25,
+ fontcolor = white
+ ];
+
+ subgraph cluster_all {
+
+ root [
+ label = "root\nset|<r0> r0|<r1> r1\n*",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1; h2; h4;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n0|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l|<r> r" ];
+ h4 [ label = "h4\n0|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ root:r1 -> h3 [ style = invis ];
+ h2:l -> h4 [ style = invis ];
+ h2:r -> h5 [ style = invis ];
+ h3:l -> h5;
+ h3:l -> h2 [ style = invis ];
+ h3:r -> h6;
+ h6:r -> h3:r;
+
+ }
+
+
+Finalmente se presenta lo que sucede cuando se elimina la última referencia
+a un ciclo (en este caso un ciclo simple de 2 celdas: ``h3`` y ``h6``). Se
+elimina la única referencia externa al ciclo (``r1``), por lo que se visita
+la celda ``h3`` decrementando su contador de referencias, pero éste
+continúa siendo mayor que 0 porque la celda ``h6`` (parte del ciclo) la
+referencia. Por lo tanto el ciclo, y todas las celdas a las que apunta que
+no tienen otras referencias externas y por lo tanto deberían ser *basura*
+también (``h5``), no pueden ser recicladas y su memoria es perdida (ver
+figura :vref:`fig:gc-rc-cycle`).
+
+
+
+.. _ref_gc_mark_sweep:
Marcado y barrido
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+.. _ref_gc_art:
-TODO
+Estado del arte
+----------------------------------------------------------------------------
+.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
+ ejemplos.
+TODO
Clasificación
-----------------------------------------------------------------------------
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
La cantidad de clasificaciones que pueden hacerse respecto a algoritmos de
recolección de basura son muy grandes. Muchas de estas clasificaciones se
.. _ref_gc_direct:
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
.. _ref_gc_inc:
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
.. _ref_gc_concurrent:
Concurrente / *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
consume el recolector, debido a la necesidad de re-escanear sub-grafos que
han sido modificados.
-.. _ref_gc_art:
-
-Estado del arte
-----------------------------------------------------------------------------
-
-.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
- ejemplos.
-
-TODO
Cloning
.. include:: links.rst
-.. vim: set ts=3 sts=3 sw=3 et tw=75 :
+.. vim: set ts=3 sts=3 sw=3 et tw=78 :
projects / z.facultad / 75.00 / informe.git / blobdiff