X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/b0956c037ae52da777b06705157486067755ec2c..9d97e3ff2b7234037d4e78de0cb126a5ede881ed:/source/gc.rst

diff --git a/source/gc.rst b/source/gc.rst
index 00cee40..0b91155 100644
--- a/source/gc.rst
+++ b/source/gc.rst
@@ -4,51 +4,89 @@
    un breve recorrido sobre el estado del arte.
    ESTADO: SIN EMPEZAR
 
-
 .. _ref_gc:
 
 Recolección de basura
 ============================================================================
 
-TODO
 
-.. Breve descripción de la utilidad de la recolección de basura
-   ESTADO: TERMINADO
-
-La recolección de basura es muchas veces vista por sus críticos de
-una forma bastante *naïve*. Muchas veces se argumenta que sólo es
-útil para programadores descuidados o que su necesidad es sólo una
-manifestación de un mal diseño. Si bien estas dos afirmaciones pueden
-ser, en algunos casos, ciertas, es falaz pensar que ese es la única
-ventaja de un recolector de basura. Uno de los aspectos más importantes
-de un recolector de basura es lograr un mayor nivel de abstracción
-[JOLI96]_. En particular, al diseñar o programar bibliotecas, de no
-haber un recolector de basura, **la administración de memoria pasa a ser
-parte de la interfaz de la biblioteca**. Y lo peor de este aspecto es
-que muy pocas veces esto es tenido en cuenta, derivando en bibliotecas
-muy difíciles de usar correctamente sin perder memoria, por no quedar
-bien clara la responsabilidad del manejo de memoria.
-
-Esto se debe a que, como se mencionó anteriormente, el manejo de memoria
-es un *artefacto* proveniente del *hardware*, no un concepto propio
-de los algoritmos a representar y como tal, nos impide desarrollar una
-mayor abstracción.
-
-Muchas veces se aduce también que la recolección de basura impide
-el desarrollo de programas eficientes. Si bien es innegable que la
-recolección de basura impone una carga extra, ésta es, en la mayoría
-de los casos, imperceptible. Incluso algunos algoritmos de recolección
-de basura pueden aumentar la eficiencia en casos determinados, como los
-recolectores que compactan, que pueden minimizar considerablemente la
-cantidad de páginas de memoria referenciadas por el programa, mejorando
-el *hit-ratio* tanto de la memoria virtual como del *cache*.  Aún si
-este no fuera el caso, o en casos de sistemas de tiempo real o zonas muy
-críticas en cuanto a la eficiencia, muchas veces es posible suspender
-el recolector de basura en dicho fragmento de código. Es cierto que esto
-rompe un poco con la idea de ganar abstracción, pero es necesario sólo
-en casos donde hay que realizar optimizaciones y las optimizaciones son,
-en general, dependientes de la plataforma (*hardware*) y por lo tanto
-de difícil abstracción.
+.. _ref_gc_intro:
+
+Introducción
+----------------------------------------------------------------------------
+
+*Recolección de basura* se refiere a la recuperación automática de memoria
+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
+abstracción y modularidad, dos conceptos claves en la ingeniería de
+software [JOLI96]_. En particular, al diseñar o programar bibliotecas, de
+no haber un recolector de basura, **la administración de memoria pasa a ser
+parte de la interfaz**, lo que produce que los módulos tengan un mayor
+grado de acoplamiento.
+
+Además hay una incontable cantidad de problemas asociados al manejo
+explícito de memoria que simplemente dejan de existir al utilizar un
+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]_.
+
+.. [#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
+programación, de alto o bajo nivel, aunque sea de forma opcional. En los
+últimos 10 años tuvo un gran avance, por la adopción en lenguajes de
+desarrollo rápido utilizados mucho en el sector empresarial, en especial
+Java_, que fue una plataforma de facto para la investigación y desarrollo
+de recolectores de basura (aunque no se limitaron a este lenguaje las
+investigaciones).
+
+En las primeras implementaciones de recolectores de basura la penalización
+en la eficiencia del programa se volvía prohibitiva para muchas
+aplicaciones. Es por esto que hubo bastante resistencia a la utilización de
+recolectores de basura, pero el avance en la investigación fue haciendo que
+cada vez sea una alternativa más viable al manejo manual de memoria,
+incluso para apliaciones con altos requerimientos de eficiencia. En la
+actualidad un programa que utiliza un recolector moderno puede ser
+comparable en eficiencia con uno que utiliza un esquema manual. En
+particular, si el programa fue diseñado con el recolector de basura en
+mente en ciertas circunstancias puede ser incluso más eficiente que uno que
+hace manejo explícito de la memoria. Muchos recolectores mejoran la
+localidad de referencia [#gcreflocal]_, haciendo que el programa tenga un
+mejor comportamiento con el caché y la memoria virtual.
+
+.. [#gcreflocal] Localidad de referencia es la medida en que los accesos
+   sucesivos de memoria cercana espacialmente son cercanos también en el
+   tiempo. Por ejemplo, un programa que lee todos los elementos de una matriz
+   contigua de una vez o que utiliza la misma variable repetidamente tiene
+   buena localidad referencia. Una buena localidad de referencia interactúa
+   bien con la memoria virtual y caché, ya que reduce el conjunto de trabajo
+   (o *working set*) y mejora la probabildad de éxito (*hit rate*).
 
 El recolector de basura debe tener un comportamiento correcto y predecible
 para que sea útil, si el programador no puede confiar en el recolector
@@ -57,82 +95,1977 @@ introduce nuevos puntos de falla en los programas, y lo que es peor,
 puntos de falla no controlados por el programador, volviendo mucho más
 difícil la búsqueda de errores.
 
-.. Presenta el problema y temas a ser tratados en el trabajo.
-   ESTADO: TERMINADO
-
-Los lenguajes de programación modernos tienen una tendencia cada vez
-más marcada a adoptar técnicas sofisticadas, haciéndolos más ricos y
-convirtiéndolos realmente en lenguajes, no en meros preprocesadores que
-convierten de una forma muy directa el código en *assembly*, permitiendo
-construcciones semánticamente más ricas y permitiendo al programar una
-mayor expresividad para plasmar algoritmos sin detenerse en los detalles
-del *hardware*.
-
-Estos conceptos supuestamente avanzados provienen, en general, de
-lenguajes académicos (muchos de ellos funcionales) que implementan estas
-funcionalidades hace mucho tiempo, pero que para su época, o bien no
-tuvieron suficiente difusión en el ambiente comercial, o bien eran muy
-lentos por la baja capacidad de procesamiento de la época o incluso
-demasiado *revolucionarios* para ser adoptados por programadores que no
-podían ver las ventajas que esos nuevos conceptos proveen.
-
-El caso de la recolección de basura (*garbage collection* en inglés)
-es uno de los más representativos. Lisp_ introdujo a principio de los
-'60 este concepto, como un mecanismo para alocar y liberar recursos
-(en general memoria alocada en el *heap*) de forma automática. Pero
-no fue hasta avanzados los '90 que esta técnica se empezó a utilizar
-en lenguajes de programación de uso comercial, cuando fue popularizado
-por Java_. Incluso luego de más de 30 años para Java_ era costosa la
-recolección de basura, lo que sumado a la presencia de una máquina
-virtual para ejecutar los programas producidos, condujo a que estos
-lenguajes sean notablemente lentos. Aún así Java_ creció y entre las
-mejoras introducidas hubieron mejoras en la recolección de basura. Otros
-lenguaje de programación populares que utilizan alguna forma de
-recolección de basura son Python_, Ruby_, PHP_ y `C#`_, entre otros.
 
 
 
-Introducción
-----------------------------------------------------------------------------
+Conceptos básicos
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-TODO
+Los programas pueden hacer uso principalmente de 4 áreas de memoria:
+
+Registros:
+   Se trata de la memoria más básica de una computadora. Es el área de
+   memoria en la que puede operar realmente el procesador, es extremadamente
+   escasa y generalmente su uso es administrado por el lenguaje de
+   programación (o compilador más específicamente). Excepto en situaciones
+   muy particulares, realizando tareas de muy bajo nivel, un programador
+   nunca manipula los registros explícitamente.
+
+Área de memoria estática:
+   Es la forma de memoria más simple que un programador utiliza
+   explícitamente. En general las variables globales se almacenan en este
+   área, que es parte inherente del programa y está disponible durante toda
+   su ejecución, por lo tanto nunca cambia su capacidad en tiempo de
+   ejecución. Es la forma más básica de administrar memoria, pero tiene una
+   limitación fundamental: **el tamaño de la memoria tiene que ser conocido
+   en tiempo de compilación**. Los primeros lenguajes de programación solo
+   contaban con este tipo de memoria (además de los registros del
+   procesador).
+
+*Stack* (pila):
+   Los primeros lenguajes de programación que hicieron uso de una pila
+   aparecieron en el año 1958 (Algol-58 y Atlas Autocode) y fueron los
+   primeros en introducir estructura de bloques, almacenando las
+   variables locales a estos bloques utilizando una pila [JOLI96]_.
+   Esto permite utilizar recursividad y tener un esquema simple de memoria
+   dinámica. Sin embargo este esquema es muy limitado porque el orden de
+   reserva y liberación de memoria tiene que estar bien establecido. Una
+   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
+   memoria más flexible y por lo tanto el más complejo de administrar; razón
+   por la cual existen los recolectores de basura.
+
+La recolección de basura impone algunas restricciones sobre la manera de
+utilizar el *heap*. Debido a que un recolector de basura debe ser capaz de
+determinar el grafo de conectividad de la memoria en uso, es necesario que
+el programa siempre tenga alguna referencia a las celdas activas en los
+registros, memoria estática o *stack* (normalmente denominado *root set*).
+
+Esto implica que una celda sea considerada basura si y sólo si no puede ser
+alcanzada a través del grafo de conectividad que se comienza a recorrer
+desde el *root set*. Por lo tanto, una celda está *viva* si y sólo si su
+dirección de memoria está almacenada en una celda *raíz* (parte del *root
+set*) o si está almacenada en otra celda *viva* del *heap*.
+
+Expresado más formalmente, dada la relación :math:`M \to N`, donde
+:math:`M` es una celda del *heap* o parte del *root set* y :math:`N` es una
+celda del *heap*, definida como:
+
+.. math::
+
+   M \to N \Longleftrightarrow M \text{ almacena un puntero a } N
+
+El conjunto de celdas vivas (o *live set*) queda determinado por:
+
+.. math::
+
+   vivas = \left\lbrace N \in Celdas \big/
+      ( \exists r \in Raices / r \to N ) \vee (\exists M \in vivas / M \to N )
+   \right\rbrace
+
+Cabe aclarar que esta es una definición conceptual, asumiendo que el
+programa siempre limpia una dirección de memoria almacenada en el *root
+set* o una celda del *heap* cuando la celda a la que apunta no va a ser
+utilizada nuevamente. Esto no es siempre cierto y los falsos positivos que
+esto produce se conoce como un tipo de pérdida de memoria (que es posible
+incluso al utilizar un recolector de basura) llamada pérdida de memoria
+*lógica*. Esto puede no ser evitable (incluso cuando el programador no
+cometa errores) en lenguajes de programación que requieran un recolector de
+basura conservativo.
+
+Por último, siendo que el recolector de basura es parte del programa de
+forma indirecta, es común ver en la literatura que se direfencia entre
+2 partes del programa, el recolector de basura y el programa en sí. Dado
+que para el recolector de basura, lo único que interesa conocer del
+programa en sí son los cambios al grafo de conectividad de las celdas,
+normalmente se lo llama *mutator* (mutador).
+
+
+
+.. _ref_gc_intro_mark:
+
+Recorrido del grafo de conectividad
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+El problema de encontrar las celdas *vivas* de un programa se reduce a recorrer
+un grafo dirigido. El grafo se define como:
+
+.. math::
+
+   G = (V,A)
+
+Donde :math:`V` es el conjunto de vértices, dado por las celdas de memoria
+y :math:`A` es un conjunto de pares ordenados (aristas), dado por la
+relación :math:`M \rightarrow N` (es decir, los punteros).
+
+El grafo comienza a recorrerse desde el *root set* y todos los vértices que
+fueron visitados componen el *live set*; el resto de los vértices son
+*basura*.
+
+Más formalmente, Definimos:
+
+*Camino*:
+   secuencia de vértices tal que cada uno de los vértices tiene una arista
+   al próximo vértice en la secuencia. Todo camino finito tiene un *vértice
+   inicial* y un *vértice final* (llamados en conjunto *vértices
+   terminales*). Cualquier vértice no terminal es denominado *vértice
+   interior*.
+
+   .. math::
+
+      \underset{v_1 \rightarrow v_N}{C} = \left\lbrace
+         v_1, \dotsc, v_N \in V \big/ \underset{i \in [1,N-1]}{\forall v_i}
+            \exists (v_i \to v_{i+1}) \in A
+      \right\rbrace
+
+*Conexión*:
+   decimos que :math:`M` está *conectado* a :math:`N` si y sólo si existe un
+   camino de :math:`M` a :math:`N`.
+
+   .. math::
+
+      M \mapsto N \Longleftrightarrow \exists \underset{M \to N}{C} \in G
+
+*Live set*:
+   el conjunto de celdas *vivas* está dado por todos los vértices
+   (:math:`v`) del grafo para los cuales existe una raíz en el *root set*
+   que esté conectada a él.
+
+   .. math::
+
+      Live \thickspace set = \left\lbrace v \in V \big/
+         \left( \exists r \in Root \thickspace set \big/ r \mapsto v \right)
+      \right\rbrace
+
+*Basura*:
+   la basura, o celdas *muertas*, quedan determinadas entonces por todas las
+   celdas del *heap* que no son parte del *live set*.
+
+   .. math::
+
+      Basura = V - Live \thickspace set
+
+Esto es, efectivamente, una partición del *heap* (ver figura
+:vref:`fig:gc-heap-parts`).
+
+
+.. fig:: fig:gc-heap-parts
+
+   Distintas partes de la memoria, incluyendo relación entre *basura*,
+   *live set*, *heap* y *root set*.
+
+   .. digraph:: g1
+
+      margin  = 0;
+      ratio   = fill;
+      size    = "4.6,3.6";
+      node [ shape = record, width = 0, height = 0 ];
+
+      subgraph cluster_heap {
+         label = "Heap";
+         style     = dashed;
+         color     = gray40;
+         fontcolor = gray40;
+
+         subgraph cluster_live {
+            label     = "Live set";
+            style     = dashed;
+            color     = gray40;
+            fontcolor = gray40;
+            node [
+               style     = filled,
+               fillcolor = gray25,
+               fontcolor = white,
+            ];
+            h1; h2; h4; h5; h6;
+         }
+
+         subgraph cluster_garbage {
+            label     = "Basura";
+            style     = dashed;
+            color     = gray40;
+            fontcolor = gray40;
+            node [ style = filled, fillcolor = white ];
+            h7; h3;
+         }
+      }
+
+      subgraph cluster_root {
+         label     = "Root set";
+         style     = dashed;
+         color     = gray40;
+         fontcolor = gray40;
+         node [ style = filled, fillcolor = gray96 ];
+         r0; r1; r2;
+      }
+
+      r0 -> h1 -> h2 -> h5;
+      r1 -> h5 -> h6 -> h1;
+      r2 -> h4;
+      h5 -> h4;
+      h7 -> h1;
+      h7 -> h3;
+
+
+Al proceso de visitar los vértices *conectados* desde el *root set* se lo
+denomina *marcado*, *fase de marcado* o *mark phase* en inglés, debido
+a que es necesario marcar los vértices para evitar visitar 2 veces el mismo
+nodo en casos de que el grafo contenga ciclos [#gccycle]_. De forma similar
+a la búsqueda, que puede realizarse *primero a lo ancho* (*breadth-first*)
+o *primero a lo alto* (*depth-first*) del grafo, el marcado de un grafo
+también puede realizarse de ambas maneras. Cada una podrá o no tener
+efectos en la eficiencia, en particular dependiendo de la aplicación puede
+convenir uno u otro método para lograr una mejor localidad de referencia.
+
+.. [#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]_::
+
+   function mark(v) is
+      if not v.marked
+         v.marked = true
+         for (src, dst) in v.edges
+            mark(dst)
+
+   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
+literatura se habla muchas veces de *colorear* las celdas. En general, una
+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
+``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).
+
+
+.. fig:: fig:gc-mark-1
+
+   Ejemplo de marcado del grafo de conectividad (parte 1).
+
+   .. subfig::
+
+      Se comienza a marcar el grafo por la raíz r0.
+
+      .. digraph:: g2_1
+
+         margin = 0;
+         ratio  = fill;
+         size   = "1.9,2.6";
+         node [ shape = record, width = 0, height = 0];
+         edge [ color = gray40 ];
+
+         subgraph cluster_all {
+
+            root [
+               label     = "root\nset|<r0> r0\n*|<r1> r1",
+               style     = filled,
+               fillcolor = gray96,
+            ];
+
+            subgraph marked {
+               node [ style = filled, fillcolor = gray25, fontcolor = white ];
+               h1;
+            };
+
+            root:r0 -> h1 [ style = bold, color = black ];
+            h1 -> h2 -> h5 -> h1;
+            root:r1 -> h6 -> h2;
+            h4 -> h3;
+            h3 -> h5;
+
+         }
+
+   .. subfig::
+
+      Luego de marcar el nodo ``h1``, se procede al ``h2``.
+
+      .. digraph:: g2_2
+
+         margin = 0;
+         ratio  = fill;
+         size   = "1.9,2.6";
+         node [ shape = record, width = 0, height = 0 ];
+         edge [ color = gray40 ];
+
+         subgraph cluster_all {
+
+            root [
+               label     = "root\nset|<r0> r0\n*|<r1> r1",
+               style     = filled,
+               fillcolor = gray96,
+            ];
+
+            subgraph marked {
+               node [ style = filled, fillcolor = gray25, fontcolor = white ];
+               h1; h2;
+            };
+
+            root:r0 -> h1 [ color = gray10 ];
+            h1 -> h2 [ style = bold, color = black ];
+            h2 -> h5 -> h1;
+            root:r1 -> h6 -> h2;
+            h4 -> h3;
+            h3 -> h5;
+
+         }
+
+   .. subfig::
+
+      Luego sigue el nodo h5.
+
+      .. digraph:: g2_3
+
+         margin = 0;
+         ratio  = fill;
+         size   = "1.9,2.6";
+         node [ shape = record, width = 0, height = 0 ];
+         edge [ color = gray40 ];
+
+         subgraph cluster_all {
+
+            root [
+               label     = "root\nset|<r0> r0\n*|<r1> r1",
+               style     = filled,
+               fillcolor = gray96,
+            ];
+
+            subgraph marked {
+               node [ style = filled, fillcolor = gray25, fontcolor = white ];
+               h1; h2; h5;
+            };
+
+            root:r0 -> h1 [ color = gray10 ];
+            h1 -> h2 [ color = gray10 ];
+            h2 -> h5 [ style = bold, color = black ];
+            h5 -> h1;
+            root:r1 -> h6 -> h2;
+            h4 -> h3;
+            h3 -> h5;
+
+         }
+
+
+.. fig:: fig:gc-mark-2
+
+   Ejemplo de marcado del grafo de conectividad (parte 2).
+
+   .. subfig::
+
+      El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo
+      tanto no se visita nuevamente.
 
+      .. digraph:: g2_4
 
+         margin = 0;
+         ratio  = fill;
+         size   = "1.9,2.6";
+         node [ shape = record, width = 0, height = 0 ];
+         edge [ color = gray40 ];
 
-Algoritmos principales
+         subgraph cluster_all {
+
+            root [
+               label     = "root\nset|<r0> r0\n*|<r1> r1",
+               style     = filled,
+               fillcolor = gray96,
+            ];
+
+            subgraph marked {
+               node [ style = filled, fillcolor = gray25, fontcolor = white ];
+               h1; h2; h5;
+            };
+
+            root:r0 -> h1 [ color = gray10 ];
+            h1 -> h2 [ color = gray10 ];
+            h2 -> h5 [ color = gray10 ];
+            h5 -> h1 [ style = bold, color = black ];
+            root:r1 -> h6 -> h2;
+            h4 -> h3;
+            h3 -> h5;
+
+         }
+
+   .. subfig::
+
+      Se concluye el marcado del sub-grafo al que conecta r0, se procede
+      a marcar el sub-grafo al que conecta r1, marcando al nodo h6.
+
+      .. digraph:: g2_5
+
+         margin = 0;
+         ratio  = fill;
+         size   = "1.9,2.6";
+         node [ shape = record, width = 0, height = 0 ];
+         edge [ color = gray40 ];
+
+         subgraph cluster_all {
+
+           root [
+              label     = "root\nset|<r0> r0|<r1> r1\n*",
+              style     = filled,
+              fillcolor = gray96,
+           ];
+
+           subgraph marked {
+              node [ style = filled, fillcolor = gray25, fontcolor = white ];
+              h1; h2; h5; h6;
+           };
+
+           root:r0 -> h1 [ color = gray10 ];
+           h1 -> h2 [ color = gray10 ];
+           h2 -> h5 [ color = gray10 ];
+           h5 -> h1 [ color = gray10 ];
+           root:r1 -> h6 [ style = bold, color = black ];
+           h6 -> h2;
+           h4 -> h3;
+           h3 -> h5;
+
+         }
+
+   .. subfig::
+
+      El nodo h6 tiene una arista al h2, pero éste ya fue marcado por lo
+      que no se vuelve a visitar. No hay más raíces, se finaliza el marcado
+      del grafo.
+
+      .. digraph:: g2_6
+
+         margin = 0;
+         ratio  = fill;
+         size   = "1.9,2.6";
+         node [ shape = record, width = 0, height = 0 ];
+         edge [ color = gray40 ];
+
+         subgraph cluster_all {
+
+            root [
+               label     = "root\nset|<r0> r0|<r1> r1\n*",
+               style     = filled,
+               fillcolor = gray96,
+            ];
+
+            subgraph marked {
+               node [ style = filled, fillcolor = gray25, fontcolor = white ];
+               h1; h2; h5; h6;
+            };
+
+            root:r0 -> h1 [ color = gray10 ];
+            h1 -> h2 [ color = gray10 ];
+            h2 -> h5 [ color = gray10 ];
+            h5 -> h1 [ color = gray10 ];
+            root:r1 -> h6 [ color = gray10 ];
+            h6 -> h2 [ style = bold, color = black ];
+            h4 -> h3;
+            h3 -> h5;
+
+         }
+
+
+
+.. _ref_gc_intro_tricolor:
+
+Abstracción tricolor
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Muchos algoritmos utilizan tres colores para realizar el marcado. El tercer
+color, gris generalmente, indica que una celda debe ser visitada. Esto
+permite algoritmos :ref:`concurrentes <ref_gc_concurrent>`
+e :ref:`incrementales <ref_gc_inc>`, además de otro tipo de optimizaciones.
+Entonces, lo que plantea esta abtracción es una nueva partición del heap al
+momento de marcar, esta vez son 3 porciones: blanca, gris y negra.
+
+Al principio todas las celdas se pintan de blanco, excepto el *root set*
+que se punta de gris. Luego se van obteniendo celdas del conjunto de las
+grises y se las pinta de negro, pintando sus hijas directas de gris.
+
+Una vez que no hay más celdas grises, tenemos la garantía de que las celdas
+negras serán el *live set* y las celdas blancas *basura*. Esto se debe
+a que siempre se mantiene esta invariante: **ninguna celda negra apunta
+directamente a una celda blanca**. Las celdas blancas siempre son apuntadas
+por celdas blancas o grises. Entonces, siempre que el conjunto de celdas
+grises sea vacío, no habrán celdas negras conectadas a blancas, siendo las
+celdas blancas *basura*.
+
+El algoritmo básico para marcar con tres colores es el siguiente (asumiendo
+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)::
+
+   function mark_phase() is
+      foreach r in root_set
+         gray_set.add(r)
+      while not gray_set.empty()
+         v = gray_set.pop()
+         black_set.add(v)
+         for (src, dst) in v.edges
+            if v in white_set
+               white_set.remove(v)
+               gray_set.add(v)
+
+Es simple notar que este algoritmo es naturalmente no recursivo, lo que de
+por sí ya presenta una ventaja sobre el marcado *bicolor*.
+
+
+
+.. _ref_gc_intro_services:
+
+Servicios
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+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]_.
+
+.. [#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.
+
+Servicios utilizados por el recolector son los siguientes:
+
+:math:`alloc() \to cell`:
+   obtiene una nueva celda de memoria. El mecanismo por el cual se obtiene
+   la celda es indistinto para esta sección, puede ser de una lista libre,
+   puede ser de un administrador de memoria de más bajo nivel provisto por
+   el sistema operativo o la biblioteca estándar de C (``malloc()``), etc.
+   Cómo organizar la memoria es un área de investigación completa y si bien
+   está estrechamente relacionada con la recolección de basura, en este
+   trabajo no se prestará particular atención a este aspecto (salvo casos
+   donde el recolector impone una cierta organización de memoria en el *low
+   level allocator*). Por simplicidad también asumiremos (a menos que se
+   indique lo contrario) que las celdas son de tamaño fijo. Esta restricción
+   normalmente puede ser fácilmente relajada (en los recolectores que la
+   tienen).
+
+:math:`free(cell)`:
+   libera una celda que ya no va a ser utilizada. La celda liberada debe
+   haber sido obtenida mediante ``alloc()``.
+
+Y los servicios básicos proporcionados por el recolector son los
+siguientes:
+
+:math:`new() \to cell`:
+   obtiene una celda de memoria para ser utilizada por el programa.
+
+:math:`update(ref, cell)`:
+   notifica al recolector que la referencia :math:`ref` ahora apunta
+   a :math:`cell`. Visto más formalmente, sería análogo a decir que hubo un
+   cambio en la conectividad del grafo: la arista :math:`src \to old` cambia
+   por :math:`src \to new` (donde :math:`src` es la celda que contiene la
+   referencia :math:`ref`, :math:`old` es la celda a la que apunta la
+   referencia :math:`ref` y :math:`new` es el argumento :math:`cell`). Si
+   :math:`cell` es ``null``, sería análogo a informar que se elimina la
+   arista :math:`src \to old`.
+
+:math:`del(cell)`:
+   este servicio, según el algoritmo, puede ser utilizado para informar un
+   cambio en la conectividad del grafo, la eliminación de una arista
+   (análogo a :math:`update(ref, null)` pero sin proporcionar información
+   sobre la arista a eliminar). Esto es generalmente útil solo en
+   :ref:`conteo de referencias <ref_gc_rc>`. Para otros recolectores puede
+   significar que el usuario asegura que no hay más referencias a esta
+   celda, es decir, análogo a eliminar el conjunto de aristas
+   :math:`\big\lbrace (v, w) \in A , v \in Live \thickspace set , w \in
+   Live \thickspace set \big/ w = cell`.
+
+:math:`collect()`:
+   indica al recolector que debe hacer un análisis del grafo de conectividad
+   en busca de *basura*. Generalmente este servicio es invocado por el
+   propio recolector cuando no hay más celdas reciclables.
+
+No todos los servicios son implementados por todos los recolectores, pero
+son lo suficientemente comunes como para describirlos de forma general en
+esta sección. Algunos son principalmente ideados para uso interno del
+recolector, aunque en ciertas circunstancias pueden ser utilizados por el
+usuario también.
+
+
+
+
+.. _ref_gc_classic:
+
+Algoritmos clásicos
 ----------------------------------------------------------------------------
 
-TODO
+En la literatura se encuentran normalmente referencias a 3 algoritmos
+clásicos, que son utilizados generalmente como bloques básicos para
+construir recolectores más complejos. Se presentan las versiones históricas
+más simples a fin de facilitar la comprensión conceptual.
+
 
 
+.. _ref_gc_rc:
 
 Conteo de referencias
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-TODO
+Se trata del algoritmo más antiguo de todos, implementado por primera vez
+por `John McCarthy`_ para Lisp_ a finales de 1950. Se trata de un método
+:ref:`directo <ref_gc_direct>` e :ref:`incremental <ref_gc_inc>` por
+naturaleza, ya que distribuye la carga de la recolección de basura durante
+toda la ejecución del programa, cada vez que el *mutator* cambia la
+conectividad de algún nodo del grafo de conectividad.
+
+El método consiste en tener un contador asociado a cada celda que contenga
+la cantidad de celdas **vivas** que apuntan a ésta. Es decir, es la
+cardinalidad del conjunto de aristas que tienen por destino a la celda.
+Formalmente podemos definir el contador :math:`rc(v)` (de *reference
+counter* en inglés) de la siguiente manera:
+
+.. math::
+
+   rc(v) = \big\lvert
+      \left\lbrace
+         (v_1, v_2) \in A \big/
+            v_1 \in Live \thickspace set \cup Root \thickspace set
+               \wedge v_2 = v
+      \right\rbrace
+   \big\rvert
+
+El *mutator* entonces debe actualizar este contador cada vez que el grafo
+de conectividad cambia, es decir, cada vez que se agrega, modifica
+o elimina una arista del grafo (o visto de una forma más cercana al código,
+cada vez que se agrega, modifica o elimina un puntero).
+
+Esta invariante es fundamental para el conteo de referencias, porque se
+asume que si el contador es 0 entonces el *mutator* no tiene ninguna
+referencia a la celda y por lo tanto es *basura*:
+
+.. math::
+
+   rc(v) = 0 \Rightarrow v \in Basura
+
+Para mantener esta invariante el *mutator*, cada vez que cambia un puntero
+debe decrementar en 1 el contador de la celda a la que apuntaba
+antiguamente  e incrementar en 1 el contador de la celda a la que apunta
+luego de la modificación. Esto asegura que la invariante se mantenga
+durante toda la ejecución del programa. Si al momento de decrementar un
+contador éste queda en 0, la celda asociada debe liberarse de forma de
+poder ser reciclada. Esto implica que si esta celda almacena punteros, los
+contadores de las celdas apuntadas deben ser decrementados también, porque
+solo deben almacenarse en el contador las aristas del *live set* para
+mantener la invariante. De esto puede resultar que otros contadores de
+referencia queden en 0 y más celdas sean liberadas. Por lo tanto,
+teóricamente la complejidad de eliminar una referencia puede ser
+:math:`O(\lvert Live \thickspace set \rvert)` en el peor caso.
+
+Las primitivas implementadas para este tipo de recolector son las
+siguientes (acompañadas de una implementación básica)::
+
+   function new() is
+      cell = alloc()
+      if cell is null
+         throw out_of_memory
+      cell.rc = 1
+      return cell
+
+   function del(cell) is
+      cell.rc = cell.rc - 1
+      if cell.rc is 0
+         foreach child* in cell.children
+            del(*child)
+         free(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
+^^^^^^^
+
+A continuación se presenta un ejemplo gráfico para facilitar la comprensión
+del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos
+punteros, ``left`` (``l``) y ``right`` (``r``) y se muestra el contador de
+referencias abajo del nombre de cada celda. Se parte con una pequeña
+estructura ya construída y se muestra como opera el algoritmo al eliminar
+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*.
+
+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-rm-1
+
+   Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
+
+   .. subfig::
+
+      Estado inicial del grafo de conectividad.
+
+      .. digraph:: g3_1
+
+         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",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            h1 [ label = "h1\n1|<l> l|<r> r" ];
+            h2 [ label = "h2\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" ];
+
+            root:r0 -> h1;
+            root:r1 -> h3;
+            h1:l -> h2;
+            h1:r -> h3;
+            h2:l -> h4;
+            h2:r -> h5;
+            h3:l -> h2;
+            h3:r -> h6;
+            h6:r -> h3:r;
+
+         }
+
+   .. subfig::
+
+      Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
+      ``h1``.
+
+      .. digraph:: g3_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\n*|<r1> r1",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            h1 [ label = "h1\n1|<l> l|<r> r" ];
+            h2 [ label = "h2\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" ];
+
+            root:r0 -> h1 [ style = bold, color = black ];
+            root:r1 -> h3;
+            h1:l -> h2;
+            h1:r -> h3;
+            h2:l -> h4;
+            h2:r -> h5;
+            h3:l -> h2;
+            h3:r -> h6;
+            h6:r -> h3:r;
+
+         }
+
+   .. subfig::
+
+      Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser
+      *basura*). Se elimina primero ``h1.l`` y luego ``h1.r``.
+
+      .. digraph:: g3_3
+
+         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\n*|<r1> r1",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
 
+            subgraph marked {
+               node [ fillcolor = white, fontcolor = black ];
+               h1;
+            };
 
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\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" ];
+
+            root:r0 -> h1 [ style = invis ];
+            root:r1 -> h3;
+            h1:l -> h2 [ style = bold, color = black ];
+            h1:r -> h3;
+            h2:l -> h4;
+            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).
+
+   .. subfig::
+
+      Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en
+      el *live set*).
+
+      .. digraph:: g3_4
+
+         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\n*|<r1> r1",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            subgraph marked {
+               node [ fillcolor = white, fontcolor = black ];
+               h1;
+            };
+
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<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" ];
+
+            root:r0 -> h1 [ style = invis ];
+            root:r1 -> h3;
+            h1:l -> h2 [ style = invis ];
+            h1:r -> h3 [ style = bold, color = black ];
+            h2:l -> h4;
+            h2:r -> h5;
+            h3:l -> h2;
+            h3:r -> h6;
+            h6:r -> h3:r;
+
+         }
+
+   .. subfig::
+
+      El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.
+
+      .. digraph:: g3_5
+
+         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",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            subgraph marked {
+               node [ fillcolor = white, fontcolor = black ];
+               h1;
+            };
+
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\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" ];
+
+            root:r0 -> h1 [ style = invis ];
+            root:r1 -> h3;
+            h1:l -> h2 [ style = invis ];
+            h1:r -> h3 [ style = invis ];
+            h2:l -> h4;
+            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* (ver figura :vref:`fig:gc-rc-up-1`).
+
+.. fig:: fig:gc-rc-up-1
+
+   Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
+   :math:`\to` ``h5`` (parte 1).
+
+   .. subfig::
+
+      Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.
+
+      .. digraph:: g4_1
+
+         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",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            subgraph marked {
+               node [ fillcolor = white, fontcolor = black ];
+               h1;
+            };
+
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<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" ];
+
+            root:r0 -> h1 [ style = invis ];
+            h1:l -> h2 [ style = invis ];
+            h1:r -> h3 [ style = invis ];
+            root:r1 -> h3;
+            h2:l -> h4;
+            h2:r -> h5;
+            h3:l -> h2;
+            h3:l -> h5 [ style = dotted, color = black ];
+            h3:r -> h6;
+            h6:r -> h3:r;
+
+         }
+
+   .. subfig::
+
+      Luego se procede a visitar las hijas de ``h3``, comenzando por ``h2``.
+
+      .. digraph:: g4_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",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            subgraph marked {
+               node [ fillcolor = white, fontcolor = black ];
+               h1;
+            };
+
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<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" ];
+
+            root:r0 -> h1 [ style = invis ];
+            h1:l -> h2 [ style = invis ];
+            h1:r -> h3 [ style = invis ];
+            root:r1 -> h3;
+            h2:l -> h4;
+            h2:r -> h5;
+            h3:l -> h2 [ style = bold, color = black ];
+            h3:l -> h5 [ style = dotted, color = black ];
+            h3:r -> h6;
+            h6:r -> h3:r;
+
+         }
+
+   .. subfig::
+
+      Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser
+      *basura*). Se eliminan las referencias a las hijas.
+
+      .. digraph:: g4_3
+
+         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",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            subgraph marked {
+               node [ fillcolor = white, fontcolor = black ];
+               h1; h2;
+            };
+
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<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" ];
+
+            root:r0 -> h1 [ style = invis ];
+            h1:l -> h2 [ style = invis ];
+            h1:r -> h3 [ style = invis ];
+            root:r1 -> h3;
+            h2:l -> h4 [ style = bold, color = black ];
+            h2:r -> h5;
+            h3:l -> h2 [ style = invis ];
+            h3:l -> h5 [ style = dotted, color = black ];
+            h3:r -> h6;
+            h6:r -> h3:r;
+
+         }
+
+
+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-up-2
+
+   Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
+   :math:`\to` ``h5`` (parte 2).
+
+   .. subfig::
+
+      Se decrementa el contador de ``h4`` quedando en 0, pasa a ser
+      *basura*. Se continúa con ``h5``.
+
+      .. digraph:: g4_4
+
+         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",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            subgraph marked {
+               node [ fillcolor = white, fontcolor = black ];
+               h1; h2; h4;
+            };
+
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<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" ];
+
+            root:r0 -> h1 [ style = invis ];
+            h1:l -> h2 [ style = invis ];
+            h1:r -> h3 [ style = invis ];
+            root:r1 -> h3;
+            h2:l -> h4 [ style = invis ];
+            h2:r -> h5 [ style = bold, color = black ];
+            h3:l -> h2 [ style = invis ];
+            h3:l -> h5 [ style = dotted, color = black ];
+            h3:r -> h6;
+            h6:r -> h3:r;
+
+         }
+
+   .. subfig::
+
+      Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.
+
+      .. digraph:: g4_5
+
+         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",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            subgraph marked {
+               node [ fillcolor = white, fontcolor = black ];
+               h1; h2; h4;
+            };
+
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<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" ];
+
+            root:r0 -> h1 [ style = invis ];
+            h1:l -> h2 [ style = invis ];
+            h1:r -> h3 [ style = invis ];
+            root:r1 -> h3;
+            h2:l -> h4 [ style = invis ];
+            h2:r -> h5 [ style = invis ];
+            h3:l -> h5 [ style = bold, color = black ];
+            h3:l -> h2 [ style = invis ];
+            h3:r -> h6;
+            h6:r -> h3:r;
+
+         }
+
+   .. subfig::
+
+      Se termina por actualizar la referencia de ``h3.l`` para que apunte
+      a ``h5``.
+
+      .. 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",
+               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;
+            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`).
+
+.. 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;
+
+         }
+
+
+
+
+.. _ref_gc_mark_sweep:
 
 Marcado y barrido
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-TODO
+Este algoritmo es el más parecido a la teoría sobre recolección de basura.
+Consiste en realizar la recolección en 2 fases: marcado y barrido. La primera
+fase consiste en el proceso de marcar el grafo de conectividad del *heap* para
+descubrir qué celdas son alcanzables desde el *root set*, tal y como se
+describió en :ref:`ref_gc_intro_mark`.
 
+Una vez marcadas todas las celdas, se sabe que las celdas *blancas* son
+*basura*, por lo tanto el paso que queda es el *barrido* de estas celdas,
+liberándolas. Esto se efectúa recorriendo todo el *heap*. Por lo tanto cada
+recolección es :math:`O(\lvert Heap \rvert)`, a diferencia del conteo de
+referencia que dijimos que en el peor caso es :math:`O(\lvert Live \thickspace
+set \rvert)`. Sin embargo el conteo de referencias se ejecuta **cada vez que
+se actualiza una referencia** mientras que la recolección en el marcado
+y barrido se realiza típicamente solo cuando el *mutator* pide una celda pero
+no hay ninguna libre. Esto hace que la constante del conteo de referencias sea
+típicamente varios órdenes de magnitud mayores que en el marcado y barrido.
 
+A continuación se presentan los servicios básicos de este algoritmo::
 
-Copia/Semi-espacio
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+   function new() is
+      cell = alloc()
+      if cell is null
+         collect()
+      cell = alloc()
+      if cell is null
+         throw out_of_memory
+      return cell
 
-TODO
+   function collect() is
+      mark_phase()
+      sweep_phase()
 
+   function sweep_phase() is
+      foreach cell in heap
+         if cell.marked
+            cell.marked = false
+         else
+            free(cell)
 
+El algoritmo ``mark_sweep()`` es exactamente igual al presentado en
+:ref:`ref_gc_intro_mark`. Es preciso notar que la fase de barrido
+(``sweep_phase()``) debe tener una comunicación extra con el *low level
+allocator* para poder obtener todas las celdas de memoria que existen en el
+*heap*.
 
-Compactado
+A diferencia del conteo de referencias, este algoritmo es :ref:`indirecto
+<ref_gc_direct>` y :ref:`no incremental <ref_gc_inc>`, ya que se realiza un
+recorrido de todo el *heap* de forma espaciada a través de la ejecución del
+programa. En general el *mutator* sufre pausas considerablemente mayores (en
+promedio) que con el conteo de referencias, lo que puede ser problemático para
+aplicaciones con requerimientos rígidos de tiempo, como aplicaciones
+*real-time*. Debido a la percepción de las pausas grandes, este tipo de
+colectores se conocen como :ref:`stop-the-world <ref_gc_concurrent>` (o
+*detener el mundo*).
+
+Una ventaja fundamental sobre el conteo de referencias es la posibilidad de
+reclamar estructuras cíclicas sin consideraciones especiales. Podemos observar
+como esto es posible analizando el ejemplo en las figuras
+:r:`fig:gc-mark-1` y :vref:`fig:gc-mark-2`. Si se eliminaran las referencias
+:math:`r0 \to h1` y :math:`h6 \to h2`, la fase de marcado consistiría
+solamente en marcar la celda :math:`h6`, pues es la única alcanzable desde el
+*root set*. Todas las demás celdas permanecerían blancas y por lo tanto pueden
+ser liberadas sin inconvenientes en la fase de barrido, que recorre el *heap*
+linealmente.
+
+
+
+.. _ref_gc_copy:
+
+Copia de semi-espacio
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-TODO
+Este algoritmo consiste en hacer una partición del *heap* en 2 mitades
+o *semi-espacios*, llamados usualmente *Fromspace* y *Tospace*. El primero se
+utiliza para alocar nuevas celdas de forma lineal, asumiendo un *heap*
+contiguo, incrementando un puntero (ver figura :vref:`fig:gc-copy`).  Esto se
+conoce como *pointer bump allocation* y es, probablemente, la forma más
+eficiente de alocar memoria (tan eficiente como alocar memoria en el *stack*).
+
+.. fig:: fig:gc-copy
+
+   Estructura del *heap* de un recolector con copia de semi-espacios.
+
+   .. aafig::
+      :aspect: 0.7
+      :scale: 1.4
+      :proportional:
+
+      zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
+
+       /---+"Fromspace"                /---+"Tospace"
+       |                               |
+       V_______________________________V_______________________________
+       | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+       | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+       | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
+       |~~~~~~~~~~~~~~~A~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+                       |
+       |               |               |    XX "Fromspace usado"
+                       \---+"libre"
+       |                               |    ZZ "Fromspace basura"
+
+       |/  "longitud del semi-espacio" |/   AA "Fromspace libre"
+       +- - - - - - - - - - - - - - - -+
+      /|                              /|    BB "Tospace"
+
+
+La segunda mitad (*Tospace*) permanece inutilizada hasta que se agota el
+espacio en el *Fromspace*; en ese momento comienza el proceso de recolección
+de basura que consiste en recorrer el grafo de conectividad, copiando las
+celdas *vivas* del *Fromspace* al *Tospace* de manera contigua, como si
+estuvieran alocando por primera vez. Como la posición en memoria de las celdas
+cambia al ser movidas, es necesario actualizar la dirección de memoria de
+todas las celdas *vivas*. Para esto se almacena una dirección de memoria de
+redirección, *forwarding address*, en las celdas que mueven. La *forwarding
+address* sirve a su vez de marca, para no recorrer una celda dos veces (como
+se explica en :ref:`ref_gc_intro_mark`). Cuando se encuentra una celda que ya
+fue movida, simplemente se actualiza la referencia por la cual se llegó a esa
+celda para que apunte a la nueva dirección, almacenada en la *forwarding
+address*. Una vez finalizado este proceso, el *Fromspace* y *Tospace*
+invierten roles y se prosigue de la misma manera (todo lo que quedó en el
+viejo *Fromspace* es *basura* por definición, por lo que se convierte el
+*Tospace*).
+
+A continuación se presenta una implementación sencilla de los servicios
+provistos por este tipo de recolectores. Cabe destacar que este tipo de
+recolectores deben estar íntimamente relacionados con el *low level
+allocator*, ya que la organización del *heap* y la forma de alocar
+memoria es parte fundamental de este algoritmo. Se asume que ya hay dos áreas
+de memoria del mismo tamaño destinadas al *Fromspace* y *Tospace*, y la
+existencia de 4 variables: ``fromspace`` (que apunta a la base del
+*Fromspace*), ``tospace`` (que apunta a la base del *Tospace*), ``spacesize``
+(que contiene el tamaño de un semi-espacio) y ``free`` (que apunta al lugar
+del *Fromspace* donde comienza la memoria libre). También vale aclarar que
+este algoritmo soporta inherentemente celdas de tamaño variable, por lo que
+los servicios ``alloc()`` y ``new()`` [#gccopynew]_ reciben como parámetro el
+tamaño de la celda a alocar::
+
+   function alloc(size) is
+      if free + size > fromspace + spacesize
+         return null
+      else
+         cell = free
+         free = free + size
+         return cell
+
+   function new(size) is
+      cell = alloc(size)
+      if cell is null
+         collect()
+      cell = alloc(size)
+      if cell is null
+         throw out_of_memory
+      return cell
+
+   function collect() is
+      free = tospace
+      foreach r in root_set
+         r = copy(r)
+      fromspace, tospace = tospace, fromspace
+
+   function copy(cell) is
+      if cell.forwarding_address is null
+         cell.forwarding_address = free
+         free = free + cell.size
+         foreach child in cell
+            child = copy(child)
+         return cell.forwarding_address
+      else
+         return cell.forwarding_address
+
+.. [#gccopynew] Notar que ``new()`` es igual que en el marcado y barrido con
+   la salvedad de que en este caso toma como parámetro el tamaño de la celda.
+
+Esta técnica tiene nombres variados en inglés: *semi-space*, *two-space*
+o simplemente *copying collector*. En este documento se denomina "copia de
+semi-espacio" porque los otros nombres son demasiado generales y pueden
+describir, por ejemplo, algoritmos donde no hay copia de celdas o donde no hay
+2 semi-espacios (como se verá en :ref:`ref_gc_art`).
+
+Al igual que el :ref:`ref_gc_mark_sweep` este algoritmo es :ref:`indirecto
+<ref_gc_direct>`, :ref:`no incremental <ref_gc_inc>` y :ref:`stop-the-world
+<ref_gc_concurrent>`. Las diferencias con los esquemas vistos hasta ahora son
+evidentes. La principal ventaja sobre el marcado y barrido (que requiere una
+pasada sobre el *live set*, el marcado, y otra sobre el *heap* entero, el
+barrido) es que este método require una sola pasada y sobre las celdas vivas
+del *heap* solamente. La principal desventaja es copia memoria, lo que puede
+ser particularmente costoso, además de requerir, como mínimo, el doble de
+memoria de lo que el *mutator* realmente necesita. Esto puede traer en
+particular problemas con la memoria virtual y el caché, por la pobre localidad
+de referencia.
+
+Por lo tanto los recolectores de este tipo pueden ser convenientes por sobre
+el marcado y barrido cuando se espera que el *live set* sea muy pequeño luego
+de una recolección. En estos casos el trabajo realizado por este tipo de
+recolectores puede ser considerablemente menor que el del marcado y barrido.
+Y por el contrario, si el *working set* es pequeño, al ser *compactado* en
+memoria puede mejorar la localidad de referencia (si el *working set* es
+grande se corre el riesgo de que la localidad de referencia empeore al
+moverse las celdas).
+
+
+Ejemplo
+^^^^^^^
+
+A continuación se presenta un sencillo ejemplo del algoritmo. Se parte de una
+estructura simple con 4 celdas en el *Fromspace* (que incluye un pequeño ciclo
+para mostrar que este algoritmo tampoco tiene inconvenientes para
+recolectarlos). Asumimos que ya no queda lugar en el *Fromspace* por lo que
+comienza la ejecución de ``collect()``. Se comienza por el *root set* que
+apunta a ``h3``, por lo tanto ésta es movida al *Tospace* primero, dejando una
+*forwarding address* a la nueva ubicación (ver figura
+:vref:`fig:gc-copy-ex-1`).
+
+.. fig:: fig:gc-copy-ex-1
+
+   Ejemplo de recolección con copia de semi-espacios (parte 1).
+
+   .. subfig::
+
+      Estructura inicial del *heap*. El *Fromspace* está complete y se inicial
+      la recolección.
+
+      .. aafig::
+         :aspect: 0.5
+         :scale: 1.25
+         :proportional:
+
+         +--------------------------------------------------+
+         | "Fromspace"                                      |
+         |        /--------------------------------\        |
+         |        | /--------\  /------\           |        |
+         |        | |        |  |      |           |        |
+         |  ______|_V________|__V______|___________V______  |
+         | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
+         | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
+         |  ~~~~~~~~~|~~~~~~~~~~A~~~~~~~A~~~~~~~~~~~~~~~~~  |
+         |      h1   |      h2  |   h3  |       h4          |
+         |           \----------/       |                   |
+         |                              \----+"root set"    |
+         |                                                  |
+         |                                                  |
+         |                                                  |
+         |  ______________________________________________  |
+         | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+         | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+         | A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
+         | |                                                |
+         | \----+"free"                                     |
+         | "Tospace"                                        |
+         +--------------------------------------------------+
+
+   .. subfig::
+
+      Se sigue la referencia del *root set*, copiando ``h3`` al *Tospace*
+      y dejando una *forwarding address*.
+
+      .. aafig::
+         :aspect: 0.5
+         :scale: 1.25
+         :proportional:
+
+         +--------------------------------------------------+
+         | "Fromspace"                                      |
+         |        /--------------------------------\        |
+         |        | /--------\  /------\           |        |
+         |        | |        |  |      |           |        |
+         |  ______|_V________|__V______|___________V______  |
+         | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
+         | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
+         |  ~~~~~~~~~|~~~~~~~~~~A~~~~~~~|A~~~~~~~~~~~~~~~~  |
+         |      h1   |      h2  |   h3  ||      h4          |
+         |           \----------/       ||                  |
+         |                              +\----+"root set"   |
+         |                             /                    |
+         |  /-------------------------+                     |
+         |  | h3                                            |
+         |  V_____________________________________________  |
+         | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+         | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+         |  ~~~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
+         |         |                                        |
+         |         \----+"free"                             |
+         | "Tospace"                                        |
+         +--------------------------------------------------+
+
+
+A continuación se copian las *hijas* de ``h3``, en este caso sólo ``h2``, que
+se ubica en el *Tospace* a continuación de ``h3``, dejando nuevamente su
+``forwarding address`` en la celda original. Al proceder recursivamente, se
+procede a copiar ``h1`` al *Tospace*, dejando una vez más la *forwarding
+address* en la celda original y procediendo con las hijas. Aquí podemos
+observar que al seguirse la referencia :math:`h1 \to h2`, como ``h2`` ya había
+sido visitada, solamente se actualiza la referencia apuntando a la nueva
+ubicación de ``h2`` pero no se vuelve a copiar la celda (ver figura
+:vref:`fig:gc-copy-ex-2`).
+
+.. fig:: fig:gc-copy-ex-2
+
+   Ejemplo de recolección con copia de semi-espacios (parte 2).
+
+   .. subfig::
 
+      Se sigue :math:`h3 \to h2`, copiando ``h2`` al *Tospace* y dejando una
+      *forwarding address*.
 
+      .. aafig::
+         :aspect: 0.5
+         :scale: 1.25
+         :proportional:
+
+         +--------------------------------------------------+
+         | "Fromspace"                                      |
+         |        /--------------------------------\        |
+         |        | /--------\  /------\           |        |
+         |        | |        |  |      |           |        |
+         |  ______|_V________|__V______|___________V______  |
+         | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
+         | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
+         |  ~~~~~~~~~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~  |
+         |      h1   |      h2  ||  h3  ||      h4          |
+         |           \----------/+      ||                  |
+         |                      /       +\----+"root set"   |
+         |         +-----------+       /                    |
+         |  /------+------------------+                     |
+         |  | h3   | h2                                     |
+         |  V______V______________________________________  |
+         | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+         | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
+         |  ~~|~~~~~~A~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
+         |    |      |     |                                |
+         |    \------/     \----+"free"                     |
+         | "Tospace"                                        |
+         +--------------------------------------------------+
+
+   .. subfig::
+
+      Se sigue :math:`h2 \to h1`, copiando ``h1``. Luego :math:`h1 \to h2`
+      pero ``h2`` no se copia, sólo se actualiza la referencia con la
+      *forwarding address*.
+
+      .. aafig::
+         :aspect: 0.5
+         :scale: 1.25
+         :proportional:
+
+         +--------------------------------------------------+
+         | "Fromspace"                                      |
+         |        /--------------------------------\        |
+         |        | /--------\  /------\           |        |
+         |        | |        |  |      |           |        |
+         |  ______|_V________|__V______|___________V______  |
+         | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
+         | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
+         |  ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~  |
+         |      h1 | |      h2  ||  h3  ||      h4          |
+         |         \-+----------/+      ||                  |
+         |           +-----+    /       +\-----+"root set"  |
+         |         +-------+---+       /                    |
+         |  /------+-------+----------+                     |
+         |  | h3   | h2    | h1                             |
+         |  V______V_______V______________________________  |
+         | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
+         | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
+         |  ~~|~~~~~~A~|~A~~|~A~~~~A~~~~~~~~~~~~~~~~~~~~~~  |
+         |    |      | | |  | |    |                        |
+         |    \------/ | \--/ |    \----+"free"             |
+         | "Tospace"   \------/                             |
+         +--------------------------------------------------+
+
+
+Se termina de copiar recursivamente las hijas de ``h1`` al copiar ``h4`` que
+resulta la última celda (sin hijas). Finalmente se invierten los roles de los
+semi-espacios y se actualiza la referencia del *root set* para que apunte a la
+nueva ubicación de ``h3``, como se muestra en la figura
+:vref:`fig:gc-copy-ex-3`.
+
+.. fig:: fig:gc-copy-ex-3
+
+   Ejemplo de recolección con copia de semi-espacios (parte 3).
+
+   .. subfig::
+
+      Se sigue :math:`h1 \to h4` copiando `h4`` al *Tospace* y dejando una
+      *forwarding address*.
+
+      .. aafig::
+         :aspect: 0.5
+         :scale: 1.25
+         :proportional:
+
+         +--------------------------------------------------+
+         | "Fromspace"                                      |
+         |        /--------------------------------\        |
+         |        | /--------\  /------\           |        |
+         |        | |        |  |      |           |        |
+         |  ______|_V________|__V______|___________V______  |
+         | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
+         | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
+         |  ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~|~~~~~  |
+         |      h1 | |      h2  ||  h3  ||      h4  \----\  |
+         |         \-+----------/+      ||               |  |
+         |           +-----+    /  +----/\---+"root set" |  |
+         |         +-------+---+  /                      |  |
+         |  /------+-------+-----+  /--------------------/  |
+         |  | h3   | h2    | h1     | h4                    |
+         |  V______V_______V________V_____________________  |
+         | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+         | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+         |  ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~  |
+         |    |      | | |  | | |      |   |                |
+         |    \------/ | \--/ | \------/   \----+"free"     |
+         | "Tospace"   \------/                             |
+         +--------------------------------------------------+
+
+   .. subfig::
+
+      Se finaliza la recolección, se intercambian los roles de los
+      semi-espacios y se actualiza la referencia del *root set*.
+
+      .. aafig::
+         :aspect: 0.5
+         :scale: 1.25
+         :proportional:
+
+         +--------------------------------------------------+
+         | "Tospace"                                        |
+         |                                                  |
+         |                                                  |
+         |                                                  |
+         |  ______________________________________________  |
+         | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
+         | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
+         |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
+         |                                                  |
+         |                                                  |
+         |                                                  |
+         | /---+"root set"                                  |
+         | |                                                |
+         | | h3      h2      h1      h4                     |
+         | V______________________________________________  |
+         | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+         | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+         |  ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~  |
+         |    |      | | |  | | |      |   |                |
+         |    \------/ | \--/ | \------/   \---+"free"      |
+         | "Fromspace" \------/                             |
+         +--------------------------------------------------+
+
+
+
+.. _ref_gc_art:
 
 Estado del arte
 ----------------------------------------------------------------------------
@@ -142,7 +2075,152 @@ Estado del arte
 
 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
+superponen entre sí, habiendo algoritmos que aplican muchas técnicas a la
+vez o recolectores híbridos que aplican una técnica para algún tipo de
+objeto y otra para otros.
+
+A continuación se enumeran las clasificaciones más importantes que se
+pudieron observar en la investigación sobre el `estado del arte`_.
+
+.. _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
+información de conectividad se mantenga activamente cada vez que hay un
+cambio en él. Normalmente se utiliza un contador de referencia en cada
+celda para este propósito, permitiendo almacenar en todo momento la
+cantidad de nodos que apuntan a ésta (dejando de lado el :ref:`problema de
+los ciclos <ref_gc_rc_cycles>`). Esto permite reclamar una celda
+instantáneamente cuando el *mutator* deja de hacer referencia a ella. Este
+tipo de recolectores son, inherentemente :ref:`incrementales <ref_gc_inc>`.
+
+Por el contrario, los recolectores **indirectos** normalmente no
+interfieren con el *mutator* en cada actualización del grafo de
+conectividad (exceptuando algunos :ref:`recolectores incrementales
+<ref_gc_inc>` que a veces necesitan instrumentar el *mutator* pero no para
+mantener el estado del grafo de conectividad completo). La recolección se
+dispara usualmente cuando el *mutator* requiere alocar memoria pero no hay
+más memoria libre conocida disponible y el recolector se encarga de generar
+la información de conectividad desde cero para determinar qué celdas son
+*basura*.
+
+Estas son las dos grandes familias de recolectores, también conocidos como
+`conteo de referencias`_ (directa) y *traicing garbage collection*
+(indirecta).
+
+
+.. _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
+causadas por el recolector (aunque generalmente el resultado es un mayor
+costo en tiempo total de recolección).
+
+De los `algoritmos clásicos`_ el único que es incremental en su forma más
+básica es el `conteo de referencias`_. Otros recolectores pueden hacerse
+incrementales de diversas maneras, pero en general consta de hacer parte
+del trabajo de escanear el grafo de conectividad cada vez que el *mutator*
+aloca memoria. En general para hacer esto es también necesario instrumentar
+al *mutator* de forma tal que informe al recolector cada vez que cambia el
+grafo de conectividad, para que éste pueda marcar al sub-grafo afectado por
+el cambio como *desactualizado* y así re-escanearlo nuevamente en la
+próxima iteración.
+
+En general la eficiencia de los recolectores incrementales disminuye
+considerablemente cuando el *mutator* actualiza muy seguido el grafo de
+conectividad, porque debe re-escanear sub-grafos que ya había escaneado una
+y otra vez. A esto se debe también que en general el tiempo de
+procesamiento total de un recolector incremental sea mayor que uno no
+incremental, aunque el tiempo de pausa de una recolección sea menor.
+
+
+.. _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
+realizar la recolección son usualmente denominados *stop-the-world* (*parar
+el mundo*), haciendo referencia a que pausan todos los hilos del *mutator*
+para poder escanear el grafo de conectividad de forma consistente.
+
+Para lograr que un recolector sea concurrente generalmente el mecanismo es
+similar al necesario para hacer un :ref:`recolector incremental
+<ref_gc_inc>`: hay que instrumentar al *mutator* para que informe al
+recolector cuando se realiza algún cambio en el grafo de conectividad, de
+forma tal que pueda volver a escanear el sub-grafo afectado por el cambio.
+
+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.
+
+
+Cloning
+
+
+1. Instrumentar el *mutator* de forma tal de que informe al recolector cada
+   vez que cambia el grafo de conectividad, de manera que pueda re-escanear
+   el sub-grafo que afectado por el cambio.
+
+2. Tomar una foto de la memoria y escanear esa foto estática en vez de la
+   memoria original, de forma que cualquier cambio en del *mutator* no
+   afecte la vista de la memoria del recolector.
+
+Ambos métodos tienen ventajas y desventajas. El primero no necesita hacer
+una copia costosa de la memoria, pero existe la posibilidad de que el
+recolector nunca pueda escanear el grafo de conectividad completo, si el
+*mutator* modifica el grafo más rápido de lo que el recolector lo escanea.
+Si bien hay formas de evitar esto, es usual que el trabajo de recolección
+se vea considerablemente incrementado por la cantidad de veces que hay que
+re-escanear el grafo. El segundo método puede ser costoso por las copias
+necesarias (aunque esto puede ser mitigado empleando alguna forma de *COW*
+[#gccow]_) y existe la posibilidad de que no se recuperen celdas que el
+*mutator*
+
+
+.. [#gccow] *COW* (del inglés *Copy On Write* o *copiar al escribir*) es
+   una técnica muy utilizada para disminuir las copias innecesarias,
+   evitando hacer la copia hasta que haya una modificación. Mientras no
+   hayan modificaciones no es necesario realizar una copia porque todos los
+   interesados verán la misma información. Esta técnica es utilizada por el
+   *kernel* de Linux_ por ejemplo, para que varias instancias de un mismo
+   proceso puedan compartir la memoria.
+
+
+Boehm, H., and M. Weiser, "Garbage Collection in an Uncooperative
+Environment", Software Practice & Experience, September 1988, pp. 807-820.
+http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/preprint.pdf
+(http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/)
+
+Boehm, H., "Space Efficient Conservative Garbage Collection", Proceedings
+of the ACM SIGPLAN '93 Conference on Programming Language Design and
+Implementation, SIGPLAN Notices 28, 6 (June 1993), pp. 197-206.
+http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi93.ps.Z
+
+Boehm, H., A. Demers, and S. Shenker, "Mostly Parallel Garbage Collection",
+Proceedings of the ACM SIGPLAN '91 Conference on Programming Language
+Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 157-164.
+http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi91.ps.Z
+
+Implementación de Bohem GC
+http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html
+
+Interfaz de Bohem GC
+http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html
+
 
 .. include:: links.rst
 
-.. vim: set ts=2 sts=2 sw=2 et tw=75 :
+.. vim: set ts=3 sts=3 sw=3 et tw=78 :