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