Mover definición de notas al pie más cerca de la referencia

[z.facultad/75.00/informe.git] / source / gc.rst

diff --git a/source/gc.rst b/source/gc.rst
index bf22c924f59d10aabeb2fd6737d7cf517766160e..4f9f91a82bab24e1629a535638e1ca2d05b24221 100644 (file)
--- a/source/gc.rst
+++ b/source/gc.rst
@@ -354,7 +354,7 @@ celda sin marcar es de color blanco y una marcada de color negro.
 
 Puede observarse un ejemplo del algoritmo en la figura
 :vref:`fig:gc-mark-1`, en la cual se marca el sub-grafo apuntando por
 
 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).
 
 :vref:`fig:gc-mark-2`), concluyendo con el marcado del grafo completo,
 dejando sin marcar solamente las celdas *basura* (en blanco).
 


@@ -803,11 +803,43 @@ siguientes (acompañadas de una implementación básica)::
       *ref = cell
 
 
       *ref = cell
 
 

+

 .. _ref_gc_rc_cycles:
 
 Ciclos
 ^^^^^^
 
 .. _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
 .. _ref_gc_rc_example:
 
 Ejemplo


@@ -822,12 +854,6 @@ o cambiar una referencia (cambios en la conectividad del grafo). En un
 comienzo todas las celdas son accesibles desde el *root set* por lo tanto
 son todas parte del *live set*.
 
 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
 
 
 .. fig:: fig:gc-rc-rm-1
 


@@ -863,7 +889,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
             h1 [ label = "h1\n1|<l> l|<r> r" ];
             h2 [ label = "h2\n2|<l> l|<r> 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" ];
             h4 [ label = "h4\n1|<l> l|<r> r" ];
             h5 [ label = "h5\n1|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -876,6 +902,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
          }
 


@@ -910,7 +937,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
             h1 [ label = "h1\n1|<l> l|<r> r" ];
             h2 [ label = "h2\n2|<l> l|<r> 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" ];
             h4 [ label = "h4\n1|<l> l|<r> r" ];
             h5 [ label = "h5\n1|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -923,6 +950,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
          }
 


@@ -962,7 +990,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n2|<l> l|<r> 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" ];
             h4 [ label = "h4\n1|<l> l|<r> r" ];
             h5 [ label = "h5\n1|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -975,11 +1003,13 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
 .. fig:: fig:gc-rc-rm-2
 
          }
 
 
 .. fig:: fig:gc-rc-rm-2

+   :padding: 0.5

 
    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
 
 
    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
 


@@ -1019,7 +1049,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n1|<l> l|<r> 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" ];
             h4 [ label = "h4\n1|<l> l|<r> r" ];
             h5 [ label = "h5\n1|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -1032,6 +1062,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
          }
 


@@ -1070,7 +1101,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n1|<l> l|<r> 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" ];
             h4 [ label = "h4\n1|<l> l|<r> r" ];
             h5 [ label = "h5\n1|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -1083,20 +1114,16 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
             h2:r -> h5;
             h3:l -> h2;
             h3:r -> h6;
             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
 
 
 .. fig:: fig:gc-rc-up-1


@@ -1139,7 +1166,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
 
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n1|<l> l|<r> 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" ];
             h4 [ label = "h4\n1|<l> l|<r> r" ];
             h5 [ label = "h5\n2|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -1153,6 +1180,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
             h3:l -> h2;
             h3:l -> h5 [ style = dotted, color = black ];
             h3:r -> h6;
             h3:l -> h2;
             h3:l -> h5 [ style = dotted, color = black ];
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
          }
 


@@ -1191,7 +1219,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
 
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n1|<l> l|<r> 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" ];
             h4 [ label = "h4\n1|<l> l|<r> r" ];
             h5 [ label = "h5\n2|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -1205,6 +1233,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
             h3:l -> h2 [ style = bold, color = black ];
             h3:l -> h5 [ style = dotted, color = black ];
             h3:r -> h6;
             h3:l -> h2 [ style = bold, color = black ];
             h3:l -> h5 [ style = dotted, color = black ];
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
          }
 


@@ -1244,7 +1273,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
 
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n1|<l> l|<r> 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" ];
             h4 [ label = "h4\n1|<l> l|<r> r" ];
             h5 [ label = "h5\n2|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -1258,6 +1287,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
             h3:l -> h2 [ style = invis ];
             h3:l -> h5 [ style = dotted, color = black ];
             h3:r -> h6;
             h3:l -> h2 [ style = invis ];
             h3:l -> h5 [ style = dotted, color = black ];
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
          }
 


@@ -1303,7 +1333,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
 
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n1|<l> l|<r> 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" ];
             h4 [ label = "h4\n0|<l> l|<r> r" ];
             h5 [ label = "h5\n2|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -1317,6 +1347,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
             h3:l -> h2 [ style = invis ];
             h3:l -> h5 [ style = dotted, color = black ];
             h3:r -> h6;
             h3:l -> h2 [ style = invis ];
             h3:l -> h5 [ style = dotted, color = black ];
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
          }
 


@@ -1355,7 +1386,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
 
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n1|<l> l|<r> 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" ];
             h4 [ label = "h4\n0|<l> l|<r> r" ];
             h5 [ label = "h5\n1|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -1369,6 +1400,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
             h3:l -> h5 [ style = bold, color = black ];
             h3:l -> h2 [ style = invis ];
             h3:r -> h6;
             h3:l -> h5 [ style = bold, color = black ];
             h3:l -> h2 [ style = invis ];
             h3:r -> h6;

+            h6:r -> h3:r;

 
          }
 
 
          }
 


@@ -1409,7 +1441,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h1 [ label = "h1\n0|<l> l|<r> r" ];
             h2 [ label = "h2\n0|<l> l|<r> 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" ];
             h4 [ label = "h4\n0|<l> l|<r> r" ];
             h5 [ label = "h5\n1|<l> l|<r> r" ];
             h6 [ label = "h6\n1|<l> l|<r> r" ];


@@ -1423,10 +1455,153 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
             h3:l -> h5;
             h3:l -> h2 [ style = invis ];
             h3:r -> h6;
             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`).
+
+
+
+

 Marcado y barrido
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Marcado y barrido
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~