source/gc.rst

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