source/gc.rst

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