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: TERMINADO
   6
   7
   8 .. _gc:
   9
  10 Recolección de basura
  11 ============================================================================
  12
  13
  14
  15 .. _gc_intro:
  16
  17 Introducción
  18 ----------------------------------------------------------------------------
  19
  20 *Recolección de basura* se refiere a la recuperación automática de memoria del
  21 *heap* [#gcheap]_ una vez que el programa ha dejado de hacer referencia a ella
  22 (y por lo tanto, ha dejado de utilizarla).
  23
  24 .. [#gcheap] *Heap* es un área de memoria que se caracteriza por ser
  25    dinámica (a diferencia del área de memoria estática que está disponible
  26    durante toda la ejecución de un programa). Un programa puede reservar
  27    memoria en tiempo de ejecución según sea necesario y liberarla cuando ya no
  28    la necesita. A diferencia del *stack*, la duración de la *reserva* no está
  29    atada a un bloque de código.
  30
  31 A medida que el tiempo pasa, cada vez los programas son más complejos y es más
  32 compleja la administración de memoria. Uno de los aspectos más importantes de
  33 un recolector de basura es lograr un mayor nivel de abstracción y modularidad,
  34 dos conceptos claves en la ingeniería de software [JOLI96]_. En particular, al
  35 diseñar o programar bibliotecas, de no haber un recolector de basura, **la
  36 administración de memoria pasa a ser parte de la interfaz**, lo que produce
  37 que los módulos tengan un mayor grado de acoplamiento.
  38
  39 Además hay una incontable cantidad de problemas asociados al manejo explícito
  40 de memoria que simplemente dejan de existir al utilizar un recolector de
  41 basura. Por ejemplo, los errores en el manejo de memoria (como *buffer
  42 overflows* [#gcbuff]_ o *dangling pointers* [#gcdang]_) son la causa más
  43 frecuente de problemas de seguridad [BEZO06]_.
  44
  45 .. [#gcbuff] Un *buffer overflow* (*desbordamiento de memoria* en
  46    castellano) se produce cuando se copia un dato a un área de memoria que no
  47    es lo suficientemente grande para contenerlo. Esto puede producir que el
  48    programa sea abortado por una violación de segmento, o peor, sobreescribir
  49    un área de memoria válida, en cuyo caso los resultados son impredecibles.
  50
  51 .. [#gcdang] Un *dangling pointer* (*puntero colgante* en castellano) es un
  52    puntero que apunta a un área de memoria inválida. Ya sea porque el elemento
  53    apuntado no es el mismo tipo o porque la memoria ya ha sido liberada. Al
  54    ser desreferenciado, los resultados son impredecibles, el programa podría
  55    abortarse por una violación de segmento o podrían pasar peores cosas si el
  56    área de memoria fue re-asignada para almacenar otro objeto.
  57
  58 La recolección de basura nació junto a Lisp_ a finales de 1950 y en los
  59 siguientes años estuvo asociada principalmente a lenguajes funcionales, pero
  60 en la actualidad está presente en prácticamente todos los lenguajes de
  61 programación, de alto o bajo nivel, aunque sea de forma opcional. En los
  62 últimos 10 años tuvo un gran avance, por la adopción en lenguajes de
  63 desarrollo rápido utilizados mucho en el sector empresarial, en especial
  64 Java_, que fue una plataforma de facto para la investigación y desarrollo de
  65 recolectores de basura (aunque no se limitaron a este lenguaje las
  66 investigaciones).
  67
  68 En las primeras implementaciones de recolectores de basura la penalización en
  69 el rendimiento del programa se volvía prohibitiva para muchas aplicaciones. Es
  70 por esto que hubo bastante resistencia a la utilización de recolectores de
  71 basura, pero el avance en la investigación fue haciendo que cada vez sea una
  72 alternativa más viable al manejo manual de memoria, incluso para aplicaciones
  73 con altos requerimientos de rendimiento. En la actualidad un programa que
  74 utiliza un recolector moderno puede ser comparable en rendimiento con uno que
  75 utiliza un esquema manual. En particular, si el programa fue diseñado con el
  76 recolector de basura en mente en ciertas circunstancias puede ser incluso más
  77 eficiente que uno que hace manejo explícito de la memoria. Muchos recolectores
  78 mejoran la localidad de referencia [#gcreflocal]_, haciendo que el programa
  79 tenga un mejor comportamiento con el caché y la memoria virtual.
  80
  81 .. [#gcreflocal] Localidad de referencia es la medida en que los accesos
  82    sucesivos de memoria cercana espacialmente son cercanos también en el
  83    tiempo. Por ejemplo, un programa que lee todos los elementos de una matriz
  84    contigua de una vez o que utiliza la misma variable repetidamente tiene
  85    buena localidad referencia. Una buena localidad de referencia interactúa
  86    bien con la memoria virtual y caché, ya que reduce el conjunto de trabajo
  87    (o *working set*) y mejora la probabildad de éxito (*hit rate*).
  88
  89 El recolector de basura debe tener un comportamiento correcto y predecible
  90 para que sea útil, si el programador no puede confiar en el recolector de
  91 basura, éste se vuelve más un problema que una solución, porque introduce
  92 nuevos puntos de falla en los programas, y lo que es peor, puntos de falla no
  93 controlados por el programador, volviendo mucho más difícil la búsqueda de
  94 errores.
  95
  96
  97
  98 .. _gc_intro_basics:
  99
 100 Conceptos básicos
 101 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 102
 103 Los programas pueden hacer uso principalmente de 4 áreas de memoria:
 104
 105 Registros
 106    Se trata de la memoria más básica de una computadora. Es el área de memoria
 107    en la que puede operar realmente el procesador, es extremadamente escasa
 108    y generalmente su uso es administrado por el lenguaje de programación (o
 109    compilador más específicamente). Excepto en situaciones muy particulares,
 110    realizando tareas de muy bajo nivel, un programador nunca manipula los
 111    registros explícitamente.
 112
 113 Área de memoria estática
 114    Es la forma de memoria más simple que un programador utiliza
 115    explícitamente. En general las variables globales se almacenan en este
 116    área, que es parte inherente del programa y está disponible durante toda su
 117    ejecución, por lo tanto nunca cambia su capacidad en tiempo de ejecución.
 118    Es la forma más básica de administrar memoria, pero tiene una limitación
 119    fundamental: **el tamaño de la memoria tiene que ser conocido en tiempo de
 120    compilación**. Los primeros lenguajes de programación solo contaban con
 121    este tipo de memoria (además de los registros del procesador).
 122
 123 *Stack* (pila)
 124    Los primeros lenguajes de programación que hicieron uso de una pila
 125    aparecieron en el año 1958 (Algol-58 y Atlas Autocode) y fueron los
 126    primeros en introducir estructura de bloques, almacenando las variables
 127    locales a estos bloques utilizando una pila [JOLI96]_.  Esto permite
 128    utilizar recursividad y tener un esquema simple de memoria dinámica. Sin
 129    embargo este esquema es muy limitado porque el orden de reserva
 130    y liberación de memoria tiene que estar bien establecido. Una celda
 131    [#gccelda]_ asignada antes que otra nunca puede ser liberada antes que
 132    aquella.
 133
 134    .. [#gccelda] En general en la literatura se nombra a una porción de
 135       memoria asignada individualmente *celda*, *nodo* u *objeto*
 136       indistintamente. En este trabajo se utilizará la misma nomenclatura
 137       (haciendo mención explícita cuando alguno de estos términos se refiera
 138       a otra cosa, como al nodo de una lista o a un objeto en el sentido de
 139       programación orientada a objetos).
 140
 141 *Heap*
 142    A diferencia del *stack*, el *heap* provee un área de memoria que puede ser
 143    obtenida dinámicamente pero sin limitaciones de orden. Es el tipo de
 144    memoria más flexible y por lo tanto el más complejo de administrar; razón
 145    por la cual existen los recolectores de basura.
 146
 147 La recolección de basura impone algunas restricciones sobre la manera de
 148 utilizar el *heap*. Debido a que un recolector de basura debe ser capaz de
 149 determinar el grafo de conectividad de la memoria en uso, es necesario que el
 150 programa siempre tenga alguna referencia a las celdas activas en los
 151 registros, memoria estática o *stack* (normalmente denominado *root set*).
 152
 153 Esto implica que una celda sea considerada basura si y sólo si no puede ser
 154 alcanzada a través del grafo de conectividad que se comienza a recorrer desde
 155 el *root set*. Por lo tanto, una celda está *viva* si y sólo si su dirección
 156 de memoria está almacenada en una celda *raíz* (parte del *root set*) o si
 157 está almacenada en otra celda *viva* del *heap*.
 158
 159 Cabe aclarar que esta es una definición conceptual, asumiendo que el programa
 160 siempre limpia una dirección de memoria almacenada en el *root set* o una
 161 celda del *heap* cuando la celda a la que apunta no va a ser utilizada
 162 nuevamente. Esto no es siempre cierto y los falsos positivos que esto produce
 163 se conoce como un tipo de pérdida de memoria (que es posible incluso al
 164 utilizar un recolector de basura) llamada pérdida de memoria *lógica*. Esto
 165 puede no ser evitable (incluso cuando el programador no cometa errores) en
 166 lenguajes de programación que requieran un recolector de basura conservativo.
 167
 168 Por último, siendo que el recolector de basura es parte del programa de forma
 169 indirecta, es común ver en la literatura que se diferencia entre dos partes
 170 del programa, el recolector de basura y el programa en sí. A la primera se la
 171 suele denominar simplemente *recolector* y a la segunda *mutator*, dado que es
 172 la única que modifica (o *muta*) el grafo de conectividad.
 173
 174
 175
 176 .. _gc_intro_mark:
 177
 178 Recorrido del grafo de conectividad
 179 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 180
 181 El problema de encontrar las celdas *vivas* de un programa se reduce
 182 a recorrer un grafo dirigido. El grafo se define como:
 183
 184 .. math::
 185
 186    G = (V,A)
 187
 188 Donde :math:`V` es el conjunto de vértices, dado por las celdas de memoria
 189 y :math:`A` es un conjunto de pares ordenados (aristas), dado por la relación
 190 :math:`M \rightarrow N` (es decir, los punteros).
 191
 192 El grafo comienza a recorrerse desde el *root set* y todos los vértices que
 193 fueron visitados componen el *live set*; el resto de los vértices son
 194 *basura*.
 195
 196 Más formalmente, Definimos:
 197
 198 *Camino*
 199    Es una secuencia de vértices tal que cada uno de los vértices tiene una
 200    arista al próximo vértice en la secuencia. Todo camino finito tiene un
 201    *vértice inicial* y un *vértice final* (llamados en conjunto *vértices
 202    terminales*).  Cualquier vértice no terminal es denominado *vértice
 203    interior*.
 204
 205    .. math::
 206
 207       \underset{v_1 \rightarrow v_N}{C} = \left\lbrace
 208          v_1, \dotsc, v_N \in V \big/ \underset{i \in [1,N-1]}{\forall v_i}
 209             \exists (v_i \to v_{i+1}) \in A
 210       \right\rbrace
 211
 212    Un camino cuyos *vértices terminales* coinciden, es decir :math:`v_1
 213    = v_N`, es denominado **Ciclo**. Cabe notar que los *vértices terminales*
 214    de un ciclo son completamente arbitrarios, ya que cualquier *vértice
 215    interior* puede ser un *vértice terminal*.
 216
 217 *Conexión*
 218    Decimos que :math:`M` está *conectado* a :math:`N` si y sólo si existe un
 219    camino de :math:`M` a :math:`N`.
 220
 221    .. math::
 222
 223       M \mapsto N \Longleftrightarrow \exists \underset{M \to N}{C} \in G
 224
 225 *Live set*
 226    Es el conjunto de celdas *vivas* está dado por todos los vértices
 227    (:math:`v`) del grafo para los cuales existe una raíz en el *root set* que
 228    esté conectada a él.
 229
 230    .. math::
 231
 232       Live \thickspace set = \left\lbrace v \in V \big/
 233          \left( \exists r \in Root \thickspace set \big/ r \mapsto v \right)
 234       \right\rbrace
 235
 236 *Basura*
 237    La basura, o celdas *muertas*, quedan determinadas entonces por todas las
 238    celdas del *heap* que no son parte del *live set*.
 239
 240    .. math::
 241
 242       Basura = V - Live \thickspace set
 243
 244 Esto es, efectivamente, una partición del *heap* (ver figura
 245 :vref:`fig:gc-heap-parts`).
 246
 247
 248 .. flt:: fig:gc-heap-parts
 249
 250    Distintas partes de la memoria *heap*
 251
 252    Distintas partes de la memoria, incluyendo relación entre *basura*, *live
 253    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 a que
 310 es necesario marcar los vértices para evitar visitar dos veces el mismo nodo
 311 en casos en los que el grafo contenga ciclos. De forma similar a la búsqueda,
 312 que puede realizarse *primero a lo ancho* (*breadth-first*) o *primero a lo
 313 alto* (*depth-first*) del grafo, el marcado de un grafo también puede
 314 realizarse de ambas maneras. Cada una podrá o no tener efectos en el
 315 rendimiento, en particular dependiendo de la aplicación puede convenir uno
 316 u otro método para lograr una mejor localidad de referencia.
 317
 318 Un algoritmo simple (recursivo) de marcado *primero a lo alto* puede ser el
 319 siguiente (asumiendo que partimos con todos los vértices sin marcar)
 320 [#gcpseudo]_::
 321
 322    function mark(v) is
 323       if not v.marked
 324          v.marked = true
 325          foreach (src, dst) in v.edges
 326             mark(dst)
 327
 328    function mark_phase() is
 329       foreach r in root_set
 330          mark(r)
 331
 332 .. [#gcpseudo] Para presentar los algoritmos se utiliza una forma simple de
 333    pseudo-código. El pseudo-código se escribe en inglés para que pueda ser más
 334    fácilmente contrastado con la literatura, que está en inglés. Para
 335    diferenciar posiciones de memoria y punteros de las celdas en sí, se usa la
 336    misma sintaxis que C, ``r*`` denota una referencia o puntero y ``*r``
 337    denota "objeto al que apunta ``r``\ ". Se sobreentiende que ``r = o``
 338    siempre toma la dirección de memoria de ``o``.
 339
 340 Una vez concluido el marcado, sabemos que todos los vértices con la marca son
 341 parte del *live set* y que todos los vértices no marcados son *basura*.  Esto
 342 es conocido también como **abstracción bicolor**, dado que en la literatura se
 343 habla muchas veces de *colorear* las celdas. En general, una celda sin marcar
 344 es de color blanco y una marcada de color negro.
 345
 346 Puede observarse un ejemplo del algoritmo en la figura :vref:`fig:gc-mark-1`,
 347 en la cual se marca el sub-grafo apuntando por ``r0``. Luego se marca el
 348 sub-grafo al que apunta ``r1`` (ver figura :vref:`fig:gc-mark-2`), concluyendo
 349 con el marcado del grafo completo, dejando sin marcar solamente las celdas
 350 *basura* (en blanco).
 351
 352
 353 .. flt:: fig:gc-mark-1
 354
 355    Ejemplo de marcado del grafo de conectividad (parte 1)
 356
 357    .. subflt::
 358
 359       Se comienza a marcar el grafo por la raíz r0.
 360
 361       .. digraph:: g2_1
 362
 363          margin = 0;
 364          ratio  = fill;
 365          size   = "1.9,2.6";
 366          node [ shape = record, width = 0, height = 0];
 367          edge [ color = gray40 ];
 368
 369          subgraph cluster_all {
 370
 371             root [
 372                label     = "root\nset|<r0> r0\n*|<r1> r1",
 373                style     = filled,
 374                fillcolor = gray96,
 375             ];
 376
 377             subgraph marked {
 378                node [ style = filled, fillcolor = gray25, fontcolor = white ];
 379                h1;
 380             };
 381
 382             root:r0 -> h1 [ style = bold, color = black ];
 383             h1 -> h2 -> h5 -> h1;
 384             root:r1 -> h6 -> h2;
 385             h4 -> h3;
 386             h3 -> h5;
 387
 388          }
 389
 390    .. subflt::
 391
 392       Luego de marcar el nodo ``h1``, se procede al ``h2``.
 393
 394       .. digraph:: g2_2
 395
 396          margin = 0;
 397          ratio  = fill;
 398          size   = "1.9,2.6";
 399          node [ shape = record, width = 0, height = 0 ];
 400          edge [ color = gray40 ];
 401
 402          subgraph cluster_all {
 403
 404             root [
 405                label     = "root\nset|<r0> r0\n*|<r1> r1",
 406                style     = filled,
 407                fillcolor = gray96,
 408             ];
 409
 410             subgraph marked {
 411                node [ style = filled, fillcolor = gray25, fontcolor = white ];
 412                h1; h2;
 413             };
 414
 415             root:r0 -> h1 [ color = gray10 ];
 416             h1 -> h2 [ style = bold, color = black ];
 417             h2 -> h5 -> h1;
 418             root:r1 -> h6 -> h2;
 419             h4 -> h3;
 420             h3 -> h5;
 421
 422          }
 423
 424    .. subflt::
 425
 426       Luego sigue el nodo h5.
 427
 428       .. digraph:: g2_3
 429
 430          margin = 0;
 431          ratio  = fill;
 432          size   = "1.9,2.6";
 433          node [ shape = record, width = 0, height = 0 ];
 434          edge [ color = gray40 ];
 435
 436          subgraph cluster_all {
 437
 438             root [
 439                label     = "root\nset|<r0> r0\n*|<r1> r1",
 440                style     = filled,
 441                fillcolor = gray96,
 442             ];
 443
 444             subgraph marked {
 445                node [ style = filled, fillcolor = gray25, fontcolor = white ];
 446                h1; h2; h5;
 447             };
 448
 449             root:r0 -> h1 [ color = gray10 ];
 450             h1 -> h2 [ color = gray10 ];
 451             h2 -> h5 [ style = bold, color = black ];
 452             h5 -> h1;
 453             root:r1 -> h6 -> h2;
 454             h4 -> h3;
 455             h3 -> h5;
 456
 457          }
 458
 459
 460 .. flt:: fig:gc-mark-2
 461
 462    Ejemplo de marcado del grafo de conectividad (parte 2)
 463
 464    .. subflt::
 465
 466       El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo
 467       tanto no se visita nuevamente.
 468
 469       .. digraph:: g2_4
 470
 471          margin = 0;
 472          ratio  = fill;
 473          size   = "1.9,2.6";
 474          node [ shape = record, width = 0, height = 0 ];
 475          edge [ color = gray40 ];
 476
 477          subgraph cluster_all {
 478
 479             root [
 480                label     = "root\nset|<r0> r0\n*|<r1> r1",
 481                style     = filled,
 482                fillcolor = gray96,
 483             ];
 484
 485             subgraph marked {
 486                node [ style = filled, fillcolor = gray25, fontcolor = white ];
 487                h1; h2; h5;
 488             };
 489
 490             root:r0 -> h1 [ color = gray10 ];
 491             h1 -> h2 [ color = gray10 ];
 492             h2 -> h5 [ color = gray10 ];
 493             h5 -> h1 [ style = bold, color = black ];
 494             root:r1 -> h6 -> h2;
 495             h4 -> h3;
 496             h3 -> h5;
 497
 498          }
 499
 500    .. subflt::
 501
 502       Se concluye el marcado del sub-grafo al que conecta r0, se procede
 503       a marcar el sub-grafo al que conecta r1, marcando al nodo h6.
 504
 505       .. digraph:: g2_5
 506
 507          margin = 0;
 508          ratio  = fill;
 509          size   = "1.9,2.6";
 510          node [ shape = record, width = 0, height = 0 ];
 511          edge [ color = gray40 ];
 512
 513          subgraph cluster_all {
 514
 515            root [
 516               label     = "root\nset|<r0> r0|<r1> r1\n*",
 517               style     = filled,
 518               fillcolor = gray96,
 519            ];
 520
 521            subgraph marked {
 522               node [ style = filled, fillcolor = gray25, fontcolor = white ];
 523               h1; h2; h5; h6;
 524            };
 525
 526            root:r0 -> h1 [ color = gray10 ];
 527            h1 -> h2 [ color = gray10 ];
 528            h2 -> h5 [ color = gray10 ];
 529            h5 -> h1 [ color = gray10 ];
 530            root:r1 -> h6 [ style = bold, color = black ];
 531            h6 -> h2;
 532            h4 -> h3;
 533            h3 -> h5;
 534
 535          }
 536
 537    .. subflt::
 538
 539       El nodo h6 tiene una arista al h2, pero éste ya fue marcado por lo
 540       que no se vuelve a visitar. No hay más raíces, se finaliza el marcado
 541       del grafo.
 542
 543       .. digraph:: g2_6
 544
 545          margin = 0;
 546          ratio  = fill;
 547          size   = "1.9,2.6";
 548          node [ shape = record, width = 0, height = 0 ];
 549          edge [ color = gray40 ];
 550
 551          subgraph cluster_all {
 552
 553             root [
 554                label     = "root\nset|<r0> r0|<r1> r1\n*",
 555                style     = filled,
 556                fillcolor = gray96,
 557             ];
 558
 559             subgraph marked {
 560                node [ style = filled, fillcolor = gray25, fontcolor = white ];
 561                h1; h2; h5; h6;
 562             };
 563
 564             root:r0 -> h1 [ color = gray10 ];
 565             h1 -> h2 [ color = gray10 ];
 566             h2 -> h5 [ color = gray10 ];
 567             h5 -> h1 [ color = gray10 ];
 568             root:r1 -> h6 [ color = gray10 ];
 569             h6 -> h2 [ style = bold, color = black ];
 570             h4 -> h3;
 571             h3 -> h5;
 572
 573          }
 574
 575
 576
 577 .. _gc_intro_tricolor:
 578
 579 Abstracción tricolor
 580 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 581
 582 Muchos algoritmos utilizan tres colores para realizar el marcado. El tercer
 583 color, gris generalmente, indica que una celda debe ser visitada. Esto permite
 584 algoritmos :ref:`concurrentes <gc_concurrent>` e :ref:`incrementales
 585 <gc_inc>`, además de otro tipo de optimizaciones.  Entonces, lo que plantea
 586 esta abstracción es una nueva partición del heap al momento de marcar, esta
 587 vez son tres porciones: blanca, gris y negra.
 588
 589 Al principio todas las celdas se pintan de blanco, excepto el *root set* que
 590 se pinta de gris. Luego se van obteniendo celdas del conjunto de las grises
 591 y se las pinta de negro, pintando sus hijas directas de gris.
 592
 593 Una vez que no hay más celdas grises, tenemos la garantía de que las celdas
 594 negras serán el *live set* y las celdas blancas *basura*. Esto se debe a que
 595 siempre se mantiene esta invariante: **ninguna celda negra apunta directamente
 596 a una celda blanca**. Las celdas blancas siempre son apuntadas por celdas
 597 blancas o grises. Entonces, siempre que el conjunto de celdas grises sea
 598 vacío, no habrán celdas negras conectadas a blancas, siendo las celdas blancas
 599 *basura*.
 600
 601 El algoritmo básico para marcar con tres colores es el siguiente (asumiendo
 602 que todas las celdas parten pintadas de blanco, es decir, el conjunto blanco
 603 contiene todas las celdas de memoria y los conjuntos negro y gris están
 604 vacíos)::
 605
 606    function mark_phase() is
 607       foreach r in root_set
 608          gray_set.add(r)
 609       while not gray_set.empty()
 610          v = gray_set.pop()
 611          black_set.add(v)
 612          foreach (src, dst) in v.edges
 613             if dst in white_set
 614                white_set.remove(dst)
 615                gray_set.add(dst)
 616
 617 Si bien este algoritmo no es recursivo, tiene un requerimiento de espacio
 618 :math:`O(\lvert Live \thickspace set \rvert)`. Un ejemplo donde se aprecia
 619 esto a simple vista es cuando el *Live set* resulta una lista simplemente
 620 enlazada, en cuyo caso el *gray_set* deberá almacenar todos los nodos del
 621 *Live set*.
 622
 623
 624
 625 .. _gc_intro_services:
 626
 627 Servicios
 628 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 629
 630 En general todos los algoritmos de recolección de basura utilizan servicios de
 631 una capa inferior [#gclowlayer]_ y proveen servicios a una capa superior
 632 [#gchilayer]_.
 633
 634 .. [#gclowlayer] En general estos servicios están provistos directamente
 635    por el sistema operativo pero también pueden estar dados por un
 636    administrador de memoria de bajo nivel (o *low level allocator* en inglés).
 637
 638 .. [#gchilayer] En general estos servicios son utilizados directamente por
 639    el lenguaje de programación, pero pueden ser utilizados directamente por el
 640    usuario del lenguaje si éste interatúa con el recolector, ya sea por algún
 641    requerimiento particular o porque el lenguaje no tiene soporte diercto de
 642    recolección de basura y el recolector está implementado como una biblioteca
 643    de usuario.
 644
 645 A continuación se presentan las primitivas en común que utilizan todos los
 646 recolectores a lo largo de este documento.
 647
 648 Servicios utilizados por el recolector son los siguientes:
 649
 650 :math:`alloc() \to cell`
 651    Obtiene una nueva celda de memoria. El mecanismo por el cual se obtiene la
 652    celda es indistinto para esta sección, puede ser de una lista libre, puede
 653    ser de un administrador de memoria de más bajo nivel provisto por el
 654    sistema operativo o la biblioteca estándar de C (``malloc()``), etc.  Cómo
 655    organizar la memoria es un área de investigación completa y si bien está
 656    estrechamente relacionada con la recolección de basura, en este trabajo no
 657    se prestará particular atención a este aspecto (salvo casos donde el
 658    recolector impone una cierta organización de memoria en el *low level
 659    allocator*). Por simplicidad también asumiremos (a menos que se indique lo
 660    contrario) que las celdas son de tamaño fijo. Esta restricción normalmente
 661    puede ser fácilmente relajada (en los recolectores que la tienen).
 662
 663 :math:`free(cell)`
 664    Libera una celda que ya no va a ser utilizada. La celda liberada debe haber
 665    sido obtenida mediante ``alloc()``.
 666
 667 Y los servicios básicos proporcionados por el recolector son los siguientes:
 668
 669 :math:`new() \to cell`
 670    Obtiene una celda de memoria para ser utilizada por el programa.
 671
 672 :math:`update(ref, cell)`
 673    Notifica al recolector que la referencia :math:`ref` ahora apunta
 674    a :math:`cell`. Visto más formalmente, sería análogo a decir que hubo un
 675    cambio en la conectividad del grafo: la arista :math:`src \to old` cambia
 676    por :math:`src \to new` (donde :math:`src` es la celda que contiene la
 677    referencia :math:`ref`, :math:`old` es la celda a la que apunta la
 678    referencia :math:`ref` y :math:`new` es el argumento :math:`cell`). Si
 679    :math:`cell` es ``null``, sería análogo a informar que se elimina la arista
 680    :math:`src \to old`.
 681
 682 :math:`del(cell)`
 683    Este servicio, según el algoritmo, puede ser utilizado para informar un
 684    cambio en la conectividad del grafo, la eliminación de una arista (análogo
 685    a :math:`update(ref, null)` pero sin proporcionar información sobre la
 686    arista a eliminar). Esto es generalmente útil solo en :ref:`conteo de
 687    referencias <gc_rc>`. Para otros recolectores puede significar que el
 688    usuario asegura que no hay más referencias a esta celda, es decir, análogo
 689    a eliminar el conjunto de aristas :math:`\big\lbrace (v, w) \in A , v \in
 690    Live \thickspace set , w \in Live \thickspace set \big/ w = cell
 691    \big\rbrace`.
 692
 693 :math:`collect()`
 694    Este servicio indica al recolector que debe hacer un análisis del grafo de
 695    conectividad en busca de *basura*. Generalmente este servicio es invocado
 696    por el propio recolector cuando no hay más celdas reciclables.
 697
 698 No todos los servicios son implementados por todos los recolectores, pero son
 699 lo suficientemente comunes como para describirlos de forma general en esta
 700 sección. Algunos son principalmente ideados para uso interno del recolector,
 701 aunque en ciertas circunstancias pueden ser utilizados por el usuario también.
 702
 703
 704
 705 .. _gc_classic:
 706
 707 Algoritmos clásicos
 708 ----------------------------------------------------------------------------
 709
 710 En la literatura se encuentran normalmente referencias a tres algoritmos
 711 clásicos, que son utilizados generalmente como bloques básicos para construir
 712 recolectores más complejos. Se presentan las versiones históricas más simples
 713 a fin de facilitar la comprensión conceptual.
 714
 715
 716
 717 .. _gc_rc:
 718
 719 Conteo de referencias
 720 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 721
 722 Se trata del algoritmo más antiguo de todos, implementado por primera vez por
 723 `John McCarthy`_ para Lisp_ a finales de 1950. Se trata de un método
 724 :ref:`directo <gc_direct>` e :ref:`incremental <gc_inc>` por naturaleza, ya
 725 que distribuye la carga de la recolección de basura durante toda la ejecución
 726 del programa, cada vez que el *mutator* cambia la conectividad de algún nodo
 727 del grafo de conectividad.
 728
 729 El método consiste en tener un contador asociado a cada celda que contenga la
 730 cantidad de celdas **vivas** que apuntan a ésta. Es decir, es la cardinalidad
 731 del conjunto de aristas que tienen por destino a la celda.  Formalmente
 732 podemos definir el contador :math:`rc(v)` (de *reference counter* en inglés)
 733 de la siguiente manera:
 734
 735 .. math::
 736
 737    rc(v) = \big\lvert
 738       \left\lbrace
 739          (v_1, v_2) \in A \big/
 740             v_1 \in Live \thickspace set \cup Root \thickspace set
 741                \wedge v_2 = v
 742       \right\rbrace
 743    \big\rvert
 744
 745 El *mutator* entonces debe actualizar este contador cada vez que el grafo de
 746 conectividad cambia, es decir, cada vez que se agrega, modifica o elimina una
 747 arista del grafo (o visto de una forma más cercana al código, cada vez que se
 748 agrega, modifica o elimina un puntero).
 749
 750 Esta invariante es fundamental para el conteo de referencias, porque se asume
 751 que si el contador es 0 entonces el *mutator* no tiene ninguna referencia a la
 752 celda y por lo tanto es *basura*:
 753
 754 .. math::
 755
 756    rc(v) = 0 \Rightarrow v \in Basura
 757
 758 Para mantener esta invariante el *mutator*, cada vez que cambia un puntero
 759 debe decrementar en 1 el contador de la celda a la que apuntaba antiguamente
 760 e incrementar en 1 el contador de la celda a la que apunta luego de la
 761 modificación. Esto asegura que la invariante se mantenga durante toda la
 762 ejecución del programa. Si al momento de decrementar un contador éste queda en
 763 0, la celda asociada debe liberarse de forma de poder ser reciclada. Esto
 764 implica que si esta celda almacena punteros, los contadores de las celdas
 765 apuntadas deben ser decrementados también, porque solo deben almacenarse en el
 766 contador las aristas del *live set* para mantener la invariante. De esto puede
 767 resultar que otros contadores de referencia queden en 0 y más celdas sean
 768 liberadas. Por lo tanto, teóricamente la complejidad de eliminar una
 769 referencia puede ser :math:`O(\lvert Live \thickspace set \rvert)` en el peor
 770 caso.
 771
 772 Las primitivas implementadas para este tipo de recolector son las siguientes
 773 (acompañadas de una implementación básica)::
 774
 775    function new() is
 776       cell = alloc()
 777       if cell is null
 778          throw out_of_memory
 779       cell.rc = 1
 780       return cell
 781
 782    function del(cell) is
 783       cell.rc = cell.rc - 1
 784       if cell.rc is 0
 785          foreach child* in cell.children
 786             del(*child)
 787          free(cell)
 788
 789    function update(ref*, cell) is
 790       cell.rc = cell.rc + 1
 791       del(*ref)
 792       *ref = cell
 793
 794
 795
 796 .. _gc_rc_cycles:
 797
 798 Ciclos
 799 ^^^^^^
 800
 801 El conteo de referencias tiene, sin embargo, un problema fundamental: **falla
 802 con estructuras cíclicas**. Esto significa que siempre que haya un ciclo en el
 803 grafo de conectividad, hay una pérdida de memoria potencial en el programa.
 804
 805 Cuando esto sucede, las celdas que participan del ciclo tienen siempre su
 806 contador mayor que 0, sin embargo puede suceder que ningún elemento del *root
 807 set* apunte a una celda dentro del ciclo, por lo tanto el ciclo es *basura*
 808 (al igual que cualquier otra celda para la cual hayan referencias desde el
 809 ciclo pero que no tenga otras referencias externas) y sin embargo los
 810 contadores no son 0. Los ciclos, por lo tanto, violan la invariante del conteo
 811 de referencia.
 812
 813 Hay formas de solucionar esto, pero siempre recaen en un esquema que va por
 814 fuera del conteo de referencias puro. En general los métodos para solucionar
 815 esto son variados y van desde realizar un marcado del sub-grafo para detectar
 816 ciclos y liberarlos hasta tener otro recolector completo de *emergencia*;
 817 pasando por tratar los ciclos como un todo para contar las referencias al
 818 ciclo completo en vez de a cada celda en particular.
 819
 820 Incluso con este problema, el conteo de referencia sin ningún tipo de solución
 821 en cuanto a la detección y recolección de ciclos fue utilizado en muchos
 822 lenguajes de programación sin que su necesidad sea tan evidente. Por ejemplo
 823 Python_ agregó recolección de ciclos en la versión 2.0 [NAS00]_ (liberada en
 824 octubre de 2000) y PHP_ recién agrega detección de ciclos en la versión 5.3
 825 [PHP530]_.
 826
 827
 828 .. _gc_rc_example:
 829
 830 Ejemplo
 831 ^^^^^^^
 832
 833 A continuación se presenta un ejemplo gráfico para facilitar la comprensión
 834 del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos
 835 punteros, ``left`` (``l``) y ``right`` (``r``) y se muestra el contador de
 836 referencias abajo del nombre de cada celda. Se parte con una pequeña
 837 estructura ya construida y se muestra como opera el algoritmo al eliminar
 838 o cambiar una referencia (cambios en la conectividad del grafo). En un
 839 comienzo todas las celdas son accesibles desde el *root set* por lo tanto son
 840 todas parte del *live set*.
 841
 842 Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina que
 843 ``h1`` se convirtió en *basura* (ver figura :vref:`fig:gc-rc-rm-1`). Esto
 844 conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 845 *live set* ya que sus contadores siguen siendo mayores a 0 (ver figura
 846 :vref:`fig:gc-rc-rm-2`).
 847
 848 .. flt:: fig:gc-rc-rm-1
 849
 850    Ejemplo de conteo de referencias: eliminación de una referencia (parte 1)
 851
 852    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
 853
 854    .. subflt::
 855
 856       Estado inicial del grafo de conectividad.
 857
 858       .. digraph:: g3_1
 859
 860          margin = 0;
 861          ratio  = fill;
 862          size   = "1.9,2.6";
 863          edge [ color = gray40 ];
 864          node [
 865             shape     = record,
 866             width     = 0,
 867             height    = 0,
 868             style     = filled,
 869             fillcolor = gray25,
 870             fontcolor = white
 871          ];
 872
 873          subgraph cluster_all {
 874
 875             root [
 876                label     = "root\nset|<r0> r0|<r1> r1",
 877                style     = filled,
 878                fillcolor = gray96,
 879                fontcolor = black,
 880             ];
 881
 882             h1 [ label = "h1\n1|<l> l|<r> r" ];
 883             h2 [ label = "h2\n2|<l> l|<r> r" ];
 884             h3 [ label = "h3\n3|<l> l|<r> r" ];
 885             h4 [ label = "h4\n1|<l> l|<r> r" ];
 886             h5 [ label = "h5\n1|<l> l|<r> r" ];
 887             h6 [ label = "h6\n1|<l> l|<r> r" ];
 888
 889             root:r0 -> h1;
 890             root:r1 -> h3;
 891             h1:l -> h2;
 892             h1:r -> h3;
 893             h2:l -> h4;
 894             h2:r -> h5;
 895             h3:l -> h2;
 896             h3:r -> h6;
 897             h6:r -> h3:r;
 898
 899          }
 900
 901    .. subflt::
 902
 903       Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
 904       ``h1``.
 905
 906       .. digraph:: g3_2
 907
 908          margin = 0;
 909          ratio  = fill;
 910          size   = "1.9,2.6";
 911          edge [ color = gray40 ];
 912          node [
 913             shape     = record,
 914             width     = 0,
 915             height    = 0,
 916             style     = filled,
 917             fillcolor = gray25,
 918             fontcolor = white
 919          ];
 920
 921          subgraph cluster_all {
 922
 923             root [
 924                label     = "root\nset|<r0> r0\n*|<r1> r1",
 925                style     = filled,
 926                fillcolor = gray96,
 927                fontcolor = black,
 928             ];
 929
 930             h1 [ label = "h1\n1|<l> l|<r> r" ];
 931             h2 [ label = "h2\n2|<l> l|<r> r" ];
 932             h3 [ label = "h3\n3|<l> l|<r> r" ];
 933             h4 [ label = "h4\n1|<l> l|<r> r" ];
 934             h5 [ label = "h5\n1|<l> l|<r> r" ];
 935             h6 [ label = "h6\n1|<l> l|<r> r" ];
 936
 937             root:r0 -> h1 [ style = bold, color = black ];
 938             root:r1 -> h3;
 939             h1:l -> h2;
 940             h1:r -> h3;
 941             h2:l -> h4;
 942             h2:r -> h5;
 943             h3:l -> h2;
 944             h3:r -> h6;
 945             h6:r -> h3:r;
 946
 947          }
 948
 949    .. subflt::
 950
 951       Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser *basura*).
 952       Se elimina primero ``h1.l`` y luego ``h1.r``.
 953
 954       .. digraph:: g3_3
 955
 956          margin = 0;
 957          ratio  = fill;
 958          size   = "1.9,2.6";
 959          edge [ color = gray40 ];
 960          node [
 961             shape     = record,
 962             width     = 0,
 963             height    = 0,
 964             style     = filled,
 965             fillcolor = gray25,
 966             fontcolor = white
 967          ];
 968
 969          subgraph cluster_all {
 970
 971             root [
 972                label     = "root\nset|<r0> r0\n*|<r1> r1",
 973                style     = filled,
 974                fillcolor = gray96,
 975                fontcolor = black,
 976             ];
 977
 978             subgraph marked {
 979                node [ fillcolor = white, fontcolor = black ];
 980                h1;
 981             };
 982
 983             h1 [ label = "h1\n0|<l> l|<r> r" ];
 984             h2 [ label = "h2\n2|<l> l|<r> r" ];
 985             h3 [ label = "h3\n3|<l> l|<r> r" ];
 986             h4 [ label = "h4\n1|<l> l|<r> r" ];
 987             h5 [ label = "h5\n1|<l> l|<r> r" ];
 988             h6 [ label = "h6\n1|<l> l|<r> r" ];
 989
 990             root:r0 -> h1 [ style = invis ];
 991             root:r1 -> h3;
 992             h1:l -> h2 [ style = bold, color = black ];
 993             h1:r -> h3;
 994             h2:l -> h4;
 995             h2:r -> h5;
 996             h3:l -> h2;
 997             h3:r -> h6;
 998             h6:r -> h3:r;
 999
1000          }
1001
1002
1003 .. flt:: fig:gc-rc-rm-2
1004    :padding: 0.5
1005
1006    Ejemplo de conteo de referencias: eliminación de una referencia (parte 2)
1007
1008    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
1009
1010    .. subflt::
1011
1012       Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en el
1013       *live set*).
1014
1015       .. digraph:: g3_4
1016
1017          margin = 0;
1018          ratio  = fill;
1019          size   = "1.9,2.6";
1020          edge [ color = gray40 ];
1021          node [
1022             shape     = record,
1023             width     = 0,
1024             height    = 0,
1025             style     = filled,
1026             fillcolor = gray25,
1027             fontcolor = white
1028          ];
1029
1030          subgraph cluster_all {
1031
1032             root [
1033                label     = "root\nset|<r0> r0\n*|<r1> r1",
1034                style     = filled,
1035                fillcolor = gray96,
1036                fontcolor = black,
1037             ];
1038
1039             subgraph marked {
1040                node [ fillcolor = white, fontcolor = black ];
1041                h1;
1042             };
1043
1044             h1 [ label = "h1\n0|<l> l|<r> r" ];
1045             h2 [ label = "h2\n1|<l> l|<r> r" ];
1046             h3 [ label = "h3\n3|<l> l|<r> r" ];
1047             h4 [ label = "h4\n1|<l> l|<r> r" ];
1048             h5 [ label = "h5\n1|<l> l|<r> r" ];
1049             h6 [ label = "h6\n1|<l> l|<r> r" ];
1050
1051             root:r0 -> h1 [ style = invis ];
1052             root:r1 -> h3;
1053             h1:l -> h2 [ style = invis ];
1054             h1:r -> h3 [ style = bold, color = black ];
1055             h2:l -> h4;
1056             h2:r -> h5;
1057             h3:l -> h2;
1058             h3:r -> h6;
1059             h6:r -> h3:r;
1060
1061          }
1062
1063    .. subflt::
1064
1065       El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.
1066
1067       .. digraph:: g3_5
1068
1069          margin = 0;
1070          ratio  = fill;
1071          size   = "1.9,2.6";
1072          edge [ color = gray40 ];
1073          node [
1074             shape     = record,
1075             width     = 0,
1076             height    = 0,
1077             style     = filled,
1078             fillcolor = gray25,
1079             fontcolor = white
1080          ];
1081
1082          subgraph cluster_all {
1083
1084             root [
1085                label     = "root\nset|<r0> r0|<r1> r1",
1086                style     = filled,
1087                fillcolor = gray96,
1088                fontcolor = black,
1089             ];
1090
1091             subgraph marked {
1092                node [ fillcolor = white, fontcolor = black ];
1093                h1;
1094             };
1095
1096             h1 [ label = "h1\n0|<l> l|<r> r" ];
1097             h2 [ label = "h2\n1|<l> l|<r> r" ];
1098             h3 [ label = "h3\n2|<l> l|<r> r" ];
1099             h4 [ label = "h4\n1|<l> l|<r> r" ];
1100             h5 [ label = "h5\n1|<l> l|<r> r" ];
1101             h6 [ label = "h6\n1|<l> l|<r> r" ];
1102
1103             root:r0 -> h1 [ style = invis ];
1104             root:r1 -> h3;
1105             h1:l -> h2 [ style = invis ];
1106             h1:r -> h3 [ style = invis ];
1107             h2:l -> h4;
1108             h2:r -> h5;
1109             h3:l -> h2;
1110             h3:r -> h6;
1111             h6:r -> h3:r;
1112
1113          }
1114
1115
1116 Luego se cambia una referencia (en vez de eliminarse) realizándose la
1117 operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador de
1118 referencias de ``h5`` para evitar confundirlo accidentalmente con *basura* si
1119 se elimina alguna celda que apuntaba a ésta. Luego se procede a decrementar el
1120 contador de ``h2`` que queda en 0, transformándose en *basura* (ver figura
1121 :vref:`fig:gc-rc-up-1`).
1122
1123 .. flt:: fig:gc-rc-up-1
1124
1125    Ejemplo de conteo de referencias: actualización de una referencia (parte 1)
1126
1127    Cambio en la referencia ``h3.l`` :math:`\to` ``h2`` a ``h3.l`` :math:`\to`
1128    ``h5`` (parte 1).
1129
1130    .. subflt::
1131
1132       Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.
1133
1134       .. digraph:: g4_1
1135
1136          margin = 0;
1137          ratio  = fill;
1138          size   = "1.9,2.6";
1139          edge [ color = gray40 ];
1140          node [
1141             shape     = record,
1142             width     = 0,
1143             height    = 0,
1144             style     = filled,
1145             fillcolor = gray25,
1146             fontcolor = white
1147          ];
1148
1149          subgraph cluster_all {
1150
1151             root [
1152                label     = "root\nset|<r0> r0|<r1> r1",
1153                style     = filled,
1154                fillcolor = gray96,
1155                fontcolor = black,
1156             ];
1157
1158             subgraph marked {
1159                node [ fillcolor = white, fontcolor = black ];
1160                h1;
1161             };
1162
1163             h1 [ label = "h1\n0|<l> l|<r> r" ];
1164             h2 [ label = "h2\n1|<l> l|<r> r" ];
1165             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1166             h4 [ label = "h4\n1|<l> l|<r> r" ];
1167             h5 [ label = "h5\n2|<l> l|<r> r" ];
1168             h6 [ label = "h6\n1|<l> l|<r> r" ];
1169
1170             root:r0 -> h1 [ style = invis ];
1171             h1:l -> h2 [ style = invis ];
1172             h1:r -> h3 [ style = invis ];
1173             root:r1 -> h3;
1174             h2:l -> h4;
1175             h2:r -> h5;
1176             h3:l -> h2;
1177             h3:l -> h5 [ style = dotted, color = black ];
1178             h3:r -> h6;
1179             h6:r -> h3:r;
1180
1181          }
1182
1183    .. subflt::
1184
1185       Luego se procede a visitar la antigua referencia de ``h3.l`` (``h2``).
1186
1187       .. digraph:: g4_2
1188
1189          margin = 0;
1190          ratio  = fill;
1191          size   = "1.9,2.6";
1192          edge [ color = gray40 ];
1193          node [
1194             shape     = record,
1195             width     = 0,
1196             height    = 0,
1197             style     = filled,
1198             fillcolor = gray25,
1199             fontcolor = white
1200          ];
1201
1202          subgraph cluster_all {
1203
1204             root [
1205                label     = "root\nset|<r0> r0|<r1> r1",
1206                style     = filled,
1207                fillcolor = gray96,
1208                fontcolor = black,
1209             ];
1210
1211             subgraph marked {
1212                node [ fillcolor = white, fontcolor = black ];
1213                h1;
1214             };
1215
1216             h1 [ label = "h1\n0|<l> l|<r> r" ];
1217             h2 [ label = "h2\n1|<l> l|<r> r" ];
1218             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1219             h4 [ label = "h4\n1|<l> l|<r> r" ];
1220             h5 [ label = "h5\n2|<l> l|<r> r" ];
1221             h6 [ label = "h6\n1|<l> l|<r> r" ];
1222
1223             root:r0 -> h1 [ style = invis ];
1224             h1:l -> h2 [ style = invis ];
1225             h1:r -> h3 [ style = invis ];
1226             root:r1 -> h3;
1227             h2:l -> h4;
1228             h2:r -> h5;
1229             h3:l -> h2 [ style = bold, color = black ];
1230             h3:l -> h5 [ style = dotted, color = black ];
1231             h3:r -> h6;
1232             h6:r -> h3:r;
1233
1234          }
1235
1236    .. subflt::
1237
1238       Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser *basura*).
1239       Se eliminan las referencias a las hijas.
1240
1241       .. digraph:: g4_3
1242
1243          margin = 0;
1244          ratio  = fill;
1245          size   = "1.9,2.6";
1246          edge [ color = gray40 ];
1247          node [
1248             shape     = record,
1249             width     = 0,
1250             height    = 0,
1251             style     = filled,
1252             fillcolor = gray25,
1253             fontcolor = white
1254          ];
1255
1256          subgraph cluster_all {
1257
1258             root [
1259                label     = "root\nset|<r0> r0|<r1> r1",
1260                style     = filled,
1261                fillcolor = gray96,
1262                fontcolor = black,
1263             ];
1264
1265             subgraph marked {
1266                node [ fillcolor = white, fontcolor = black ];
1267                h1; h2;
1268             };
1269
1270             h1 [ label = "h1\n0|<l> l|<r> r" ];
1271             h2 [ label = "h2\n1|<l> l|<r> r" ];
1272             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1273             h4 [ label = "h4\n1|<l> l|<r> r" ];
1274             h5 [ label = "h5\n2|<l> l|<r> r" ];
1275             h6 [ label = "h6\n1|<l> l|<r> r" ];
1276
1277             root:r0 -> h1 [ style = invis ];
1278             h1:l -> h2 [ style = invis ];
1279             h1:r -> h3 [ style = invis ];
1280             root:r1 -> h3;
1281             h2:l -> h4 [ style = bold, color = black ];
1282             h2:r -> h5;
1283             h3:l -> h2 [ style = invis ];
1284             h3:l -> h5 [ style = dotted, color = black ];
1285             h3:r -> h6;
1286             h6:r -> h3:r;
1287
1288          }
1289
1290
1291 Lo mismo pasa cuando se desciende a ``h4``, pero al descender a ``h5``
1292 y decrementar el contador, éste sigue siendo mayor que 0 (pues ``h3`` va
1293 a apuntar a ``h5``) así que permanece en el *live set*. Finalmente se termina
1294 de actualizar la referencia ``h3.l`` para que apunte a ``h5`` (ver figura
1295 :vref:`fig:gc-rc-up-2`).
1296
1297 .. flt:: fig:gc-rc-up-2
1298
1299    Ejemplo de conteo de referencias: actualización de una referencia (parte 2)
1300
1301    Cambio en la referencia ``h3.l`` :math:`\to` ``h2`` a ``h3.l`` :math:`\to`
1302    ``h5`` (parte 2).
1303
1304    .. subflt::
1305
1306       Se decrementa el contador de ``h4`` quedando en 0, pasa a ser *basura*.
1307       Se continúa con ``h5``.
1308
1309       .. digraph:: g4_4
1310
1311          margin = 0;
1312          ratio  = fill;
1313          size   = "1.9,2.6";
1314          edge [ color = gray40 ];
1315          node [
1316             shape     = record,
1317             width     = 0,
1318             height    = 0,
1319             style     = filled,
1320             fillcolor = gray25,
1321             fontcolor = white
1322          ];
1323
1324          subgraph cluster_all {
1325
1326             root [
1327                label     = "root\nset|<r0> r0|<r1> r1",
1328                style     = filled,
1329                fillcolor = gray96,
1330                fontcolor = black,
1331             ];
1332
1333             subgraph marked {
1334                node [ fillcolor = white, fontcolor = black ];
1335                h1; h2; h4;
1336             };
1337
1338             h1 [ label = "h1\n0|<l> l|<r> r" ];
1339             h2 [ label = "h2\n1|<l> l|<r> r" ];
1340             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1341             h4 [ label = "h4\n0|<l> l|<r> r" ];
1342             h5 [ label = "h5\n2|<l> l|<r> r" ];
1343             h6 [ label = "h6\n1|<l> l|<r> r" ];
1344
1345             root:r0 -> h1 [ style = invis ];
1346             h1:l -> h2 [ style = invis ];
1347             h1:r -> h3 [ style = invis ];
1348             root:r1 -> h3;
1349             h2:l -> h4 [ style = invis ];
1350             h2:r -> h5 [ style = bold, color = black ];
1351             h3:l -> h2 [ style = invis ];
1352             h3:l -> h5 [ style = dotted, color = black ];
1353             h3:r -> h6;
1354             h6:r -> h3:r;
1355
1356          }
1357
1358    .. subflt::
1359
1360       Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.
1361
1362       .. digraph:: g4_5
1363
1364          margin = 0;
1365          ratio  = fill;
1366          size   = "1.9,2.6";
1367          edge [ color = gray40 ];
1368          node [
1369             shape     = record,
1370             width     = 0,
1371             height    = 0,
1372             style     = filled,
1373             fillcolor = gray25,
1374             fontcolor = white
1375          ];
1376
1377          subgraph cluster_all {
1378
1379             root [
1380                label     = "root\nset|<r0> r0|<r1> r1",
1381                style     = filled,
1382                fillcolor = gray96,
1383                fontcolor = black,
1384             ];
1385
1386             subgraph marked {
1387                node [ fillcolor = white, fontcolor = black ];
1388                h1; h2; h4;
1389             };
1390
1391             h1 [ label = "h1\n0|<l> l|<r> r" ];
1392             h2 [ label = "h2\n1|<l> l|<r> r" ];
1393             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1394             h4 [ label = "h4\n0|<l> l|<r> r" ];
1395             h5 [ label = "h5\n1|<l> l|<r> r" ];
1396             h6 [ label = "h6\n1|<l> l|<r> r" ];
1397
1398             root:r0 -> h1 [ style = invis ];
1399             h1:l -> h2 [ style = invis ];
1400             h1:r -> h3 [ style = invis ];
1401             root:r1 -> h3;
1402             h2:l -> h4 [ style = invis ];
1403             h2:r -> h5 [ style = invis ];
1404             h3:l -> h5 [ style = bold, color = black ];
1405             h3:l -> h2 [ style = invis ];
1406             h3:r -> h6;
1407             h6:r -> h3:r;
1408
1409          }
1410
1411    .. subflt::
1412
1413       Se termina por actualizar la referencia de ``h3.l`` para que apunte
1414       a ``h5``.
1415
1416       .. digraph:: g4_6
1417
1418          margin = 0;
1419          ratio  = fill;
1420          size   = "1.9,2.6";
1421          edge [ color = gray40 ];
1422          node [
1423             shape     = record,
1424             width     = 0,
1425             height    = 0,
1426             style     = filled,
1427             fillcolor = gray25,
1428             fontcolor = white
1429          ];
1430
1431          subgraph cluster_all {
1432
1433             root [
1434                label     = "root\nset|<r0> r0|<r1> r1",
1435                style     = filled,
1436                fillcolor = gray96,
1437                fontcolor = black,
1438             ];
1439
1440             subgraph marked {
1441                node [ fillcolor = white, fontcolor = black ];
1442                h1; h2; h4;
1443             };
1444
1445             h1 [ label = "h1\n0|<l> l|<r> r" ];
1446             h1 [ label = "h1\n0|<l> l|<r> r" ];
1447             h2 [ label = "h2\n0|<l> l|<r> r" ];
1448             h3 [ label = "h3\n2|<l> l|<r> r" ];
1449             h4 [ label = "h4\n0|<l> l|<r> r" ];
1450             h5 [ label = "h5\n1|<l> l|<r> r" ];
1451             h6 [ label = "h6\n1|<l> l|<r> r" ];
1452
1453             root:r0 -> h1 [ style = invis ];
1454             h1:l -> h2 [ style = invis ];
1455             h1:r -> h3 [ style = invis ];
1456             root:r1 -> h3;
1457             h2:l -> h4 [ style = invis ];
1458             h2:r -> h5 [ style = invis ];
1459             h3:l -> h5;
1460             h3:l -> h2 [ style = invis ];
1461             h3:r -> h6;
1462             h6:r -> h3:r;
1463
1464          }
1465
1466
1467 Finalmente se presenta lo que sucede cuando se elimina la última referencia
1468 a un ciclo (en este caso un ciclo simple de 2 celdas: ``h3`` y ``h6``). Se
1469 elimina la única referencia externa al ciclo (``r1``), por lo que se visita la
1470 celda ``h3`` decrementando su contador de referencias, pero éste continúa
1471 siendo mayor que 0 porque la celda ``h6`` (parte del ciclo) la referencia. Por
1472 lo tanto el ciclo, y todas las celdas a las que apunta que no tienen otras
1473 referencias externas y por lo tanto deberían ser *basura* también (``h5``), no
1474 pueden ser recicladas y su memoria es perdida (ver figura
1475 :vref:`fig:gc-rc-cycle`).
1476
1477 .. flt:: fig:gc-rc-cycle
1478    :padding: 0.5
1479
1480    Ejemplo de conteo de referencias: pérdida de memoria debido a un ciclo
1481
1482    Eliminación de la referencia ``r1`` :math:`\to` ``h3`` (pérdida de memoria
1483    debido a un ciclo).
1484
1485    .. subflt::
1486
1487       El ejecutarse ``update(r1, null)`` se visita la celda ``h3``.
1488
1489       .. digraph:: g4_6
1490
1491          margin = 0;
1492          ratio  = fill;
1493          size   = "1.9,2.6";
1494          edge [ color = gray40 ];
1495          node [
1496             shape     = record,
1497             width     = 0,
1498             height    = 0,
1499             style     = filled,
1500             fillcolor = gray25,
1501             fontcolor = white
1502          ];
1503
1504          subgraph cluster_all {
1505
1506             root [
1507                label     = "root\nset|<r0> r0|<r1> r1\n*",
1508                style     = filled,
1509                fillcolor = gray96,
1510                fontcolor = black,
1511             ];
1512
1513             subgraph marked {
1514                node [ fillcolor = white, fontcolor = black ];
1515                h1; h2; h4;
1516             };
1517
1518             h1 [ label = "h1\n0|<l> l|<r> r" ];
1519             h1 [ label = "h1\n0|<l> l|<r> r" ];
1520             h2 [ label = "h2\n0|<l> l|<r> r" ];
1521             h3 [ label = "h3\n2|<l> l|<r> r" ];
1522             h4 [ label = "h4\n0|<l> l|<r> r" ];
1523             h5 [ label = "h5\n1|<l> l|<r> r" ];
1524             h6 [ label = "h6\n1|<l> l|<r> r" ];
1525
1526             root:r0 -> h1 [ style = invis ];
1527             h1:l -> h2 [ style = invis ];
1528             h1:r -> h3 [ style = invis ];
1529             root:r1 -> h3 [ style = bold, color = black ];
1530             h2:l -> h4 [ style = invis ];
1531             h2:r -> h5 [ style = invis ];
1532             h3:l -> h5;
1533             h3:l -> h2 [ style = invis ];
1534             h3:r -> h6;
1535             h6:r -> h3:r;
1536
1537          }
1538
1539    .. subflt::
1540
1541       Se decrementa el contador de ``h3`` pero sigue siendo mayor que 0 por el
1542       ciclo.
1543
1544       .. digraph:: g5_2
1545
1546          margin = 0;
1547          ratio  = fill;
1548          size   = "1.9,2.6";
1549          edge [ color = gray40 ];
1550          node [
1551             shape     = record,
1552             width     = 0,
1553             height    = 0,
1554             style     = filled,
1555             fillcolor = gray25,
1556             fontcolor = white
1557          ];
1558
1559          subgraph cluster_all {
1560
1561             root [
1562                label     = "root\nset|<r0> r0|<r1> r1\n*",
1563                style     = filled,
1564                fillcolor = gray96,
1565                fontcolor = black,
1566             ];
1567
1568             subgraph marked {
1569                node [ fillcolor = white, fontcolor = black ];
1570                h1; h2; h4;
1571             };
1572
1573             h1 [ label = "h1\n0|<l> l|<r> r" ];
1574             h1 [ label = "h1\n0|<l> l|<r> r" ];
1575             h2 [ label = "h2\n0|<l> l|<r> r" ];
1576             h3 [ label = "h3\n1|<l> l|<r> r" ];
1577             h4 [ label = "h4\n0|<l> l|<r> r" ];
1578             h5 [ label = "h5\n1|<l> l|<r> r" ];
1579             h6 [ label = "h6\n1|<l> l|<r> r" ];
1580
1581             root:r0 -> h1 [ style = invis ];
1582             h1:l -> h2 [ style = invis ];
1583             h1:r -> h3 [ style = invis ];
1584             root:r1 -> h3 [ style = invis ];
1585             h2:l -> h4 [ style = invis ];
1586             h2:r -> h5 [ style = invis ];
1587             h3:l -> h5;
1588             h3:l -> h2 [ style = invis ];
1589             h3:r -> h6;
1590             h6:r -> h3:r;
1591
1592          }
1593
1594
1595
1596 .. _gc_mark_sweep:
1597
1598 Marcado y barrido
1599 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1600
1601 Este algoritmo es el más parecido a la teoría sobre recolección de basura.
1602 Consiste en realizar la recolección en 2 fases: marcado y barrido. La primera
1603 fase consiste en el proceso de marcar el grafo de conectividad del *heap* para
1604 descubrir qué celdas son alcanzables desde el *root set*, tal y como se
1605 describió en :ref:`gc_intro_mark`.
1606
1607 Una vez marcadas todas las celdas, se sabe que las celdas *blancas* son
1608 *basura*, por lo tanto el paso que queda es el *barrido* de estas celdas,
1609 liberándolas. Esto se efectúa recorriendo todo el *heap*. Por lo tanto cada
1610 recolección es :math:`O(\lvert Heap \rvert)`, a diferencia del conteo de
1611 referencia que dijimos que en el peor caso es :math:`O(\lvert Live \thickspace
1612 set \rvert)`. Sin embargo el conteo de referencias se ejecuta **cada vez que
1613 se actualiza una referencia** mientras que la recolección en el marcado
1614 y barrido se realiza típicamente solo cuando el *mutator* pide una celda pero
1615 no hay ninguna libre. Esto hace que la constante del conteo de referencias sea
1616 típicamente varios órdenes de magnitud mayores que en el marcado y barrido.
1617
1618 A continuación se presentan los servicios básicos de este algoritmo::
1619
1620    function new() is
1621       cell = alloc()
1622       if cell is null
1623          collect()
1624       cell = alloc()
1625       if cell is null
1626          throw out_of_memory
1627       return cell
1628
1629    function collect() is
1630       mark_phase()
1631       sweep_phase()
1632
1633    function sweep_phase() is
1634       foreach cell in heap
1635          if cell.marked
1636             cell.marked = false
1637          else
1638             free(cell)
1639
1640 El algoritmo ``mark_sweep()`` es exactamente igual al presentado en
1641 :ref:`gc_intro_mark`. Es preciso notar que la fase de barrido
1642 (``sweep_phase()``) debe tener una comunicación extra con el *low level
1643 allocator* para poder obtener todas las celdas de memoria que existen en el
1644 *heap*.
1645
1646 A diferencia del conteo de referencias, este algoritmo es :ref:`indirecto
1647 <gc_direct>` y :ref:`no incremental <gc_inc>`, ya que se realiza un recorrido
1648 de todo el *heap* de forma espaciada a través de la ejecución del programa. En
1649 general el *mutator* sufre pausas considerablemente mayores (en promedio) que
1650 con el conteo de referencias, lo que puede ser problemático para aplicaciones
1651 con requerimientos rígidos de tiempo, como aplicaciones *real-time*. Debido
1652 a la percepción de las pausas grandes, este tipo de colectores se conocen como
1653 :ref:`stop-the-world <gc_concurrent>` (o *detener el mundo*).
1654
1655 Una ventaja fundamental sobre el conteo de referencias es la posibilidad de
1656 reclamar estructuras cíclicas sin consideraciones especiales. Podemos observar
1657 como esto es posible analizando el ejemplo en las figuras :r:`fig:gc-mark-1`
1658 y :vref:`fig:gc-mark-2`. Si se eliminaran las referencias :math:`r0 \to h1`
1659 y :math:`h6 \to h2`, la fase de marcado consistiría solamente en marcar la
1660 celda :math:`h6`, pues es la única alcanzable desde el *root set*. Todas las
1661 demás celdas permanecerían blancas y por lo tanto pueden ser liberadas sin
1662 inconvenientes en la fase de barrido, que recorre el *heap* linealmente.
1663
1664
1665
1666 .. _gc_copy:
1667
1668 Copia de semi-espacio
1669 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1670
1671 Este algoritmo consiste en hacer una partición del *heap* en 2 mitades
1672 o *semi-espacios*, llamados usualmente *Fromspace* y *Tospace*. El primero se
1673 utiliza para asignar nuevas celdas de forma lineal, asumiendo un *heap*
1674 contiguo, incrementando un puntero (ver figura :vref:`fig:gc-copy`).  Esto se
1675 conoce como *pointer bump allocation* y es, probablemente, la forma más
1676 eficiente de asignar memoria (tan eficiente como asignar memoria en el
1677 *stack*). Esto permite además evitar el problema de la *fragmentación* de
1678 memoria [#gcfrag]_ que normalmente afectan a los otros algoritmos clásicos (o
1679 sus *low level allocators*).
1680
1681 .. [#gcfrag] La *fragmentación* de memoria sucede cuando se asignan objetos
1682    de distintos tamaños y luego libera alguno intermedio, produciendo
1683    *huecos*. Estos *huecos* quedan inutilizables hasta que se quiera
1684    asignar un nuevo objeto de tamaño igual al *hueco* (o menor). Si esto no
1685    sucede y se acumulan muchos *huecos* se dice que la memoria está
1686    *fragmentada*.
1687
1688 .. flt:: fig:gc-copy
1689
1690    Estructura del *heap* de un recolector con copia de semi-espacios
1691
1692    .. aafig::
1693       :aspect: 70
1694       :scale: 115
1695
1696       zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
1697
1698        /---+"Fromspace"                /---+"Tospace"
1699        |                               |
1700        V_______________________________V_______________________________
1701        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1702        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1703        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1704        |~~~~~~~~~~~~~~~A~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1705                        |
1706        |               |               |    XX "Fromspace usado"
1707                        \---+"libre"
1708        |                               |    ZZ "Fromspace basura"
1709
1710        |/  "longitud del semi-espacio" |/   AA "Fromspace libre"
1711        +- - - - - - - - - - - - - - - -+
1712       /|                              /|    BB "Tospace"
1713
1714
1715 La segunda mitad (*Tospace*) permanece inutilizada hasta que se agota el
1716 espacio en el *Fromspace*; en ese momento comienza el proceso de recolección
1717 de basura que consiste en recorrer el grafo de conectividad, copiando las
1718 celdas *vivas* del *Fromspace* al *Tospace* de manera contigua, como si
1719 estuvieran asignando por primera vez. Como la posición en memoria de las
1720 celdas cambia al ser movidas, es necesario actualizar la dirección de memoria
1721 de todas las celdas *vivas*. Para esto se almacena una dirección de memoria de
1722 re-dirección, *forwarding address*, en las celdas que mueven. La *forwarding
1723 address* sirve a su vez de marca, para no recorrer una celda dos veces (como
1724 se explica en :ref:`gc_intro_mark`). Cuando se encuentra una celda que ya fue
1725 movida, simplemente se actualiza la referencia por la cual se llegó a esa
1726 celda para que apunte a la nueva dirección, almacenada en la *forwarding
1727 address*. Una vez finalizado este proceso, el *Fromspace* y *Tospace*
1728 invierten roles y se prosigue de la misma manera (todo lo que quedó en el
1729 viejo *Fromspace* es *basura* por definición, por lo que se convierte el
1730 *Tospace*).
1731
1732 A continuación se presenta una implementación sencilla de los servicios
1733 provistos por este tipo de recolectores. Cabe destacar que este tipo de
1734 recolectores deben estar íntimamente relacionados con el *low level
1735 allocator*, ya que la organización del *heap* y la forma de asignar memoria es
1736 parte fundamental de este algoritmo. Se asume que ya hay dos áreas de memoria
1737 del mismo tamaño destinadas al *Fromspace* y *Tospace*, y la existencia de
1738 4 variables: ``fromspace`` (que apunta a la base del *Fromspace*), ``tospace``
1739 (que apunta a la base del *Tospace*), ``spacesize`` (que contiene el tamaño de
1740 un semi-espacio) y ``free`` (que apunta al lugar del *Fromspace* donde
1741 comienza la memoria libre). También vale aclarar que este algoritmo soporta
1742 inherentemente celdas de tamaño variable, por lo que los servicios ``alloc()``
1743 y ``new()`` [#gccopynew]_ reciben como parámetro el tamaño de la celda
1744 a asignar::
1745
1746    function alloc(size) is
1747       if free + size > fromspace + spacesize
1748          return null
1749       else
1750          cell = free
1751          free = free + size
1752          return cell
1753
1754    function new(size) is
1755       cell = alloc(size)
1756       if cell is null
1757          collect()
1758       cell = alloc(size)
1759       if cell is null
1760          throw out_of_memory
1761       return cell
1762
1763    function collect() is
1764       free = tospace
1765       foreach r in root_set
1766          r = copy(r)
1767       fromspace, tospace = tospace, fromspace
1768
1769    function copy(cell) is
1770       if cell.forwarding_address is null
1771          cell.forwarding_address = free
1772          free = free + cell.size
1773          foreach child in cell
1774             child = copy(child)
1775          return cell.forwarding_address
1776       else
1777          return cell.forwarding_address
1778
1779 .. [#gccopynew] Notar que ``new()`` es igual que en el marcado y barrido con
1780    la salvedad de que en este caso toma como parámetro el tamaño de la celda.
1781
1782 Esta técnica tiene nombres variados en inglés: *semi-space*, *two-space*
1783 o simplemente *copying collector*. En este documento se denomina "copia de
1784 semi-espacio" porque los otros nombres son demasiado generales y pueden
1785 describir, por ejemplo, algoritmos donde no hay copia de celdas o donde no hay
1786 2 semi-espacios (como se verá en :ref:`gc_art`).
1787
1788 Al igual que el :ref:`gc_mark_sweep` este algoritmo es :ref:`indirecto
1789 <gc_direct>`, :ref:`no incremental <gc_inc>` y :ref:`stop-the-world
1790 <gc_concurrent>`. Las diferencias con los esquemas vistos hasta ahora son
1791 evidentes. La principal ventaja sobre el marcado y barrido (que requiere una
1792 pasada sobre el *live set*, el marcado, y otra sobre el *heap* entero, el
1793 barrido) es que este método requiere una sola pasada y sobre las celdas vivas
1794 del *heap* solamente. La principal desventaja es copia memoria, lo que puede
1795 ser particularmente costoso, además de requerir, como mínimo, el doble de
1796 memoria de lo que el *mutator* realmente necesita. Esto puede traer en
1797 particular problemas con la memoria virtual y el caché, por la pobre localidad
1798 de referencia.
1799
1800 Por lo tanto los recolectores de este tipo pueden ser convenientes por sobre
1801 el marcado y barrido cuando se espera que el *live set* sea muy pequeño luego
1802 de una recolección. En estos casos el trabajo realizado por este tipo de
1803 recolectores puede ser considerablemente menor que el del marcado y barrido.
1804 Y por el contrario, si el *working set* es pequeño, al ser *compactado* en
1805 memoria puede mejorar la localidad de referencia (si el *working set* es
1806 grande se corre el riesgo de que la localidad de referencia empeore al moverse
1807 las celdas).
1808
1809
1810 Ejemplo
1811 ^^^^^^^
1812
1813 A continuación se presenta un sencillo ejemplo del algoritmo. Se parte de una
1814 estructura simple con 4 celdas en el *Fromspace* (que incluye un pequeño ciclo
1815 para mostrar que este algoritmo tampoco tiene inconvenientes para
1816 recolectarlos). Asumimos que ya no queda lugar en el *Fromspace* por lo que
1817 comienza la ejecución de ``collect()``. Se comienza por el *root set* que
1818 apunta a ``h3``, por lo tanto ésta es movida al *Tospace* primero, dejando una
1819 *forwarding address* a la nueva ubicación (ver figura
1820 :vref:`fig:gc-copy-ex-1`).
1821
1822 .. flt:: fig:gc-copy-ex-1
1823
1824    Ejemplo de recolección con copia de semi-espacios (parte 1)
1825
1826    .. subflt::
1827
1828       Estructura inicial del *heap*. El *Fromspace* está complete y se inicial
1829       la recolección.
1830
1831       .. aafig::
1832
1833          +--------------------------------------------------+
1834          | "Fromspace"                                      |
1835          |        /--------------------------------\        |
1836          |        | /--------\  /------\           |        |
1837          |        | |        |  |      |           |        |
1838          |  ______|_V________|__V______|___________V______  |
1839          | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
1840          | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
1841          |  ~~~~~~~~~|~~~~~~~~~~A~~~~~~~A~~~~~~~~~~~~~~~~~  |
1842          |      h1   |      h2  |   h3  |       h4          |
1843          |           \----------/       |                   |
1844          |                              \----+"root set"    |
1845          |                                                  |
1846          |                                                  |
1847          |                                                  |
1848          |  ______________________________________________  |
1849          | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1850          | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1851          | A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1852          | |                                                |
1853          | \----+"free"                                     |
1854          | "Tospace"                                        |
1855          +--------------------------------------------------+
1856
1857    .. subflt::
1858
1859       Se sigue la referencia del *root set*, copiando ``h3`` al *Tospace*
1860       y dejando una *forwarding address*.
1861
1862       .. aafig::
1863
1864          +--------------------------------------------------+
1865          | "Fromspace"                                      |
1866          |        /--------------------------------\        |
1867          |        | /--------\  /------\           |        |
1868          |        | |        |  |      |           |        |
1869          |  ______|_V________|__V______|___________V______  |
1870          | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
1871          | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
1872          |  ~~~~~~~~~|~~~~~~~~~~A~~~~~~~|A~~~~~~~~~~~~~~~~  |
1873          |      h1   |      h2  |   h3  ||      h4          |
1874          |           \----------/       ||                  |
1875          |                              +\----+"root set"   |
1876          |                             /                    |
1877          |  /-------------------------+                     |
1878          |  | h3                                            |
1879          |  V_____________________________________________  |
1880          | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1881          | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1882          |  ~~~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1883          |         |                                        |
1884          |         \----+"free"                             |
1885          | "Tospace"                                        |
1886          +--------------------------------------------------+
1887
1888
1889 A continuación se copian las *hijas* de ``h3``, en este caso sólo ``h2``, que
1890 se ubica en el *Tospace* a continuación de ``h3``, dejando nuevamente su
1891 ``forwarding address`` en la celda original. Al proceder recursivamente, se
1892 procede a copiar ``h1`` al *Tospace*, dejando una vez más la *forwarding
1893 address* en la celda original y procediendo con las hijas. Aquí podemos
1894 observar que al seguirse la referencia :math:`h1 \to h2`, como ``h2`` ya había
1895 sido visitada, solamente se actualiza la referencia apuntando a la nueva
1896 ubicación de ``h2`` pero no se vuelve a copiar la celda (ver figura
1897 :vref:`fig:gc-copy-ex-2`).
1898
1899 .. flt:: fig:gc-copy-ex-2
1900
1901    Ejemplo de recolección con copia de semi-espacios (parte 2)
1902
1903    .. subflt::
1904
1905       Se sigue :math:`h3 \to h2`, copiando ``h2`` al *Tospace* y dejando una
1906       *forwarding address*.
1907
1908       .. aafig::
1909
1910          +--------------------------------------------------+
1911          | "Fromspace"                                      |
1912          |        /--------------------------------\        |
1913          |        | /--------\  /------\           |        |
1914          |        | |        |  |      |           |        |
1915          |  ______|_V________|__V______|___________V______  |
1916          | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1917          | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1918          |  ~~~~~~~~~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~  |
1919          |      h1   |      h2  ||  h3  ||      h4          |
1920          |           \----------/+      ||                  |
1921          |                      /       +\----+"root set"   |
1922          |         +-----------+       /                    |
1923          |  /------+------------------+                     |
1924          |  | h3   | h2                                     |
1925          |  V______V______________________________________  |
1926          | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1927          | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1928          |  ~~|~~~~~~A~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1929          |    |      |     |                                |
1930          |    \------/     \----+"free"                     |
1931          | "Tospace"                                        |
1932          +--------------------------------------------------+
1933
1934    .. subflt::
1935
1936       Se sigue :math:`h2 \to h1`, copiando ``h1``. Luego :math:`h1 \to h2`
1937       pero ``h2`` no se copia, sólo se actualiza la referencia con la
1938       *forwarding address*.
1939
1940       .. aafig::
1941
1942          +--------------------------------------------------+
1943          | "Fromspace"                                      |
1944          |        /--------------------------------\        |
1945          |        | /--------\  /------\           |        |
1946          |        | |        |  |      |           |        |
1947          |  ______|_V________|__V______|___________V______  |
1948          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1949          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1950          |  ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~  |
1951          |      h1 | |      h2  ||  h3  ||      h4          |
1952          |         \-+----------/+      ||                  |
1953          |           +-----+    /       +\-----+"root set"  |
1954          |         +-------+---+       /                    |
1955          |  /------+-------+----------+                     |
1956          |  | h3   | h2    | h1                             |
1957          |  V______V_______V______________________________  |
1958          | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
1959          | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
1960          |  ~~|~~~~~~A~|~A~~|~A~~~~A~~~~~~~~~~~~~~~~~~~~~~  |
1961          |    |      | | |  | |    |                        |
1962          |    \------/ | \--/ |    \----+"free"             |
1963          | "Tospace"   \------/                             |
1964          +--------------------------------------------------+
1965
1966
1967 Se termina de copiar recursivamente las hijas de ``h1`` al copiar ``h4`` que
1968 resulta la última celda (sin hijas). Finalmente se invierten los roles de los
1969 semi-espacios y se actualiza la referencia del *root set* para que apunte a la
1970 nueva ubicación de ``h3``, como se muestra en la figura
1971 :vref:`fig:gc-copy-ex-3`.
1972
1973 .. flt:: fig:gc-copy-ex-3
1974
1975    Ejemplo de recolección con copia de semi-espacios (parte 3)
1976
1977    .. subflt::
1978
1979       Se sigue :math:`h1 \to h4` copiando `h4`` al *Tospace* y dejando una
1980       *forwarding address*.
1981
1982       .. aafig::
1983
1984          +--------------------------------------------------+
1985          | "Fromspace"                                      |
1986          |        /--------------------------------\        |
1987          |        | /--------\  /------\           |        |
1988          |        | |        |  |      |           |        |
1989          |  ______|_V________|__V______|___________V______  |
1990          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
1991          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
1992          |  ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~|~~~~~  |
1993          |      h1 | |      h2  ||  h3  ||      h4  \----\  |
1994          |         \-+----------/+      ||               |  |
1995          |           +-----+    /  +----/\---+"root set" |  |
1996          |         +-------+---+  /                      |  |
1997          |  /------+-------+-----+  /--------------------/  |
1998          |  | h3   | h2    | h1     | h4                    |
1999          |  V______V_______V________V_____________________  |
2000          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2001          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2002          |  ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~  |
2003          |    |      | | |  | | |      |   |                |
2004          |    \------/ | \--/ | \------/   \----+"free"     |
2005          | "Tospace"   \------/                             |
2006          +--------------------------------------------------+
2007
2008    .. subflt::
2009
2010       Se finaliza la recolección, se intercambian los roles de los
2011       semi-espacios y se actualiza la referencia del *root set*.
2012
2013       .. aafig::
2014
2015          +--------------------------------------------------+
2016          | "Tospace"                                        |
2017          |                                                  |
2018          |                                                  |
2019          |                                                  |
2020          |  ______________________________________________  |
2021          | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
2022          | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
2023          |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
2024          |                                                  |
2025          |                                                  |
2026          |                                                  |
2027          | /---+"root set"                                  |
2028          | |                                                |
2029          | | h3      h2      h1      h4                     |
2030          | V______________________________________________  |
2031          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2032          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2033          |  ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~  |
2034          |    |      | | |  | | |      |   |                |
2035          |    \------/ | \--/ | \------/   \---+"free"      |
2036          | "Fromspace" \------/                             |
2037          +--------------------------------------------------+
2038
2039
2040
2041 .. _gc_art:
2042
2043 Estado del arte
2044 ----------------------------------------------------------------------------
2045
2046 La manera en que la investigación sobre recolección de basura ha crecido es
2047 realmente sorprendente. Hay, al menos, 2995 publicaciones sobre recolección de
2048 basura registradas al momento de escribir este documento [GCBIB]_. Esto hace
2049 que el análisis del estado del arte sea particularmente complejo y laborioso.
2050
2051 Analizar todas las publicaciones existentes es algo excede los objetivos de
2052 este trabajo, por lo tanto se analizó solo una porción significativa,
2053 utilizando como punto de partida a [JOLI96]_.
2054
2055 De este análisis se observó que la gran mayoría de los algoritmos son
2056 combinaciones de diferentes características básicas; por lo tanto se intentó
2057 aislar estas características que son utilizadas como bloques de construcción
2058 para algoritmos complejos. Ésta tampoco resultó ser una tarea sencilla debido
2059 a que muchos de estos bloques de construcción básicos están interrelacionados
2060 y encontrar una división clara para obtener características realmente atómicas
2061 no es trivial.
2062
2063 La construcción de recolectores más complejos se ve alimentada también por la
2064 existencia de recolectores *híbridos*; es decir, recolectores que utilizan más
2065 de un algoritmo dependiendo de alguna característica de la memoria
2066 a administrar. No es poco común observar recolectores que utilizan un
2067 algoritmo diferente para celdas que sobreviven varias recolecciones que para
2068 las que mueren rápidamente, o que usan diferentes algoritmos para objetos
2069 pequeños y grandes, o que se comporten de forma conservativa para ciertas
2070 celdas y sean precisos para otras.
2071
2072 De todas estas combinaciones resulta el escenario tan fértil para la
2073 investigación sobre recolección de basura.
2074
2075 A continuación se presentan las principales clases de algoritmos
2076 y características básicas encontradas durante la investigación del estado del
2077 arte. La separación de clases y aislamiento de características no es siempre
2078 trivial, ya que hay ciertas clases de recolectores que están interrelacionadas
2079 (o ciertas características pueden estar presentes sólo en recolectores de una
2080 clase en particular).
2081
2082
2083
2084 .. _gc_direct:
2085
2086 Recolección directa / indirecta
2087 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2088
2089 Generalmente se llama recolección **directa** a aquella en la cual el
2090 compilador o lenguaje instrumenta al *mutator* de forma tal que la información
2091 sobre el grafo de conectividad se mantenga activamente cada vez que hay un
2092 cambio en él. Normalmente se utiliza un contador de referencia en cada celda
2093 para este propósito, permitiendo almacenar en todo momento la cantidad de
2094 nodos que apuntan a ésta (ver :ref:`gc_rc`). Esto permite reclamar una celda
2095 instantáneamente cuando el *mutator* deja de hacer referencia a ella.  Este
2096 tipo de recolectores son inherentemente :ref:`incrementales <gc_inc>`.
2097
2098 Por el contrario, los recolectores **indirectos** normalmente no interfieren
2099 con el *mutator* en cada actualización del grafo de conectividad (exceptuando
2100 algunos :ref:`recolectores incrementales <gc_inc>` que a veces necesitan
2101 instrumentar el *mutator* pero no para mantener el estado del grafo de
2102 conectividad completo). La recolección se dispara usualmente cuando el
2103 *mutator* requiere asignar memoria pero no hay más memoria libre conocida
2104 disponible y el recolector se encarga de generar la información de
2105 conectividad desde cero para determinar qué celdas son *basura*.
2106 Prácticamente todos los recolectores menos el :ref:`conteo de referencias
2107 <gc_rc>` están dentro de esta categoría (como por ejemplo, el :ref:`marcado
2108 y barrido <gc_mark_sweep>` y :ref:`copia de semi-espacio <gc_copy>`).
2109
2110 Otros ejemplos de recolectores modernos *directos* son el recolector de basura
2111 de Python_ [NAS00]_ y [LINS05]_ (aunque ambos tiene un algoritmo *indirecto*
2112 para recuperar ciclos).
2113
2114
2115
2116 .. _gc_inc:
2117
2118 Recolección incremental
2119 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2120
2121 Recolección incremental es aquella que se realiza de forma intercalada con el
2122 *mutator*. En general el propósito es disminuir el tiempo de las pausas
2123 causadas por el recolector (aunque generalmente el resultado es un mayor costo
2124 total de recolección en términos de tiempo).
2125
2126 De los `algoritmos clásicos`_ el único que es incremental en su forma más
2127 básica es el :ref:`conteo de referencias <gc_rc>`. Otros recolectores pueden
2128 hacerse incrementales de diversas maneras, pero en general consta de hacer
2129 parte del trabajo de escanear el grafo de conectividad cada vez que el
2130 *mutator* asigna memoria. En general para hacer esto es también necesario
2131 instrumentar al *mutator* de forma tal que informe al recolector cada vez que
2132 cambia el grafo de conectividad, para que éste pueda marcar al sub-grafo
2133 afectado por el cambio como *desactualizado* y así re-escanearlo nuevamente en
2134 la próxima iteración. Para realizar esto en recolectores :ref:`indirectos
2135 <gc_direct>` se utiliza la :ref:`abstracción tricolor <gc_intro_tricolor>`;
2136 cuando el *mutator* cambia una referencia, se marca *gris* la celda que la
2137 contiene, de modo que el recolector vuelva a visitarla.
2138
2139 En general el rendimiento de los recolectores incrementales disminuye
2140 considerablemente cuando el *mutator* actualiza muy seguido el grafo de
2141 conectividad, porque debe re-escanear sub-grafos que ya había escaneado una
2142 y otra vez. A esto se debe también que en general el tiempo de procesamiento
2143 total de un recolector incremental sea mayor que uno no incremental, aunque el
2144 tiempo de pausa de una recolección sea menor.
2145
2146 Ejemplos de recolectores que se encuentran dentro de esta categoría son
2147 [BOEH91]_, [LINS05]_,
2148
2149
2150
2151 .. _gc_concurrent:
2152
2153 Recolección concurrente / paralela / *stop-the-world*
2154 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2155
2156 Los recolectores concurrentes son aquellos que pueden correr en paralelo con
2157 el *mutator*. Por el contrario, aquellos que pausan el *mutator* para realizar
2158 la recolección son usualmente denominados *stop-the-world* (*detener el
2159 mundo*), haciendo referencia a que pausan todos los hilos del *mutator* para
2160 poder escanear el grafo de conectividad de forma consistente. Hay una tercera
2161 clase de colectores que si bien son *stop-the-world*, utilizan todos los hilos
2162 disponibles para realizar la recolección (ver figura
2163 :vref:`fig:gc-concurrent`).
2164
2165 .. flt:: fig:gc-concurrent
2166
2167    Distintos tipos de recolectores según el comportamiento en ambientes
2168    multi-hilo
2169
2170    .. subflt::
2171
2172       *Stop-the-world*.
2173
2174       .. aafig::
2175          :scale: 110
2176          :aspect: 70
2177
2178           ___________________________________________________________________
2179          |                                                                   |
2180          | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
2181          |                                                                   |
2182          | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHHHHHHH |
2183          |                                                                   |
2184          | HHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
2185          |                                                                   |
2186          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2187          |___________________________________________________________________|
2188
2189    .. subflt::
2190
2191       Paralelo.
2192
2193       .. aafig::
2194          :scale: 110
2195          :aspect: 70
2196
2197           ___________________________________________________________________
2198          |                                                                   |
2199          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2200          |                                                                   |
2201          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2202          |                                                                   |
2203          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2204          |                                                                   |
2205          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2206          |___________________________________________________________________|
2207
2208    .. subflt::
2209
2210       Concurrente.
2211
2212       .. aafig::
2213          :scale: 110
2214          :aspect: 70
2215
2216           ___________________________________________________________________
2217          |                                                                   |
2218          | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
2219          |                                                                   |
2220          | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
2221          |                                                                   |
2222          | ZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZ |
2223          |                                                                   |
2224          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2225          |___________________________________________________________________|
2226
2227
2228 Para lograr que un recolector sea concurrente generalmente el mecanismo es
2229 similar al necesario para hacer un :ref:`recolector incremental <gc_inc>`: hay
2230 que instrumentar al *mutator* para que informe al recolector cuando se realiza
2231 algún cambio en el grafo de conectividad, de forma tal que pueda volver
2232 a escanear el sub-grafo afectado por el cambio.
2233
2234 Esto también trae como consecuencia el incremento en el tiempo total que
2235 consume el recolector, debido a la necesidad de re-escanear sub-grafos que han
2236 sido modificados, además de la sincronización necesaria entre *mutator*
2237 y recolector.
2238
2239 ¿Cuál es la idea entonces de un recolector concurrente? Una vez más, al igual
2240 que los recolectores incrementales, el principal objetivo es disminuir las
2241 largas pausas provocadas por la recolección de basura. Sin embargo, este tipo
2242 de algoritmos además permite hacer un mejor aprovechamiento de las
2243 arquitecturas *multi-core* [#gcmulticore]_ que cada vez son más comunes, ya
2244 que el *mutator* y el recolector pueden estar corriendo realmente en paralelo,
2245 cada uno en un procesador distinto. Algunos recolectores van más allá
2246 y permiten incluso paralelizar la recolección de basura en varios hilos
2247 ([HUEL98]_, [LINS05]_). Otros ejemplos de recolectores concurrentes (aunque no
2248 ofrece paralelización del procesamiento del recolector en varios hilos) son
2249 [BOEH91]_, [RODR97]_.
2250
2251 .. [#gcmulticore] Una arquitectura *multi-core* es aquella que combina dos
2252    o más núcleos (*cores*) independientes que trabajan a la misma frecuencia,
2253    pero dentro de un solo circuito integrado o procesador.
2254
2255 Todos los :ref:`algoritmos clásicos <gc_classic>` que se han citado son del
2256 tipo *stop-the-world*.
2257
2258
2259
2260 .. _gc_free_list:
2261
2262 Lista de libres / *pointer bump allocation*
2263 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2264
2265 Esta clasificación se refiere principalmente a la forma en que se organiza el
2266 *heap*, íntimamente relacionado al *low level allocator*. Si bien se ha dicho
2267 que en este trabajo no se prestará particular atención a este aspecto, en
2268 ciertos algoritmos es tan relevante que tampoco es sensato pasarlo por alto
2269 completamente.
2270
2271 En términos generales, hay dos formas fundamentales de organizar el *heap*,
2272 manteniendo una lista de libres o realizando *pointer bump allocation*, como
2273 se explicó en :ref:`gc_copy`. La primera forma consiste, a grandes rasgos, en
2274 separar el *heap* en celdas (que pueden agruparse según tamaño) y enlazarlas
2275 en una lista de libres. Al solicitarse una nueva celda simplemente se la
2276 desenlaza de la lista de libres. Por otro lado, cuando el recolector detecta
2277 una celda *muerta*, la vuelve a enlazar en la lista de libres. Este es un
2278 esquema simple pero con limitaciones, entre las principales, el costo de
2279 asignar puede ser alto si hay muchos tamaños distintos de celda y soportar
2280 tamaño de celda variable puede ser complejo o acarrear muchas otras
2281 ineficiencias. El :ref:`marcado y barrido <gc_mark_sweep>` en general usa este
2282 esquema, al igual que el :ref:`conteo de referencias <gc_rc>`.
2283
2284 Otro forma de organizar el *heap* es utilizándolo como una especie de *stack*
2285 en el cual para asignar simplemente se incrementa un puntero. Este esquema es
2286 simple y eficiente, si el recolector puede mover celdas (ver
2287 :ref:`gc_moving`); de otra manera asignar puede ser muy costoso si hay que
2288 buscar un *hueco* en el heap (es decir, deja de reducirse a incrementar un
2289 puntero). El clásico ejemplo de esta familia es el algoritmo visto en
2290 :ref:`gc_copy`.
2291
2292 Sin embargo, entre estos dos extremos, hay todo tipo de híbridos. Existen
2293 recolectores basados en *regiones*, que se encuentran en un punto intermedio.
2294 Dentro de una región se utiliza un esquema de *pointer bump allocation* pero
2295 las regiones en sí se administran como una lista de libres (como por ejemplo
2296 [BLAC08]_). Otra variación (más común) de este esquema son los *two level
2297 allocators* que asignan páginas completas (similar a las regiones) y dentro de
2298 cada página se asignan las celdas. Ambas, páginas y celdas, se administran
2299 como listas de libres (ejemplos que utilizan este esquema son [BOEHWD]_ y el
2300 :ref:`recolector actual de D <dgc_actual>`).
2301
2302
2303
2304 .. _gc_moving:
2305
2306 Movimiento de celdas
2307 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2308
2309 Otra característica muy importante del recolector de basura es si mueve las
2310 celdas o no. En general el movimiento de celdas viene de la mano del esquema
2311 de :ref:`pointer bump allocation <gc_free_list>`, ya que *compacta* todas las
2312 celdas *vivas* al comienzo del *heap* luego de una recolección, permitiendo
2313 este esquema para asignar nuevas celdas, pero puede utilizarse en esquemas
2314 híbridos como recolectores basados en *regiones* (por ejemplo [BLAC08]_).
2315
2316 Además los recolectores con movimiento de celdas deben ser :ref:`precisos
2317 <gc_conserv>`, porque es necesario tener la información completa de los tipos
2318 para saber cuando actualizar los punteros (de otra manera se podría escribir
2319 un dato de una celda que no era un puntero). Para que un recolector pueda
2320 mover celdas, aunque sea parcialmente, en recolectores *semi-precisos* se
2321 utiliza un método conocido como *pinning* (que significa algo como *pinchar
2322 con un alfiler*); una celda es *pinned* (*pinchada*) cuando hay alguna
2323 referencia no-precisa a ella, y por lo tanto no puede ser movida (porque no se
2324 puede estar seguro si es posible actualizar dicha referencia).
2325
2326 La ventaja principal de los colectores con movimiento es la posibilidad de
2327 utilizar :ref:`pointer bump allocation <gc_free_list>` y que es sencillo
2328 implementar recolectores :ref:`generacionales <gc_part>` sobre estos.
2329
2330 De los algoritmos clásicos sólo la :ref:`copia de semi-espacios <gc_copy>`
2331 mueve celdas, el :ref:`conteo de referencias <gc_rc>` y :ref:`marcado
2332 y barrido <gc_mark_sweep>` no lo hacen. Además hay otro algoritmo bastante
2333 básico que mueve celdas, el **marcado y compactado**. Éste no tiene
2334 2 semi-espacios, directamente mueve las celdas compactándolas al comienzo del
2335 *heap*. El algoritmo es un poco más complejo que la :ref:`copia de
2336 semi-espacios <gc_copy>` pero suele poder proveer una mayor localidad de
2337 referencia y *desperdicia* un semi-espacio que está inutilizado salgo en el
2338 momento de la recolección. Por ejemplo para Mono_, que antes usaba un
2339 recolector conservativo sin movimiento ([BOEHWD]_) se está implementando un
2340 recolector de este tipo [MOLAWE]_ [MOLA06]_.
2341
2342
2343
2344 .. _gc_conserv:
2345
2346 Recolectores conservativos vs precisos
2347 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2348
2349 Los recolectores *conservativos* son aquellos que tienen la capacidad de poder
2350 lidiar con un *root set* o celdas que no tengan información de tipos asociada.
2351 Esto significa que el recolector no sabe donde hay punteros (o referencias) en
2352 una celda o raiz dada. Es decir, una ubicación particular puede ser un puntero
2353 o no. Esto trae una variada cantidad de problemas, como retención de celdas
2354 que en realidad son *basura* simplemente porque hay algún dato que coincide
2355 con la dirección de memoria en la que está almacenada esa celda *basura*
2356 [#gcflasepos]_. Además los recolectores puramente conservativos no puede mover
2357 celdas (ver :ref:`gc_moving`), porque no pueden arriesgarse a actualizar los
2358 punteros por el riesgo que existe de que sean falsos positivos.
2359
2360 .. [#gcflasepos] Esto es lo que se conoce como un *falso positivo*, algo que
2361    aparenta ser un puntero pero en realidad no lo es.
2362
2363 Sin embargo hay ciertas circunstancias que hacen que no quede más remedio que
2364 el recolector sea conservativo, por ejemplo cuando se utiliza un recolector de
2365 basura para un lenguaje que no ha sido pensado para tener uno (como C o C++).
2366
2367 Por el contrario, los recolectores que poseen a su disposición información
2368 completa sobre el tipo de la celda, y por ende información sobre cuales de sus
2369 campos son realmente punteros, son denominados *precisos*. Estos recolectores
2370 no están sujetos a estas limitaciones y por lo tanto son potencialmente más
2371 eficientes en cuanto a tiempo y espacio. Los lenguajes que fueron diseñados
2372 para tener un recolector de basura (y en especial aquellos que son de relativo
2373 alto nivel) en general disponen de recolectores precisos.
2374
2375 Hay casos donde se posee información de tipos para algunas celdas solamente,
2376 o más comúnmente se posee información de tipos de celdas que se encuentran en
2377 el *heap* pero no para el *stack* y registros (por ejemplo [MOLA06]_). En
2378 estos casos se puede adoptar un esquema híbrido y tratar algunas referencias
2379 de forma conservativa y otras de forma precisa, de manera de mitigar, aunque
2380 sea de forma parcial, los efectos adversos de los recolectores conservativos.
2381 Estos recolectores son conocidos como *semi-precisos*. Los recolectores
2382 semi-precisos pueden mover celdas si utilizan un mecanismo de *pinning* (ver
2383 :ref:`gc_moving`).
2384
2385 El ejemplo de recolector conservativo por excelencia es el recolector
2386 `Boehm-Demers-Wiser`_ ([BOEH88]_, [BOEH91]_, [BOEH93]_, [BOEHWD]_) aunque
2387 puede comportarse de forma semi-precisa si el usuario se encarga de darle la
2388 información de tipos (en cuyo caso el recolector deja de ser transparente para
2389 el usuario). Otros ejemplos de recolectores con cierto grado de precisión son
2390 el :ref:`recolector actual de D <dgc_actual>` y [BLAC08]_.
2391
2392
2393
2394 .. _gc_part:
2395
2396 Recolección por particiones / generacional
2397 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2398
2399 Otra forma de reducir la cantidad de pausas y la cantidad de trabajo realizado
2400 por el recolector en general es dividiendo el *heap* en particiones de manera
2401 tal de recolectar solo las partes donde más probabilidad de encontrar *basura*
2402 haya.
2403
2404 Entonces, si el recolector tiene algún mecanismo para identificar zonas de
2405 alta concentración de *basura* puede hacer la recolección solo en ese área
2406 donde el trabajo va a ser mejor recompensado (ver figura :vref:`fig:gc-part`).
2407
2408 .. flt:: fig:gc-part
2409
2410    Concentración de basura en distintas particiones del *heap*
2411
2412    .. aafig::
2413       :scale: 110
2414       :aspect: 70
2415
2416        _______________________________________________________________________
2417       |                                                                       |
2418       |   +-----------------------------+   +-----------------------------+   |
2419       |  /             Baja              \ /             Alta              \  |
2420       | +                                 +                                 + |
2421       | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
2422       | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
2423       |                                                                       |
2424       |        GG Celdas vivas                                ZZ Basura       |
2425       |_______________________________________________________________________|
2426
2427
2428 Sin embargo encontrar zonas de alta concentración no es trivial. La forma más
2429 divulgada de encontrar estas zonas es dividiendo el *heap* en una partición
2430 utilizada para almacenar celdas *jóvenes* y otra para celdas *viejas*. Una
2431 celda *vieja* es aquella que ha *sobrevivido* una cantidad *N* de
2432 recolecciones, mientras que el resto se consideran *jóvenes* (las celdas
2433 *nacen* jóvenes).  Los recolectores que utilizan este tipo de partición son
2434 ampliamente conocido como recolectores **generacionales**. La *hipótesis
2435 generacional* dice que el área de celdas jóvenes tiene una mayor probabilidad
2436 de ser un área de alta concentración de basura [JOLI96]_. Basándose en esto,
2437 los recolectores generacionales primero intentan recuperar espacio del área de
2438 celdas jóvenes y luego, de ser necesario, del área de celdas viejas. Es
2439 posible tener varias generaciones e ir subiendo de generación a generación
2440 a medida que es necesario. Sin embargo en general no se obtienen buenos
2441 resultados una vez que se superan las 3 particiones. La complejidad que trae
2442 este método es que para recolectar la generación joven es necesario tomar las
2443 referencias de la generación vieja a la joven como parte del *root set* (de
2444 otra forma podrían tomarse celdas como *basura* que todavía son utilizadas por
2445 las celdas viejas). Revisar toda la generación vieja no es una opción porque
2446 sería prácticamente lo mismo que realizar una recolección del *heap* completo.
2447 La solución está entonces, una vez más, en instrumentar el *mutator* para que
2448 avise al recolector cuando cambia una referencia de la generación vieja a la
2449 joven (no es necesario vigilar las referencias en sentido inverso ya que
2450 cuando se recolecta la generación vieja se hace una recolección del *heap*
2451 completo).
2452
2453 Sin embargo, a pesar de ser este el esquema más difundido para dividir el
2454 *heap* y realizar una recolección parcial sobre un área de alta concentración
2455 de basura no es la única. Otros recolectores proponen hacer un análisis
2456 estático del código revisando la conectividad entre los objetos según sus
2457 tipos (esto es posible solo en lenguajes con *tipado* estático), de manera tal
2458 de separar en distintas áreas grupos de tipos que no pueden tener referencias
2459 entre sí [HIRZ03]_. Este análisis hace que sea innecesario instrumentar el
2460 *mutator* para reportar al recolector cambios de referencias
2461 inter-particiones, sencillamente porque queda demostrado que no existe dicho
2462 tipo de referencias. Esto quita una de las principales ineficiencias
2463 y complejidades del esquema generacional.
2464
2465
2466
2467 .. include:: links.rst
2468
2469 .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :