============================================================================
+.. _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
-.. _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
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;
}
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;
}
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;
}
: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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
projects / z.facultad / 75.00 / informe.git / blobdiff