X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/b0956c037ae52da777b06705157486067755ec2c..5f79318a52fc6ada10154cb148008bd9d44fa22e:/source/gc.rst?ds=sidebyside diff --git a/source/gc.rst b/source/gc.rst index 00cee40..bf22c92 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -4,51 +4,79 @@ 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. +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, haciendo que el programa tenga un mejor +comportamiento con el caché y la memoria virtual. 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,83 +85,1364 @@ 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). + + + + +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 +y de esta manera tener un mejor comportamiento de la memoria virtual o del +*caché*. + +.. [#gccycle] Un ciclo es un camino donde el *vértice inicial* es el mismo + que el *vértice final*. Por lo tanto, los *vértices terminales* son + completamente arbitrarios, ya que cualquier *vértice interior* puede ser + un *vértice terminal*. + +Un algoritmo simple (recursivo) de marcado *primero a lo alto* puede ser +el siguiente (asumiendo que partimos con todos los vértices sin marcar) +[#gcpseudo]_:: + + mark(v) + if not v.marked + v.marked = true + for (src, dst) in v.edges + mark(dst) + + mark_phase() + for 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`` (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\n*| 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 -Algoritmos principales + 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\n*| 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\n*| 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\n*| 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| 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| 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_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 ` +e :ref:`incrementales `, 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):: + + mark_phase() + for 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_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 `. 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_clasic: + +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 ` e :ref:`incremental ` 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:: -Marcado y barrido -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + 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 -TODO +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:: -Copia/Semi-espacio + 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):: + + new() + cell = alloc() + if cell is null + throw out_of_memory + cell.rc = 1 + return cell + + del(cell) + cell.rc = cell.rc - 1 + if cell.rc is 0 + for child* in cell.children + del(*child) + free(cell) + + update(ref*, cell) + cell.rc = cell.rc + 1 + del(*ref) + *ref = cell + + +.. _ref_gc_rc_cycles: + +Ciclos +^^^^^^ + +.. _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* (figura :vref:`fig:gc-rc-rm-1`). Esto +conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el +*live set* ya que sus contadores siguen siendo mayores a 0 (figura +:vref:`fig:gc-rc-rm-2`). + + +.. fig:: fig:gc-rc-rm-1 + + 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + h1 [ label = "h1\n1| l| r" ]; + h2 [ label = "h2\n2| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + .. 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\n*| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + h1 [ label = "h1\n1| l| r" ]; + h2 [ label = "h2\n2| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + .. 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\n*| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n2| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + +.. fig:: fig:gc-rc-rm-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\n*| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + .. 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + +Luego se cambia una referencia (en vez de eliminarse) realizándose la +operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador +de referencias de ``h5`` para evitar confundirlo accidentalmente con +*basura* si se elimina alguna celda que apuntaba a ésta. Luego se procede +a decrementar el contador de ``h2`` que queda en 0, transformándose en +*basura* (figura :vref:`fig:gc-rc-up-1`). Lo mismo pasa cuando se desciende +a ``h4``, pero al descender a ``h5`` y decrementar el contador, éste sigue +siendo mayor que 0 (pues ``h3`` va a apuntar a ``h5``) así que permanece en +el *live set*. Finalmente se termina de actualizar la referencia ``h3.l`` +para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). + + +.. 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n2| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + .. 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; + }; + + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n2| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + .. 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; + }; + + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n2| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + +.. 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; h4; + }; + + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n0| l| r" ]; + h5 [ label = "h5\n2| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + .. 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; h4; + }; + + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n0| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + .. 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; h4; + }; + + h1 [ label = "h1\n0| l| r" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n0| l| r" ]; + h3 [ label = "h3\n1| l| r" ]; + h4 [ label = "h4\n0| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| 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; + + } + + +Marcado y barrido ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ TODO -Compactado +Copia/Semi-espacio ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ TODO +.. _ref_gc_art: + Estado del arte ---------------------------------------------------------------------------- @@ -142,7 +1451,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 `). Esto permite reclamar una celda +instantáneamente cuando el *mutator* deja de hacer referencia a ella. Este +tipo de recolectores son, inherentemente :ref:`incrementales `. + +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 +` 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 +`: 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 :