Utilizar foreach en vez de for en pseudo-código

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

diff --git a/source/gc.rst b/source/gc.rst
index 661a578fa41c3d73e5c9f33c9a11768c798ce8ab..96da51bc7cba15b9c756bfcb71680884804a9e41 100644 (file)
--- a/source/gc.rst
+++ b/source/gc.rst
@@ -10,6 +10,8 @@ Recolección de basura
 ============================================================================
 
 
 ============================================================================
 
 

+.. _ref_gc_intro:
+

 Introducción
 ----------------------------------------------------------------------------
 
 Introducción
 ----------------------------------------------------------------------------
 


@@ -17,6 +19,13 @@ 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).
 
 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
 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


@@ -32,6 +41,21 @@ recolector de basura. Por ejemplo, los errores en el manejo de memoria
 (como *buffer overflows* [#gcbuff]_ o *dangling pointers* [#gcdang]_) son
 la causa más frecuente de problemas de seguridad [BEZO06]_.
 
 (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
 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


@@ -64,26 +88,6 @@ puntos de falla no controlados por el programador, volviendo mucho más
 difícil la búsqueda de errores.
 
 
 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
 
 
 Conceptos básicos


@@ -121,6 +125,13 @@ Registros:
    celda [#gccelda]_ alocada antes que otra nunca puede ser liberada antes
    que aquella.
 
    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
 *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


@@ -173,14 +184,8 @@ programa en sí son los cambios al grafo de conectividad de las celdas,
 normalmente se lo llama *mutator* (mutador).
 
 
 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
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Recorrido del grafo de conectividad
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


@@ -317,20 +322,33 @@ convenir uno u otro método para lograr una mejor localidad de referencia
 y de esta manera tener un mejor comportamiento de la memoria virtual o del
 *caché*.
 
 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]_::
 
 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)
 
       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)
 
          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
 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


@@ -339,7 +357,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).
 


@@ -567,21 +585,8 @@ 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
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Abstracción tricolor
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


@@ -610,8 +615,8 @@ que todas las celdas parten pintadas de blanco, es decir, el conjunto
 blanco contiene todas las celdas de memoria y los conjuntos negro y gris
 están vacíos)::
 
 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()
          gray_set.add(r)
       while not gray_set.empty()
          v = gray_set.pop()


@@ -626,7 +631,7 @@ por sí ya presenta una ventaja sobre el marcado *bicolor*.
 
 
 
 
 
 

-.. _ref_gc_services:
+.. _ref_gc_intro_services:

 
 Servicios
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 Servicios
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


@@ -635,6 +640,18 @@ En general todos los algoritmos de recolección de basura utilizan servicios
 de una capa inferior [#gclowlayer]_ y proveen servicios a una capa superior
 [#gchilayer]_.
 
 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.
 
 A continuación se presentan las primitivas en común que utilizan todos los
 recolectores a lo largo de este documento.
 


@@ -697,20 +714,9 @@ recolector, aunque en ciertas circunstancias pueden ser utilizados por el
 usuario también.
 
 
 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
 ----------------------------------------------------------------------------
 
 Algoritmos clásicos
 ----------------------------------------------------------------------------


@@ -780,31 +786,63 @@ teóricamente la complejidad de eliminar una referencia puede ser
 Las primitivas implementadas para este tipo de recolector son las
 siguientes (acompañadas de una implementación básica)::
 
 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
 
       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
       cell.rc = cell.rc - 1
       if cell.rc is 0

-         for child* in cell.children
+         foreach child* in cell.children

             del(*child)
          free(cell)
 
             del(*child)
          free(cell)
 

-   update(ref*, cell)
+   function update(ref*, cell) is

       cell.rc = cell.rc + 1
       del(*ref)
       *ref = cell
 
 
       cell.rc = cell.rc + 1
       del(*ref)
       *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


@@ -819,12 +857,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
 


@@ -860,7 +892,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" ];


@@ -873,6 +905,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;

 
          }
 
 
          }
 


@@ -907,7 +940,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" ];


@@ -920,6 +953,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;

 
          }
 
 
          }
 


@@ -959,7 +993,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" ];


@@ -972,11 +1006,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).
 


@@ -1016,7 +1052,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" ];


@@ -1029,6 +1065,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;

 
          }
 
 
          }
 


@@ -1067,7 +1104,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" ];


@@ -1080,20 +1117,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


@@ -1136,7 +1169,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" ];


@@ -1150,6 +1183,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;

 
          }
 
 
          }
 


@@ -1188,7 +1222,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" ];


@@ -1202,6 +1236,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;

 
          }
 
 
          }
 


@@ -1241,7 +1276,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" ];


@@ -1255,6 +1290,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;

 
          }
 
 
          }
 


@@ -1300,7 +1336,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" ];


@@ -1314,6 +1350,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;

 
          }
 
 
          }
 


@@ -1352,7 +1389,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" ];


@@ -1366,6 +1403,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;

 
          }
 
 
          }
 


@@ -1406,7 +1444,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" ];


@@ -1420,9 +1458,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`).
+
+
+
+.. _ref_gc_mark_sweep:

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


@@ -1438,13 +1620,18 @@ TODO
 
 
 
 
 
 

+.. _ref_gc_art:

 
 

-TODO
+Estado del arte
+----------------------------------------------------------------------------

 
 

+.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
+   ejemplos.

 
 

+TODO

 
 Clasificación
 
 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
 
 La cantidad de clasificaciones que pueden hacerse respecto a algoritmos de
 recolección de basura son muy grandes. Muchas de estas clasificaciones se


@@ -1458,7 +1645,7 @@ pudieron observar en la investigación sobre el `estado del arte`_.
 .. _ref_gc_direct:
 
 Directa / indirecta
 .. _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
 
 Generalmente se llama recolección **directa** a aquella en la cual el
 compilador o lenguaje instrumenta al *mutator* de forma tal que la


@@ -1488,7 +1675,7 @@ Estas son las dos grandes familias de recolectores, también conocidos como
 .. _ref_gc_inc:
 
 Incremental
 .. _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
 
 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


@@ -1516,7 +1703,7 @@ incremental, aunque el tiempo de pausa de una recolección sea menor.
 .. _ref_gc_concurrent:
 
 Concurrente / *stop-the-world*
 .. _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
 
 Los recolectores concurrentes son aquellos que pueden correr en paralelo
 con el *mutator*. Por el contrario, aquellos que pausan el *mutator* para


@@ -1534,15 +1721,6 @@ Esto también trae como consecuencia el incremento en el tiempo total que
 consume el recolector, debido a la necesidad de re-escanear sub-grafos que
 han sido modificados.
 
 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
 
 
 Cloning
 


@@ -1600,4 +1778,4 @@ http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html
 
 .. include:: links.rst
 
 
 .. 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 :