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 re-asignada 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]_ asignada 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 asignada 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 asignar 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 asignar memoria (tan eficiente como asignar memoria en el
1690 *stack*).
1691
1692 .. fig:: fig:gc-copy
1693
1694    Estructura del *heap* de un recolector con copia de semi-espacios.
1695
1696    .. aafig::
1697       :aspect: 0.7
1698       :scale: 1.4
1699
1700       zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
1701
1702        /---+"Fromspace"                /---+"Tospace"
1703        |                               |
1704        V_______________________________V_______________________________
1705        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1706        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1707        | XXXX  X  XXX  aaaaaaaaaaaaaaaa|bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb|
1708        |~~~~~~~~~~~~~~~A~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1709                        |
1710        |               |               |    XX "Fromspace usado"
1711                        \---+"libre"
1712        |                               |    ZZ "Fromspace basura"
1713
1714        |/  "longitud del semi-espacio" |/   AA "Fromspace libre"
1715        +- - - - - - - - - - - - - - - -+
1716       /|                              /|    BB "Tospace"
1717
1718
1719 La segunda mitad (*Tospace*) permanece inutilizada hasta que se agota el
1720 espacio en el *Fromspace*; en ese momento comienza el proceso de recolección
1721 de basura que consiste en recorrer el grafo de conectividad, copiando las
1722 celdas *vivas* del *Fromspace* al *Tospace* de manera contigua, como si
1723 estuvieran asignando por primera vez. Como la posición en memoria de las
1724 celdas cambia al ser movidas, es necesario actualizar la dirección de memoria
1725 de todas las celdas *vivas*. Para esto se almacena una dirección de memoria de
1726 redirección, *forwarding address*, en las celdas que mueven. La *forwarding
1727 address* sirve a su vez de marca, para no recorrer una celda dos veces (como
1728 se explica en :ref:`gc_intro_mark`). Cuando se encuentra una celda que ya fue
1729 movida, simplemente se actualiza la referencia por la cual se llegó a esa
1730 celda para que apunte a la nueva dirección, almacenada en la *forwarding
1731 address*. Una vez finalizado este proceso, el *Fromspace* y *Tospace*
1732 invierten roles y se prosigue de la misma manera (todo lo que quedó en el
1733 viejo *Fromspace* es *basura* por definición, por lo que se convierte el
1734 *Tospace*).
1735
1736 A continuación se presenta una implementación sencilla de los servicios
1737 provistos por este tipo de recolectores. Cabe destacar que este tipo de
1738 recolectores deben estar íntimamente relacionados con el *low level
1739 allocator*, ya que la organización del *heap* y la forma de asignar memoria es
1740 parte fundamental de este algoritmo. Se asume que ya hay dos áreas de memoria
1741 del mismo tamaño destinadas al *Fromspace* y *Tospace*, y la existencia de
1742 4 variables: ``fromspace`` (que apunta a la base del *Fromspace*), ``tospace``
1743 (que apunta a la base del *Tospace*), ``spacesize`` (que contiene el tamaño de
1744 un semi-espacio) y ``free`` (que apunta al lugar del *Fromspace* donde
1745 comienza la memoria libre). También vale aclarar que este algoritmo soporta
1746 inherentemente celdas de tamaño variable, por lo que los servicios ``alloc()``
1747 y ``new()`` [#gccopynew]_ reciben como parámetro el tamaño de la celda
1748 a asignar::
1749
1750    function alloc(size) is
1751       if free + size > fromspace + spacesize
1752          return null
1753       else
1754          cell = free
1755          free = free + size
1756          return cell
1757
1758    function new(size) is
1759       cell = alloc(size)
1760       if cell is null
1761          collect()
1762       cell = alloc(size)
1763       if cell is null
1764          throw out_of_memory
1765       return cell
1766
1767    function collect() is
1768       free = tospace
1769       foreach r in root_set
1770          r = copy(r)
1771       fromspace, tospace = tospace, fromspace
1772
1773    function copy(cell) is
1774       if cell.forwarding_address is null
1775          cell.forwarding_address = free
1776          free = free + cell.size
1777          foreach child in cell
1778             child = copy(child)
1779          return cell.forwarding_address
1780       else
1781          return cell.forwarding_address
1782
1783 .. [#gccopynew] Notar que ``new()`` es igual que en el marcado y barrido con
1784    la salvedad de que en este caso toma como parámetro el tamaño de la celda.
1785
1786 Esta técnica tiene nombres variados en inglés: *semi-space*, *two-space*
1787 o simplemente *copying collector*. En este documento se denomina "copia de
1788 semi-espacio" porque los otros nombres son demasiado generales y pueden
1789 describir, por ejemplo, algoritmos donde no hay copia de celdas o donde no hay
1790 2 semi-espacios (como se verá en :ref:`gc_art`).
1791
1792 Al igual que el :ref:`gc_mark_sweep` este algoritmo es :ref:`indirecto
1793 <gc_direct>`, :ref:`no incremental <gc_inc>` y :ref:`stop-the-world
1794 <gc_concurrent>`. Las diferencias con los esquemas vistos hasta ahora son
1795 evidentes. La principal ventaja sobre el marcado y barrido (que requiere una
1796 pasada sobre el *live set*, el marcado, y otra sobre el *heap* entero, el
1797 barrido) es que este método require una sola pasada y sobre las celdas vivas
1798 del *heap* solamente. La principal desventaja es copia memoria, lo que puede
1799 ser particularmente costoso, además de requerir, como mínimo, el doble de
1800 memoria de lo que el *mutator* realmente necesita. Esto puede traer en
1801 particular problemas con la memoria virtual y el caché, por la pobre localidad
1802 de referencia.
1803
1804 Por lo tanto los recolectores de este tipo pueden ser convenientes por sobre
1805 el marcado y barrido cuando se espera que el *live set* sea muy pequeño luego
1806 de una recolección. En estos casos el trabajo realizado por este tipo de
1807 recolectores puede ser considerablemente menor que el del marcado y barrido.
1808 Y por el contrario, si el *working set* es pequeño, al ser *compactado* en
1809 memoria puede mejorar la localidad de referencia (si el *working set* es
1810 grande se corre el riesgo de que la localidad de referencia empeore al moverse
1811 las celdas).
1812
1813
1814 Ejemplo
1815 ^^^^^^^
1816
1817 A continuación se presenta un sencillo ejemplo del algoritmo. Se parte de una
1818 estructura simple con 4 celdas en el *Fromspace* (que incluye un pequeño ciclo
1819 para mostrar que este algoritmo tampoco tiene inconvenientes para
1820 recolectarlos). Asumimos que ya no queda lugar en el *Fromspace* por lo que
1821 comienza la ejecución de ``collect()``. Se comienza por el *root set* que
1822 apunta a ``h3``, por lo tanto ésta es movida al *Tospace* primero, dejando una
1823 *forwarding address* a la nueva ubicación (ver figura
1824 :vref:`fig:gc-copy-ex-1`).
1825
1826 .. fig:: fig:gc-copy-ex-1
1827
1828    Ejemplo de recolección con copia de semi-espacios (parte 1).
1829
1830    .. subfig::
1831
1832       Estructura inicial del *heap*. El *Fromspace* está complete y se inicial
1833       la recolección.
1834
1835       .. aafig::
1836          :scale: 1.25
1837
1838          +--------------------------------------------------+
1839          | "Fromspace"                                      |
1840          |        /--------------------------------\        |
1841          |        | /--------\  /------\           |        |
1842          |        | |        |  |      |           |        |
1843          |  ______|_V________|__V______|___________V______  |
1844          | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
1845          | ZZZZGGGGGGGGZZZZGGGGGGGGggggggggZZZZGGGGGGGGZZZZ |
1846          |  ~~~~~~~~~|~~~~~~~~~~A~~~~~~~A~~~~~~~~~~~~~~~~~  |
1847          |      h1   |      h2  |   h3  |       h4          |
1848          |           \----------/       |                   |
1849          |                              \----+"root set"    |
1850          |                                                  |
1851          |                                                  |
1852          |                                                  |
1853          |  ______________________________________________  |
1854          | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1855          | BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1856          | A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1857          | |                                                |
1858          | \----+"free"                                     |
1859          | "Tospace"                                        |
1860          +--------------------------------------------------+
1861
1862    .. subfig::
1863
1864       Se sigue la referencia del *root set*, copiando ``h3`` al *Tospace*
1865       y dejando una *forwarding address*.
1866
1867       .. aafig::
1868          :scale: 1.25
1869
1870          +--------------------------------------------------+
1871          | "Fromspace"                                      |
1872          |        /--------------------------------\        |
1873          |        | /--------\  /------\           |        |
1874          |        | |        |  |      |           |        |
1875          |  ______|_V________|__V______|___________V______  |
1876          | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
1877          | ZZZZGGGGGGGGZZZZGGGGGGGGffffffffZZZZGGGGGGGGZZZZ |
1878          |  ~~~~~~~~~|~~~~~~~~~~A~~~~~~~|A~~~~~~~~~~~~~~~~  |
1879          |      h1   |      h2  |   h3  ||      h4          |
1880          |           \----------/       ||                  |
1881          |                              +\----+"root set"   |
1882          |                             /                    |
1883          |  /-------------------------+                     |
1884          |  | h3                                            |
1885          |  V_____________________________________________  |
1886          | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1887          | HHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1888          |  ~~~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1889          |         |                                        |
1890          |         \----+"free"                             |
1891          | "Tospace"                                        |
1892          +--------------------------------------------------+
1893
1894
1895 A continuación se copian las *hijas* de ``h3``, en este caso sólo ``h2``, que
1896 se ubica en el *Tospace* a continuación de ``h3``, dejando nuevamente su
1897 ``forwarding address`` en la celda original. Al proceder recursivamente, se
1898 procede a copiar ``h1`` al *Tospace*, dejando una vez más la *forwarding
1899 address* en la celda original y procediendo con las hijas. Aquí podemos
1900 observar que al seguirse la referencia :math:`h1 \to h2`, como ``h2`` ya había
1901 sido visitada, solamente se actualiza la referencia apuntando a la nueva
1902 ubicación de ``h2`` pero no se vuelve a copiar la celda (ver figura
1903 :vref:`fig:gc-copy-ex-2`).
1904
1905 .. fig:: fig:gc-copy-ex-2
1906
1907    Ejemplo de recolección con copia de semi-espacios (parte 2).
1908
1909    .. subfig::
1910
1911       Se sigue :math:`h3 \to h2`, copiando ``h2`` al *Tospace* y dejando una
1912       *forwarding address*.
1913
1914       .. aafig::
1915          :scale: 1.25
1916
1917          +--------------------------------------------------+
1918          | "Fromspace"                                      |
1919          |        /--------------------------------\        |
1920          |        | /--------\  /------\           |        |
1921          |        | |        |  |      |           |        |
1922          |  ______|_V________|__V______|___________V______  |
1923          | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1924          | ZZZZGGGGGGGGZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1925          |  ~~~~~~~~~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~  |
1926          |      h1   |      h2  ||  h3  ||      h4          |
1927          |           \----------/+      ||                  |
1928          |                      /       +\----+"root set"   |
1929          |         +-----------+       /                    |
1930          |  /------+------------------+                     |
1931          |  | h3   | h2                                     |
1932          |  V______V______________________________________  |
1933          | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1934          | HHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB |
1935          |  ~~|~~~~~~A~~~~~A~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
1936          |    |      |     |                                |
1937          |    \------/     \----+"free"                     |
1938          | "Tospace"                                        |
1939          +--------------------------------------------------+
1940
1941    .. subfig::
1942
1943       Se sigue :math:`h2 \to h1`, copiando ``h1``. Luego :math:`h1 \to h2`
1944       pero ``h2`` no se copia, sólo se actualiza la referencia con la
1945       *forwarding address*.
1946
1947       .. aafig::
1948          :scale: 1.25
1949
1950          +--------------------------------------------------+
1951          | "Fromspace"                                      |
1952          |        /--------------------------------\        |
1953          |        | /--------\  /------\           |        |
1954          |        | |        |  |      |           |        |
1955          |  ______|_V________|__V______|___________V______  |
1956          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1957          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZGGGGGGGGZZZZ |
1958          |  ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~~~~~~~  |
1959          |      h1 | |      h2  ||  h3  ||      h4          |
1960          |         \-+----------/+      ||                  |
1961          |           +-----+    /       +\-----+"root set"  |
1962          |         +-------+---+       /                    |
1963          |  /------+-------+----------+                     |
1964          |  | h3   | h2    | h1                             |
1965          |  V______V_______V______________________________  |
1966          | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
1967          | HHHHHHHHhhhhhhhhHHHHHHHHBBBBBBBBBBBBBBBBBBBBBBBB |
1968          |  ~~|~~~~~~A~|~A~~|~A~~~~A~~~~~~~~~~~~~~~~~~~~~~  |
1969          |    |      | | |  | |    |                        |
1970          |    \------/ | \--/ |    \----+"free"             |
1971          | "Tospace"   \------/                             |
1972          +--------------------------------------------------+
1973
1974
1975 Se termina de copiar recursivamente las hijas de ``h1`` al copiar ``h4`` que
1976 resulta la última celda (sin hijas). Finalmente se invierten los roles de los
1977 semi-espacios y se actualiza la referencia del *root set* para que apunte a la
1978 nueva ubicación de ``h3``, como se muestra en la figura
1979 :vref:`fig:gc-copy-ex-3`.
1980
1981 .. fig:: fig:gc-copy-ex-3
1982
1983    Ejemplo de recolección con copia de semi-espacios (parte 3).
1984
1985    .. subfig::
1986
1987       Se sigue :math:`h1 \to h4` copiando `h4`` al *Tospace* y dejando una
1988       *forwarding address*.
1989
1990       .. aafig::
1991          :scale: 1.25
1992
1993          +--------------------------------------------------+
1994          | "Fromspace"                                      |
1995          |        /--------------------------------\        |
1996          |        | /--------\  /------\           |        |
1997          |        | |        |  |      |           |        |
1998          |  ______|_V________|__V______|___________V______  |
1999          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
2000          | ZZZZFFFFFFFFZZZZFFFFFFFFffffffffZZZZFFFFFFFFZZZZ |
2001          |  ~~~~~~~|~|~~~~~~~~~~A|~~~~~~|A~~~~~~~~~~|~~~~~  |
2002          |      h1 | |      h2  ||  h3  ||      h4  \----\  |
2003          |         \-+----------/+      ||               |  |
2004          |           +-----+    /  +----/\---+"root set" |  |
2005          |         +-------+---+  /                      |  |
2006          |  /------+-------+-----+  /--------------------/  |
2007          |  | h3   | h2    | h1     | h4                    |
2008          |  V______V_______V________V_____________________  |
2009          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2010          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2011          |  ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~  |
2012          |    |      | | |  | | |      |   |                |
2013          |    \------/ | \--/ | \------/   \----+"free"     |
2014          | "Tospace"   \------/                             |
2015          +--------------------------------------------------+
2016
2017    .. subfig::
2018
2019       Se finaliza la recolección, se intercambian los roles de los
2020       semi-espacios y se actualiza la referencia del *root set*.
2021
2022       .. aafig::
2023          :scale: 1.25
2024
2025          +--------------------------------------------------+
2026          | "Tospace"                                        |
2027          |                                                  |
2028          |                                                  |
2029          |                                                  |
2030          |  ______________________________________________  |
2031          | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
2032          | AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
2033          |  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  |
2034          |                                                  |
2035          |                                                  |
2036          |                                                  |
2037          | /---+"root set"                                  |
2038          | |                                                |
2039          | | h3      h2      h1      h4                     |
2040          | V______________________________________________  |
2041          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2042          | HHHHHHHHhhhhhhhhHHHHHHHHhhhhhhhhBBBBBBBBBBBBBBBB |
2043          |  ~~|~~~~~~A~|~A~~|~A~|~~~~~~A~~~A~~~~~~~~~~~~~~  |
2044          |    |      | | |  | | |      |   |                |
2045          |    \------/ | \--/ | \------/   \---+"free"      |
2046          | "Fromspace" \------/                             |
2047          +--------------------------------------------------+
2048
2049
2050
2051 .. _gc_art:
2052
2053 Estado del arte
2054 ----------------------------------------------------------------------------
2055
2056 La manera en que la investigación sobre recolección de basura ha crecido es
2057 realmente sorprendente. Hay, al menos, 2995 publicaciones sobre recolección de
2058 basura registradas al momento de escribir este documento [GCBIB]_. Esto hace
2059 que el análisis del estado del arte sea particularmente complejo y laborioso.
2060
2061 Analizar todas las publicaciones existentes es algo excede los objetivos de
2062 este trabajo, por lo tanto se analizó solo una porción significativa,
2063 utilizando como punto de partida a [JOLI96]_.
2064
2065 De este análisis se observó que la gran mayoría de los algoritmos son
2066 combinaciones de diferentes características básicas; por lo tanto se intentó
2067 aislar estas características que son utilizadas como bloques de construcción
2068 para algoritmos complejos. Ésta tampoco resultó ser una tarea sencilla debido
2069 a que muchos de estos bloques de construcción básicos están interrelacionados
2070 y encontrar una división clara para obtener características realmente atómicas
2071 no es trivial.
2072
2073 La construcción de recolectores más complejos se ve alimentada también por la
2074 existencia de recolectores *híbridos*; es decir, recolectores que utilizan más
2075 de un algoritmo dependiendo de alguna característica de la memoria
2076 a administrar. No es poco común observar recolectores que utilizan un
2077 algoritmo diferente para celdas que sobreviven varias recolecciones que para
2078 las que mueren rápidamente, o que usan diferentes algoritmos para objetos
2079 pequeños y grandes, o que se comporten de forma conservativa para ciertas
2080 celdas y sean precisos para otras.
2081
2082 De todas estas combinaciones resulta el escenario tan fértil para la
2083 investigación sobre recolección de basura.
2084
2085 A continuación se presentan las principales clases de algoritmos
2086 y características básicas encontradas durante la investigación del estado del
2087 arte. La separación de clases y aislamiento de características no es siempre
2088 trivial, ya que hay ciertas clases de recolectores que están interrelacionadas
2089 (o ciertas características pueden estar presentes sólo en recolectores de una
2090 clase en particular).
2091
2092
2093
2094 .. _gc_direct:
2095
2096 Recolección directa / indirecta
2097 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2098
2099 Generalmente se llama recolección **directa** a aquella en la cual el
2100 compilador o lenguaje instrumenta al *mutator* de forma tal que la información
2101 sobre el grafo de conectividad se mantenga activamente cada vez que hay un
2102 cambio en él. Normalmente se utiliza un contador de referencia en cada celda
2103 para este propósito, permitiendo almacenar en todo momento la cantidad de
2104 nodos que apuntan a ésta (ver :ref:`gc_rc`). Esto permite reclamar una celda
2105 instantáneamente cuando el *mutator* deja de hacer referencia a ella.  Este
2106 tipo de recolectores son inherentemente :ref:`incrementales <gc_inc>`.
2107
2108 Por el contrario, los recolectores **indirectos** normalmente no interfieren
2109 con el *mutator* en cada actualización del grafo de conectividad (exceptuando
2110 algunos :ref:`recolectores incrementales <gc_inc>` que a veces necesitan
2111 instrumentar el *mutator* pero no para mantener el estado del grafo de
2112 conectividad completo). La recolección se dispara usualmente cuando el
2113 *mutator* requiere asignar memoria pero no hay más memoria libre conocida
2114 disponible y el recolector se encarga de generar la información de
2115 conectividad desde cero para determinar qué celdas son *basura*.
2116
2117 Esta es la madre de toda clasificación, también conocidos como :ref:`conteo de
2118 referencias <gc_rc>` (directa) y *traicing garbage collection* (indirecta).
2119 Prácticamente todos los recolectores menos el :ref:`conteo de referencias
2120 <gc_rc>` están dentro de esta última categoría (como por ejemplo, el
2121 :ref:`marcado y barrido <gc_mark_sweep>` y :ref:`copia de semi-espacio
2122 <gc_copy>`).
2123
2124 Otros ejemplos de recolectores modernos *directos* son el recolector de basura
2125 de Python_ [NAS00]_ y [LINS05]_ (aunque ambos tiene un algoritmo *indirecto*
2126 para recuperar ciclos).
2127
2128
2129
2130 .. _gc_inc:
2131
2132 Recolección incremental
2133 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2134
2135 Recolección incremental es aquella que se realiza de forma intercalada con el
2136 *mutator*. En general el propósito es disminuir el tiempo de las pausas
2137 causadas por el recolector (aunque generalmente el resultado es un mayor costo
2138 total de recolección en términos de tiempo).
2139
2140 De los `algoritmos clásicos`_ el único que es incremental en su forma más
2141 básica es el :ref:`conteo de referencias <gc_rc>`. Otros recolectores pueden
2142 hacerse incrementales de diversas maneras, pero en general consta de hacer
2143 parte del trabajo de escanear el grafo de conectividad cada vez que el
2144 *mutator* asigna memoria. En general para hacer esto es también necesario
2145 instrumentar al *mutator* de forma tal que informe al recolector cada vez que
2146 cambia el grafo de conectividad, para que éste pueda marcar al sub-grafo
2147 afectado por el cambio como *desactualizado* y así re-escanearlo nuevamente en
2148 la próxima iteración. Para realizar esto en recolectores :ref:`indirectos
2149 <gc_direct>` se utiliza la :ref:`abstracción tricolor <gc_intro_tricolor>`;
2150 cuando el *mutator* cambia una referencia, se marca *gris* la celda que la
2151 contiene, de modo que el recolector vuelva a visitarla.
2152
2153 En general la eficiencia de los recolectores incrementales disminuye
2154 considerablemente cuando el *mutator* actualiza muy seguido el grafo de
2155 conectividad, porque debe re-escanear sub-grafos que ya había escaneado una
2156 y otra vez. A esto se debe también que en general el tiempo de procesamiento
2157 total de un recolector incremental sea mayor que uno no incremental, aunque el
2158 tiempo de pausa de una recolección sea menor.
2159
2160 Ejemplos de recolectores que se encuentran dentro de esta categoría son
2161 [BOEH91]_, [LINS05]_,
2162
2163
2164
2165 .. _gc_concurrent:
2166
2167 Recolección concurrente / paralela / *stop-the-world*
2168 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2169
2170 Los recolectores concurrentes son aquellos que pueden correr en paralelo con
2171 el *mutator*. Por el contrario, aquellos que pausan el *mutator* para realizar
2172 la recolección son usualmente denominados *stop-the-world* (*detener el
2173 mundo*), haciendo referencia a que pausan todos los hilos del *mutator* para
2174 poder escanear el grafo de conectividad de forma consistente. Hay una tercera
2175 clase de colectores que si bien son *stop-the-world*, utilizan todos los hilos
2176 disponibles para realizar la recolección (ver figura
2177 :vref:`fig:gc-concurrent`).
2178
2179 .. fig:: fig:gc-concurrent
2180
2181    Distintos tipos de recolectores según el comportamiento en ambientes
2182    multi-hilo.
2183
2184    .. subfig::
2185
2186       *Stop-the-world*.
2187
2188       .. aafig::
2189          :aspect: 0.7
2190
2191           ___________________________________________________________________
2192          |                                                                   |
2193          | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
2194          |                                                                   |
2195          | HHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHHHHHHH |
2196          |                                                                   |
2197          | HHHHHHHHHXXXXXXXXXXXXXHHHHHHHHHHHHZZZZZZZZZZZZZHHHHHHHHHHHHHHHHHH |
2198          |                                                                   |
2199          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2200          |___________________________________________________________________|
2201
2202    .. subfig::
2203
2204       Paralelo.
2205
2206       .. aafig::
2207          :aspect: 0.7
2208
2209           ___________________________________________________________________
2210          |                                                                   |
2211          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2212          |                                                                   |
2213          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2214          |                                                                   |
2215          | HHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHXXXXXHHHHHHHHHHHHHHHHHHHHHHHHHH |
2216          |                                                                   |
2217          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2218          |___________________________________________________________________|
2219
2220    .. subfig::
2221
2222       Concurrente.
2223
2224       .. aafig::
2225          :aspect: 0.7
2226
2227           ___________________________________________________________________
2228          |                                                                   |
2229          | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
2230          |                                                                   |
2231          | HHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHZZHHHHHHHHHHHHHHHHHHHHHHHHHHHHH |
2232          |                                                                   |
2233          | ZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZ |
2234          |                                                                   |
2235          |         HH Mutator           ZZ Inactivo         XX Recolector    |
2236          |___________________________________________________________________|
2237
2238
2239 Para lograr que un recolector sea concurrente generalmente el mecanismo es
2240 similar al necesario para hacer un :ref:`recolector incremental <gc_inc>`: hay
2241 que instrumentar al *mutator* para que informe al recolector cuando se realiza
2242 algún cambio en el grafo de conectividad, de forma tal que pueda volver
2243 a escanear el sub-grafo afectado por el cambio.
2244
2245 Esto también trae como consecuencia el incremento en el tiempo total que
2246 consume el recolector, debido a la necesidad de re-escanear sub-grafos que han
2247 sido modificados, además de la sincronización necesaria entre *mutator*
2248 y recolector.
2249
2250 ¿Cúal es la idea entonces de un recolector concurrente? Una vez más, al igual
2251 que los recolectores incrementales, el principal objetivo es disminuir las
2252 largas pausas provocadas por la recolección de basura. Sin embargo, este tipo
2253 de algoritmos además permite hacer un mejor aprovechamiento de las
2254 arquitecturas *multi-core* [#gcmulticore]_ que cada vez se afirman más, ya que
2255 el *mutator* y el recolector pueden estar corriendo realmente en paralelo,
2256 cada uno en un procesador distinto. Algunos recolectores van más allá
2257 y permiten incluso paralelizar la recolección de basura en varios hilos
2258 ([HUEL98]_, [LINS05]_). Otros ejemplos de recolectores concurrentes (aunque no
2259 ofrece paralelización del procesamiento del recolector en varios hilos) son
2260 [BOEH91]_, [RODR97]_.
2261
2262 .. [#gcmulticore] Una arquitectura *multi-core* es aquella que combina dos
2263    o más núcleos (*cores*) independientes que trabajan a la misma frecuencia,
2264    pero dentro de un solo circuito integrado o procesador.
2265
2266 Todos los :ref:`algoritmos clásicos <gc_classic>` que se han citado son del
2267 tipo *stop-the-world*.
2268
2269
2270
2271 .. _gc_free_list:
2272
2273 Lista de libres / *pointer bump allocation*
2274 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2275
2276 Esta clasificación se refiere principalmente a la forma en que se organiza el
2277 *heap*, íntimamente relacionado al *low level allocator*. Si bien se ha dicho
2278 que en este trabajo no se prestará particular atención a este aspecto, en
2279 ciertos algoritmos es tan relevante que tampoco es sensato pasarlo por alto
2280 completamente.
2281
2282 En términos generales, hay dos formas fundamentales de organizar el *heap*,
2283 manteniendo una lista de libres o realizando *pointer bump allocation*, como
2284 se explicó en :ref:`gc_copy`. La primera forma consiste, a grandes rasgos, en
2285 separar el *heap* en celdas (que pueden agruparse según tamaño) y enlazarlas
2286 en una lista de libres. Al solicitarse una nueva celda simplemente se la
2287 desenlaza de la lista de libres. Por otro lado, cuando el recolector detecta
2288 una celda *muerta*, la vuelve a enlazar en la lista de libres. Este es un
2289 esquema simple pero con limitaciones, entre las principales, el costo de
2290 asignar puede ser alto si hay muchos tamaños distintos de celda y soportar
2291 tamaño de celda variable puede ser complejo o acarrear muchas otras
2292 ineficiencias. :ref:`gc_mark_sweep` en general usa este esquema, al igual que
2293 :ref:`gc_rc`.
2294
2295 Otro forma de organizar el *heap* es utilizándolo como una especie de *stack*
2296 en el cual para asignar simplemente se incrementa un puntero. Este esquema es
2297 simple y eficiente, si el recolector puede mover celdas (ver
2298 :ref:`gc_moving`); de otra manera asignar puede ser muy costoso si hay que
2299 buscar un *hueco* en el heap (es decir, deja de reducirse a incrementar un
2300 puntero). El clásico ejemplo de esta familia es :ref:`gc_copy`.
2301
2302 Sin embargo, entre estos dos extremos, hay todo tipo de híbridos. Existen
2303 recolectores basados en *regiones*, que se encuentran en un punto intermedio.
2304 Dentro de una región se utiliza un esquema de *pointer bump allocation* pero
2305 las regiones en sí se administran como una lista de libres (como por ejemplo
2306 [BLAC08]_). Otra variación (más común) de este esquema son los *two level
2307 allocators* que asignan páginas completas (similar a las regiones) y dentro de
2308 cada página se asignan las celdas. Ambas, páginas y celdas, se administran
2309 como listas de libres (ejemplos que utilizan este esquema son [BOEHWD]_ y el
2310 :ref:`recolector actual de D <dgc_actual>`).
2311
2312
2313
2314 .. _gc_moving:
2315
2316 Movimiento de celdas
2317 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2318
2319 Otra característica muy importante del recolector de basura es si mueve las
2320 celdas o no. En general el movimiento de celdas viene de la mano del esquema
2321 de :ref:`pointer bump allocation <gc_free_list>`, ya que *compacta* todas las
2322 celdas *vivas* al comienzo del *heap* luego de una recolección, permitiendo
2323 este esquema para asignar nuevas celdas, pero puede utilizarse en esquemas
2324 híbridos como recolectores basados en *regiones* (por ejemplo [BLAC08]_).
2325
2326 Además los recolectores con movimiento de celdas deben ser :ref:`precisos
2327 <gc_conserv>`, porque es necesario tener la información completa de los tipos
2328 para saber cuando actualizar los punteros (de otra manera se podría escribir
2329 un dato de una celda que no era un puntero). Para que un recolector pueda
2330 mover celdas, aunque sea parcialmente, en recolectores *semi-precisos* se
2331 utiliza un método conocido como *pinning* (que significa algo como *pinchar
2332 con un alfiler*); una celda es *pinned* (*pinchada*) cuando hay alguna
2333 referencia no-precisa a ella, y por lo tanto no puede ser movida (porque no se
2334 puede estar seguro si es posible actualizar dicha referencia).
2335
2336 La ventaja principal de los colectores con movimiento es la posibilidad de
2337 utilizar :ref:`pointer bump allocation <gc_free_list>` y que es sencillo
2338 implementar recolectores :ref:`generacionales <gc_part>` sobre estos.
2339
2340 De los algoritmos clásicos sólo la :ref:`copia de semi-espacios <gc_copy>`
2341 mueve celdas, el :ref:`conteo de referencias <gc_rc>` y :ref:`marcado
2342 y barrido <gc_mark_sweep>` no lo hacen. Además hay otro algoritmo bastante
2343 básico que mueve celdas, el **marcado y compactado**. Éste no tiene
2344 2 semi-espacios, directamente mueve las celdas compactándolas al comienzo del
2345 *heap*. El algoritmo es un poco más complejo que la :ref:`copia de
2346 semi-espacios <gc_copy>` pero suele poder proveer una mayor localidad de
2347 referencia y *desperdicia* un semi-espacio que está inutilizado salgo en el
2348 momento de la recolección. Por ejemplo para Mono_, que antes usaba un
2349 recolector conservativo sin movimiento ([BOEHWD]_) se está implementando un
2350 recolector de este tipo [MOLAWE]_ [MOLA06]_.
2351
2352
2353
2354 .. _gc_conserv:
2355
2356 Recolectores conservativos vs precisos
2357 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2358
2359 Los recolectores *conservativos* son aquellos que tienen la capacidad de poder
2360 lidiar con un *root set* o celdas que no tengan información de tipos asociada.
2361 Esto significa que el recolector no sabe donde hay punteros (o referencias) en
2362 una celda o raiz dada. Es decir, una ubicación particular puede ser un puntero
2363 o no. Esto trae una variada cantidad de problemas, como retención de celdas
2364 que en realidad son *basura* simplemente porque hay algún dato que coincide
2365 con la dirección de memoria en la que está almacenada esa celda *basura*
2366 [#gcflasepos]_. Además los recolectores puramente conservativos no puede mover
2367 celdas (ver :ref:`gc_moving`), porque no pueden arriesgarse a actualizar los
2368 punteros por el riesgo que existe de que sean falsos positivos.
2369
2370 .. [#gcflasepos] Esto es lo que se conoce como un *falso positivo*, algo que
2371    aparenta ser un puntero pero en realidad no lo es.
2372
2373 Sin embargo hay ciertas circunstancias que hacen que no quede más remedio que
2374 el recolector sea conservativo, por ejemplo cuando se utiliza un recolector de
2375 basura para un lenguaje que no ha sido pensado para tener uno (como C o C++).
2376
2377 Por el contrario, los recolectores que poseen a su disposición información
2378 completa sobre el tipo de la celda, y por ende información sobre cuales de sus
2379 campos son realmente punteros, son denominados *precisos*. Estos recolectores
2380 no están sujetos a estas limitaciones y por lo tanto son potencialmente más
2381 eficientes en cuanto a tiempo y espacio. Los lenguajes que fueron diseñados
2382 para tener un recolector de basura (y en especial aquellos que son de relativo
2383 alto nivel) en general disponen de recolectores precisos.
2384
2385 Hay casos donde se posee información de tipos para algunas celdas solamente,
2386 o más comunmente se posee información de tipos de celdas que se encuentran en
2387 el *heap* pero no para el *stack* y registros (por ejemplo [MOLA06]_). En
2388 estos casos se puede adoptar un esquema híbrido y tratar algunas referencias
2389 de forma conservativa y otras de forma precisa, de manera de mitigar, aunque
2390 sea de forma parcial, los efectos adversos de los recolectores conservativos.
2391 Estos recolectores son conocidos como *semi-precisos*. Los recolectores
2392 semi-precisos pueden mover celdas si utilizan un mecanismo de *pinning* (ver
2393 :ref:`gc_moving`).
2394
2395 El ejemplo de recolector conservativo por excelencia es el recolector
2396 `Boehm-Demers-Wiser`_ ([BOEH88]_, [BOEH91]_, [BOEH93]_, [BOEHWD]_) aunque
2397 puede comportarse de forma semi-precisa si el usuario se encarga de darle la
2398 información de tipos (en cuyo caso el recolector deja de ser transparente para
2399 el usuario). Otros ejemplos de recolectores con cierto grado de
2400 conservativismo son el :ref:`recolector actual de D <dgc_actual>` y [BLAC08]_.
2401
2402
2403
2404 .. _gc_part:
2405
2406 Recolección particionada
2407 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2408
2409 Otra forma de reducir la cantidad de pausas y la cantidad de trabajo realizado
2410 por el recolector en general es particionando el *heap* de manera tal de
2411 recolectar solo las partes donde más probabilidad de encontrar *basura* haya.
2412
2413 Entonces, si el recolector tiene algún mecanismo para identificar zonas de
2414 alta concentración de *basura* puede hacer la recolección solo en ese área
2415 donde el trabajo va a ser mejor recompensado (ver :vref:`fig:gc-part`).
2416
2417 .. fig:: fig:gc-part
2418
2419    Concentración de basura en distintas particiones del *heap*.
2420
2421    .. aafig::
2422       :aspect: 0.7
2423
2424        _______________________________________________________________________
2425       |                                                                       |
2426       |   +-----------------------------+   +-----------------------------+   |
2427       |  /             Baja              \ /             Alta              \  |
2428       | +                                 +                                 + |
2429       | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
2430       | GGGGGGGZZGGGGGZZGGGGGGGGZZGGGGGGGGZZZZZGGZZZZZZZZZZZZZZZZGGZZZZZZGGZZ |
2431       |                                                                       |
2432       |        GG Celdas vivas                                ZZ Basura       |
2433       |_______________________________________________________________________|
2434
2435
2436 Sin embargo encontrar zonas de alta concentración no es trivial. La forma más
2437 divulgada de encontrar estas zonas es particionando el *heap* en un área
2438 utilizada para almacenar celdas *jóvenes* y otra para celdas *viejas*. Una
2439 celda *vieja* es aquella que ha *sobrevivido* una cantidad N de recolecciones,
2440 mientras que el resto se consideran *jóvenes* (las celdas *nacen* jóvenes).
2441 Los recolectores que utilizan este tipo de partición son ampliamente conocido
2442 como recolectores **generacionales**. La *hipótesis generacional* dice que el
2443 área de celdas jóvenes tiene una mayor probabilidad de ser un área de alta
2444 concentración de basura [JOLI96]_. Basandose en esto, los recolectores
2445 generacionales primero intentan recuperar espacio del área de celdas jóvenes
2446 y luego, de ser necesario, del área de celdas viejas. Es posible tener varias
2447 generaciones e ir subiendo de generación a generación a medida que es
2448 necesario. Sin embargo en general no se obtienen buenos resultados una vez que
2449 se superan las 3 particiones. La complejidad que trae este método es que para
2450 recolectar la generación joven es necesario tomar las referencias de la
2451 generación vieja a la joven como parte del *root set* (de otra forma podrían
2452 tomarse celdas como *basura* que todavía son utilizadas por las celdas
2453 viejas). Revisar toda la generación vieja no es una opción porque sería
2454 prácticamente lo mismo que realizar una recolección del *heap* completo. La
2455 solución está entonces, una vez más, en instrumentar el *mutator* para que
2456 avise al recolector cuando cambia una referencia de la generación vieja a la
2457 joven (no es necesario monitorear las referencias en sentido inverso ya que
2458 cuando se recolecta la generación vieja se hace una recolección del *heap*
2459 completo).
2460
2461 Sin embargo, a pesar de ser este el esquema más difundido para particionar el
2462 *heap* y realizar una recolección parcial sobre un área de alta concentración
2463 de basura no es la única. Otros recolectores proponen hacer un análisis
2464 estático del código revisando la conectividad entre los objetos según sus
2465 tipos (esto es posible solo en lenguajes con tipado estático), de manera tal
2466 de separar en distintas áreas grupos de tipos que no pueden tener referencias
2467 entre sí [HIRZ03]_. Este análisis hace que sea inecesario instrumentar el
2468 *mutator* para reportar al recolector cambios de referencias
2469 inter-particiones, sencillamente porque queda demostrado que no existe dicho
2470 tipo de referencias. Esto quita una de las principale ineficiencias
2471 y complejidades del esquema generacional.
2472
2473
2474
2475 .. include:: links.rst
2476
2477 .. vim: set ts=3 sts=3 sw=3 et tw=78 :