X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/b0956c037ae52da777b06705157486067755ec2c..6eefbae7d9d9a1e30f7637ecc41f56a21dc93567:/source/gc.rst?ds=sidebyside diff --git a/source/gc.rst b/source/gc.rst index 00cee40..de03886 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -2,147 +2,2471 @@ .. 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 +el rendimiento 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 aplicaciones +con altos requerimientos de rendimiento. En la actualidad un programa que +utiliza un recolector moderno puede ser comparable en rendimiento 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. +.. _gc_intro_basics: +Conceptos básicos +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Introducción ----------------------------------------------------------------------------- +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]_ 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*. + +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 diferencia entre dos partes +del programa, el recolector de basura y el programa en sí. A la primera se la +suele denominar simplemente *recolector* y a la segunda *mutator*, dado que es +la única que modifica (o *muta*) el grafo de conectividad. + + + +.. _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 + + Un camino cuyos *vértices terminales* coinciden, es decir :math:`v_1 + = v_N`, es denominado **Ciclo**. Cabe notar que los *vértices terminales* + de un ciclo son completamente arbitrarios, ya que cualquier *vértice + interior* puede ser un *vértice terminal*. + +*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 dos veces el mismo nodo +en casos en los que el grafo contenga ciclos. 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 el +rendimiento, en particular dependiendo de la aplicación puede convenir uno +u otro método para lograr una mejor localidad de referencia. + +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 + foreach (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\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 + + 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:: -TODO + 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 ]; -Algoritmos principales + 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; + + } + + + +.. _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 ` e :ref:`incrementales +`, además de otro tipo de optimizaciones. Entonces, lo que plantea +esta abstracción es una nueva partición del heap al momento de marcar, esta +vez son tres porciones: blanca, gris y negra. + +Al principio todas las celdas se pintan de blanco, excepto el *root set* que +se pinta 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) + foreach (src, dst) in v.edges + if dst in white_set + white_set.remove(dst) + gray_set.add(dst) + +Si bien este algoritmo no es recursivo, tiene un requerimiento de espacio +:math:`O(\lvert Live \thickspace set \rvert)`. Un ejemplo donde se aprecia +esto a simple vista es cuando el *Live set* resulta una lista simplemente +enlazada, en cuyo caso el *gray_set* deberá almacenar todos los nodos del +*Live set*. + + + +.. _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 `. 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 + \big\rbrace`. + +: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 tres 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 ` 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:: + + 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. + +Cuando esto sucede, las celdas que participan del ciclo tienen siempre su +contador mayor que 0, sin embargo puede suceder que ningún elemento del *root +set* apunte a una celda dentro del ciclo, por lo tanto el ciclo es *basura* +(al igual que cualquier otra celda para la cual hayan referencias desde el +ciclo pero que no tenga otras referencias externas) y sin embargo los +contadores no son 0. Los ciclos, por lo tanto, violan 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 sub-grafo para detectar +ciclos y liberarlos hasta tener otro recolector completo de *emergencia*; +pasando por tratar los ciclos como un todo para 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 +[PHP530]_. + + +.. _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 construida 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + h1 [ label = "h1\n1| l| r" ]; + h2 [ label = "h2\n2| l| r" ]; + h3 [ label = "h3\n3| 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; + 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\n*| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + h1 [ label = "h1\n1| l| r" ]; + h2 [ label = "h2\n2| l| r" ]; + h3 [ label = "h3\n3| 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; + 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\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\n3| 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; + 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\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\n3| 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; + 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| 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 = 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 ``h3.l`` :math:`\to` ``h2`` a ``h3.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\n2| 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; + h6:r -> h3:r; + + } + + .. subfig:: + + Luego se procede a visitar la antigua referencia de ``h3.l`` (``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\n2| 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; + 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| 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\n2| 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; + 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 ``h3.l`` :math:`\to` ``h2`` a ``h3.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\n2| 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; + 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| 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\n2| 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; + 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| 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\n2| 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; + 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| r1\n*", + 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\n2| 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 [ 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| r1\n*", + 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 [ 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() -TODO + function sweep_phase() is + foreach cell in heap + if cell.marked + cell.marked = false + else + free(cell) +El algoritmo ``mark_sweep()`` es exactamente igual al presentado en +:ref:`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 +` y :ref:`no incremental `, 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 ` (o *detener el mundo*). -Compactado +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. + + + +.. _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: 70 + :scale: 115 + + 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 +re-direcció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 +`, :ref:`no incremental ` y :ref:`stop-the-world +`. 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 requiere 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:: + +--------------------------------------------------+ + | "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:: + + +--------------------------------------------------+ + | "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:: + + +--------------------------------------------------+ + | "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:: + + +--------------------------------------------------+ + | "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:: + + +--------------------------------------------------+ + | "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:: + + +--------------------------------------------------+ + | "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 `. + +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 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 ` (directa) y *traicing garbage collection* (indirecta). +Prácticamente todos los recolectores menos el :ref:`conteo de referencias +` están dentro de esta última categoría (como por ejemplo, el +:ref:`marcado y barrido ` y :ref:`copia de semi-espacio +`). + +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 `. 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 +` se utiliza la :ref:`abstracción 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 el rendimiento 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:: + :scale: 110 + :aspect: 70 + + ___________________________________________________________________ + | | + | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH | + | | + | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHHHHHHH | + | | + | HHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH | + | | + | HH Mutator ZZ Inactivo XX Recolector | + |___________________________________________________________________| + + .. subfig:: + + Paralelo. + + .. aafig:: + :scale: 110 + :aspect: 70 + + ___________________________________________________________________ + | | + | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH | + | | + | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH | + | | + | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH | + | | + | HH Mutator ZZ Inactivo XX Recolector | + |___________________________________________________________________| + + .. subfig:: + + Concurrente. + + .. aafig:: + :scale: 110 + :aspect: 70 + + ___________________________________________________________________ + | | + | 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 `: 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. + +¿Cuál 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 son más comunes, 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 ` 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. El :ref:`marcado y barrido ` en general usa este +esquema, al igual que el :ref:`conteo de referencias `. + +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 el algoritmo visto en +: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 `). + + + +.. _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 `, 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 +`, 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 ` y que es sencillo +implementar recolectores :ref:`generacionales ` sobre estos. + +De los algoritmos clásicos sólo la :ref:`copia de semi-espacios ` +mueve celdas, el :ref:`conteo de referencias ` y :ref:`marcado +y barrido ` 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 ` 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 comúnmente 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 precisión son +el :ref:`recolector actual de D ` y [BLAC08]_. + + + +.. _gc_part: + +Recolección por particiones / generacional +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Otra forma de reducir la cantidad de pausas y la cantidad de trabajo realizado +por el recolector en general es dividiendo el *heap* en particiones 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:: + :scale: 110 + :aspect: 70 + + _______________________________________________________________________ + | | + | +-----------------------------+ +-----------------------------+ | + | / 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 dividiendo el *heap* en una partición +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]_. Basándose 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 vigilar 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 dividir 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 innecesario 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 principales 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 spelllang=es :