2 .. Introducción a la importancia de la recolección de basura y sus
3 principales técnicas, con sus ventajas y desventajas. También se da
4 un breve recorrido sobre el estado del arte.
10 ============================================================================
14 ----------------------------------------------------------------------------
16 *Recolección de basura* se refiere a la recuperación automática de memoria
17 del *heap* [#gcheap]_ una vez que el programa ha dejado de hacer referencia
18 a ella (y por lo tanto, ha dejado de utilizarla).
20 A medida que el tiempo pasa, cada vez los programas son más complejos y es
21 más compleja la administración de memoria. Uno de los aspectos más
22 importantes de un recolector de basura es lograr un mayor nivel de
23 abstracción y modularidad, dos conceptos claves en la ingeniería de
24 software [JOLI96]_. En particular, al diseñar o programar bibliotecas, de
25 no haber un recolector de basura, **la administración de memoria pasa a ser
26 parte de la interfaz**, lo que produce que los módulos tengan un mayor
27 grado de acoplamiento.
29 Además hay una incontable cantidad de problemas asociados al manejo
30 explícito de memoria que simplemente dejan de existir al utilizar un
31 recolector de basura. Por ejemplo, los errores en el manejo de memoria
32 (como *buffer overflows* [#gcbuff]_ o *dangling pointers* [#gcdang]_) son
33 la causa más frecuente de problemas de seguridad [BEZO06]_.
35 La recolección de basura nació junto a Lisp_ a finales de 1950 y en los
36 siguientes años estuvo asociada principalmente a lenguajes funcionales,
37 pero en la actualidad está presente en prácticamente todos los lenguajes de
38 programación, de alto o bajo nivel, aunque sea de forma opcional. En los
39 últimos 10 años tuvo un gran avance, por la adopción en lenguajes de
40 desarrollo rápido utilizados mucho en el sector empresarial, en especial
41 Java_, que fue una plataforma de facto para la investigación y desarrollo
42 de recolectores de basura (aunque no se limitaron a este lenguaje las
45 En las primeras implementaciones de recolectores de basura la penalización
46 en la eficiencia del programa se volvía prohibitiva para muchas
47 aplicaciones. Es por esto que hubo bastante resistencia a la utilización de
48 recolectores de basura, pero el avance en la investigación fue haciendo que
49 cada vez sea una alternativa más viable al manejo manual de memoria,
50 incluso para apliaciones con altos requerimientos de eficiencia. En la
51 actualidad un programa que utiliza un recolector moderno puede ser
52 comparable en eficiencia con uno que utiliza un esquema manual. En
53 particular, si el programa fue diseñado con el recolector de basura en
54 mente en ciertas circunstancias puede ser incluso más eficiente que uno que
55 hace manejo explícito de la memoria. Muchos recolectores mejoran la
56 localidad de referencia, haciendo que el programa tenga un mejor
57 comportamiento con el caché y la memoria virtual.
59 El recolector de basura debe tener un comportamiento correcto y predecible
60 para que sea útil, si el programador no puede confiar en el recolector
61 de basura, éste se vuelve más un problema que una solución, porque
62 introduce nuevos puntos de falla en los programas, y lo que es peor,
63 puntos de falla no controlados por el programador, volviendo mucho más
64 difícil la búsqueda de errores.
67 .. [#gcheap] *Heap* es un área de memoria que se caracteriza por ser
68 dinámica (a diferencia del área de memoria estática que está disponible
69 durante toda la ejecución de un programa). Un programa puede reservar
70 memoria en tiempo de ejecución según sea necesario y liberarla cuando ya
71 no la necesita. A diferencia del *stack*, la duración de la *reserva* no
72 está atada a un bloque de código.
73 .. [#gcbuff] Un *buffer overflow* (*desbordamiento de memoria* en
74 castellano) se produce cuando se copia un dato a un área de memoria que
75 no es lo suficientemente grande para contenerlo. Esto puede producir que
76 el programa sea abortado por una violación de segmento, o peor,
77 sobreescribir un área de memoria válida, en cuyo caso los resultados son
79 .. [#gcdang] Un *dangling pointer* (*puntero colgante* en castellano) es un
80 puntero que apunta a un área de memoria inválida. Ya sea porque el
81 elemento apuntado no es el mismo tipo o porque la memoria ya ha sido
82 liberada. Al ser desreferenciado, los resultados son impredecibles, el
83 programa podría abortarse por una violación de segmento o podrían pasar
84 peores cosas si el área de memoria fue realocada para almacenar otro
90 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
92 Los programas pueden hacer uso principalmente de 4 áreas de memoria:
95 Se trata de la memoria más básica de una computadora. Es el área de
96 memoria en la que puede operar realmente el procesador, es extremadamente
97 escasa y generalmente su uso es administrado por el lenguaje de
98 programación (o compilador más específicamente). Excepto en situaciones
99 muy particulares, realizando tareas de muy bajo nivel, un programador
100 nunca manipula los registros explícitamente.
102 Área de memoria estática:
103 Es la forma de memoria más simple que un programador utiliza
104 explícitamente. En general las variables globales se almacenan en este
105 área, que es parte inherente del programa y está disponible durante toda
106 su ejecución, por lo tanto nunca cambia su capacidad en tiempo de
107 ejecución. Es la forma más básica de administrar memoria, pero tiene una
108 limitación fundamental: **el tamaño de la memoria tiene que ser conocido
109 en tiempo de compilación**. Los primeros lenguajes de programación solo
110 contaban con este tipo de memoria (además de los registros del
114 Los primeros lenguajes de programación que hicieron uso de una pila
115 aparecieron en el año 1958 (Algol-58 y Atlas Autocode) y fueron los
116 primeros en introducir estructura de bloques, almacenando las
117 variables locales a estos bloques utilizando una pila [JOLI96]_.
118 Esto permite utilizar recursividad y tener un esquema simple de memoria
119 dinámica. Sin embargo este esquema es muy limitado porque el orden de
120 reserva y liberación de memoria tiene que estar bien establecido. Una
121 celda [#gccelda]_ alocada antes que otra nunca puede ser liberada antes
125 A diferencia del *stack*, el *heap* provee un área de memoria que puede
126 ser obtenida dinámicamente pero sin limitaciones de orden. Es el tipo de
127 memoria más flexible y por lo tanto el más complejo de administrar; razón
128 por la cual existen los recolectores de basura.
130 La recolección de basura impone algunas restricciones sobre la manera de
131 utilizar el *heap*. Debido a que un recolector de basura debe ser capaz de
132 determinar el grafo de conectividad de la memoria en uso, es necesario que
133 el programa siempre tenga alguna referencia a las celdas activas en los
134 registros, memoria estática o *stack* (normalmente denominado *root set*).
136 Esto implica que una celda sea considerada basura si y sólo si no puede ser
137 alcanzada a través del grafo de conectividad que se comienza a recorrer
138 desde el *root set*. Por lo tanto, una celda está *viva* si y sólo si su
139 dirección de memoria está almacenada en una celda *raíz* (parte del *root
140 set*) o si está almacenada en otra celda *viva* del *heap*.
142 Expresado más formalmente, dada la relación :math:`M \to N`, donde
143 :math:`M` es una celda del *heap* o parte del *root set* y :math:`N` es una
144 celda del *heap*, definida como:
148 M \to N \Longleftrightarrow M \text{ almacena un puntero a } N
150 El conjunto de celdas vivas (o *live set*) queda determinado por:
154 vivas = \left\lbrace N \in Celdas \big/
155 ( \exists r \in Raices / r \to N ) \vee (\exists M \in vivas / M \to N )
158 Cabe aclarar que esta es una definición conceptual, asumiendo que el
159 programa siempre limpia una dirección de memoria almacenada en el *root
160 set* o una celda del *heap* cuando la celda a la que apunta no va a ser
161 utilizada nuevamente. Esto no es siempre cierto y los falsos positivos que
162 esto produce se conoce como un tipo de pérdida de memoria (que es posible
163 incluso al utilizar un recolector de basura) llamada pérdida de memoria
164 *lógica*. Esto puede no ser evitable (incluso cuando el programador no
165 cometa errores) en lenguajes de programación que requieran un recolector de
168 Por último, siendo que el recolector de basura es parte del programa de
169 forma indirecta, es común ver en la literatura que se direfencia entre
170 2 partes del programa, el recolector de basura y el programa en sí. Dado
171 que para el recolector de basura, lo único que interesa conocer del
172 programa en sí son los cambios al grafo de conectividad de las celdas,
173 normalmente se lo llama *mutator* (mutador).
176 .. [#gccelda] En general en la literatura se nombra a una porción de
177 memoria alocada individualmente *celda*, *nodo* u *objeto*
178 indistintamente. En este trabajo se utilizará la misma nomenclatura
179 (haciendo mención explícita cuando alguno de estos términos se refiera
180 a otra cosa, como al nodo de una lista o a un objeto en el sentido de
181 programación orientada a objetos).
185 Recorrido del grafo de conectividad
186 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
188 El problema de encontrar las celdas *vivas* de un programa se reduce a recorrer
189 un grafo dirigido. El grafo se define como:
195 Donde :math:`V` es el conjunto de vértices, dado por las celdas de memoria
196 y :math:`A` es un conjunto de pares ordenados (aristas), dado por la
197 relación :math:`M \rightarrow N` (es decir, los punteros).
199 El grafo comienza a recorrerse desde el *root set* y todos los vértices que
200 fueron visitados componen el *live set*; el resto de los vértices son
203 Más formalmente, Definimos:
206 secuencia de vértices tal que cada uno de los vértices tiene una arista
207 al próximo vértice en la secuencia. Todo camino finito tiene un *vértice
208 inicial* y un *vértice final* (llamados en conjunto *vértices
209 terminales*). Cualquier vértice no terminal es denominado *vértice
214 \underset{v_1 \rightarrow v_N}{C} = \left\lbrace
215 v_1, \dotsc, v_N \in V \big/ \underset{i \in [1,N-1]}{\forall v_i}
216 \exists (v_i \to v_{i+1}) \in A
220 decimos que :math:`M` está *conectado* a :math:`N` si y sólo si existe un
221 camino de :math:`M` a :math:`N`.
225 M \mapsto N \Longleftrightarrow \exists \underset{M \to N}{C} \in G
228 el conjunto de celdas *vivas* está dado por todos los vértices
229 (:math:`v`) del grafo para los cuales existe una raíz en el *root set*
230 que esté conectada a él.
234 Live \thickspace set = \left\lbrace v \in V \big/
235 \left( \exists r \in Root \thickspace set \big/ r \mapsto v \right)
239 la basura, o celdas *muertas*, quedan determinadas entonces por todas las
240 celdas del *heap* que no son parte del *live set*.
244 Basura = V - Live \thickspace set
246 Esto es, efectivamente, una partición del *heap* (ver figura
247 :vref:`fig:gc-heap-parts`).
250 .. fig:: fig:gc-heap-parts
252 Distintas partes de la memoria, incluyendo relación entre *basura*,
253 *live set*, *heap* y *root set*.
260 node [ shape = record, width = 0, height = 0 ];
262 subgraph cluster_heap {
268 subgraph cluster_live {
281 subgraph cluster_garbage {
286 node [ style = filled, fillcolor = white ];
291 subgraph cluster_root {
296 node [ style = filled, fillcolor = gray96 ];
300 r0 -> h1 -> h2 -> h5;
301 r1 -> h5 -> h6 -> h1;
308 Al proceso de visitar los vértices *conectados* desde el *root set* se lo
309 denomina *marcado*, *fase de marcado* o *mark phase* en inglés, debido
310 a que es necesario marcar los vértices para evitar visitar 2 veces el mismo
311 nodo en casos de que el grafo contenga ciclos [#gccycle]_. De forma similar
312 a la búsqueda, que puede realizarse *primero a lo ancho* (*breadth-first*)
313 o *primero a lo alto* (*depth-first*) del grafo, el marcado de un grafo
314 también puede realizarse de ambas maneras. Cada una podrá o no tener
315 efectos en la eficiencia, en particular dependiendo de la aplicación puede
316 convenir uno u otro método para lograr una mejor localidad de referencia
317 y de esta manera tener un mejor comportamiento de la memoria virtual o del
320 Un algoritmo simple (recursivo) de marcado *primero a lo alto* puede ser
321 el siguiente (asumiendo que partimos con todos los vértices sin marcar)
327 for (src, dst) in v.edges
334 Una vez concluido el marcado, sabemos que todos los vértices con la marca
335 son parte del *live set* y que todos los vértices no marcados son *basura*.
336 Esto es conocido también como **abstracción bicolor**, dado que en la
337 literatura se habla muchas veces de *colorear* las celdas. En general, una
338 celda sin marcar es de color blanco y una marcada de color negro.
340 Puede observarse un ejemplo del algoritmo en la figura
341 :vref:`fig:gc-mark-1`, en la cual se marca el sub-grafo apuntando por
342 ``r0``. Luego se marca el sub-grafo al que apunta ``r1`` (figura
343 :vref:`fig:gc-mark-2`), concluyendo con el marcado del grafo completo,
344 dejando sin marcar solamente las celdas *basura* (en blanco).
347 .. fig:: fig:gc-mark-1
349 Ejemplo de marcado del grafo de conectividad (parte 1).
353 Se comienza a marcar el grafo por la raíz r0.
360 node [ shape = record, width = 0, height = 0];
361 edge [ color = gray40 ];
363 subgraph cluster_all {
366 label = "root\nset|<r0> r0\n*|<r1> r1",
372 node [ style = filled, fillcolor = gray25, fontcolor = white ];
376 root:r0 -> h1 [ style = bold, color = black ];
377 h1 -> h2 -> h5 -> h1;
386 Luego de marcar el nodo ``h1``, se procede al ``h2``.
393 node [ shape = record, width = 0, height = 0 ];
394 edge [ color = gray40 ];
396 subgraph cluster_all {
399 label = "root\nset|<r0> r0\n*|<r1> r1",
405 node [ style = filled, fillcolor = gray25, fontcolor = white ];
409 root:r0 -> h1 [ color = gray10 ];
410 h1 -> h2 [ style = bold, color = black ];
420 Luego sigue el nodo h5.
427 node [ shape = record, width = 0, height = 0 ];
428 edge [ color = gray40 ];
430 subgraph cluster_all {
433 label = "root\nset|<r0> r0\n*|<r1> r1",
439 node [ style = filled, fillcolor = gray25, fontcolor = white ];
443 root:r0 -> h1 [ color = gray10 ];
444 h1 -> h2 [ color = gray10 ];
445 h2 -> h5 [ style = bold, color = black ];
454 .. fig:: fig:gc-mark-2
456 Ejemplo de marcado del grafo de conectividad (parte 2).
460 El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo
461 tanto no se visita nuevamente.
468 node [ shape = record, width = 0, height = 0 ];
469 edge [ color = gray40 ];
471 subgraph cluster_all {
474 label = "root\nset|<r0> r0\n*|<r1> r1",
480 node [ style = filled, fillcolor = gray25, fontcolor = white ];
484 root:r0 -> h1 [ color = gray10 ];
485 h1 -> h2 [ color = gray10 ];
486 h2 -> h5 [ color = gray10 ];
487 h5 -> h1 [ style = bold, color = black ];
496 Se concluye el marcado del sub-grafo al que conecta r0, se procede
497 a marcar el sub-grafo al que conecta r1, marcando al nodo h6.
504 node [ shape = record, width = 0, height = 0 ];
505 edge [ color = gray40 ];
507 subgraph cluster_all {
510 label = "root\nset|<r0> r0|<r1> r1\n*",
516 node [ style = filled, fillcolor = gray25, fontcolor = white ];
520 root:r0 -> h1 [ color = gray10 ];
521 h1 -> h2 [ color = gray10 ];
522 h2 -> h5 [ color = gray10 ];
523 h5 -> h1 [ color = gray10 ];
524 root:r1 -> h6 [ style = bold, color = black ];
533 El nodo h6 tiene una arista al h2, pero éste ya fue marcado por lo
534 que no se vuelve a visitar. No hay más raíces, se finaliza el marcado
542 node [ shape = record, width = 0, height = 0 ];
543 edge [ color = gray40 ];
545 subgraph cluster_all {
548 label = "root\nset|<r0> r0|<r1> r1\n*",
554 node [ style = filled, fillcolor = gray25, fontcolor = white ];
558 root:r0 -> h1 [ color = gray10 ];
559 h1 -> h2 [ color = gray10 ];
560 h2 -> h5 [ color = gray10 ];
561 h5 -> h1 [ color = gray10 ];
562 root:r1 -> h6 [ color = gray10 ];
563 h6 -> h2 [ style = bold, color = black ];
570 .. [#gccycle] Un ciclo es un camino donde el *vértice inicial* es el mismo
571 que el *vértice final*. Por lo tanto, los *vértices terminales* son
572 completamente arbitrarios, ya que cualquier *vértice interior* puede ser
573 un *vértice terminal*.
574 .. [#gcpseudo] Para presentar los algoritmos se utiliza una forma simple de
575 pseudo-código. El pseudo-código se escribe en inglés para que pueda ser
576 más fácilmente contrastado con la literatura, que está en inglés. Para
577 diferenciar posiciones de memoria y punteros de las celdas en sí, se usa
578 la misma sintaxis que C, ``r*`` denota una referencia o puntero y ``*r``
579 denota "objeto al que apunta ``r``\ ". Se sobreentiende que ``r = o``
580 siempre toma la dirección de memoria de ``o``.
587 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
589 Muchos algoritmos utilizan tres colores para realizar el marcado. El tercer
590 color, gris generalmente, indica que una celda debe ser visitada. Esto
591 permite algoritmos :ref:`concurrentes <ref_gc_concurrent>`
592 e :ref:`incrementales <ref_gc_inc>`, además de otro tipo de optimizaciones.
593 Entonces, lo que plantea esta abtracción es una nueva partición del heap al
594 momento de marcar, esta vez son 3 porciones: blanca, gris y negra.
596 Al principio todas las celdas se pintan de blanco, excepto el *root set*
597 que se punta de gris. Luego se van obteniendo celdas del conjunto de las
598 grises y se las pinta de negro, pintando sus hijas directas de gris.
600 Una vez que no hay más celdas grises, tenemos la garantía de que las celdas
601 negras serán el *live set* y las celdas blancas *basura*. Esto se debe
602 a que siempre se mantiene esta invariante: **ninguna celda negra apunta
603 directamente a una celda blanca**. Las celdas blancas siempre son apuntadas
604 por celdas blancas o grises. Entonces, siempre que el conjunto de celdas
605 grises sea vacío, no habrán celdas negras conectadas a blancas, siendo las
606 celdas blancas *basura*.
608 El algoritmo básico para marcar con tres colores es el siguiente (asumiendo
609 que todas las celdas parten pintadas de blanco, es decir, el conjunto
610 blanco contiene todas las celdas de memoria y los conjuntos negro y gris
616 while not gray_set.empty()
619 for (src, dst) in v.edges
624 Es simple notar que este algoritmo es naturalmente no recursivo, lo que de
625 por sí ya presenta una ventaja sobre el marcado *bicolor*.
632 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
634 En general todos los algoritmos de recolección de basura utilizan servicios
635 de una capa inferior [#gclowlayer]_ y proveen servicios a una capa superior
638 A continuación se presentan las primitivas en común que utilizan todos los
639 recolectores a lo largo de este documento.
641 Servicios utilizados por el recolector son los siguientes:
643 :math:`alloc() \to cell`:
644 obtiene una nueva celda de memoria. El mecanismo por el cual se obtiene
645 la celda es indistinto para esta sección, puede ser de una lista libre,
646 puede ser de un administrador de memoria de más bajo nivel provisto por
647 el sistema operativo o la biblioteca estándar de C (``malloc()``), etc.
648 Cómo organizar la memoria es un área de investigación completa y si bien
649 está estrechamente relacionada con la recolección de basura, en este
650 trabajo no se prestará particular atención a este aspecto (salvo casos
651 donde el recolector impone una cierta organización de memoria en el *low
652 level allocator*). Por simplicidad también asumiremos (a menos que se
653 indique lo contrario) que las celdas son de tamaño fijo. Esta restricción
654 normalmente puede ser fácilmente relajada (en los recolectores que la
658 libera una celda que ya no va a ser utilizada. La celda liberada debe
659 haber sido obtenida mediante ``alloc()``.
661 Y los servicios básicos proporcionados por el recolector son los
664 :math:`new() \to cell`:
665 obtiene una celda de memoria para ser utilizada por el programa.
667 :math:`update(ref, cell)`:
668 notifica al recolector que la referencia :math:`ref` ahora apunta
669 a :math:`cell`. Visto más formalmente, sería análogo a decir que hubo un
670 cambio en la conectividad del grafo: la arista :math:`src \to old` cambia
671 por :math:`src \to new` (donde :math:`src` es la celda que contiene la
672 referencia :math:`ref`, :math:`old` es la celda a la que apunta la
673 referencia :math:`ref` y :math:`new` es el argumento :math:`cell`). Si
674 :math:`cell` es ``null``, sería análogo a informar que se elimina la
675 arista :math:`src \to old`.
678 este servicio, según el algoritmo, puede ser utilizado para informar un
679 cambio en la conectividad del grafo, la eliminación de una arista
680 (análogo a :math:`update(ref, null)` pero sin proporcionar información
681 sobre la arista a eliminar). Esto es generalmente útil solo en
682 :ref:`conteo de referencias <ref_gc_rc>`. Para otros recolectores puede
683 significar que el usuario asegura que no hay más referencias a esta
684 celda, es decir, análogo a eliminar el conjunto de aristas
685 :math:`\big\lbrace (v, w) \in A , v \in Live \thickspace set , w \in
686 Live \thickspace set \big/ w = cell`.
689 indica al recolector que debe hacer un análisis del grafo de conectividad
690 en busca de *basura*. Generalmente este servicio es invocado por el
691 propio recolector cuando no hay más celdas reciclables.
693 No todos los servicios son implementados por todos los recolectores, pero
694 son lo suficientemente comunes como para describirlos de forma general en
695 esta sección. Algunos son principalmente ideados para uso interno del
696 recolector, aunque en ciertas circunstancias pueden ser utilizados por el
700 .. [#gclowlayer] En general estos servicios están provistos directamente
701 por el sistema operativo pero también pueden estar dados por un
702 administrador de memoria de bajo nivel (o *low level allocator* en
704 .. [#gchilayer] En general estos servicios son utilizados directamente por
705 el lenguaje de programación, pero pueden ser utilizados directamente por
706 el usuario del lenguaje si éste interatúa con el recolector, ya sea por
707 algún requerimiento particular o porque el lenguaje no tiene soporte
708 diercto de recolección de basura y el recolector está implementado como
709 una biblioteca de usuario.
716 ----------------------------------------------------------------------------
718 En la literatura se encuentran normalmente referencias a 3 algoritmos
719 clásicos, que son utilizados generalmente como bloques básicos para
720 construir recolectores más complejos. Se presentan las versiones históricas
721 más simples a fin de facilitar la comprensión conceptual.
727 Conteo de referencias
728 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
730 Se trata del algoritmo más antiguo de todos, implementado por primera vez
731 por `John McCarthy`_ para Lisp_ a finales de 1950. Se trata de un método
732 :ref:`directo <ref_gc_direct>` e :ref:`incremental <ref_gc_inc>` por
733 naturaleza, ya que distribuye la carga de la recolección de basura durante
734 toda la ejecución del programa, cada vez que el *mutator* cambia la
735 conectividad de algún nodo del grafo de conectividad.
737 El método consiste en tener un contador asociado a cada celda que contenga
738 la cantidad de celdas **vivas** que apuntan a ésta. Es decir, es la
739 cardinalidad del conjunto de aristas que tienen por destino a la celda.
740 Formalmente podemos definir el contador :math:`rc(v)` (de *reference
741 counter* en inglés) de la siguiente manera:
747 (v_1, v_2) \in A \big/
748 v_1 \in Live \thickspace set \cup Root \thickspace set
753 El *mutator* entonces debe actualizar este contador cada vez que el grafo
754 de conectividad cambia, es decir, cada vez que se agrega, modifica
755 o elimina una arista del grafo (o visto de una forma más cercana al código,
756 cada vez que se agrega, modifica o elimina un puntero).
758 Esta invariante es fundamental para el conteo de referencias, porque se
759 asume que si el contador es 0 entonces el *mutator* no tiene ninguna
760 referencia a la celda y por lo tanto es *basura*:
764 rc(v) = 0 \Rightarrow v \in Basura
766 Para mantener esta invariante el *mutator*, cada vez que cambia un puntero
767 debe decrementar en 1 el contador de la celda a la que apuntaba
768 antiguamente e incrementar en 1 el contador de la celda a la que apunta
769 luego de la modificación. Esto asegura que la invariante se mantenga
770 durante toda la ejecución del programa. Si al momento de decrementar un
771 contador éste queda en 0, la celda asociada debe liberarse de forma de
772 poder ser reciclada. Esto implica que si esta celda almacena punteros, los
773 contadores de las celdas apuntadas deben ser decrementados también, porque
774 solo deben almacenarse en el contador las aristas del *live set* para
775 mantener la invariante. De esto puede resultar que otros contadores de
776 referencia queden en 0 y más celdas sean liberadas. Por lo tanto,
777 teóricamente la complejidad de eliminar una referencia puede ser
778 :math:`O(\lvert Live \thickspace set \rvert)` en el peor caso.
780 Las primitivas implementadas para este tipo de recolector son las
781 siguientes (acompañadas de una implementación básica)::
791 cell.rc = cell.rc - 1
793 for child* in cell.children
798 cell.rc = cell.rc + 1
806 A continuación se presenta un ejemplo gráfico para facilitar la comprensión
807 del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos
808 punteros, ``left`` (``l``) y ``right`` (``r``) y se muestra el contador de
809 referencias abajo del nombre de cada celda. Se parte con una pequeña
810 estructura ya construída y se muestra como opera el algoritmo al eliminar
811 o cambiar una referencia (cambios en la conectividad del grafo). En un
812 comienzo todas las celdas son accesibles desde el *root set* por lo tanto
813 son todas parte del *live set*.
815 Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina
816 que ``h1`` se convirtió en *basura* (figura :vref:`fig:gc-rc-rm-1`). Esto
817 conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
818 *live set* ya que sus contadores siguen siendo mayores a 0 (figura
819 :vref:`fig:gc-rc-rm-2`).
822 .. fig:: fig:gc-rc-rm-1
824 Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
828 Estado inicial del grafo de conectividad.
835 edge [ color = gray40 ];
845 subgraph cluster_all {
848 label = "root\nset|<r0> r0|<r1> r1",
854 h1 [ label = "h1\n1|<l> l|<r> r" ];
855 h2 [ label = "h2\n2|<l> l|<r> r" ];
856 h3 [ label = "h3\n2|<l> l|<r> r" ];
857 h4 [ label = "h4\n1|<l> l|<r> r" ];
858 h5 [ label = "h5\n1|<l> l|<r> r" ];
859 h6 [ label = "h6\n1|<l> l|<r> r" ];
874 Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
882 edge [ color = gray40 ];
892 subgraph cluster_all {
895 label = "root\nset|<r0> r0\n*|<r1> r1",
901 h1 [ label = "h1\n1|<l> l|<r> r" ];
902 h2 [ label = "h2\n2|<l> l|<r> r" ];
903 h3 [ label = "h3\n2|<l> l|<r> r" ];
904 h4 [ label = "h4\n1|<l> l|<r> r" ];
905 h5 [ label = "h5\n1|<l> l|<r> r" ];
906 h6 [ label = "h6\n1|<l> l|<r> r" ];
908 root:r0 -> h1 [ style = bold, color = black ];
921 Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser
922 *basura*). Se elimina primero ``h1.l`` y luego ``h1.r``.
929 edge [ color = gray40 ];
939 subgraph cluster_all {
942 label = "root\nset|<r0> r0\n*|<r1> r1",
949 node [ fillcolor = white, fontcolor = black ];
953 h1 [ label = "h1\n0|<l> l|<r> r" ];
954 h2 [ label = "h2\n2|<l> l|<r> r" ];
955 h3 [ label = "h3\n2|<l> l|<r> r" ];
956 h4 [ label = "h4\n1|<l> l|<r> r" ];
957 h5 [ label = "h5\n1|<l> l|<r> r" ];
958 h6 [ label = "h6\n1|<l> l|<r> r" ];
960 root:r0 -> h1 [ style = invis ];
962 h1:l -> h2 [ style = bold, color = black ];
972 .. fig:: fig:gc-rc-rm-2
974 Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
978 Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en
986 edge [ color = gray40 ];
996 subgraph cluster_all {
999 label = "root\nset|<r0> r0\n*|<r1> r1",
1006 node [ fillcolor = white, fontcolor = black ];
1010 h1 [ label = "h1\n0|<l> l|<r> r" ];
1011 h2 [ label = "h2\n1|<l> l|<r> r" ];
1012 h3 [ label = "h3\n2|<l> l|<r> r" ];
1013 h4 [ label = "h4\n1|<l> l|<r> r" ];
1014 h5 [ label = "h5\n1|<l> l|<r> r" ];
1015 h6 [ label = "h6\n1|<l> l|<r> r" ];
1017 root:r0 -> h1 [ style = invis ];
1019 h1:l -> h2 [ style = invis ];
1020 h1:r -> h3 [ style = bold, color = black ];
1030 El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.
1037 edge [ color = gray40 ];
1047 subgraph cluster_all {
1050 label = "root\nset|<r0> r0|<r1> r1",
1057 node [ fillcolor = white, fontcolor = black ];
1061 h1 [ label = "h1\n0|<l> l|<r> r" ];
1062 h2 [ label = "h2\n1|<l> l|<r> r" ];
1063 h3 [ label = "h3\n1|<l> l|<r> r" ];
1064 h4 [ label = "h4\n1|<l> l|<r> r" ];
1065 h5 [ label = "h5\n1|<l> l|<r> r" ];
1066 h6 [ label = "h6\n1|<l> l|<r> r" ];
1068 root:r0 -> h1 [ style = invis ];
1070 h1:l -> h2 [ style = invis ];
1071 h1:r -> h3 [ style = invis ];
1080 Luego se cambia una referencia (en vez de eliminarse) realizándose la
1081 operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador
1082 de referencias de ``h5`` para evitar confundirlo accidentalmente con
1083 *basura* si se elimina alguna celda que apuntaba a ésta. Luego se procede
1084 a decrementar el contador de ``h2`` que queda en 0, transformándose en
1085 *basura* (figura :vref:`fig:gc-rc-up-1`). Lo mismo pasa cuando se desciende
1086 a ``h4``, pero al descender a ``h5`` y decrementar el contador, éste sigue
1087 siendo mayor que 0 (pues ``h3`` va a apuntar a ``h5``) así que permanece en
1088 el *live set*. Finalmente se termina de actualizar la referencia ``h3.l``
1089 para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
1092 .. fig:: fig:gc-rc-up-1
1094 Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
1095 :math:`\to` ``h5`` (parte 1).
1099 Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.
1106 edge [ color = gray40 ];
1116 subgraph cluster_all {
1119 label = "root\nset|<r0> r0|<r1> r1",
1126 node [ fillcolor = white, fontcolor = black ];
1130 h1 [ label = "h1\n0|<l> l|<r> r" ];
1131 h2 [ label = "h2\n1|<l> l|<r> r" ];
1132 h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
1133 h4 [ label = "h4\n1|<l> l|<r> r" ];
1134 h5 [ label = "h5\n2|<l> l|<r> r" ];
1135 h6 [ label = "h6\n1|<l> l|<r> r" ];
1137 root:r0 -> h1 [ style = invis ];
1138 h1:l -> h2 [ style = invis ];
1139 h1:r -> h3 [ style = invis ];
1144 h3:l -> h5 [ style = dotted, color = black ];
1151 Luego se procede a visitar las hijas de ``h3``, comenzando por ``h2``.
1158 edge [ color = gray40 ];
1168 subgraph cluster_all {
1171 label = "root\nset|<r0> r0|<r1> r1",
1178 node [ fillcolor = white, fontcolor = black ];
1182 h1 [ label = "h1\n0|<l> l|<r> r" ];
1183 h2 [ label = "h2\n1|<l> l|<r> r" ];
1184 h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
1185 h4 [ label = "h4\n1|<l> l|<r> r" ];
1186 h5 [ label = "h5\n2|<l> l|<r> r" ];
1187 h6 [ label = "h6\n1|<l> l|<r> r" ];
1189 root:r0 -> h1 [ style = invis ];
1190 h1:l -> h2 [ style = invis ];
1191 h1:r -> h3 [ style = invis ];
1195 h3:l -> h2 [ style = bold, color = black ];
1196 h3:l -> h5 [ style = dotted, color = black ];
1203 Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser
1204 *basura*). Se eliminan las referencias a las hijas.
1211 edge [ color = gray40 ];
1221 subgraph cluster_all {
1224 label = "root\nset|<r0> r0|<r1> r1",
1231 node [ fillcolor = white, fontcolor = black ];
1235 h1 [ label = "h1\n0|<l> l|<r> r" ];
1236 h2 [ label = "h2\n1|<l> l|<r> r" ];
1237 h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
1238 h4 [ label = "h4\n1|<l> l|<r> r" ];
1239 h5 [ label = "h5\n2|<l> l|<r> r" ];
1240 h6 [ label = "h6\n1|<l> l|<r> r" ];
1242 root:r0 -> h1 [ style = invis ];
1243 h1:l -> h2 [ style = invis ];
1244 h1:r -> h3 [ style = invis ];
1246 h2:l -> h4 [ style = bold, color = black ];
1248 h3:l -> h2 [ style = invis ];
1249 h3:l -> h5 [ style = dotted, color = black ];
1255 .. fig:: fig:gc-rc-up-2
1257 Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
1258 :math:`\to` ``h5`` (parte 2).
1262 Se decrementa el contador de ``h4`` quedando en 0, pasa a ser
1263 *basura*. Se continúa con ``h5``.
1270 edge [ color = gray40 ];
1280 subgraph cluster_all {
1283 label = "root\nset|<r0> r0|<r1> r1",
1290 node [ fillcolor = white, fontcolor = black ];
1294 h1 [ label = "h1\n0|<l> l|<r> r" ];
1295 h2 [ label = "h2\n1|<l> l|<r> r" ];
1296 h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
1297 h4 [ label = "h4\n0|<l> l|<r> r" ];
1298 h5 [ label = "h5\n2|<l> l|<r> r" ];
1299 h6 [ label = "h6\n1|<l> l|<r> r" ];
1301 root:r0 -> h1 [ style = invis ];
1302 h1:l -> h2 [ style = invis ];
1303 h1:r -> h3 [ style = invis ];
1305 h2:l -> h4 [ style = invis ];
1306 h2:r -> h5 [ style = bold, color = black ];
1307 h3:l -> h2 [ style = invis ];
1308 h3:l -> h5 [ style = dotted, color = black ];
1315 Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.
1322 edge [ color = gray40 ];
1332 subgraph cluster_all {
1335 label = "root\nset|<r0> r0|<r1> r1",
1342 node [ fillcolor = white, fontcolor = black ];
1346 h1 [ label = "h1\n0|<l> l|<r> r" ];
1347 h2 [ label = "h2\n1|<l> l|<r> r" ];
1348 h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
1349 h4 [ label = "h4\n0|<l> l|<r> r" ];
1350 h5 [ label = "h5\n1|<l> l|<r> r" ];
1351 h6 [ label = "h6\n1|<l> l|<r> r" ];
1353 root:r0 -> h1 [ style = invis ];
1354 h1:l -> h2 [ style = invis ];
1355 h1:r -> h3 [ style = invis ];
1357 h2:l -> h4 [ style = invis ];
1358 h2:r -> h5 [ style = invis ];
1359 h3:l -> h5 [ style = bold, color = black ];
1360 h3:l -> h2 [ style = invis ];
1367 Se termina por actualizar la referencia de ``h3.l`` para que apunte
1375 edge [ color = gray40 ];
1385 subgraph cluster_all {
1388 label = "root\nset|<r0> r0|<r1> r1",
1395 node [ fillcolor = white, fontcolor = black ];
1399 h1 [ label = "h1\n0|<l> l|<r> r" ];
1400 h1 [ label = "h1\n0|<l> l|<r> r" ];
1401 h2 [ label = "h2\n0|<l> l|<r> r" ];
1402 h3 [ label = "h3\n1|<l> l|<r> r" ];
1403 h4 [ label = "h4\n0|<l> l|<r> r" ];
1404 h5 [ label = "h5\n1|<l> l|<r> r" ];
1405 h6 [ label = "h6\n1|<l> l|<r> r" ];
1407 root:r0 -> h1 [ style = invis ];
1408 h1:l -> h2 [ style = invis ];
1409 h1:r -> h3 [ style = invis ];
1411 h2:l -> h4 [ style = invis ];
1412 h2:r -> h5 [ style = invis ];
1414 h3:l -> h2 [ style = invis ];
1422 TODO El problema de los ciclos
1426 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1433 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1440 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1447 ----------------------------------------------------------------------------
1449 La cantidad de clasificaciones que pueden hacerse respecto a algoritmos de
1450 recolección de basura son muy grandes. Muchas de estas clasificaciones se
1451 superponen entre sí, habiendo algoritmos que aplican muchas técnicas a la
1452 vez o recolectores híbridos que aplican una técnica para algún tipo de
1453 objeto y otra para otros.
1455 A continuación se enumeran las clasificaciones más importantes que se
1456 pudieron observar en la investigación sobre el `estado del arte`_.
1461 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1463 Generalmente se llama recolección **directa** a aquella en la cual el
1464 compilador o lenguaje instrumenta al *mutator* de forma tal que la
1465 información de conectividad se mantenga activamente cada vez que hay un
1466 cambio en él. Normalmente se utiliza un contador de referencia en cada
1467 celda para este propósito, permitiendo almacenar en todo momento la
1468 cantidad de nodos que apuntan a ésta (dejando de lado el :ref:`problema de
1469 los ciclos <ref_gc_cycles>`). Esto permite reclamar una celda
1470 instantáneamente cuando el *mutator* deja de hacer referencia a ella. Este
1471 tipo de recolectores son, inherentemente :ref:`incrementales <ref_gc_inc>`.
1473 Por el contrario, los recolectores **indirectos** normalmente no
1474 interfieren con el *mutator* en cada actualización del grafo de
1475 conectividad (exceptuando algunos :ref:`recolectores incrementales
1476 <ref_gc_inc>` que a veces necesitan instrumentar el *mutator* pero no para
1477 mantener el estado del grafo de conectividad completo). La recolección se
1478 dispara usualmente cuando el *mutator* requiere alocar memoria pero no hay
1479 más memoria libre conocida disponible y el recolector se encarga de generar
1480 la información de conectividad desde cero para determinar qué celdas son
1483 Estas son las dos grandes familias de recolectores, también conocidos como
1484 `conteo de referencias`_ (directa) y *traicing garbage collection*
1491 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1493 Recolección incremental es aquella que se realiza de forma intercalada con
1494 el *mutator*. En general el propósito es disminuir el tiempo de las pausas
1495 causadas por el recolector (aunque generalmente el resultado es un mayor
1496 costo en tiempo total de recolección).
1498 De los `algoritmos clásicos`_ el único que es incremental en su forma más
1499 básica es el `conteo de referencias`_. Otros recolectores pueden hacerse
1500 incrementales de diversas maneras, pero en general consta de hacer parte
1501 del trabajo de escanear el grafo de conectividad cada vez que el *mutator*
1502 aloca memoria. En general para hacer esto es también necesario instrumentar
1503 al *mutator* de forma tal que informe al recolector cada vez que cambia el
1504 grafo de conectividad, para que éste pueda marcar al sub-grafo afectado por
1505 el cambio como *desactualizado* y así re-escanearlo nuevamente en la
1508 En general la eficiencia de los recolectores incrementales disminuye
1509 considerablemente cuando el *mutator* actualiza muy seguido el grafo de
1510 conectividad, porque debe re-escanear sub-grafos que ya había escaneado una
1511 y otra vez. A esto se debe también que en general el tiempo de
1512 procesamiento total de un recolector incremental sea mayor que uno no
1513 incremental, aunque el tiempo de pausa de una recolección sea menor.
1516 .. _ref_gc_concurrent:
1518 Concurrente / *stop-the-world*
1519 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1521 Los recolectores concurrentes son aquellos que pueden correr en paralelo
1522 con el *mutator*. Por el contrario, aquellos que pausan el *mutator* para
1523 realizar la recolección son usualmente denominados *stop-the-world* (*parar
1524 el mundo*), haciendo referencia a que pausan todos los hilos del *mutator*
1525 para poder escanear el grafo de conectividad de forma consistente.
1527 Para lograr que un recolector sea concurrente generalmente el mecanismo es
1528 similar al necesario para hacer un :ref:`recolector incremental
1529 <ref_gc_inc>`: hay que instrumentar al *mutator* para que informe al
1530 recolector cuando se realiza algún cambio en el grafo de conectividad, de
1531 forma tal que pueda volver a escanear el sub-grafo afectado por el cambio.
1533 Esto también trae como consecuencia el incremento en el tiempo total que
1534 consume el recolector, debido a la necesidad de re-escanear sub-grafos que
1535 han sido modificados.
1540 ----------------------------------------------------------------------------
1542 .. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
1550 1. Instrumentar el *mutator* de forma tal de que informe al recolector cada
1551 vez que cambia el grafo de conectividad, de manera que pueda re-escanear
1552 el sub-grafo que afectado por el cambio.
1554 2. Tomar una foto de la memoria y escanear esa foto estática en vez de la
1555 memoria original, de forma que cualquier cambio en del *mutator* no
1556 afecte la vista de la memoria del recolector.
1558 Ambos métodos tienen ventajas y desventajas. El primero no necesita hacer
1559 una copia costosa de la memoria, pero existe la posibilidad de que el
1560 recolector nunca pueda escanear el grafo de conectividad completo, si el
1561 *mutator* modifica el grafo más rápido de lo que el recolector lo escanea.
1562 Si bien hay formas de evitar esto, es usual que el trabajo de recolección
1563 se vea considerablemente incrementado por la cantidad de veces que hay que
1564 re-escanear el grafo. El segundo método puede ser costoso por las copias
1565 necesarias (aunque esto puede ser mitigado empleando alguna forma de *COW*
1566 [#gccow]_) y existe la posibilidad de que no se recuperen celdas que el
1570 .. [#gccow] *COW* (del inglés *Copy On Write* o *copiar al escribir*) es
1571 una técnica muy utilizada para disminuir las copias innecesarias,
1572 evitando hacer la copia hasta que haya una modificación. Mientras no
1573 hayan modificaciones no es necesario realizar una copia porque todos los
1574 interesados verán la misma información. Esta técnica es utilizada por el
1575 *kernel* de Linux_ por ejemplo, para que varias instancias de un mismo
1576 proceso puedan compartir la memoria.
1579 Boehm, H., and M. Weiser, "Garbage Collection in an Uncooperative
1580 Environment", Software Practice & Experience, September 1988, pp. 807-820.
1581 http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/preprint.pdf
1582 (http://www.hpl.hp.com/personal/Hans_Boehm/spe_gc_paper/)
1584 Boehm, H., "Space Efficient Conservative Garbage Collection", Proceedings
1585 of the ACM SIGPLAN '93 Conference on Programming Language Design and
1586 Implementation, SIGPLAN Notices 28, 6 (June 1993), pp. 197-206.
1587 http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi93.ps.Z
1589 Boehm, H., A. Demers, and S. Shenker, "Mostly Parallel Garbage Collection",
1590 Proceedings of the ACM SIGPLAN '91 Conference on Programming Language
1591 Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 157-164.
1592 http://www.hpl.hp.com/personal/Hans_Boehm/gc/papers/pldi91.ps.Z
1594 Implementación de Bohem GC
1595 http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html
1597 Interfaz de Bohem GC
1598 http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html
1601 .. include:: links.rst
1603 .. vim: set ts=3 sts=3 sw=3 et tw=75 :