]> git.llucax.com Git - z.facultad/75.00/informe.git/blob - source/gc.rst
Completar ejemplo de conteo de referencias
[z.facultad/75.00/informe.git] / source / gc.rst
1
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.
5    ESTADO: SIN EMPEZAR
6
7 .. _ref_gc:
8
9 Recolección de basura
10 ============================================================================
11
12
13 Introducción
14 ----------------------------------------------------------------------------
15
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).
19
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.
28
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]_.
34
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
43 investigaciones).
44
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.
58
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.
65
66
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
78    impredecibles.
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
85    objeto.
86
87
88
89 Conceptos básicos
90 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
91
92 Los programas pueden hacer uso principalmente de 4 áreas de memoria:
93
94 Registros:
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.
101
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
111    procesador).
112
113 *Stack* (pila):
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
122    que aquella.
123
124 *Heap*:
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.
129
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*).
135
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*.
141
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:
145
146 .. math::
147
148    M \to N \Longleftrightarrow M \text{ almacena un puntero a } N
149
150 El conjunto de celdas vivas (o *live set*) queda determinado por:
151
152 .. math::
153
154    vivas = \left\lbrace N \in Celdas \big/
155       ( \exists r \in Raices / r \to N ) \vee (\exists M \in vivas / M \to N )
156    \right\rbrace
157
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
166 basura conservativo.
167
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).
174
175
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).
182
183
184
185 Recorrido del grafo de conectividad
186 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
187
188 El problema de encontrar las celdas *vivas* de un programa se reduce a recorrer
189 un grafo dirigido. El grafo se define como:
190
191 .. math::
192
193    G = (V,A)
194
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).
198
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
201 *basura*.
202
203 Más formalmente, Definimos:
204
205 *Camino*:
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
210    interior*.
211
212    .. math::
213
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
217       \right\rbrace
218
219 *Conexión*:
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`.
222
223    .. math::
224
225       M \mapsto N \Longleftrightarrow \exists \underset{M \to N}{C} \in G
226
227 *Live set*:
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.
231
232    .. math::
233
234       Live \thickspace set = \left\lbrace v \in V \big/
235          \left( \exists r \in Root \thickspace set \big/ r \mapsto v \right)
236       \right\rbrace
237
238 *Basura*:
239    la basura, o celdas *muertas*, quedan determinadas entonces por todas las
240    celdas del *heap* que no son parte del *live set*.
241
242    .. math::
243
244       Basura = V - Live \thickspace set
245
246 Esto es, efectivamente, una partición del *heap* (ver figura
247 :vref:`fig:gc-heap-parts`).
248
249
250 .. fig:: fig:gc-heap-parts
251
252    Distintas partes de la memoria, incluyendo relación entre *basura*,
253    *live set*, *heap* y *root set*.
254
255    .. digraph:: g1
256
257       margin  = 0;
258       ratio   = fill;
259       size    = "4.6,3.6";
260       node [ shape = record, width = 0, height = 0 ];
261
262       subgraph cluster_heap {
263          label = "Heap";
264          style     = dashed;
265          color     = gray40;
266          fontcolor = gray40;
267
268          subgraph cluster_live {
269             label     = "Live set";
270             style     = dashed;
271             color     = gray40;
272             fontcolor = gray40;
273             node [
274                style     = filled,
275                fillcolor = gray25,
276                fontcolor = white,
277             ];
278             h1; h2; h4; h5; h6;
279          }
280
281          subgraph cluster_garbage {
282             label     = "Basura";
283             style     = dashed;
284             color     = gray40;
285             fontcolor = gray40;
286             node [ style = filled, fillcolor = white ];
287             h7; h3;
288          }
289       }
290
291       subgraph cluster_root {
292          label     = "Root set";
293          style     = dashed;
294          color     = gray40;
295          fontcolor = gray40;
296          node [ style = filled, fillcolor = gray96 ];
297          r0; r1; r2;
298       }
299
300       r0 -> h1 -> h2 -> h5;
301       r1 -> h5 -> h6 -> h1;
302       r2 -> h4;
303       h5 -> h4;
304       h7 -> h1;
305       h7 -> h3;
306
307
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
318 *caché*.
319
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)
322 [#gcpseudo]_::
323
324    mark(v)
325       if not v.marked
326          v.marked = true
327          for (src, dst) in v.edges
328             mark(dst)
329
330    mark_phase()
331       for r in root_set
332          mark(r)
333
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.
339
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).
345
346
347 .. fig:: fig:gc-mark-1
348
349    Ejemplo de marcado del grafo de conectividad (parte 1).
350
351    .. subfig::
352
353       Se comienza a marcar el grafo por la raíz r0.
354
355       .. digraph:: g2_1
356
357          margin = 0;
358          ratio  = fill;
359          size   = "1.9,2.6";
360          node [ shape = record, width = 0, height = 0];
361          edge [ color = gray40 ];
362
363          subgraph cluster_all {
364
365             root [
366                label     = "root\nset|<r0> r0\n*|<r1> r1",
367                style     = filled,
368                fillcolor = gray96,
369             ];
370
371             subgraph marked {
372                node [ style = filled, fillcolor = gray25, fontcolor = white ];
373                h1;
374             };
375
376             root:r0 -> h1 [ style = bold, color = black ];
377             h1 -> h2 -> h5 -> h1;
378             root:r1 -> h6 -> h2;
379             h4 -> h3;
380             h3 -> h5;
381
382          }
383
384    .. subfig::
385
386       Luego de marcar el nodo ``h1``, se procede al ``h2``.
387
388       .. digraph:: g2_2
389
390          margin = 0;
391          ratio  = fill;
392          size   = "1.9,2.6";
393          node [ shape = record, width = 0, height = 0 ];
394          edge [ color = gray40 ];
395
396          subgraph cluster_all {
397
398             root [
399                label     = "root\nset|<r0> r0\n*|<r1> r1",
400                style     = filled,
401                fillcolor = gray96,
402             ];
403
404             subgraph marked {
405                node [ style = filled, fillcolor = gray25, fontcolor = white ];
406                h1; h2;
407             };
408
409             root:r0 -> h1 [ color = gray10 ];
410             h1 -> h2 [ style = bold, color = black ];
411             h2 -> h5 -> h1;
412             root:r1 -> h6 -> h2;
413             h4 -> h3;
414             h3 -> h5;
415
416          }
417
418    .. subfig::
419
420       Luego sigue el nodo h5.
421
422       .. digraph:: g2_3
423
424          margin = 0;
425          ratio  = fill;
426          size   = "1.9,2.6";
427          node [ shape = record, width = 0, height = 0 ];
428          edge [ color = gray40 ];
429
430          subgraph cluster_all {
431
432             root [
433                label     = "root\nset|<r0> r0\n*|<r1> r1",
434                style     = filled,
435                fillcolor = gray96,
436             ];
437
438             subgraph marked {
439                node [ style = filled, fillcolor = gray25, fontcolor = white ];
440                h1; h2; h5;
441             };
442
443             root:r0 -> h1 [ color = gray10 ];
444             h1 -> h2 [ color = gray10 ];
445             h2 -> h5 [ style = bold, color = black ];
446             h5 -> h1;
447             root:r1 -> h6 -> h2;
448             h4 -> h3;
449             h3 -> h5;
450
451          }
452
453
454 .. fig:: fig:gc-mark-2
455
456    Ejemplo de marcado del grafo de conectividad (parte 2).
457
458    .. subfig::
459
460       El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo
461       tanto no se visita nuevamente.
462
463       .. digraph:: g2_4
464
465          margin = 0;
466          ratio  = fill;
467          size   = "1.9,2.6";
468          node [ shape = record, width = 0, height = 0 ];
469          edge [ color = gray40 ];
470
471          subgraph cluster_all {
472
473             root [
474                label     = "root\nset|<r0> r0\n*|<r1> r1",
475                style     = filled,
476                fillcolor = gray96,
477             ];
478
479             subgraph marked {
480                node [ style = filled, fillcolor = gray25, fontcolor = white ];
481                h1; h2; h5;
482             };
483
484             root:r0 -> h1 [ color = gray10 ];
485             h1 -> h2 [ color = gray10 ];
486             h2 -> h5 [ color = gray10 ];
487             h5 -> h1 [ style = bold, color = black ];
488             root:r1 -> h6 -> h2;
489             h4 -> h3;
490             h3 -> h5;
491
492          }
493
494    .. subfig::
495
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.
498
499       .. digraph:: g2_5
500
501          margin = 0;
502          ratio  = fill;
503          size   = "1.9,2.6";
504          node [ shape = record, width = 0, height = 0 ];
505          edge [ color = gray40 ];
506
507          subgraph cluster_all {
508
509            root [
510               label     = "root\nset|<r0> r0|<r1> r1\n*",
511               style     = filled,
512               fillcolor = gray96,
513            ];
514
515            subgraph marked {
516               node [ style = filled, fillcolor = gray25, fontcolor = white ];
517               h1; h2; h5; h6;
518            };
519
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 ];
525            h6 -> h2;
526            h4 -> h3;
527            h3 -> h5;
528
529          }
530
531    .. subfig::
532
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
535       del grafo.
536
537       .. digraph:: g2_6
538
539          margin = 0;
540          ratio  = fill;
541          size   = "1.9,2.6";
542          node [ shape = record, width = 0, height = 0 ];
543          edge [ color = gray40 ];
544
545          subgraph cluster_all {
546
547             root [
548                label     = "root\nset|<r0> r0|<r1> r1\n*",
549                style     = filled,
550                fillcolor = gray96,
551             ];
552
553             subgraph marked {
554                node [ style = filled, fillcolor = gray25, fontcolor = white ];
555                h1; h2; h5; h6;
556             };
557
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 ];
564             h4 -> h3;
565             h3 -> h5;
566
567          }
568
569
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``.
581
582
583
584 .. _ref_gc_tricolor:
585
586 Abstracción tricolor
587 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
588
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.
595
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.
599
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*.
607
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
611 están vacíos)::
612
613    mark_phase()
614       for r in root_set
615          gray_set.add(r)
616       while not gray_set.empty()
617          v = gray_set.pop()
618          black_set.add(v)
619          for (src, dst) in v.edges
620             if v in white_set
621                white_set.remove(v)
622                gray_set.add(v)
623
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*.
626
627
628
629 .. _ref_gc_services:
630
631 Servicios
632 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
633
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
636 [#gchilayer]_.
637
638 A continuación se presentan las primitivas en común que utilizan todos los
639 recolectores a lo largo de este documento.
640
641 Servicios utilizados por el recolector son los siguientes:
642
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
655    tienen).
656
657 :math:`free(cell)`:
658    libera una celda que ya no va a ser utilizada. La celda liberada debe
659    haber sido obtenida mediante ``alloc()``.
660
661 Y los servicios básicos proporcionados por el recolector son los
662 siguientes:
663
664 :math:`new() \to cell`:
665    obtiene una celda de memoria para ser utilizada por el programa.
666
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`.
676
677 :math:`del(cell)`:
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`.
687
688 :math:`collect()`:
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.
692
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
697 usuario también.
698
699
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
703    inglés).
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.
710
711
712
713 .. _ref_gc_clasic:
714
715 Algoritmos clásicos
716 ----------------------------------------------------------------------------
717
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.
722
723
724
725 .. _ref_gc_rc:
726
727 Conteo de referencias
728 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
729
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.
736
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:
742
743 .. math::
744
745    rc(v) = \big\lvert
746       \left\lbrace
747          (v_1, v_2) \in A \big/
748             v_1 \in Live \thickspace set \cup Root \thickspace set
749                \wedge v_2 = v
750       \right\rbrace
751    \big\rvert
752
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).
757
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*:
761
762 .. math::
763
764    rc(v) = 0 \Rightarrow v \in Basura
765
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.
779
780 Las primitivas implementadas para este tipo de recolector son las
781 siguientes (acompañadas de una implementación básica)::
782
783    new()
784       cell = alloc()
785       if cell is null
786          throw out_of_memory
787       cell.rc = 1
788       return cell
789
790    del(cell)
791       cell.rc = cell.rc - 1
792       if cell.rc is 0
793          for child* in cell.children
794             del(*child)
795          free(cell)
796
797    update(ref*, cell)
798       cell.rc = cell.rc + 1
799       del(*ref)
800       *ref = cell
801
802
803 Ejemplo
804 ^^^^^^^
805
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*.
814
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`).
820
821
822 .. fig:: fig:gc-rc-rm-1
823
824    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
825
826    .. subfig::
827
828       Estado inicial del grafo de conectividad.
829
830       .. digraph:: g3_1
831
832          margin = 0;
833          ratio  = fill;
834          size   = "1.9,2.6";
835          edge [ color = gray40 ];
836          node [
837             shape     = record,
838             width     = 0,
839             height    = 0,
840             style     = filled,
841             fillcolor = gray25,
842             fontcolor = white
843          ];
844
845          subgraph cluster_all {
846
847             root [
848                label     = "root\nset|<r0> r0|<r1> r1",
849                style     = filled,
850                fillcolor = gray96,
851                fontcolor = black,
852             ];
853
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" ];
860
861             root:r0 -> h1;
862             root:r1 -> h3;
863             h1:l -> h2;
864             h1:r -> h3;
865             h2:l -> h4;
866             h2:r -> h5;
867             h3:l -> h2;
868             h3:r -> h6;
869
870          }
871
872    .. subfig::
873
874       Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
875       ``h1``.
876
877       .. digraph:: g3_2
878
879          margin = 0;
880          ratio  = fill;
881          size   = "1.9,2.6";
882          edge [ color = gray40 ];
883          node [
884             shape     = record,
885             width     = 0,
886             height    = 0,
887             style     = filled,
888             fillcolor = gray25,
889             fontcolor = white
890          ];
891
892          subgraph cluster_all {
893
894             root [
895                label     = "root\nset|<r0> r0\n*|<r1> r1",
896                style     = filled,
897                fillcolor = gray96,
898                fontcolor = black,
899             ];
900
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" ];
907
908             root:r0 -> h1 [ style = bold, color = black ];
909             root:r1 -> h3;
910             h1:l -> h2;
911             h1:r -> h3;
912             h2:l -> h4;
913             h2:r -> h5;
914             h3:l -> h2;
915             h3:r -> h6;
916
917          }
918
919    .. subfig::
920
921       Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser
922       *basura*). Se elimina primero ``h1.l`` y luego ``h1.r``.
923
924       .. digraph:: g3_3
925
926          margin = 0;
927          ratio  = fill;
928          size   = "1.9,2.6";
929          edge [ color = gray40 ];
930          node [
931             shape     = record,
932             width     = 0,
933             height    = 0,
934             style     = filled,
935             fillcolor = gray25,
936             fontcolor = white
937          ];
938
939          subgraph cluster_all {
940
941             root [
942                label     = "root\nset|<r0> r0\n*|<r1> r1",
943                style     = filled,
944                fillcolor = gray96,
945                fontcolor = black,
946             ];
947
948             subgraph marked {
949                node [ fillcolor = white, fontcolor = black ];
950                h1;
951             };
952
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" ];
959
960             root:r0 -> h1 [ style = invis ];
961             root:r1 -> h3;
962             h1:l -> h2 [ style = bold, color = black ];
963             h1:r -> h3;
964             h2:l -> h4;
965             h2:r -> h5;
966             h3:l -> h2;
967             h3:r -> h6;
968
969          }
970
971
972 .. fig:: fig:gc-rc-rm-2
973
974    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
975
976    .. subfig::
977
978       Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en
979       el *live set*).
980
981       .. digraph:: g3_4
982
983          margin = 0;
984          ratio  = fill;
985          size   = "1.9,2.6";
986          edge [ color = gray40 ];
987          node [
988             shape     = record,
989             width     = 0,
990             height    = 0,
991             style     = filled,
992             fillcolor = gray25,
993             fontcolor = white
994          ];
995
996          subgraph cluster_all {
997
998             root [
999                label     = "root\nset|<r0> r0\n*|<r1> r1",
1000                style     = filled,
1001                fillcolor = gray96,
1002                fontcolor = black,
1003             ];
1004
1005             subgraph marked {
1006                node [ fillcolor = white, fontcolor = black ];
1007                h1;
1008             };
1009
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" ];
1016
1017             root:r0 -> h1 [ style = invis ];
1018             root:r1 -> h3;
1019             h1:l -> h2 [ style = invis ];
1020             h1:r -> h3 [ style = bold, color = black ];
1021             h2:l -> h4;
1022             h2:r -> h5;
1023             h3:l -> h2;
1024             h3:r -> h6;
1025
1026          }
1027
1028    .. subfig::
1029
1030       El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.
1031
1032       .. digraph:: g3_5
1033
1034          margin = 0;
1035          ratio  = fill;
1036          size   = "1.9,2.6";
1037          edge [ color = gray40 ];
1038          node [
1039             shape     = record,
1040             width     = 0,
1041             height    = 0,
1042             style     = filled,
1043             fillcolor = gray25,
1044             fontcolor = white
1045          ];
1046
1047          subgraph cluster_all {
1048
1049             root [
1050                label     = "root\nset|<r0> r0|<r1> r1",
1051                style     = filled,
1052                fillcolor = gray96,
1053                fontcolor = black,
1054             ];
1055
1056             subgraph marked {
1057                node [ fillcolor = white, fontcolor = black ];
1058                h1;
1059             };
1060
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" ];
1067
1068             root:r0 -> h1 [ style = invis ];
1069             root:r1 -> h3;
1070             h1:l -> h2 [ style = invis ];
1071             h1:r -> h3 [ style = invis ];
1072             h2:l -> h4;
1073             h2:r -> h5;
1074             h3:l -> h2;
1075             h3:r -> h6;
1076
1077          }
1078
1079
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`).
1090
1091
1092 .. fig:: fig:gc-rc-up-1
1093
1094    Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
1095    :math:`\to` ``h5`` (parte 1).
1096
1097    .. subfig::
1098
1099       Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.
1100
1101       .. digraph:: g4_1
1102
1103          margin = 0;
1104          ratio  = fill;
1105          size   = "1.9,2.6";
1106          edge [ color = gray40 ];
1107          node [
1108             shape     = record,
1109             width     = 0,
1110             height    = 0,
1111             style     = filled,
1112             fillcolor = gray25,
1113             fontcolor = white
1114          ];
1115
1116          subgraph cluster_all {
1117
1118             root [
1119                label     = "root\nset|<r0> r0|<r1> r1",
1120                style     = filled,
1121                fillcolor = gray96,
1122                fontcolor = black,
1123             ];
1124
1125             subgraph marked {
1126                node [ fillcolor = white, fontcolor = black ];
1127                h1;
1128             };
1129
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" ];
1136
1137             root:r0 -> h1 [ style = invis ];
1138             h1:l -> h2 [ style = invis ];
1139             h1:r -> h3 [ style = invis ];
1140             root:r1 -> h3;
1141             h2:l -> h4;
1142             h2:r -> h5;
1143             h3:l -> h2;
1144             h3:l -> h5 [ style = dotted, color = black ];
1145             h3:r -> h6;
1146
1147          }
1148
1149    .. subfig::
1150
1151       Luego se procede a visitar las hijas de ``h3``, comenzando por ``h2``.
1152
1153       .. digraph:: g4_2
1154
1155          margin = 0;
1156          ratio  = fill;
1157          size   = "1.9,2.6";
1158          edge [ color = gray40 ];
1159          node [
1160             shape     = record,
1161             width     = 0,
1162             height    = 0,
1163             style     = filled,
1164             fillcolor = gray25,
1165             fontcolor = white
1166          ];
1167
1168          subgraph cluster_all {
1169
1170             root [
1171                label     = "root\nset|<r0> r0|<r1> r1",
1172                style     = filled,
1173                fillcolor = gray96,
1174                fontcolor = black,
1175             ];
1176
1177             subgraph marked {
1178                node [ fillcolor = white, fontcolor = black ];
1179                h1;
1180             };
1181
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" ];
1188
1189             root:r0 -> h1 [ style = invis ];
1190             h1:l -> h2 [ style = invis ];
1191             h1:r -> h3 [ style = invis ];
1192             root:r1 -> h3;
1193             h2:l -> h4;
1194             h2:r -> h5;
1195             h3:l -> h2 [ style = bold, color = black ];
1196             h3:l -> h5 [ style = dotted, color = black ];
1197             h3:r -> h6;
1198
1199          }
1200
1201    .. subfig::
1202
1203       Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser
1204       *basura*). Se eliminan las referencias a las hijas.
1205
1206       .. digraph:: g4_3
1207
1208          margin = 0;
1209          ratio  = fill;
1210          size   = "1.9,2.6";
1211          edge [ color = gray40 ];
1212          node [
1213             shape     = record,
1214             width     = 0,
1215             height    = 0,
1216             style     = filled,
1217             fillcolor = gray25,
1218             fontcolor = white
1219          ];
1220
1221          subgraph cluster_all {
1222
1223             root [
1224                label     = "root\nset|<r0> r0|<r1> r1",
1225                style     = filled,
1226                fillcolor = gray96,
1227                fontcolor = black,
1228             ];
1229
1230             subgraph marked {
1231                node [ fillcolor = white, fontcolor = black ];
1232                h1; h2;
1233             };
1234
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" ];
1241
1242             root:r0 -> h1 [ style = invis ];
1243             h1:l -> h2 [ style = invis ];
1244             h1:r -> h3 [ style = invis ];
1245             root:r1 -> h3;
1246             h2:l -> h4 [ style = bold, color = black ];
1247             h2:r -> h5;
1248             h3:l -> h2 [ style = invis ];
1249             h3:l -> h5 [ style = dotted, color = black ];
1250             h3:r -> h6;
1251
1252          }
1253
1254
1255 .. fig:: fig:gc-rc-up-2
1256
1257    Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
1258    :math:`\to` ``h5`` (parte 2).
1259
1260    .. subfig::
1261
1262       Se decrementa el contador de ``h4`` quedando en 0, pasa a ser
1263       *basura*. Se continúa con ``h5``.
1264
1265       .. digraph:: g4_4
1266
1267          margin = 0;
1268          ratio  = fill;
1269          size   = "1.9,2.6";
1270          edge [ color = gray40 ];
1271          node [
1272             shape     = record,
1273             width     = 0,
1274             height    = 0,
1275             style     = filled,
1276             fillcolor = gray25,
1277             fontcolor = white
1278          ];
1279
1280          subgraph cluster_all {
1281
1282             root [
1283                label     = "root\nset|<r0> r0|<r1> r1",
1284                style     = filled,
1285                fillcolor = gray96,
1286                fontcolor = black,
1287             ];
1288
1289             subgraph marked {
1290                node [ fillcolor = white, fontcolor = black ];
1291                h1; h2; h4;
1292             };
1293
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" ];
1300
1301             root:r0 -> h1 [ style = invis ];
1302             h1:l -> h2 [ style = invis ];
1303             h1:r -> h3 [ style = invis ];
1304             root:r1 -> h3;
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 ];
1309             h3:r -> h6;
1310
1311          }
1312
1313    .. subfig::
1314
1315       Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.
1316
1317       .. digraph:: g4_5
1318
1319          margin = 0;
1320          ratio  = fill;
1321          size   = "1.9,2.6";
1322          edge [ color = gray40 ];
1323          node [
1324             shape     = record,
1325             width     = 0,
1326             height    = 0,
1327             style     = filled,
1328             fillcolor = gray25,
1329             fontcolor = white
1330          ];
1331
1332          subgraph cluster_all {
1333
1334             root [
1335                label     = "root\nset|<r0> r0|<r1> r1",
1336                style     = filled,
1337                fillcolor = gray96,
1338                fontcolor = black,
1339             ];
1340
1341             subgraph marked {
1342                node [ fillcolor = white, fontcolor = black ];
1343                h1; h2; h4;
1344             };
1345
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" ];
1352
1353             root:r0 -> h1 [ style = invis ];
1354             h1:l -> h2 [ style = invis ];
1355             h1:r -> h3 [ style = invis ];
1356             root:r1 -> h3;
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 ];
1361             h3:r -> h6;
1362
1363          }
1364
1365    .. subfig::
1366
1367       Se termina por actualizar la referencia de ``h3.l`` para que apunte
1368       a ``h5``.
1369
1370       .. digraph:: g4_6
1371
1372          margin = 0;
1373          ratio  = fill;
1374          size   = "1.9,2.6";
1375          edge [ color = gray40 ];
1376          node [
1377             shape     = record,
1378             width     = 0,
1379             height    = 0,
1380             style     = filled,
1381             fillcolor = gray25,
1382             fontcolor = white
1383          ];
1384
1385          subgraph cluster_all {
1386
1387             root [
1388                label     = "root\nset|<r0> r0|<r1> r1",
1389                style     = filled,
1390                fillcolor = gray96,
1391                fontcolor = black,
1392             ];
1393
1394             subgraph marked {
1395                node [ fillcolor = white, fontcolor = black ];
1396                h1; h2; h4;
1397             };
1398
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" ];
1406
1407             root:r0 -> h1 [ style = invis ];
1408             h1:l -> h2 [ style = invis ];
1409             h1:r -> h3 [ style = invis ];
1410             root:r1 -> h3;
1411             h2:l -> h4 [ style = invis ];
1412             h2:r -> h5 [ style = invis ];
1413             h3:l -> h5;
1414             h3:l -> h2 [ style = invis ];
1415             h3:r -> h6;
1416
1417          }
1418
1419
1420 .. _ref_gc_cycles:
1421
1422 TODO El problema de los ciclos
1423
1424
1425 Marcado y barrido
1426 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1427
1428 TODO
1429
1430
1431
1432 Copia/Semi-espacio
1433 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1434
1435 TODO
1436
1437
1438
1439 Compactado
1440 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1441
1442 TODO
1443
1444
1445
1446 Clasificación
1447 ----------------------------------------------------------------------------
1448
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.
1454
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`_.
1457
1458 .. _ref_gc_direct:
1459
1460 Directa / indirecta
1461 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1462
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>`.
1472
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
1481 *basura*.
1482
1483 Estas son las dos grandes familias de recolectores, también conocidos como
1484 `conteo de referencias`_ (directa) y *traicing garbage collection*
1485 (indirecta).
1486
1487
1488 .. _ref_gc_inc:
1489
1490 Incremental
1491 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1492
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).
1497
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
1506 próxima iteración.
1507
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.
1514
1515
1516 .. _ref_gc_concurrent:
1517
1518 Concurrente / *stop-the-world*
1519 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1520
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.
1526
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.
1532
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.
1536
1537 .. _ref_gc_art:
1538
1539 Estado del arte
1540 ----------------------------------------------------------------------------
1541
1542 .. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
1543    ejemplos.
1544
1545 TODO
1546
1547 Cloning
1548
1549
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.
1553
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.
1557
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
1567 *mutator*
1568
1569
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.
1577
1578
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/)
1583
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
1588
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
1593
1594 Implementación de Bohem GC
1595 http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html
1596
1597 Interfaz de Bohem GC
1598 http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html
1599
1600
1601 .. include:: links.rst
1602
1603 .. vim: set ts=3 sts=3 sw=3 et tw=75 :