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