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