source/gc.rst

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