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**. Las celdas blancas siempre son apuntadas por celdas
 591 blancas o grises. Entonces, siempre que el conjunto de celdas grises sea
 592 vacío, no habrán celdas negras conectadas a blancas, siendo las celdas blancas
 593 *basura*.
 594
 595 El algoritmo básico para marcar con tres colores es el siguiente (asumiendo
 596 que todas las celdas parten pintadas de blanco, es decir, el conjunto blanco
 597 contiene todas las celdas de memoria y los conjuntos negro y gris están
 598 vacíos)::
 599
 600    function mark_phase() is
 601       foreach r in root_set
 602          gray_set.add(r)
 603       while not gray_set.empty()
 604          v = gray_set.pop()
 605          black_set.add(v)
 606          foreach (src, dst) in v.edges
 607             if dst in white_set
 608                white_set.remove(dst)
 609                gray_set.add(dst)
 610
 611 Si bien este algoritmo no es recursivo, tiene un requerimiento de espacio
 612 :math:`O(\lvert Live \thickspace set \rvert)`. Un ejemplo donde se aprecia
 613 esto a simple vista es cuando el *Live set* resulta una lista simplemente
 614 enlazada, en cuyo caso el *gray_set* deberá almacenar todos los nodos del
 615 *Live set*.
 616
 617
 618
 619 .. _gc_intro_services:
 620
 621 Servicios
 622 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 623
 624 En general todos los algoritmos de recolección de basura utilizan servicios de
 625 una capa inferior [#gclowlayer]_ y proveen servicios a una capa superior
 626 [#gchilayer]_.
 627
 628 .. [#gclowlayer] En general estos servicios están provistos directamente
 629    por el sistema operativo pero también pueden estar dados por un
 630    administrador de memoria de bajo nivel (o *low level allocator* en inglés).
 631
 632 .. [#gchilayer] En general estos servicios son utilizados directamente por
 633    el lenguaje de programación, pero pueden ser utilizados directamente por el
 634    usuario del lenguaje si éste interatúa con el recolector, ya sea por algún
 635    requerimiento particular o porque el lenguaje no tiene soporte diercto de
 636    recolección de basura y el recolector está implementado como una biblioteca
 637    de usuario.
 638
 639 A continuación se presentan las primitivas en común que utilizan todos los
 640 recolectores a lo largo de este documento.
 641
 642 Servicios utilizados por el recolector son los siguientes:
 643
 644 :math:`alloc() \to cell`
 645    Obtiene una nueva celda de memoria. El mecanismo por el cual se obtiene la
 646    celda es indistinto para esta sección, puede ser de una lista libre, puede
 647    ser de un administrador de memoria de más bajo nivel provisto por el
 648    sistema operativo o la biblioteca estándar de C (``malloc()``), etc.  Cómo
 649    organizar la memoria es un área de investigación completa y si bien está
 650    estrechamente relacionada con la recolección de basura, en este trabajo no
 651    se prestará particular atención a este aspecto (salvo casos donde el
 652    recolector impone una cierta organización de memoria en el *low level
 653    allocator*). Por simplicidad también asumiremos (a menos que se indique lo
 654    contrario) que las celdas son de tamaño fijo. Esta restricción normalmente
 655    puede ser fácilmente relajada (en los recolectores que la tienen).
 656
 657 :math:`free(cell)`
 658    Libera una celda que ya no va a ser utilizada. La celda liberada debe haber
 659    sido obtenida mediante ``alloc()``.
 660
 661 Y los servicios básicos proporcionados por el recolector son los siguientes:
 662
 663 :math:`new() \to cell`
 664    Obtiene una celda de memoria para ser utilizada por el programa.
 665
 666 :math:`update(ref, cell)`
 667    Notifica al recolector que la referencia :math:`ref` ahora apunta
 668    a :math:`cell`. Visto más formalmente, sería análogo a decir que hubo un
 669    cambio en la conectividad del grafo: la arista :math:`src \to old` cambia
 670    por :math:`src \to new` (donde :math:`src` es la celda que contiene la
 671    referencia :math:`ref`, :math:`old` es la celda a la que apunta la
 672    referencia :math:`ref` y :math:`new` es el argumento :math:`cell`). Si
 673    :math:`cell` es ``null``, sería análogo a informar que se elimina la arista
 674    :math:`src \to old`.
 675
 676 :math:`del(cell)`
 677    Este servicio, según el algoritmo, puede ser utilizado para informar un
 678    cambio en la conectividad del grafo, la eliminación de una arista (análogo
 679    a :math:`update(ref, null)` pero sin proporcionar información sobre la
 680    arista a eliminar). Esto es generalmente útil solo en :ref:`conteo de
 681    referencias <gc_rc>`. Para otros recolectores puede significar que el
 682    usuario asegura que no hay más referencias a esta celda, es decir, análogo
 683    a eliminar el conjunto de aristas :math:`\big\lbrace (v, w) \in A , v \in
 684    Live \thickspace set , w \in Live \thickspace set \big/ w = cell
 685    \big\rbrace`.
 686
 687 :math:`collect()`
 688    Este servicio indica al recolector que debe hacer un análisis del grafo de
 689    conectividad en busca de *basura*. Generalmente este servicio es invocado
 690    por el propio recolector cuando no hay más celdas reciclables.
 691
 692 No todos los servicios son implementados por todos los recolectores, pero son
 693 lo suficientemente comunes como para describirlos de forma general en esta
 694 sección. Algunos son principalmente ideados para uso interno del recolector,
 695 aunque en ciertas circunstancias pueden ser utilizados por el usuario también.
 696
 697
 698
 699 .. _gc_classic:
 700
 701 Algoritmos clásicos
 702 ----------------------------------------------------------------------------
 703
 704 En la literatura se encuentran normalmente referencias a tres algoritmos
 705 clásicos, que son utilizados generalmente como bloques básicos para construir
 706 recolectores más complejos. Se presentan las versiones históricas más simples
 707 a fin de facilitar la comprensión conceptual.
 708
 709
 710
 711 .. _gc_rc:
 712
 713 Conteo de referencias
 714 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 715
 716 Se trata del algoritmo más antiguo de todos, implementado por primera vez por
 717 `John McCarthy`_ para Lisp_ a finales de 1950. Se trata de un método
 718 :ref:`directo <gc_direct>` e :ref:`incremental <gc_inc>` por naturaleza, ya
 719 que distribuye la carga de la recolección de basura durante toda la ejecución
 720 del programa, cada vez que el *mutator* cambia la conectividad de algún nodo
 721 del grafo de conectividad.
 722
 723 El método consiste en tener un contador asociado a cada celda que contenga la
 724 cantidad de celdas **vivas** que apuntan a ésta. Es decir, es la cardinalidad
 725 del conjunto de aristas que tienen por destino a la celda.  Formalmente
 726 podemos definir el contador :math:`rc(v)` (de *reference counter* en inglés)
 727 de la siguiente manera:
 728
 729 .. math::
 730
 731    rc(v) = \big\lvert
 732       \left\lbrace
 733          (v_1, v_2) \in A \big/
 734             v_1 \in Live \thickspace set \cup Root \thickspace set
 735                \wedge v_2 = v
 736       \right\rbrace
 737    \big\rvert
 738
 739 El *mutator* entonces debe actualizar este contador cada vez que el grafo de
 740 conectividad cambia, es decir, cada vez que se agrega, modifica o elimina una
 741 arista del grafo (o visto de una forma más cercana al código, cada vez que se
 742 agrega, modifica o elimina un puntero).
 743
 744 Esta invariante es fundamental para el conteo de referencias, porque se asume
 745 que si el contador es 0 entonces el *mutator* no tiene ninguna referencia a la
 746 celda y por lo tanto es *basura*:
 747
 748 .. math::
 749
 750    rc(v) = 0 \Rightarrow v \in Basura
 751
 752 Para mantener esta invariante el *mutator*, cada vez que cambia un puntero
 753 debe decrementar en 1 el contador de la celda a la que apuntaba antiguamente
 754 e incrementar en 1 el contador de la celda a la que apunta luego de la
 755 modificación. Esto asegura que la invariante se mantenga durante toda la
 756 ejecución del programa. Si al momento de decrementar un contador éste queda en
 757 0, la celda asociada debe liberarse de forma de poder ser reciclada. Esto
 758 implica que si esta celda almacena punteros, los contadores de las celdas
 759 apuntadas deben ser decrementados también, porque solo deben almacenarse en el
 760 contador las aristas del *live set* para mantener la invariante. De esto puede
 761 resultar que otros contadores de referencia queden en 0 y más celdas sean
 762 liberadas. Por lo tanto, teóricamente la complejidad de eliminar una
 763 referencia puede ser :math:`O(\lvert Live \thickspace set \rvert)` en el peor
 764 caso.
 765
 766 Las primitivas implementadas para este tipo de recolector son las siguientes
 767 (acompañadas de una implementación básica)::
 768
 769    function new() is
 770       cell = alloc()
 771       if cell is null
 772          throw out_of_memory
 773       cell.rc = 1
 774       return cell
 775
 776    function del(cell) is
 777       cell.rc = cell.rc - 1
 778       if cell.rc is 0
 779          foreach child* in cell.children
 780             del(*child)
 781          free(cell)
 782
 783    function update(ref*, cell) is
 784       cell.rc = cell.rc + 1
 785       del(*ref)
 786       *ref = cell
 787
 788
 789
 790 .. _gc_rc_cycles:
 791
 792 Ciclos
 793 ^^^^^^
 794
 795 El conteo de referencias tiene, sin embargo, un problema fundamental: **falla
 796 con estructuras cíclicas**. Esto significa que siempre que haya un ciclo en el
 797 grafo de conectividad, hay una pérdida de memoria potencial en el programa.
 798
 799 Cuando esto sucede, las celdas que participan del ciclo tienen siempre su
 800 contador mayor que 0, sin embargo puede suceder que ningún elemento del *root
 801 set* apunte a una celda dentro del ciclo, por lo tanto el ciclo es *basura*
 802 (al igual que cualquier otra celda para la cual hayan referencias desde el
 803 ciclo pero que no tenga otras referencias externas) y sin embargo los
 804 contadores no son 0. Los ciclos, por lo tanto, violan la invariante del conteo
 805 de referencia.
 806
 807 Hay formas de solucionar esto, pero siempre recaen en un esquema que va por
 808 fuera del conteo de referencias puro. En general los métodos para solucionar
 809 esto son variados y van desde realizar un marcado del sub-grafo para detectar
 810 ciclos y liberarlos hasta tener otro recolector completo de *emergencia*;
 811 pasando por tratar los ciclos como un todo para contar las referencias al
 812 ciclo completo en vez de a cada celda en particular.
 813
 814 Incluso con este problema, el conteo de referencia sin ningún tipo de solución
 815 en cuanto a la detección y recolección de ciclos fue utilizado en muchos
 816 lenguajes de programación sin que su necesidad sea tan evidente. Por ejemplo
 817 Python_ agregó recolección de ciclos en la versión 2.0 [NAS00]_ (liberada en
 818 octubre de 2000) y PHP_ recién agrega detección de ciclos en la versión 5.3
 819 [PHP530]_.
 820
 821
 822 .. _gc_rc_example:
 823
 824 Ejemplo
 825 ^^^^^^^
 826
 827 A continuación se presenta un ejemplo gráfico para facilitar la comprensión
 828 del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos
 829 punteros, ``left`` (``l``) y ``right`` (``r``) y se muestra el contador de
 830 referencias abajo del nombre de cada celda. Se parte con una pequeña
 831 estructura ya construida y se muestra como opera el algoritmo al eliminar
 832 o cambiar una referencia (cambios en la conectividad del grafo). En un
 833 comienzo todas las celdas son accesibles desde el *root set* por lo tanto son
 834 todas parte del *live set*.
 835
 836 Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina que
 837 ``h1`` se convirtió en *basura* (ver figura :vref:`fig:gc-rc-rm-1`). Esto
 838 conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 839 *live set* ya que sus contadores siguen siendo mayores a 0 (ver figura
 840 :vref:`fig:gc-rc-rm-2`).
 841
 842 .. flt:: fig:gc-rc-rm-1
 843
 844    Ejemplo de conteo de referencias: eliminación de una referencia (parte 1)
 845
 846    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
 847
 848    .. subflt::
 849
 850       Estado inicial del grafo de conectividad.
 851
 852       .. digraph:: g3_1
 853
 854          margin = 0;
 855          ratio  = fill;
 856          size   = "1.9,2.6";
 857          edge [ color = gray40 ];
 858          node [
 859             shape     = record,
 860             width     = 0,
 861             height    = 0,
 862             style     = filled,
 863             fillcolor = gray25,
 864             fontcolor = white
 865          ];
 866
 867          subgraph cluster_all {
 868
 869             root [
 870                label     = "root\nset|<r0> r0|<r1> r1",
 871                style     = filled,
 872                fillcolor = gray96,
 873                fontcolor = black,
 874             ];
 875
 876             h1 [ label = "h1\n1|<l> l|<r> r" ];
 877             h2 [ label = "h2\n2|<l> l|<r> r" ];
 878             h3 [ label = "h3\n3|<l> l|<r> r" ];
 879             h4 [ label = "h4\n1|<l> l|<r> r" ];
 880             h5 [ label = "h5\n1|<l> l|<r> r" ];
 881             h6 [ label = "h6\n1|<l> l|<r> r" ];
 882
 883             root:r0 -> h1;
 884             root:r1 -> h3;
 885             h1:l -> h2;
 886             h1:r -> h3;
 887             h2:l -> h4;
 888             h2:r -> h5;
 889             h3:l -> h2;
 890             h3:r -> h6;
 891             h6:r -> h3:r;
 892
 893          }
 894
 895    .. subflt::
 896
 897       Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
 898       ``h1``.
 899
 900       .. digraph:: g3_2
 901
 902          margin = 0;
 903          ratio  = fill;
 904          size   = "1.9,2.6";
 905          edge [ color = gray40 ];
 906          node [
 907             shape     = record,
 908             width     = 0,
 909             height    = 0,
 910             style     = filled,
 911             fillcolor = gray25,
 912             fontcolor = white
 913          ];
 914
 915          subgraph cluster_all {
 916
 917             root [
 918                label     = "root\nset|<r0> r0\n*|<r1> r1",
 919                style     = filled,
 920                fillcolor = gray96,
 921                fontcolor = black,
 922             ];
 923
 924             h1 [ label = "h1\n1|<l> l|<r> r" ];
 925             h2 [ label = "h2\n2|<l> l|<r> r" ];
 926             h3 [ label = "h3\n3|<l> l|<r> r" ];
 927             h4 [ label = "h4\n1|<l> l|<r> r" ];
 928             h5 [ label = "h5\n1|<l> l|<r> r" ];
 929             h6 [ label = "h6\n1|<l> l|<r> r" ];
 930
 931             root:r0 -> h1 [ style = bold, color = black ];
 932             root:r1 -> h3;
 933             h1:l -> h2;
 934             h1:r -> h3;
 935             h2:l -> h4;
 936             h2:r -> h5;
 937             h3:l -> h2;
 938             h3:r -> h6;
 939             h6:r -> h3:r;
 940
 941          }
 942
 943    .. subflt::
 944
 945       Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser *basura*).
 946       Se elimina primero ``h1.l`` y luego ``h1.r``.
 947
 948       .. digraph:: g3_3
 949
 950          margin = 0;
 951          ratio  = fill;
 952          size   = "1.9,2.6";
 953          edge [ color = gray40 ];
 954          node [
 955             shape     = record,
 956             width     = 0,
 957             height    = 0,
 958             style     = filled,
 959             fillcolor = gray25,
 960             fontcolor = white
 961          ];
 962
 963          subgraph cluster_all {
 964
 965             root [
 966                label     = "root\nset|<r0> r0\n*|<r1> r1",
 967                style     = filled,
 968                fillcolor = gray96,
 969                fontcolor = black,
 970             ];
 971
 972             subgraph marked {
 973                node [ fillcolor = white, fontcolor = black ];
 974                h1;
 975             };
 976
 977             h1 [ label = "h1\n0|<l> l|<r> r" ];
 978             h2 [ label = "h2\n2|<l> l|<r> r" ];
 979             h3 [ label = "h3\n3|<l> l|<r> r" ];
 980             h4 [ label = "h4\n1|<l> l|<r> r" ];
 981             h5 [ label = "h5\n1|<l> l|<r> r" ];
 982             h6 [ label = "h6\n1|<l> l|<r> r" ];
 983
 984             root:r0 -> h1 [ style = invis ];
 985             root:r1 -> h3;
 986             h1:l -> h2 [ style = bold, color = black ];
 987             h1:r -> h3;
 988             h2:l -> h4;
 989             h2:r -> h5;
 990             h3:l -> h2;
 991             h3:r -> h6;
 992             h6:r -> h3:r;
 993
 994          }
 995
 996
 997 .. flt:: fig:gc-rc-rm-2
 998    :padding: 0.5
 999
1000    Ejemplo de conteo de referencias: eliminación de una referencia (parte 2)
1001
1002    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
1003
1004    .. subflt::
1005
1006       Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en el
1007       *live set*).
1008
1009       .. digraph:: g3_4
1010
1011          margin = 0;
1012          ratio  = fill;
1013          size   = "1.9,2.6";
1014          edge [ color = gray40 ];
1015          node [
1016             shape     = record,
1017             width     = 0,
1018             height    = 0,
1019             style     = filled,
1020             fillcolor = gray25,
1021             fontcolor = white
1022          ];
1023
1024          subgraph cluster_all {
1025
1026             root [
1027                label     = "root\nset|<r0> r0\n*|<r1> r1",
1028                style     = filled,
1029                fillcolor = gray96,
1030                fontcolor = black,
1031             ];
1032
1033             subgraph marked {
1034                node [ fillcolor = white, fontcolor = black ];
1035                h1;
1036             };
1037
1038             h1 [ label = "h1\n0|<l> l|<r> r" ];
1039             h2 [ label = "h2\n1|<l> l|<r> r" ];
1040             h3 [ label = "h3\n3|<l> l|<r> r" ];
1041             h4 [ label = "h4\n1|<l> l|<r> r" ];
1042             h5 [ label = "h5\n1|<l> l|<r> r" ];
1043             h6 [ label = "h6\n1|<l> l|<r> r" ];
1044
1045             root:r0 -> h1 [ style = invis ];
1046             root:r1 -> h3;
1047             h1:l -> h2 [ style = invis ];
1048             h1:r -> h3 [ style = bold, color = black ];
1049             h2:l -> h4;
1050             h2:r -> h5;
1051             h3:l -> h2;
1052             h3:r -> h6;
1053             h6:r -> h3:r;
1054
1055          }
1056
1057    .. subflt::
1058
1059       El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.
1060
1061       .. digraph:: g3_5
1062
1063          margin = 0;
1064          ratio  = fill;
1065          size   = "1.9,2.6";
1066          edge [ color = gray40 ];
1067          node [
1068             shape     = record,
1069             width     = 0,
1070             height    = 0,
1071             style     = filled,
1072             fillcolor = gray25,
1073             fontcolor = white
1074          ];
1075
1076          subgraph cluster_all {
1077
1078             root [
1079                label     = "root\nset|<r0> r0|<r1> r1",
1080                style     = filled,
1081                fillcolor = gray96,
1082                fontcolor = black,
1083             ];
1084
1085             subgraph marked {
1086                node [ fillcolor = white, fontcolor = black ];
1087                h1;
1088             };
1089
1090             h1 [ label = "h1\n0|<l> l|<r> r" ];
1091             h2 [ label = "h2\n1|<l> l|<r> r" ];
1092             h3 [ label = "h3\n2|<l> l|<r> r" ];
1093             h4 [ label = "h4\n1|<l> l|<r> r" ];
1094             h5 [ label = "h5\n1|<l> l|<r> r" ];
1095             h6 [ label = "h6\n1|<l> l|<r> r" ];
1096
1097             root:r0 -> h1 [ style = invis ];
1098             root:r1 -> h3;
1099             h1:l -> h2 [ style = invis ];
1100             h1:r -> h3 [ style = invis ];
1101             h2:l -> h4;
1102             h2:r -> h5;
1103             h3:l -> h2;
1104             h3:r -> h6;
1105             h6:r -> h3:r;
1106
1107          }
1108
1109
1110 Luego se cambia una referencia (en vez de eliminarse) realizándose la
1111 operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador de
1112 referencias de ``h5`` para evitar confundirlo accidentalmente con *basura* si
1113 se elimina alguna celda que apuntaba a ésta. Luego se procede a decrementar el
1114 contador de ``h2`` que queda en 0, transformándose en *basura* (ver figura
1115 :vref:`fig:gc-rc-up-1`).
1116
1117 .. flt:: fig:gc-rc-up-1
1118
1119    Ejemplo de conteo de referencias: actualización de una referencia (parte 1)
1120
1121    Cambio en la referencia ``h3.l`` :math:`\to` ``h2`` a ``h3.l`` :math:`\to`
1122    ``h5`` (parte 1).
1123
1124    .. subflt::
1125
1126       Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.
1127
1128       .. digraph:: g4_1
1129
1130          margin = 0;
1131          ratio  = fill;
1132          size   = "1.9,2.6";
1133          edge [ color = gray40 ];
1134          node [
1135             shape     = record,
1136             width     = 0,
1137             height    = 0,
1138             style     = filled,
1139             fillcolor = gray25,
1140             fontcolor = white
1141          ];
1142
1143          subgraph cluster_all {
1144
1145             root [
1146                label     = "root\nset|<r0> r0|<r1> r1",
1147                style     = filled,
1148                fillcolor = gray96,
1149                fontcolor = black,
1150             ];
1151
1152             subgraph marked {
1153                node [ fillcolor = white, fontcolor = black ];
1154                h1;
1155             };
1156
1157             h1 [ label = "h1\n0|<l> l|<r> r" ];
1158             h2 [ label = "h2\n1|<l> l|<r> r" ];
1159             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1160             h4 [ label = "h4\n1|<l> l|<r> r" ];
1161             h5 [ label = "h5\n2|<l> l|<r> r" ];
1162             h6 [ label = "h6\n1|<l> l|<r> r" ];
1163
1164             root:r0 -> h1 [ style = invis ];
1165             h1:l -> h2 [ style = invis ];
1166             h1:r -> h3 [ style = invis ];
1167             root:r1 -> h3;
1168             h2:l -> h4;
1169             h2:r -> h5;
1170             h3:l -> h2;
1171             h3:l -> h5 [ style = dotted, color = black ];
1172             h3:r -> h6;
1173             h6:r -> h3:r;
1174
1175          }
1176
1177    .. subflt::
1178
1179       Luego se procede a visitar la antigua referencia de ``h3.l`` (``h2``).
1180
1181       .. digraph:: g4_2
1182
1183          margin = 0;
1184          ratio  = fill;
1185          size   = "1.9,2.6";
1186          edge [ color = gray40 ];
1187          node [
1188             shape     = record,
1189             width     = 0,
1190             height    = 0,
1191             style     = filled,
1192             fillcolor = gray25,
1193             fontcolor = white
1194          ];
1195
1196          subgraph cluster_all {
1197
1198             root [
1199                label     = "root\nset|<r0> r0|<r1> r1",
1200                style     = filled,
1201                fillcolor = gray96,
1202                fontcolor = black,
1203             ];
1204
1205             subgraph marked {
1206                node [ fillcolor = white, fontcolor = black ];
1207                h1;
1208             };
1209
1210             h1 [ label = "h1\n0|<l> l|<r> r" ];
1211             h2 [ label = "h2\n1|<l> l|<r> r" ];
1212             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1213             h4 [ label = "h4\n1|<l> l|<r> r" ];
1214             h5 [ label = "h5\n2|<l> l|<r> r" ];
1215             h6 [ label = "h6\n1|<l> l|<r> r" ];
1216
1217             root:r0 -> h1 [ style = invis ];
1218             h1:l -> h2 [ style = invis ];
1219             h1:r -> h3 [ style = invis ];
1220             root:r1 -> h3;
1221             h2:l -> h4;
1222             h2:r -> h5;
1223             h3:l -> h2 [ style = bold, color = black ];
1224             h3:l -> h5 [ style = dotted, color = black ];
1225             h3:r -> h6;
1226             h6:r -> h3:r;
1227
1228          }
1229
1230    .. subflt::
1231
1232       Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser *basura*).
1233       Se eliminan las referencias a las hijas.
1234
1235       .. digraph:: g4_3
1236
1237          margin = 0;
1238          ratio  = fill;
1239          size   = "1.9,2.6";
1240          edge [ color = gray40 ];
1241          node [
1242             shape     = record,
1243             width     = 0,
1244             height    = 0,
1245             style     = filled,
1246             fillcolor = gray25,
1247             fontcolor = white
1248          ];
1249
1250          subgraph cluster_all {
1251
1252             root [
1253                label     = "root\nset|<r0> r0|<r1> r1",
1254                style     = filled,
1255                fillcolor = gray96,
1256                fontcolor = black,
1257             ];
1258
1259             subgraph marked {
1260                node [ fillcolor = white, fontcolor = black ];
1261                h1; h2;
1262             };
1263
1264             h1 [ label = "h1\n0|<l> l|<r> r" ];
1265             h2 [ label = "h2\n1|<l> l|<r> r" ];
1266             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1267             h4 [ label = "h4\n1|<l> l|<r> r" ];
1268             h5 [ label = "h5\n2|<l> l|<r> r" ];
1269             h6 [ label = "h6\n1|<l> l|<r> r" ];
1270
1271             root:r0 -> h1 [ style = invis ];
1272             h1:l -> h2 [ style = invis ];
1273             h1:r -> h3 [ style = invis ];
1274             root:r1 -> h3;
1275             h2:l -> h4 [ style = bold, color = black ];
1276             h2:r -> h5;
1277             h3:l -> h2 [ style = invis ];
1278             h3:l -> h5 [ style = dotted, color = black ];
1279             h3:r -> h6;
1280             h6:r -> h3:r;
1281
1282          }
1283
1284
1285 Lo mismo pasa cuando se desciende a ``h4``, pero al descender a ``h5``
1286 y decrementar el contador, éste sigue siendo mayor que 0 (pues ``h3`` va
1287 a apuntar a ``h5``) así que permanece en el *live set*. Finalmente se termina
1288 de actualizar la referencia ``h3.l`` para que apunte a ``h5`` (ver figura
1289 :vref:`fig:gc-rc-up-2`).
1290
1291 .. flt:: fig:gc-rc-up-2
1292
1293    Ejemplo de conteo de referencias: actualización de una referencia (parte 2)
1294
1295    Cambio en la referencia ``h3.l`` :math:`\to` ``h2`` a ``h3.l`` :math:`\to`
1296    ``h5`` (parte 2).
1297
1298    .. subflt::
1299
1300       Se decrementa el contador de ``h4`` quedando en 0, pasa a ser *basura*.
1301       Se continúa con ``h5``.
1302
1303       .. digraph:: g4_4
1304
1305          margin = 0;
1306          ratio  = fill;
1307          size   = "1.9,2.6";
1308          edge [ color = gray40 ];
1309          node [
1310             shape     = record,
1311             width     = 0,
1312             height    = 0,
1313             style     = filled,
1314             fillcolor = gray25,
1315             fontcolor = white
1316          ];
1317
1318          subgraph cluster_all {
1319
1320             root [
1321                label     = "root\nset|<r0> r0|<r1> r1",
1322                style     = filled,
1323                fillcolor = gray96,
1324                fontcolor = black,
1325             ];
1326
1327             subgraph marked {
1328                node [ fillcolor = white, fontcolor = black ];
1329                h1; h2; h4;
1330             };
1331
1332             h1 [ label = "h1\n0|<l> l|<r> r" ];
1333             h2 [ label = "h2\n1|<l> l|<r> r" ];
1334             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1335             h4 [ label = "h4\n0|<l> l|<r> r" ];
1336             h5 [ label = "h5\n2|<l> l|<r> r" ];
1337             h6 [ label = "h6\n1|<l> l|<r> r" ];
1338
1339             root:r0 -> h1 [ style = invis ];
1340             h1:l -> h2 [ style = invis ];
1341             h1:r -> h3 [ style = invis ];
1342             root:r1 -> h3;
1343             h2:l -> h4 [ style = invis ];
1344             h2:r -> h5 [ style = bold, color = black ];
1345             h3:l -> h2 [ style = invis ];
1346             h3:l -> h5 [ style = dotted, color = black ];
1347             h3:r -> h6;
1348             h6:r -> h3:r;
1349
1350          }
1351
1352    .. subflt::
1353
1354       Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.
1355
1356       .. digraph:: g4_5
1357
1358          margin = 0;
1359          ratio  = fill;
1360          size   = "1.9,2.6";
1361          edge [ color = gray40 ];
1362          node [
1363             shape     = record,
1364             width     = 0,
1365             height    = 0,
1366             style     = filled,
1367             fillcolor = gray25,
1368             fontcolor = white
1369          ];
1370
1371          subgraph cluster_all {
1372
1373             root [
1374                label     = "root\nset|<r0> r0|<r1> r1",
1375                style     = filled,
1376                fillcolor = gray96,
1377                fontcolor = black,
1378             ];
1379
1380             subgraph marked {
1381                node [ fillcolor = white, fontcolor = black ];
1382                h1; h2; h4;
1383             };
1384
1385             h1 [ label = "h1\n0|<l> l|<r> r" ];
1386             h2 [ label = "h2\n1|<l> l|<r> r" ];
1387             h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
1388             h4 [ label = "h4\n0|<l> l|<r> r" ];
1389             h5 [ label = "h5\n1|<l> l|<r> r" ];
1390             h6 [ label = "h6\n1|<l> l|<r> r" ];
1391
1392             root:r0 -> h1 [ style = invis ];
1393             h1:l -> h2 [ style = invis ];
1394             h1:r -> h3 [ style = invis ];
1395             root:r1 -> h3;
1396             h2:l -> h4 [ style = invis ];
1397             h2:r -> h5 [ style = invis ];
1398             h3:l -> h5 [ style = bold, color = black ];
1399             h3:l -> h2 [ style = invis ];
1400             h3:r -> h6;
1401             h6:r -> h3:r;
1402
1403          }
1404
1405    .. subflt::
1406
1407       Se termina por actualizar la referencia de ``h3.l`` para que apunte
1408       a ``h5``.
1409
1410       .. digraph:: g4_6
1411
1412          margin = 0;
1413          ratio  = fill;
1414          size   = "1.9,2.6";
1415          edge [ color = gray40 ];
1416          node [
1417             shape     = record,
1418             width     = 0,
1419             height    = 0,
1420             style     = filled,
1421             fillcolor = gray25,
1422             fontcolor = white
1423          ];
1424
1425          subgraph cluster_all {
1426
1427             root [
1428                label     = "root\nset|<r0> r0|<r1> r1",
1429                style     = filled,
1430                fillcolor = gray96,
1431                fontcolor = black,
1432             ];
1433
1434             subgraph marked {
1435                node [ fillcolor = white, fontcolor = black ];
1436                h1; h2; h4;
1437             };
1438
1439             h1 [ label = "h1\n0|<l> l|<r> r" ];
1440             h1 [ label = "h1\n0|<l> l|<r> r" ];
1441             h2 [ label = "h2\n0|<l> l|<r> r" ];
1442             h3 [ label = "h3\n2|<l> l|<r> r" ];
1443             h4 [ label = "h4\n0|<l> l|<r> r" ];
1444             h5 [ label = "h5\n1|<l> l|<r> r" ];
1445             h6 [ label = "h6\n1|<l> l|<r> r" ];
1446
1447             root:r0 -> h1 [ style = invis ];
1448             h1:l -> h2 [ style = invis ];
1449             h1:r -> h3 [ style = invis ];
1450             root:r1 -> h3;
1451             h2:l -> h4 [ style = invis ];
1452             h2:r -> h5 [ style = invis ];
1453             h3:l -> h5;
1454             h3:l -> h2 [ style = invis ];
1455             h3:r -> h6;
1456             h6:r -> h3:r;
1457
1458          }
1459
1460
1461 Finalmente se presenta lo que sucede cuando se elimina la última referencia
1462 a un ciclo (en este caso un ciclo simple de 2 celdas: ``h3`` y ``h6``). Se
1463 elimina la única referencia externa al ciclo (``r1``), por lo que se visita la
1464 celda ``h3`` decrementando su contador de referencias, pero éste continúa
1465 siendo mayor que 0 porque la celda ``h6`` (parte del ciclo) la referencia. Por
1466 lo tanto el ciclo, y todas las celdas a las que apunta que no tienen otras
1467 referencias externas y por lo tanto deberían ser *basura* también (``h5``), no
1468 pueden ser recicladas y su memoria es perdida (ver figura
1469 :vref:`fig:gc-rc-cycle`).
1470
1471 .. flt:: fig:gc-rc-cycle
1472    :padding: 0.5
1473
1474    Ejemplo de conteo de referencias: pérdida de memoria debido a un ciclo
1475
1476    Eliminación de la referencia ``r1`` :math:`\to` ``h3`` (pérdida de memoria
1477    debido a un ciclo).
1478
1479    .. subflt::
1480
1481       El ejecutarse ``update(r1, null)`` se visita la celda ``h3``.
1482
1483       .. digraph:: g4_6
1484
1485          margin = 0;
1486          ratio  = fill;
1487          size   = "1.9,2.6";
1488          edge [ color = gray40 ];
1489          node [
1490             shape     = record,
1491             width     = 0,
1492             height    = 0,
1493             style     = filled,
1494             fillcolor = gray25,
1495             fontcolor = white
1496          ];
1497
1498          subgraph cluster_all {
1499
1500             root [
1501                label     = "root\nset|<r0> r0|<r1> r1\n*",
1502                style     = filled,
1503                fillcolor = gray96,
1504                fontcolor = black,
1505             ];
1506
1507             subgraph marked {
1508                node [ fillcolor = white, fontcolor = black ];
1509                h1; h2; h4;
1510             };
1511
1512             h1 [ label = "h1\n0|<l> l|<r> r" ];
1513             h1 [ label = "h1\n0|<l> l|<r> r" ];
1514             h2 [ label = "h2\n0|<l> l|<r> r" ];
1515             h3 [ label = "h3\n2|<l> l|<r> r" ];
1516             h4 [ label = "h4\n0|<l> l|<r> r" ];
1517             h5 [ label = "h5\n1|<l> l|<r> r" ];
1518             h6 [ label = "h6\n1|<l> l|<r> r" ];
1519
1520             root:r0 -> h1 [ style = invis ];
1521             h1:l -> h2 [ style = invis ];
1522             h1:r -> h3 [ style = invis ];
1523             root:r1 -> h3 [ style = bold, color = black ];
1524             h2:l -> h4 [ style = invis ];
1525             h2:r -> h5 [ style = invis ];
1526             h3:l -> h5;
1527             h3:l -> h2 [ style = invis ];
1528             h3:r -> h6;
1529             h6:r -> h3:r;
1530
1531          }
1532
1533    .. subflt::
1534
1535       Se decrementa el contador de ``h3`` pero sigue siendo mayor que 0 por el
1536       ciclo.
1537
1538       .. digraph:: g5_2
1539
1540          margin = 0;
1541          ratio  = fill;
1542          size   = "1.9,2.6";
1543          edge [ color = gray40 ];
1544          node [
1545             shape     = record,
1546             width     = 0,
1547             height    = 0,
1548             style     = filled,
1549             fillcolor = gray25,
1550             fontcolor = white
1551          ];
1552
1553          subgraph cluster_all {
1554
1555             root [
1556                label     = "root\nset|<r0> r0|<r1> r1\n*",
1557                style     = filled,
1558                fillcolor = gray96,
1559                fontcolor = black,
1560             ];
1561
1562             subgraph marked {
1563                node [ fillcolor = white, fontcolor = black ];
1564                h1; h2; h4;
1565             };
1566
1567             h1 [ label = "h1\n0|<l> l|<r> r" ];
1568             h1 [ label = "h1\n0|<l> l|<r> r" ];
1569             h2 [ label = "h2\n0|<l> l|<r> r" ];
1570             h3 [ label = "h3\n1|<l> l|<r> r" ];
1571             h4 [ label = "h4\n0|<l> l|<r> r" ];
1572             h5 [ label = "h5\n1|<l> l|<r> r" ];
1573             h6 [ label = "h6\n1|<l> l|<r> r" ];
1574
1575             root:r0 -> h1 [ style = invis ];
1576             h1:l -> h2 [ style = invis ];
1577             h1:r -> h3 [ style = invis ];
1578             root:r1 -> h3 [ style = invis ];
1579             h2:l -> h4 [ style = invis ];
1580             h2:r -> h5 [ style = invis ];
1581             h3:l -> h5;
1582             h3:l -> h2 [ style = invis ];
1583             h3:r -> h6;
1584             h6:r -> h3:r;
1585
1586          }
1587
1588
1589
1590 .. _gc_mark_sweep:
1591
1592 Marcado y barrido
1593 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1594
1595 Este algoritmo es el más parecido a la teoría sobre recolección de basura.
1596 Consiste en realizar la recolección en 2 fases: marcado y barrido. La primera
1597 fase consiste en el proceso de marcar el grafo de conectividad del *heap* para
1598 descubrir qué celdas son alcanzables desde el *root set*, tal y como se
1599 describió en :ref:`gc_intro_mark`.
1600
1601 Una vez marcadas todas las celdas, se sabe que las celdas *blancas* son
1602 *basura*, por lo tanto el paso que queda es el *barrido* de estas celdas,
1603 liberándolas. Esto se efectúa recorriendo todo el *heap*. Por lo tanto cada
1604 recolección es :math:`O(\lvert Heap \rvert)`, a diferencia del conteo de
1605 referencia que dijimos que en el peor caso es :math:`O(\lvert Live \thickspace
1606 set \rvert)`. Sin embargo el conteo de referencias se ejecuta **cada vez que
1607 se actualiza una referencia** mientras que la recolección en el marcado
1608 y barrido se realiza típicamente solo cuando el *mutator* pide una celda pero
1609 no hay ninguna libre. Esto hace que la constante del conteo de referencias sea
1610 típicamente varios órdenes de magnitud mayores que en el marcado y barrido.
1611
1612 A continuación se presentan los servicios básicos de este algoritmo::
1613
1614    function new() is
1615       cell = alloc()
1616       if cell is null
1617          collect()
1618       cell = alloc()
1619       if cell is null
1620          throw out_of_memory
1621       return cell
1622
1623    function collect() is
1624       mark_phase()
1625       sweep_phase()
1626
1627    function sweep_phase() is
1628       foreach cell in heap
1629          if cell.marked
1630             cell.marked = false
1631          else
1632             free(cell)
1633
1634 El algoritmo ``mark_sweep()`` es exactamente igual al presentado en
1635 :ref:`gc_intro_mark`. Es preciso notar que la fase de barrido
1636 (``sweep_phase()``) debe tener una comunicación extra con el *low level
1637 allocator* para poder obtener todas las celdas de memoria que existen en el
1638 *heap*.
1639
1640 A diferencia del conteo de referencias, este algoritmo es :ref:`indirecto
1641 <gc_direct>` y :ref:`no incremental <gc_inc>`, ya que se realiza un recorrido
1642 de todo el *heap* de forma espaciada a través de la ejecución del programa. En
1643 general el *mutator* sufre pausas considerablemente mayores (en promedio) que
1644 con el conteo de referencias, lo que puede ser problemático para aplicaciones
1645 con requerimientos rígidos de tiempo, como aplicaciones *real-time*. Debido
1646 a la percepción de las pausas grandes, este tipo de colectores se conocen como
1647 :ref:`stop-the-world <gc_concurrent>` (o *detener el mundo*).
1648
1649 Una ventaja fundamental sobre el conteo de referencias es la posibilidad de
1650 reclamar estructuras cíclicas sin consideraciones especiales. Podemos observar
1651 como esto es posible analizando el ejemplo en las figuras :r:`fig:gc-mark-1`
1652 y :vref:`fig:gc-mark-2`. Si se eliminaran las referencias :math:`r0 \to h1`
1653 y :math:`h6 \to h2`, la fase de marcado consistiría solamente en marcar la
1654 celda :math:`h6`, pues es la única alcanzable desde el *root set*. Todas las
1655 demás celdas permanecerían blancas y por lo tanto pueden ser liberadas sin
1656 inconvenientes en la fase de barrido, que recorre el *heap* linealmente.
1657
1658
1659
1660 .. _gc_copy:
1661
1662 Copia de semi-espacio
1663 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1664
1665 Este algoritmo consiste en hacer una partición del *heap* en 2 mitades
1666 o *semi-espacios*, llamados usualmente *Fromspace* y *Tospace*. El primero se
1667 utiliza para asignar nuevas celdas de forma lineal, asumiendo un *heap*
1668 contiguo, incrementando un puntero (ver figura :vref:`fig:gc-copy`).  Esto se
1669 conoce como *pointer bump allocation* y es, probablemente, la forma más
1670 eficiente de asignar memoria (tan eficiente como asignar memoria en el
1671 *stack*). Esto permite además evitar el problema de la *fragmentación* de
1672 memoria [#gcfrag]_ que normalmente afectan a los otros algoritmos clásicos (o
1673 sus *low level allocators*).
1674
1675 .. [#gcfrag] La *fragmentación* de memoria sucede cuando se asignan objetos
1676    de distintos tamaños y luego libera alguno intermedio, produciendo
1677    *huecos*. Estos *huecos* quedan inutilizables hasta que se quiera
1678    asignar un nuevo objeto de tamaño igual al *hueco* (o menor). Si esto no
1679    sucede y se acumulan muchos *huecos* se dice que la memoria está
1680    *fragmentada*.
1681
1682 .. flt:: fig:gc-copy
1683
1684    Estructura del *heap* de un recolector con copia de semi-espacios
1685
1686    .. aafig::
1687       :aspect: 70
1688       :scale: 115
1689
1690       zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
1691
1692        /---+"Fromspace"                /---+"Tospace"
1693        |                               |
1694        V_______________________________V_______________________________
1695        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1696        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1697        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1698        |~~~~~~~~~~~~~~~A~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1699                        |
1700        |               |               |    XX "Fromspace usado"
1701                        \---+"libre"
1702        |                               |    ZZ "Fromspace basura"
1703
1704        |/  "longitud del semi-espacio" |/   AA "Fromspace libre"
1705        +- - - - - - - - - - - - - - - -+
1706       /|                              /|    BB "Tospace"
1707
1708
1709 La segunda mitad (*Tospace*) permanece inutilizada hasta que se agota el
1710 espacio en el *Fromspace*; en ese momento comienza el proceso de recolección
1711 de basura que consiste en recorrer el grafo de conectividad, copiando las
1712 celdas *vivas* del *Fromspace* al *Tospace* de manera contigua, como si
1713 estuvieran asignando por primera vez. Como la posición en memoria de las
1714 celdas cambia al ser movidas, es necesario actualizar la dirección de memoria
1715 de todas las celdas *vivas*. Para esto se almacena una dirección de memoria de
1716 re-dirección, *forwarding address*, en las celdas que mueven. La *forwarding
1717 address* sirve a su vez de marca, para no recorrer una celda dos veces (como
1718 se explica en :ref:`gc_intro_mark`). Cuando se encuentra una celda que ya fue
1719 movida, simplemente se actualiza la referencia por la cual se llegó a esa
1720 celda para que apunte a la nueva dirección, almacenada en la *forwarding
1721 address*. Una vez finalizado este proceso, el *Fromspace* y *Tospace*
1722 invierten roles y se prosigue de la misma manera (todo lo que quedó en el
1723 viejo *Fromspace* es *basura* por definición, por lo que se convierte el
1724 *Tospace*).
1725
1726 A continuación se presenta una implementación sencilla de los servicios
1727 provistos por este tipo de recolectores. Cabe destacar que este tipo de
1728 recolectores deben estar íntimamente relacionados con el *low level
1729 allocator*, ya que la organización del *heap* y la forma de asignar memoria es
1730 parte fundamental de este algoritmo. Se asume que ya hay dos áreas de memoria
1731 del mismo tamaño destinadas al *Fromspace* y *Tospace*, y la existencia de
1732 4 variables: ``fromspace`` (que apunta a la base del *Fromspace*), ``tospace``
1733 (que apunta a la base del *Tospace*), ``spacesize`` (que contiene el tamaño de
1734 un semi-espacio) y ``free`` (que apunta al lugar del *Fromspace* donde
1735 comienza la memoria libre). También vale aclarar que este algoritmo soporta
1736 inherentemente celdas de tamaño variable, por lo que los servicios ``alloc()``
1737 y ``new()`` [#gccopynew]_ reciben como parámetro el tamaño de la celda
1738 a asignar::
1739
1740    function alloc(size) is
1741       if free + size > fromspace + spacesize
1742          return null
1743       else
1744          cell = free
1745          free = free + size
1746          return cell
1747
1748    function new(size) is
1749       cell = alloc(size)
1750       if cell is null
1751          collect()
1752       cell = alloc(size)
1753       if cell is null
1754          throw out_of_memory
1755       return cell
1756
1757    function collect() is
1758       free = tospace
1759       foreach r in root_set
1760          r = copy(r)
1761       fromspace, tospace = tospace, fromspace
1762
1763    function copy(cell) is
1764       if cell.forwarding_address is null
1765          cell.forwarding_address = free
1766          free = free + cell.size
1767          foreach child in cell
1768             child = copy(child)
1769          return cell.forwarding_address
1770       else
1771          return cell.forwarding_address
1772
1773 .. [#gccopynew] Notar que ``new()`` es igual que en el marcado y barrido con
1774    la salvedad de que en este caso toma como parámetro el tamaño de la celda.
1775
1776 Esta técnica tiene nombres variados en inglés: *semi-space*, *two-space*
1777 o simplemente *copying collector*. En este documento se denomina "copia de
1778 semi-espacio" porque los otros nombres son demasiado generales y pueden
1779 describir, por ejemplo, algoritmos donde no hay copia de celdas o donde no hay
1780 2 semi-espacios (como se verá en :ref:`gc_art`).
1781
1782 Al igual que el :ref:`gc_mark_sweep` este algoritmo es :ref:`indirecto
1783 <gc_direct>`, :ref:`no incremental <gc_inc>` y :ref:`stop-the-world
1784 <gc_concurrent>`. Las diferencias con los esquemas vistos hasta ahora son
1785 evidentes. La principal ventaja sobre el marcado y barrido (que requiere una
1786 pasada sobre el *live set*, el marcado, y otra sobre el *heap* entero, el
1787 barrido) es que este método requiere una sola pasada y sobre las celdas vivas
1788 del *heap* solamente. La principal desventaja es copia memoria, lo que puede
1789 ser particularmente costoso, además de requerir, como mínimo, el doble de
1790 memoria de lo que el *mutator* realmente necesita. Esto puede traer en
1791 particular problemas con la memoria virtual y el caché, por la pobre localidad
1792 de referencia.
1793
1794 Por lo tanto los recolectores de este tipo pueden ser convenientes por sobre
1795 el marcado y barrido cuando se espera que el *live set* sea muy pequeño luego
1796 de una recolección. En estos casos el trabajo realizado por este tipo de
1797 recolectores puede ser considerablemente menor que el del marcado y barrido.
1798 Y por el contrario, si el *working set* es pequeño, al ser *compactado* en
1799 memoria puede mejorar la localidad de referencia (si el *working set* es
1800 grande se corre el riesgo de que la localidad de referencia empeore al moverse
1801 las celdas).
1802
1803
1804 Ejemplo
1805 ^^^^^^^
1806
1807 A continuación se presenta un sencillo ejemplo del algoritmo. Se parte de una
1808 estructura simple con 4 celdas en el *Fromspace* (que incluye un pequeño ciclo
1809 para mostrar que este algoritmo tampoco tiene inconvenientes para
1810 recolectarlos). Asumimos que ya no queda lugar en el *Fromspace* por lo que
1811 comienza la ejecución de ``collect()``. Se comienza por el *root set* que
1812 apunta a ``h3``, por lo tanto ésta es movida al *Tospace* primero, dejando una
1813 *forwarding address* a la nueva ubicación (ver figura
1814 :vref:`fig:gc-copy-ex-1`).
1815
1816 .. flt:: fig:gc-copy-ex-1
1817
1818    Ejemplo de recolección con copia de semi-espacios (parte 1)
1819
1820    .. subflt::
1821
1822       Estructura inicial del *heap*. El *Fromspace* está complete y se inicial
1823       la recolección.
1824
1825       .. aafig::
1826
1827          +--------------------------------------------------+
1828          | "Fromspace"                                      |
1829          |        /--------------------------------\        |
1830          |        | /--------\  /------\           |        |
1831          |        | |        |  |      |           |        |
1832          |  ______|_V________|__V______|___________V______  |
1833          | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
1834          | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
1835          |  ~~~~~~~~~|~~~~~~~~~~A~~~~~~~A~~~~~~~~~~~~~~~~~  |
1836          |      h1   |      h2  |   h3  |       h4          |
1837          |           \----------/       |                   |
1838          |                              \----+"root set"    |
1839          |                                                  |
1840          |                                                  |
1841          |                                                  |
1842          |  ______________________________________________  |
1843          | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1844          | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1845          | A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1846          | |                                                |
1847          | \----+"free"                                     |
1848          | "Tospace"                                        |
1849          +--------------------------------------------------+
1850
1851    .. subflt::
1852
1853       Se sigue la referencia del *root set*, copiando ``h3`` al *Tospace*
1854       y dejando una *forwarding address*.
1855
1856       .. aafig::
1857
1858          +--------------------------------------------------+
1859          | "Fromspace"                                      |
1860          |        /--------------------------------\        |
1861          |        | /--------\  /------\           |        |
1862          |        | |        |  |      |           |        |
1863          |  ______|_V________|__V______|___________V______  |
1864          | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
1865          | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
1866          |  ~~~~~~~~~|~~~~~~~~~~A~~~~~~~|A~~~~~~~~~~~~~~~~  |
1867          |      h1   |      h2  |   h3  ||      h4          |
1868          |           \----------/       ||                  |
1869          |                              +\----+"root set"   |
1870          |                             /                    |
1871          |  /-------------------------+                     |
1872          |  | h3                                            |
1873          |  V_____________________________________________  |
1874          | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1875          | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1876          |  ~~~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1877          |         |                                        |
1878          |         \----+"free"                             |
1879          | "Tospace"                                        |
1880          +--------------------------------------------------+
1881
1882
1883 A continuación se copian las *hijas* de ``h3``, en este caso sólo ``h2``, que
1884 se ubica en el *Tospace* a continuación de ``h3``, dejando nuevamente su
1885 ``forwarding address`` en la celda original. Al proceder recursivamente, se
1886 procede a copiar ``h1`` al *Tospace*, dejando una vez más la *forwarding
1887 address* en la celda original y procediendo con las hijas. Aquí podemos
1888 observar que al seguirse la referencia :math:`h1 \to h2`, como ``h2`` ya había
1889 sido visitada, solamente se actualiza la referencia apuntando a la nueva
1890 ubicación de ``h2`` pero no se vuelve a copiar la celda (ver figura
1891 :vref:`fig:gc-copy-ex-2`).
1892
1893 .. flt:: fig:gc-copy-ex-2
1894
1895    Ejemplo de recolección con copia de semi-espacios (parte 2)
1896
1897    .. subflt::
1898
1899       Se sigue :math:`h3 \to h2`, copiando ``h2`` al *Tospace* y dejando una
1900       *forwarding address*.
1901
1902       .. aafig::
1903
1904          +--------------------------------------------------+
1905          | "Fromspace"                                      |
1906          |        /--------------------------------\        |
1907          |        | /--------\  /------\           |        |
1908          |        | |        |  |      |           |        |
1909          |  ______|_V________|__V______|___________V______  |
1910          | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1911          | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1912          |  ~~~~~~~~~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~  |
1913          |      h1   |      h2  ||  h3  ||      h4          |
1914          |           \----------/+      ||                  |
1915          |                      /       +\----+"root set"   |
1916          |         +-----------+       /                    |
1917          |  /------+------------------+                     |
1918          |  | h3   | h2                                     |
1919          |  V______V______________________________________  |
1920          | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1921          | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1922          |  ~~|~~~~~~A~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1923          |    |      |     |                                |
1924          |    \------/     \----+"free"                     |
1925          | "Tospace"                                        |
1926          +--------------------------------------------------+
1927
1928    .. subflt::
1929
1930       Se sigue :math:`h2 \to h1`, copiando ``h1``. Luego :math:`h1 \to h2`
1931       pero ``h2`` no se copia, sólo se actualiza la referencia con la
1932       *forwarding address*.
1933
1934       .. aafig::
1935
1936          +--------------------------------------------------+
1937          | "Fromspace"                                      |
1938          |        /--------------------------------\        |
1939          |        | /--------\  /------\           |        |
1940          |        | |        |  |      |           |        |
1941          |  ______|_V________|__V______|___________V______  |
1942          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1943          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1944          |  ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~  |
1945          |      h1 | |      h2  ||  h3  ||      h4          |
1946          |         \-+----------/+      ||                  |
1947          |           +-----+    /       +\-----+"root set"  |
1948          |         +-------+---+       /                    |
1949          |  /------+-------+----------+                     |
1950          |  | h3   | h2    | h1                             |
1951          |  V______V_______V______________________________  |
1952          | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
1953          | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
1954          |  ~~|~~~~~~A~|~A~~|~A~~~~A~~~~~~~~~~~~~~~~~~~~~~  |
1955          |    |      | | |  | |    |                        |
1956          |    \------/ | \--/ |    \----+"free"             |
1957          | "Tospace"   \------/                             |
1958          +--------------------------------------------------+
1959
1960
1961 Se termina de copiar recursivamente las hijas de ``h1`` al copiar ``h4`` que
1962 resulta la última celda (sin hijas). Finalmente se invierten los roles de los
1963 semi-espacios y se actualiza la referencia del *root set* para que apunte a la
1964 nueva ubicación de ``h3``, como se muestra en la figura
1965 :vref:`fig:gc-copy-ex-3`.
1966
1967 .. flt:: fig:gc-copy-ex-3
1968
1969    Ejemplo de recolección con copia de semi-espacios (parte 3)
1970
1971    .. subflt::
1972
1973       Se sigue :math:`h1 \to h4` copiando `h4`` al *Tospace* y dejando una
1974       *forwarding address*.
1975
1976       .. aafig::
1977
1978          +--------------------------------------------------+
1979          | "Fromspace"                                      |
1980          |        /--------------------------------\        |
1981          |        | /--------\  /------\           |        |
1982          |        | |        |  |      |           |        |
1983          |  ______|_V________|__V______|___________V______  |
1984          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
1985          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
1986          |  ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~|~~~~~  |
1987          |      h1 | |      h2  ||  h3  ||      h4  \----\  |
1988          |         \-+----------/+      ||               |  |
1989          |           +-----+    /  +----/\---+"root set" |  |
1990          |         +-------+---+  /                      |  |
1991          |  /------+-------+-----+  /--------------------/  |
1992          |  | h3   | h2    | h1     | h4                    |
1993          |  V______V_______V________V_____________________  |
1994          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
1995          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
1996          |  ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~  |
1997          |    |      | | |  | | |      |   |                |
1998          |    \------/ | \--/ | \------/   \----+"free"     |
1999          | "Tospace"   \------/                             |
2000          +--------------------------------------------------+
2001
2002    .. subflt::
2003
2004       Se finaliza la recolección, se intercambian los roles de los
2005       semi-espacios y se actualiza la referencia del *root set*.
2006
2007       .. aafig::
2008
2009          +--------------------------------------------------+
2010          | "Tospace"                                        |
2011          |                                                  |
2012          |                                                  |
2013          |                                                  |
2014          |  ______________________________________________  |
2015          | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
2016          | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
2017          |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
2018          |                                                  |
2019          |                                                  |
2020          |                                                  |
2021          | /---+"root set"                                  |
2022          | |                                                |
2023          | | h3      h2      h1      h4                     |
2024          | V______________________________________________  |
2025          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2026          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2027          |  ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~  |
2028          |    |      | | |  | | |      |   |                |
2029          |    \------/ | \--/ | \------/   \---+"free"      |
2030          | "Fromspace" \------/                             |
2031          +--------------------------------------------------+
2032
2033
2034
2035 .. _gc_art:
2036
2037 Estado del arte
2038 ----------------------------------------------------------------------------
2039
2040 La manera en que la investigación sobre recolección de basura ha crecido es
2041 realmente sorprendente. Hay, al menos, 2995 publicaciones sobre recolección de
2042 basura registradas al momento de escribir este documento [GCBIB]_. Esto hace
2043 que el análisis del estado del arte sea particularmente complejo y laborioso.
2044
2045 Analizar todas las publicaciones existentes es algo excede los objetivos de
2046 este trabajo, por lo tanto se analizó solo una porción significativa,
2047 utilizando como punto de partida a [JOLI96]_.
2048
2049 De este análisis se observó que la gran mayoría de los algoritmos son
2050 combinaciones de diferentes características básicas; por lo tanto se intentó
2051 aislar estas características que son utilizadas como bloques de construcción
2052 para algoritmos complejos. Ésta tampoco resultó ser una tarea sencilla debido
2053 a que muchos de estos bloques de construcción básicos están interrelacionados
2054 y encontrar una división clara para obtener características realmente atómicas
2055 no es trivial.
2056
2057 La construcción de recolectores más complejos se ve alimentada también por la
2058 existencia de recolectores *híbridos*; es decir, recolectores que utilizan más
2059 de un algoritmo dependiendo de alguna característica de la memoria
2060 a administrar. No es poco común observar recolectores que utilizan un
2061 algoritmo diferente para celdas que sobreviven varias recolecciones que para
2062 las que mueren rápidamente, o que usan diferentes algoritmos para objetos
2063 pequeños y grandes, o que se comporten de forma conservativa para ciertas
2064 celdas y sean precisos para otras.
2065
2066 De todas estas combinaciones resulta el escenario tan fértil para la
2067 investigación sobre recolección de basura.
2068
2069 A continuación se presentan las principales clases de algoritmos
2070 y características básicas encontradas durante la investigación del estado del
2071 arte. La separación de clases y aislamiento de características no es siempre
2072 trivial, ya que hay ciertas clases de recolectores que están interrelacionadas
2073 (o ciertas características pueden estar presentes sólo en recolectores de una
2074 clase en particular).
2075
2076
2077
2078 .. _gc_direct:
2079
2080 Recolección directa / indirecta
2081 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2082
2083 Generalmente se llama recolección **directa** a aquella en la cual el
2084 compilador o lenguaje instrumenta al *mutator* de forma tal que la información
2085 sobre el grafo de conectividad se mantenga activamente cada vez que hay un
2086 cambio en él. Normalmente se utiliza un contador de referencia en cada celda
2087 para este propósito, permitiendo almacenar en todo momento la cantidad de
2088 nodos que apuntan a ésta (ver :ref:`gc_rc`). Esto permite reclamar una celda
2089 instantáneamente cuando el *mutator* deja de hacer referencia a ella.  Este
2090 tipo de recolectores son inherentemente :ref:`incrementales <gc_inc>`.
2091
2092 Por el contrario, los recolectores **indirectos** normalmente no interfieren
2093 con el *mutator* en cada actualización del grafo de conectividad (exceptuando
2094 algunos :ref:`recolectores incrementales <gc_inc>` que a veces necesitan
2095 instrumentar el *mutator* pero no para mantener el estado del grafo de
2096 conectividad completo). La recolección se dispara usualmente cuando el
2097 *mutator* requiere asignar memoria pero no hay más memoria libre conocida
2098 disponible y el recolector se encarga de generar la información de
2099 conectividad desde cero para determinar qué celdas son *basura*.
2100 Prácticamente todos los recolectores menos el :ref:`conteo de referencias
2101 <gc_rc>` están dentro de esta categoría (como por ejemplo, el :ref:`marcado
2102 y barrido <gc_mark_sweep>` y :ref:`copia de semi-espacio <gc_copy>`).
2103
2104 Otros ejemplos de recolectores modernos *directos* son el recolector de basura
2105 de Python_ [NAS00]_ y [LINS05]_ (aunque ambos tiene un algoritmo *indirecto*
2106 para recuperar ciclos).
2107
2108
2109
2110 .. _gc_inc:
2111
2112 Recolección incremental
2113 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2114
2115 Recolección incremental es aquella que se realiza de forma intercalada con el
2116 *mutator*. En general el propósito es disminuir el tiempo de las pausas
2117 causadas por el recolector (aunque generalmente el resultado es un mayor costo
2118 total de recolección en términos de tiempo).
2119
2120 De los `algoritmos clásicos`_ el único que es incremental en su forma más
2121 básica es el :ref:`conteo de referencias <gc_rc>`. Otros recolectores pueden
2122 hacerse incrementales de diversas maneras, pero en general consta de hacer
2123 parte del trabajo de escanear el grafo de conectividad cada vez que el
2124 *mutator* asigna memoria. En general para hacer esto es también necesario
2125 instrumentar al *mutator* de forma tal que informe al recolector cada vez que
2126 cambia el grafo de conectividad, para que éste pueda marcar al sub-grafo
2127 afectado por el cambio como *desactualizado* y así re-escanearlo nuevamente en
2128 la próxima iteración. Para realizar esto en recolectores :ref:`indirectos
2129 <gc_direct>` se utiliza la :ref:`abstracción tricolor <gc_intro_tricolor>`;
2130 cuando el *mutator* cambia una referencia, se marca *gris* la celda que la
2131 contiene, de modo que el recolector vuelva a visitarla.
2132
2133 En general el rendimiento de los recolectores incrementales disminuye
2134 considerablemente cuando el *mutator* actualiza muy seguido el grafo de
2135 conectividad, porque debe re-escanear sub-grafos que ya había escaneado una
2136 y otra vez. A esto se debe también que en general el tiempo de procesamiento
2137 total de un recolector incremental sea mayor que uno no incremental, aunque el
2138 tiempo de pausa de una recolección sea menor.
2139
2140 Ejemplos de recolectores que se encuentran dentro de esta categoría son
2141 [BOEH91]_, [LINS05]_,
2142
2143
2144
2145 .. _gc_concurrent:
2146
2147 Recolección concurrente / paralela / *stop-the-world*
2148 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2149
2150 Los recolectores concurrentes son aquellos que pueden correr en paralelo con
2151 el *mutator*. Por el contrario, aquellos que pausan el *mutator* para realizar
2152 la recolección son usualmente denominados *stop-the-world* (*detener el
2153 mundo*), haciendo referencia a que pausan todos los hilos del *mutator* para
2154 poder escanear el grafo de conectividad de forma consistente. Hay una tercera
2155 clase de colectores que si bien son *stop-the-world*, utilizan todos los hilos
2156 disponibles para realizar la recolección (ver figura
2157 :vref:`fig:gc-concurrent`).
2158
2159 .. flt:: fig:gc-concurrent
2160
2161    Distintos tipos de recolectores según el comportamiento en ambientes
2162    multi-hilo
2163
2164    .. subflt::
2165
2166       *Stop-the-world*.
2167
2168       .. aafig::
2169          :scale: 110
2170          :aspect: 70
2171
2172           ___________________________________________________________________
2173          |                                                                   |
2174          | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
2175          |                                                                   |
2176          | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHHHHHHH |
2177          |                                                                   |
2178          | HHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
2179          |                                                                   |
2180          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2181          |___________________________________________________________________|
2182
2183    .. subflt::
2184
2185       Paralelo.
2186
2187       .. aafig::
2188          :scale: 110
2189          :aspect: 70
2190
2191           ___________________________________________________________________
2192          |                                                                   |
2193          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2194          |                                                                   |
2195          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2196          |                                                                   |
2197          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2198          |                                                                   |
2199          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2200          |___________________________________________________________________|
2201
2202    .. subflt::
2203
2204       Concurrente.
2205
2206       .. aafig::
2207          :scale: 110
2208          :aspect: 70
2209
2210           ___________________________________________________________________
2211          |                                                                   |
2212          | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
2213          |                                                                   |
2214          | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
2215          |                                                                   |
2216          | ZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZ |
2217          |                                                                   |
2218          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2219          |___________________________________________________________________|
2220
2221
2222 Para lograr que un recolector sea concurrente generalmente el mecanismo es
2223 similar al necesario para hacer un :ref:`recolector incremental <gc_inc>`: hay
2224 que instrumentar al *mutator* para que informe al recolector cuando se realiza
2225 algún cambio en el grafo de conectividad, de forma tal que pueda volver
2226 a escanear el sub-grafo afectado por el cambio.
2227
2228 Esto también trae como consecuencia el incremento en el tiempo total que
2229 consume el recolector, debido a la necesidad de re-escanear sub-grafos que han
2230 sido modificados, además de la sincronización necesaria entre *mutator*
2231 y recolector.
2232
2233 ¿Cuál es la idea entonces de un recolector concurrente? Una vez más, al igual
2234 que los recolectores incrementales, el principal objetivo es disminuir las
2235 largas pausas provocadas por la recolección de basura. Sin embargo, este tipo
2236 de algoritmos además permite hacer un mejor aprovechamiento de las
2237 arquitecturas *multi-core* [#gcmulticore]_ que cada vez son más comunes, ya
2238 que el *mutator* y el recolector pueden estar corriendo realmente en paralelo,
2239 cada uno en un procesador distinto. Algunos recolectores van más allá
2240 y permiten incluso paralelizar la recolección de basura en varios hilos
2241 ([HUEL98]_, [LINS05]_). Otros ejemplos de recolectores concurrentes (aunque no
2242 ofrece paralelización del procesamiento del recolector en varios hilos) son
2243 [BOEH91]_, [RODR97]_.
2244
2245 .. [#gcmulticore] Una arquitectura *multi-core* es aquella que combina dos
2246    o más núcleos (*cores*) independientes que trabajan a la misma frecuencia,
2247    pero dentro de un solo circuito integrado o procesador.
2248
2249 Todos los :ref:`algoritmos clásicos <gc_classic>` que se han citado son del
2250 tipo *stop-the-world*.
2251
2252
2253
2254 .. _gc_free_list:
2255
2256 Lista de libres / *pointer bump allocation*
2257 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2258
2259 Esta clasificación se refiere principalmente a la forma en que se organiza el
2260 *heap*, íntimamente relacionado al *low level allocator*. Si bien se ha dicho
2261 que en este trabajo no se prestará particular atención a este aspecto, en
2262 ciertos algoritmos es tan relevante que tampoco es sensato pasarlo por alto
2263 completamente.
2264
2265 En términos generales, hay dos formas fundamentales de organizar el *heap*,
2266 manteniendo una lista de libres o realizando *pointer bump allocation*, como
2267 se explicó en :ref:`gc_copy`. La primera forma consiste, a grandes rasgos, en
2268 separar el *heap* en celdas (que pueden agruparse según tamaño) y enlazarlas
2269 en una lista de libres. Al solicitarse una nueva celda simplemente se la
2270 desenlaza de la lista de libres. Por otro lado, cuando el recolector detecta
2271 una celda *muerta*, la vuelve a enlazar en la lista de libres. Este es un
2272 esquema simple pero con limitaciones, entre las principales, el costo de
2273 asignar puede ser alto si hay muchos tamaños distintos de celda y soportar
2274 tamaño de celda variable puede ser complejo o acarrear muchas otras
2275 ineficiencias. El :ref:`marcado y barrido <gc_mark_sweep>` en general usa este
2276 esquema, al igual que el :ref:`conteo de referencias <gc_rc>`.
2277
2278 Otro forma de organizar el *heap* es utilizándolo como una especie de *stack*
2279 en el cual para asignar simplemente se incrementa un puntero. Este esquema es
2280 simple y eficiente, si el recolector puede mover celdas (ver
2281 :ref:`gc_moving`); de otra manera asignar puede ser muy costoso si hay que
2282 buscar un *hueco* en el heap (es decir, deja de reducirse a incrementar un
2283 puntero). El clásico ejemplo de esta familia es el algoritmo visto en
2284 :ref:`gc_copy`.
2285
2286 Sin embargo, entre estos dos extremos, hay todo tipo de híbridos. Existen
2287 recolectores basados en *regiones*, que se encuentran en un punto intermedio.
2288 Dentro de una región se utiliza un esquema de *pointer bump allocation* pero
2289 las regiones en sí se administran como una lista de libres (como por ejemplo
2290 [BLAC08]_). Otra variación (más común) de este esquema son los *two level
2291 allocators* que asignan páginas completas (similar a las regiones) y dentro de
2292 cada página se asignan las celdas. Ambas, páginas y celdas, se administran
2293 como listas de libres (ejemplos que utilizan este esquema son [BOEHWD]_ y el
2294 :ref:`recolector actual de D <dgc_actual>`).
2295
2296
2297
2298 .. _gc_moving:
2299
2300 Movimiento de celdas
2301 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2302
2303 Otra característica muy importante del recolector de basura es si mueve las
2304 celdas o no. En general el movimiento de celdas viene de la mano del esquema
2305 de :ref:`pointer bump allocation <gc_free_list>`, ya que *compacta* todas las
2306 celdas *vivas* al comienzo del *heap* luego de una recolección, permitiendo
2307 este esquema para asignar nuevas celdas, pero puede utilizarse en esquemas
2308 híbridos como recolectores basados en *regiones* (por ejemplo [BLAC08]_).
2309
2310 Además los recolectores con movimiento de celdas deben ser :ref:`precisos
2311 <gc_conserv>`, porque es necesario tener la información completa de los tipos
2312 para saber cuando actualizar los punteros (de otra manera se podría escribir
2313 un dato de una celda que no era un puntero). Para que un recolector pueda
2314 mover celdas, aunque sea parcialmente, en recolectores *semi-precisos* se
2315 utiliza un método conocido como *pinning* (que significa algo como *pinchar
2316 con un alfiler*); una celda es *pinned* (*pinchada*) cuando hay alguna
2317 referencia no-precisa a ella, y por lo tanto no puede ser movida (porque no se
2318 puede estar seguro si es posible actualizar dicha referencia).
2319
2320 La ventaja principal de los colectores con movimiento es la posibilidad de
2321 utilizar :ref:`pointer bump allocation <gc_free_list>` y que es sencillo
2322 implementar recolectores :ref:`generacionales <gc_part>` sobre estos.
2323
2324 De los algoritmos clásicos sólo la :ref:`copia de semi-espacios <gc_copy>`
2325 mueve celdas, el :ref:`conteo de referencias <gc_rc>` y :ref:`marcado
2326 y barrido <gc_mark_sweep>` no lo hacen. Además hay otro algoritmo bastante
2327 básico que mueve celdas, el **marcado y compactado**. Éste no tiene
2328 2 semi-espacios, directamente mueve las celdas compactándolas al comienzo del
2329 *heap*. El algoritmo es un poco más complejo que la :ref:`copia de
2330 semi-espacios <gc_copy>` pero suele proveer una mayor localidad de referencia
2331 y no *desperdicia* un semi-espacio que está inutilizado salvo en el momento de
2332 la recolección. Por ejemplo para Mono_, que antes usaba un recolector
2333 conservativo sin movimiento ([BOEHWD]_) se está implementando un recolector de
2334 este tipo [MOLAWE]_ [MOLA06]_.
2335
2336
2337
2338 .. _gc_conserv:
2339
2340 Recolectores conservativos versus precisos
2341 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2342
2343 Los recolectores *conservativos* son aquellos que tienen la capacidad de poder
2344 lidiar con un *root set* o celdas que no tengan información de tipos asociada.
2345 Esto significa que el recolector no sabe donde hay punteros (o referencias) en
2346 una celda o raiz dada. Es decir, una ubicación particular puede ser un puntero
2347 o no. Esto trae una variada cantidad de problemas, como retención de celdas
2348 que en realidad son *basura* simplemente porque hay algún dato que coincide
2349 con la dirección de memoria en la que está almacenada esa celda *basura*
2350 [#gcflasepos]_. Además los recolectores puramente conservativos no puede mover
2351 celdas (ver :ref:`gc_moving`), dado que no pueden actualizar los supuestos
2352 punteros por la posibilidad de que sean *falsos positivos*.
2353
2354 .. [#gcflasepos] Esto es lo que se conoce como un *falso positivo*, algo que
2355    aparenta ser un puntero pero en realidad no lo es.
2356
2357 Sin embargo hay ciertas circunstancias que hacen que no quede más remedio que
2358 el recolector sea conservativo, por ejemplo cuando se utiliza un recolector de
2359 basura para un lenguaje que no ha sido pensado para tener uno (como C o C++).
2360
2361 Por el contrario, los recolectores que poseen a su disposición información
2362 completa sobre el tipo de la celda, y por ende información sobre cuales de sus
2363 campos son realmente punteros, son denominados *precisos*. Estos recolectores
2364 no están sujetos a estas limitaciones y por lo tanto son potencialmente más
2365 eficientes en cuanto a tiempo y espacio. Los lenguajes que fueron diseñados
2366 para tener un recolector de basura (y en especial aquellos que son de relativo
2367 alto nivel) en general disponen de recolectores precisos.
2368
2369 Hay casos donde se posee información de tipos para algunas celdas solamente,
2370 o más comúnmente se posee información de tipos de celdas que se encuentran en
2371 el *heap* pero no para el *stack* y registros (por ejemplo [MOLA06]_). En
2372 estos casos se puede adoptar un esquema híbrido y tratar algunas referencias
2373 de forma conservativa y otras de forma precisa, de manera de mitigar, aunque
2374 sea de forma parcial, los efectos adversos de los recolectores conservativos.
2375 Estos recolectores son conocidos como *semi-precisos*. Los recolectores
2376 semi-precisos pueden mover celdas si utilizan un mecanismo de *pinning* (ver
2377 :ref:`gc_moving`).
2378
2379 El ejemplo de recolector conservativo por excelencia es el recolector
2380 `Boehm-Demers-Wiser`_ ([BOEH88]_, [BOEH91]_, [BOEH93]_, [BOEHWD]_) aunque
2381 puede comportarse de forma semi-precisa si el usuario se encarga de darle la
2382 información de tipos (en cuyo caso el recolector deja de ser transparente para
2383 el usuario). Otros ejemplos de recolectores con cierto grado de precisión son
2384 el :ref:`recolector actual de D <dgc_actual>` y [BLAC08]_.
2385
2386
2387
2388 .. _gc_part:
2389
2390 Recolección por particiones / generacional
2391 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2392
2393 Otra forma de reducir la cantidad de pausas y la cantidad de trabajo realizado
2394 por el recolector en general es dividiendo el *heap* en particiones de manera
2395 tal de recolectar solo las partes donde más probabilidad de encontrar *basura*
2396 haya.
2397
2398 Entonces, si el recolector tiene algún mecanismo para identificar zonas de
2399 alta concentración de *basura* puede hacer la recolección solo en ese área
2400 donde el trabajo va a ser mejor recompensado (ver figura :vref:`fig:gc-part`).
2401
2402 .. flt:: fig:gc-part
2403
2404    Concentración de basura en distintas particiones del *heap*
2405
2406    .. aafig::
2407       :scale: 110
2408       :aspect: 70
2409
2410        _______________________________________________________________________
2411       |                                                                       |
2412       |   +-----------------------------+   +-----------------------------+   |
2413       |  /             Baja              \ /             Alta              \  |
2414       | +                                 +                                 + |
2415       | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
2416       | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
2417       |                                                                       |
2418       |        GG Celdas vivas                                ZZ Basura       |
2419       |_______________________________________________________________________|
2420
2421
2422 Sin embargo encontrar zonas de alta concentración no es trivial. La forma más
2423 divulgada de encontrar estas zonas es dividiendo el *heap* en una partición
2424 utilizada para almacenar celdas *jóvenes* y otra para celdas *viejas*. Una
2425 celda *vieja* es aquella que ha *sobrevivido* una cantidad *N* de
2426 recolecciones, mientras que el resto se consideran *jóvenes* (las celdas
2427 *nacen* jóvenes).  Los recolectores que utilizan este tipo de partición son
2428 ampliamente conocido como recolectores **generacionales**. La *hipótesis
2429 generacional* dice que el área de celdas jóvenes tiene una mayor probabilidad
2430 de ser un área de alta concentración de basura [JOLI96]_. Basándose en esto,
2431 los recolectores generacionales primero intentan recuperar espacio del área de
2432 celdas jóvenes y luego, de ser necesario, del área de celdas viejas. Es
2433 posible tener varias generaciones e ir subiendo de generación a generación
2434 a medida que es necesario. Sin embargo en general no se obtienen buenos
2435 resultados una vez que se superan las 3 particiones. La complejidad que trae
2436 este método es que para recolectar la generación joven es necesario tomar las
2437 referencias de la generación vieja a la joven como parte del *root set* (de
2438 otra forma podrían tomarse celdas como *basura* que todavía son utilizadas por
2439 las celdas viejas). Revisar toda la generación vieja no es una opción porque
2440 sería prácticamente lo mismo que realizar una recolección del *heap* completo.
2441 La solución está entonces, una vez más, en instrumentar el *mutator* para que
2442 avise al recolector cuando cambia una referencia de la generación vieja a la
2443 joven (no es necesario vigilar las referencias en sentido inverso ya que
2444 cuando se recolecta la generación vieja se hace una recolección del *heap*
2445 completo).
2446
2447 Sin embargo, a pesar de ser este el esquema más difundido para dividir el
2448 *heap* y realizar una recolección parcial sobre un área de alta concentración
2449 de basura, no es la única. Otros recolectores proponen hacer un análisis
2450 estático del código revisando la conectividad entre los objetos según sus
2451 tipos (esto es posible solo en lenguajes con *tipado* estático), de manera tal
2452 de separar en distintas áreas grupos de tipos que no pueden tener referencias
2453 entre sí [HIRZ03]_. Este análisis hace que sea innecesario instrumentar el
2454 *mutator* para reportar al recolector cambios de referencias
2455 inter-particiones, sencillamente porque queda demostrado que no existe dicho
2456 tipo de referencias. Esto quita una de las principales ineficiencias
2457 y complejidades del esquema generacional.
2458
2459
2460
2461 .. include:: links.rst
2462
2463 .. vim: set ts=3 sts=3 sw=3 et tw=78 spelllang=es :