source/gc.rst

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