.. Introducción a la importancia de la recolección de basura y sus
principales técnicas, con sus ventajas y desventajas. También se da
un breve recorrido sobre el estado del arte.
- ESTADO: SIN EMPEZAR
+ ESTADO: TERMINADO
-.. _ref_gc:
+.. _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.
+.. _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 re-asignada 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
-de basura, éste se vuelve más un problema que una solución, porque
-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.
+para que sea útil, si el programador no puede confiar en el recolector de
+basura, éste se vuelve más un problema que una solución, porque 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.
+Conceptos básicos
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Los programas pueden hacer uso principalmente de 4 áreas de memoria:
-Introducción
-----------------------------------------------------------------------------
+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]_ asignada antes que otra nunca puede ser liberada antes que
+ aquella.
+
+ .. [#gccelda] En general en la literatura se nombra a una porción de
+ memoria asignada 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).
+
+
+
+.. _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 *heap*.
+
+ 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 ];
+
+ 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,
+ ];
-TODO
+ 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;
+ }
-Algoritmos principales
+ .. 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;
+
+ }
+
+
+
+.. _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 <gc_concurrent>` e :ref:`incrementales
+<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*.
+
+
+
+.. _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 <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.
+
+
+
+.. _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.
+.. _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 <gc_direct>` e :ref:`incremental <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
+
+
+
+.. _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]_.
+
+
+.. _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
+
+ Ejemplo de conteo de referencias: eliminación de una referencia (parte 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
+
+ Ejemplo de conteo de referencias: eliminación de una referencia (parte 2).
+
+ 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
+ Ejemplo de conteo de referencias: actualización de una referencia (parte 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
+
+ Ejemplo de conteo de referencias: actualización de una referencia (parte 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
+
+ Ejemplo de conteo de referencias: pérdida de memoria debido a un ciclo.
+
+ 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;
+
+ }
+
+
+
+.. _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:`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
+
+ function collect() is
+ mark_phase()
+ sweep_phase()
+
+ function sweep_phase() is
+ foreach cell in heap
+ if cell.marked
+ cell.marked = false
+ else
+ free(cell)
-TODO
+El algoritmo ``mark_sweep()`` es exactamente igual al presentado en
+: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*.
+A diferencia del conteo de referencias, este algoritmo es :ref:`indirecto
+<gc_direct>` y :ref:`no incremental <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 <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.
-Compactado
+
+
+.. _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 asignar 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 asignar memoria (tan eficiente como asignar memoria en el
+*stack*). Esto permite además evitar el problema de la *fragmentación* de
+memoria [#gcfrag]_ que normalmente afectan a los otros algoritmos clásicos (o
+sus *low level allocators*).
+
+.. [#gcfrag] La *fragmentación* de memoria sucede cuando se asignan objetos
+ de distintos tamaños y luego libera alguno intermedio, produciendo
+ *huecos*. Estos *huecos* quedan inutilizables hasta que se quiera
+ asignar un nuevo objeto de tamaño igual al *hueco* (o menor). Si esto no
+ sucede y se acumulan muchos *huecos* se dice que la memoria está
+ *fragmentada*.
+
+.. fig:: fig:gc-copy
+
+ Estructura del *heap* de un recolector con copia de semi-espacios.
+
+ .. aafig::
+ :aspect: 0.7
+ :scale: 1.4
+
+ 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 asignando 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:`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 asignar 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 asignar::
+
+ 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:`gc_art`).
+
+Al igual que el :ref:`gc_mark_sweep` este algoritmo es :ref:`indirecto
+<gc_direct>`, :ref:`no incremental <gc_inc>` y :ref:`stop-the-world
+<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::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "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::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "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::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "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::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "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::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "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::
+ :scale: 1.25
+
+ +--------------------------------------------------+
+ | "Tospace" |
+ | |
+ | |
+ | |
+ | ______________________________________________ |
+ | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
+ | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
+ | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
+ | |
+ | |
+ | |
+ | /---+"root set" |
+ | | |
+ | | h3 h2 h1 h4 |
+ | V______________________________________________ |
+ | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+ | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
+ | ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~ |
+ | | | | | | | | | | |
+ | \------/ | \--/ | \------/ \---+"free" |
+ | "Fromspace" \------/ |
+ +--------------------------------------------------+
+
+
+
+.. _gc_art:
Estado del arte
----------------------------------------------------------------------------
-.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
- ejemplos.
+La manera en que la investigación sobre recolección de basura ha crecido es
+realmente sorprendente. Hay, al menos, 2995 publicaciones sobre recolección de
+basura registradas al momento de escribir este documento [GCBIB]_. Esto hace
+que el análisis del estado del arte sea particularmente complejo y laborioso.
+
+Analizar todas las publicaciones existentes es algo excede los objetivos de
+este trabajo, por lo tanto se analizó solo una porción significativa,
+utilizando como punto de partida a [JOLI96]_.
+
+De este análisis se observó que la gran mayoría de los algoritmos son
+combinaciones de diferentes características básicas; por lo tanto se intentó
+aislar estas características que son utilizadas como bloques de construcción
+para algoritmos complejos. Ésta tampoco resultó ser una tarea sencilla debido
+a que muchos de estos bloques de construcción básicos están interrelacionados
+y encontrar una división clara para obtener características realmente atómicas
+no es trivial.
+
+La construcción de recolectores más complejos se ve alimentada también por la
+existencia de recolectores *híbridos*; es decir, recolectores que utilizan más
+de un algoritmo dependiendo de alguna característica de la memoria
+a administrar. No es poco común observar recolectores que utilizan un
+algoritmo diferente para celdas que sobreviven varias recolecciones que para
+las que mueren rápidamente, o que usan diferentes algoritmos para objetos
+pequeños y grandes, o que se comporten de forma conservativa para ciertas
+celdas y sean precisos para otras.
+
+De todas estas combinaciones resulta el escenario tan fértil para la
+investigación sobre recolección de basura.
+
+A continuación se presentan las principales clases de algoritmos
+y características básicas encontradas durante la investigación del estado del
+arte. La separación de clases y aislamiento de características no es siempre
+trivial, ya que hay ciertas clases de recolectores que están interrelacionadas
+(o ciertas características pueden estar presentes sólo en recolectores de una
+clase en particular).
+
+
+
+.. _gc_direct:
+
+Recolección 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
+sobre el grafo 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 (ver :ref:`gc_rc`). Esto permite reclamar una celda
+instantáneamente cuando el *mutator* deja de hacer referencia a ella. Este
+tipo de recolectores son inherentemente :ref:`incrementales <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 <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 asignar 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*.
+
+Esta es la madre de toda clasificación, también conocidos como :ref:`conteo de
+referencias <gc_rc>` (directa) y *traicing garbage collection* (indirecta).
+Prácticamente todos los recolectores menos el :ref:`conteo de referencias
+<gc_rc>` están dentro de esta última categoría (como por ejemplo, el
+:ref:`marcado y barrido <gc_mark_sweep>` y :ref:`copia de semi-espacio
+<gc_copy>`).
+
+Otros ejemplos de recolectores modernos *directos* son el recolector de basura
+de Python_ [NAS00]_ y [LINS05]_ (aunque ambos tiene un algoritmo *indirecto*
+para recuperar ciclos).
+
+
+
+.. _gc_inc:
+
+Recolección 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
+total de recolección en términos de tiempo).
+
+De los `algoritmos clásicos`_ el único que es incremental en su forma más
+básica es el :ref:`conteo de referencias <gc_rc>`. 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* asigna 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. Para realizar esto en recolectores :ref:`indirectos
+<gc_direct>` se utiliza la :ref:`abstracción tricolor <gc_intro_tricolor>`;
+cuando el *mutator* cambia una referencia, se marca *gris* la celda que la
+contiene, de modo que el recolector vuelva a visitarla.
+
+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.
+
+Ejemplos de recolectores que se encuentran dentro de esta categoría son
+[BOEH91]_, [LINS05]_,
+
+
+
+.. _gc_concurrent:
+
+Recolección concurrente / paralela / *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* (*detener el
+mundo*), haciendo referencia a que pausan todos los hilos del *mutator* para
+poder escanear el grafo de conectividad de forma consistente. Hay una tercera
+clase de colectores que si bien son *stop-the-world*, utilizan todos los hilos
+disponibles para realizar la recolección (ver figura
+:vref:`fig:gc-concurrent`).
+
+.. fig:: fig:gc-concurrent
+
+ Distintos tipos de recolectores según el comportamiento en ambientes
+ multi-hilo.
+
+ .. subfig::
+
+ *Stop-the-world*.
+
+ .. aafig::
+ :aspect: 0.7
+
+ ___________________________________________________________________
+ | |
+ | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
+ | |
+ | HH Mutator ZZ Inactivo XX Recolector |
+ |___________________________________________________________________|
+
+ .. subfig::
+
+ Paralelo.
+
+ .. aafig::
+ :aspect: 0.7
+
+ ___________________________________________________________________
+ | |
+ | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | HH Mutator ZZ Inactivo XX Recolector |
+ |___________________________________________________________________|
+
+ .. subfig::
+
+ Concurrente.
+
+ .. aafig::
+ :aspect: 0.7
+
+ ___________________________________________________________________
+ | |
+ | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
+ | |
+ | ZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZ |
+ | |
+ | HH Mutator ZZ Inactivo XX Recolector |
+ |___________________________________________________________________|
+
+
+Para lograr que un recolector sea concurrente generalmente el mecanismo es
+similar al necesario para hacer un :ref:`recolector incremental <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, además de la sincronización necesaria entre *mutator*
+y recolector.
+
+¿Cúal es la idea entonces de un recolector concurrente? Una vez más, al igual
+que los recolectores incrementales, el principal objetivo es disminuir las
+largas pausas provocadas por la recolección de basura. Sin embargo, este tipo
+de algoritmos además permite hacer un mejor aprovechamiento de las
+arquitecturas *multi-core* [#gcmulticore]_ que cada vez se afirman más, ya que
+el *mutator* y el recolector pueden estar corriendo realmente en paralelo,
+cada uno en un procesador distinto. Algunos recolectores van más allá
+y permiten incluso paralelizar la recolección de basura en varios hilos
+([HUEL98]_, [LINS05]_). Otros ejemplos de recolectores concurrentes (aunque no
+ofrece paralelización del procesamiento del recolector en varios hilos) son
+[BOEH91]_, [RODR97]_.
+
+.. [#gcmulticore] Una arquitectura *multi-core* es aquella que combina dos
+ o más núcleos (*cores*) independientes que trabajan a la misma frecuencia,
+ pero dentro de un solo circuito integrado o procesador.
+
+Todos los :ref:`algoritmos clásicos <gc_classic>` que se han citado son del
+tipo *stop-the-world*.
+
+
+
+.. _gc_free_list:
+
+Lista de libres / *pointer bump allocation*
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Esta clasificación se refiere principalmente a la forma en que se organiza el
+*heap*, íntimamente relacionado al *low level allocator*. Si bien se ha dicho
+que en este trabajo no se prestará particular atención a este aspecto, en
+ciertos algoritmos es tan relevante que tampoco es sensato pasarlo por alto
+completamente.
+
+En términos generales, hay dos formas fundamentales de organizar el *heap*,
+manteniendo una lista de libres o realizando *pointer bump allocation*, como
+se explicó en :ref:`gc_copy`. La primera forma consiste, a grandes rasgos, en
+separar el *heap* en celdas (que pueden agruparse según tamaño) y enlazarlas
+en una lista de libres. Al solicitarse una nueva celda simplemente se la
+desenlaza de la lista de libres. Por otro lado, cuando el recolector detecta
+una celda *muerta*, la vuelve a enlazar en la lista de libres. Este es un
+esquema simple pero con limitaciones, entre las principales, el costo de
+asignar puede ser alto si hay muchos tamaños distintos de celda y soportar
+tamaño de celda variable puede ser complejo o acarrear muchas otras
+ineficiencias. :ref:`gc_mark_sweep` en general usa este esquema, al igual que
+:ref:`gc_rc`.
+
+Otro forma de organizar el *heap* es utilizándolo como una especie de *stack*
+en el cual para asignar simplemente se incrementa un puntero. Este esquema es
+simple y eficiente, si el recolector puede mover celdas (ver
+:ref:`gc_moving`); de otra manera asignar puede ser muy costoso si hay que
+buscar un *hueco* en el heap (es decir, deja de reducirse a incrementar un
+puntero). El clásico ejemplo de esta familia es :ref:`gc_copy`.
+
+Sin embargo, entre estos dos extremos, hay todo tipo de híbridos. Existen
+recolectores basados en *regiones*, que se encuentran en un punto intermedio.
+Dentro de una región se utiliza un esquema de *pointer bump allocation* pero
+las regiones en sí se administran como una lista de libres (como por ejemplo
+[BLAC08]_). Otra variación (más común) de este esquema son los *two level
+allocators* que asignan páginas completas (similar a las regiones) y dentro de
+cada página se asignan las celdas. Ambas, páginas y celdas, se administran
+como listas de libres (ejemplos que utilizan este esquema son [BOEHWD]_ y el
+:ref:`recolector actual de D <dgc_actual>`).
+
+
+
+.. _gc_moving:
+
+Movimiento de celdas
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Otra característica muy importante del recolector de basura es si mueve las
+celdas o no. En general el movimiento de celdas viene de la mano del esquema
+de :ref:`pointer bump allocation <gc_free_list>`, ya que *compacta* todas las
+celdas *vivas* al comienzo del *heap* luego de una recolección, permitiendo
+este esquema para asignar nuevas celdas, pero puede utilizarse en esquemas
+híbridos como recolectores basados en *regiones* (por ejemplo [BLAC08]_).
+
+Además los recolectores con movimiento de celdas deben ser :ref:`precisos
+<gc_conserv>`, porque es necesario tener la información completa de los tipos
+para saber cuando actualizar los punteros (de otra manera se podría escribir
+un dato de una celda que no era un puntero). Para que un recolector pueda
+mover celdas, aunque sea parcialmente, en recolectores *semi-precisos* se
+utiliza un método conocido como *pinning* (que significa algo como *pinchar
+con un alfiler*); una celda es *pinned* (*pinchada*) cuando hay alguna
+referencia no-precisa a ella, y por lo tanto no puede ser movida (porque no se
+puede estar seguro si es posible actualizar dicha referencia).
+
+La ventaja principal de los colectores con movimiento es la posibilidad de
+utilizar :ref:`pointer bump allocation <gc_free_list>` y que es sencillo
+implementar recolectores :ref:`generacionales <gc_part>` sobre estos.
+
+De los algoritmos clásicos sólo la :ref:`copia de semi-espacios <gc_copy>`
+mueve celdas, el :ref:`conteo de referencias <gc_rc>` y :ref:`marcado
+y barrido <gc_mark_sweep>` no lo hacen. Además hay otro algoritmo bastante
+básico que mueve celdas, el **marcado y compactado**. Éste no tiene
+2 semi-espacios, directamente mueve las celdas compactándolas al comienzo del
+*heap*. El algoritmo es un poco más complejo que la :ref:`copia de
+semi-espacios <gc_copy>` pero suele poder proveer una mayor localidad de
+referencia y *desperdicia* un semi-espacio que está inutilizado salgo en el
+momento de la recolección. Por ejemplo para Mono_, que antes usaba un
+recolector conservativo sin movimiento ([BOEHWD]_) se está implementando un
+recolector de este tipo [MOLAWE]_ [MOLA06]_.
+
+
+
+.. _gc_conserv:
+
+Recolectores conservativos vs precisos
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Los recolectores *conservativos* son aquellos que tienen la capacidad de poder
+lidiar con un *root set* o celdas que no tengan información de tipos asociada.
+Esto significa que el recolector no sabe donde hay punteros (o referencias) en
+una celda o raiz dada. Es decir, una ubicación particular puede ser un puntero
+o no. Esto trae una variada cantidad de problemas, como retención de celdas
+que en realidad son *basura* simplemente porque hay algún dato que coincide
+con la dirección de memoria en la que está almacenada esa celda *basura*
+[#gcflasepos]_. Además los recolectores puramente conservativos no puede mover
+celdas (ver :ref:`gc_moving`), porque no pueden arriesgarse a actualizar los
+punteros por el riesgo que existe de que sean falsos positivos.
+
+.. [#gcflasepos] Esto es lo que se conoce como un *falso positivo*, algo que
+ aparenta ser un puntero pero en realidad no lo es.
+
+Sin embargo hay ciertas circunstancias que hacen que no quede más remedio que
+el recolector sea conservativo, por ejemplo cuando se utiliza un recolector de
+basura para un lenguaje que no ha sido pensado para tener uno (como C o C++).
+
+Por el contrario, los recolectores que poseen a su disposición información
+completa sobre el tipo de la celda, y por ende información sobre cuales de sus
+campos son realmente punteros, son denominados *precisos*. Estos recolectores
+no están sujetos a estas limitaciones y por lo tanto son potencialmente más
+eficientes en cuanto a tiempo y espacio. Los lenguajes que fueron diseñados
+para tener un recolector de basura (y en especial aquellos que son de relativo
+alto nivel) en general disponen de recolectores precisos.
+
+Hay casos donde se posee información de tipos para algunas celdas solamente,
+o más comunmente se posee información de tipos de celdas que se encuentran en
+el *heap* pero no para el *stack* y registros (por ejemplo [MOLA06]_). En
+estos casos se puede adoptar un esquema híbrido y tratar algunas referencias
+de forma conservativa y otras de forma precisa, de manera de mitigar, aunque
+sea de forma parcial, los efectos adversos de los recolectores conservativos.
+Estos recolectores son conocidos como *semi-precisos*. Los recolectores
+semi-precisos pueden mover celdas si utilizan un mecanismo de *pinning* (ver
+:ref:`gc_moving`).
+
+El ejemplo de recolector conservativo por excelencia es el recolector
+`Boehm-Demers-Wiser`_ ([BOEH88]_, [BOEH91]_, [BOEH93]_, [BOEHWD]_) aunque
+puede comportarse de forma semi-precisa si el usuario se encarga de darle la
+información de tipos (en cuyo caso el recolector deja de ser transparente para
+el usuario). Otros ejemplos de recolectores con cierto grado de
+conservativismo son el :ref:`recolector actual de D <dgc_actual>` y [BLAC08]_.
+
+
+
+.. _gc_part:
+
+Recolección particionada / generacional
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Otra forma de reducir la cantidad de pausas y la cantidad de trabajo realizado
+por el recolector en general es particionando el *heap* de manera tal de
+recolectar solo las partes donde más probabilidad de encontrar *basura* haya.
+
+Entonces, si el recolector tiene algún mecanismo para identificar zonas de
+alta concentración de *basura* puede hacer la recolección solo en ese área
+donde el trabajo va a ser mejor recompensado (ver :vref:`fig:gc-part`).
+
+.. fig:: fig:gc-part
+
+ Concentración de basura en distintas particiones del *heap*.
+
+ .. aafig::
+ :aspect: 0.7
+
+ _______________________________________________________________________
+ | |
+ | +-----------------------------+ +-----------------------------+ |
+ | / Baja \ / Alta \ |
+ | + + + |
+ | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
+ | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
+ | |
+ | GG Celdas vivas ZZ Basura |
+ |_______________________________________________________________________|
+
+
+Sin embargo encontrar zonas de alta concentración no es trivial. La forma más
+divulgada de encontrar estas zonas es particionando el *heap* en un área
+utilizada para almacenar celdas *jóvenes* y otra para celdas *viejas*. Una
+celda *vieja* es aquella que ha *sobrevivido* una cantidad N de recolecciones,
+mientras que el resto se consideran *jóvenes* (las celdas *nacen* jóvenes).
+Los recolectores que utilizan este tipo de partición son ampliamente conocido
+como recolectores **generacionales**. La *hipótesis generacional* dice que el
+área de celdas jóvenes tiene una mayor probabilidad de ser un área de alta
+concentración de basura [JOLI96]_. Basandose en esto, los recolectores
+generacionales primero intentan recuperar espacio del área de celdas jóvenes
+y luego, de ser necesario, del área de celdas viejas. Es posible tener varias
+generaciones e ir subiendo de generación a generación a medida que es
+necesario. Sin embargo en general no se obtienen buenos resultados una vez que
+se superan las 3 particiones. La complejidad que trae este método es que para
+recolectar la generación joven es necesario tomar las referencias de la
+generación vieja a la joven como parte del *root set* (de otra forma podrían
+tomarse celdas como *basura* que todavía son utilizadas por las celdas
+viejas). Revisar toda la generación vieja no es una opción porque sería
+prácticamente lo mismo que realizar una recolección del *heap* completo. La
+solución está entonces, una vez más, en instrumentar el *mutator* para que
+avise al recolector cuando cambia una referencia de la generación vieja a la
+joven (no es necesario monitorear las referencias en sentido inverso ya que
+cuando se recolecta la generación vieja se hace una recolección del *heap*
+completo).
+
+Sin embargo, a pesar de ser este el esquema más difundido para particionar el
+*heap* y realizar una recolección parcial sobre un área de alta concentración
+de basura no es la única. Otros recolectores proponen hacer un análisis
+estático del código revisando la conectividad entre los objetos según sus
+tipos (esto es posible solo en lenguajes con tipado estático), de manera tal
+de separar en distintas áreas grupos de tipos que no pueden tener referencias
+entre sí [HIRZ03]_. Este análisis hace que sea inecesario instrumentar el
+*mutator* para reportar al recolector cambios de referencias
+inter-particiones, sencillamente porque queda demostrado que no existe dicho
+tipo de referencias. Esto quita una de las principale ineficiencias
+y complejidades del esquema generacional.
-TODO
.. 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 :
projects / z.facultad / 75.00 / informe.git / blobdiff