============================================================================
+.. _ref_gc_intro:
+
Introducción
----------------------------------------------------------------------------
+.. _ref_gc_intro_mark:
Recorrido del grafo de conectividad
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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
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).
-.. _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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-.. _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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. 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