X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/aa8eff50c89900e85fe1b37f48e84decca03e534..7024d6c53ac7bf2f10720fa6693c1d24329bdac1:/source/gc.rst diff --git a/source/gc.rst b/source/gc.rst index 661a578..96da51b 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -10,6 +10,8 @@ Recolección de basura ============================================================================ +.. _ref_gc_intro: + Introducción ---------------------------------------------------------------------------- @@ -17,6 +19,13 @@ Introducción del *heap* [#gcheap]_ una vez que el programa ha dejado de hacer referencia a ella (y por lo tanto, ha dejado de utilizarla). +.. [#gcheap] *Heap* es un área de memoria que se caracteriza por ser + dinámica (a diferencia del área de memoria estática que está disponible + durante toda la ejecución de un programa). Un programa puede reservar + memoria en tiempo de ejecución según sea necesario y liberarla cuando ya + no la necesita. A diferencia del *stack*, la duración de la *reserva* no + está atada a un bloque de código. + A medida que el tiempo pasa, cada vez los programas son más complejos y es más compleja la administración de memoria. Uno de los aspectos más importantes de un recolector de basura es lograr un mayor nivel de @@ -32,6 +41,21 @@ recolector de basura. Por ejemplo, los errores en el manejo de memoria (como *buffer overflows* [#gcbuff]_ o *dangling pointers* [#gcdang]_) son la causa más frecuente de problemas de seguridad [BEZO06]_. +.. [#gcbuff] Un *buffer overflow* (*desbordamiento de memoria* en + castellano) se produce cuando se copia un dato a un área de memoria que + no es lo suficientemente grande para contenerlo. Esto puede producir que + el programa sea abortado por una violación de segmento, o peor, + sobreescribir un área de memoria válida, en cuyo caso los resultados son + impredecibles. + +.. [#gcdang] Un *dangling pointer* (*puntero colgante* en castellano) es un + puntero que apunta a un área de memoria inválida. Ya sea porque el + elemento apuntado no es el mismo tipo o porque la memoria ya ha sido + liberada. Al ser desreferenciado, los resultados son impredecibles, el + programa podría abortarse por una violación de segmento o podrían pasar + peores cosas si el área de memoria fue realocada para almacenar otro + objeto. + La recolección de basura nació junto a Lisp_ a finales de 1950 y en los siguientes años estuvo asociada principalmente a lenguajes funcionales, pero en la actualidad está presente en prácticamente todos los lenguajes de @@ -64,26 +88,6 @@ puntos de falla no controlados por el programador, volviendo mucho más difícil la búsqueda de errores. -.. [#gcheap] *Heap* es un área de memoria que se caracteriza por ser - dinámica (a diferencia del área de memoria estática que está disponible - durante toda la ejecución de un programa). Un programa puede reservar - memoria en tiempo de ejecución según sea necesario y liberarla cuando ya - no la necesita. A diferencia del *stack*, la duración de la *reserva* no - está atada a un bloque de código. -.. [#gcbuff] Un *buffer overflow* (*desbordamiento de memoria* en - castellano) se produce cuando se copia un dato a un área de memoria que - no es lo suficientemente grande para contenerlo. Esto puede producir que - el programa sea abortado por una violación de segmento, o peor, - sobreescribir un área de memoria válida, en cuyo caso los resultados son - impredecibles. -.. [#gcdang] Un *dangling pointer* (*puntero colgante* en castellano) es un - puntero que apunta a un área de memoria inválida. Ya sea porque el - elemento apuntado no es el mismo tipo o porque la memoria ya ha sido - liberada. Al ser desreferenciado, los resultados son impredecibles, el - programa podría abortarse por una violación de segmento o podrían pasar - peores cosas si el área de memoria fue realocada para almacenar otro - objeto. - Conceptos básicos @@ -121,6 +125,13 @@ Registros: celda [#gccelda]_ alocada antes que otra nunca puede ser liberada antes que aquella. + .. [#gccelda] En general en la literatura se nombra a una porción de + memoria alocada individualmente *celda*, *nodo* u *objeto* + indistintamente. En este trabajo se utilizará la misma nomenclatura + (haciendo mención explícita cuando alguno de estos términos se + refiera a otra cosa, como al nodo de una lista o a un objeto en el + sentido de programación orientada a objetos). + *Heap*: A diferencia del *stack*, el *heap* provee un área de memoria que puede ser obtenida dinámicamente pero sin limitaciones de orden. Es el tipo de @@ -173,14 +184,8 @@ programa en sí son los cambios al grafo de conectividad de las celdas, normalmente se lo llama *mutator* (mutador). -.. [#gccelda] En general en la literatura se nombra a una porción de - memoria alocada individualmente *celda*, *nodo* u *objeto* - indistintamente. En este trabajo se utilizará la misma nomenclatura - (haciendo mención explícita cuando alguno de estos términos se refiera - a otra cosa, como al nodo de una lista o a un objeto en el sentido de - programación orientada a objetos). - +.. _ref_gc_intro_mark: Recorrido del grafo de conectividad ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -317,20 +322,33 @@ convenir uno u otro método para lograr una mejor localidad de referencia y de esta manera tener un mejor comportamiento de la memoria virtual o del *caché*. +.. [#gccycle] Un ciclo es un camino donde el *vértice inicial* es el mismo + que el *vértice final*. Por lo tanto, los *vértices terminales* son + completamente arbitrarios, ya que cualquier *vértice interior* puede ser + un *vértice terminal*. + Un algoritmo simple (recursivo) de marcado *primero a lo alto* puede ser el siguiente (asumiendo que partimos con todos los vértices sin marcar) [#gcpseudo]_:: - mark(v) + function mark(v) is if not v.marked v.marked = true for (src, dst) in v.edges mark(dst) - mark_phase() - for r in root_set + function mark_phase() is + foreach r in root_set mark(r) +.. [#gcpseudo] Para presentar los algoritmos se utiliza una forma simple de + pseudo-código. El pseudo-código se escribe en inglés para que pueda ser + más fácilmente contrastado con la literatura, que está en inglés. Para + diferenciar posiciones de memoria y punteros de las celdas en sí, se usa + la misma sintaxis que C, ``r*`` denota una referencia o puntero y ``*r`` + denota "objeto al que apunta ``r``\ ". Se sobreentiende que ``r = o`` + siempre toma la dirección de memoria de ``o``. + Una vez concluido el marcado, sabemos que todos los vértices con la marca son parte del *live set* y que todos los vértices no marcados son *basura*. Esto es conocido también como **abstracción bicolor**, dado que en la @@ -339,7 +357,7 @@ celda sin marcar es de color blanco y una marcada de color negro. Puede observarse un ejemplo del algoritmo en la figura :vref:`fig:gc-mark-1`, en la cual se marca el sub-grafo apuntando por -``r0``. Luego se marca el sub-grafo al que apunta ``r1`` (figura +``r0``. Luego se marca el sub-grafo al que apunta ``r1`` (ver figura :vref:`fig:gc-mark-2`), concluyendo con el marcado del grafo completo, dejando sin marcar solamente las celdas *basura* (en blanco). @@ -567,21 +585,8 @@ dejando sin marcar solamente las celdas *basura* (en blanco). } -.. [#gccycle] Un ciclo es un camino donde el *vértice inicial* es el mismo - que el *vértice final*. Por lo tanto, los *vértices terminales* son - completamente arbitrarios, ya que cualquier *vértice interior* puede ser - un *vértice terminal*. -.. [#gcpseudo] Para presentar los algoritmos se utiliza una forma simple de - pseudo-código. El pseudo-código se escribe en inglés para que pueda ser - más fácilmente contrastado con la literatura, que está en inglés. Para - diferenciar posiciones de memoria y punteros de las celdas en sí, se usa - la misma sintaxis que C, ``r*`` denota una referencia o puntero y ``*r`` - denota "objeto al que apunta ``r``\ ". Se sobreentiende que ``r = o`` - siempre toma la dirección de memoria de ``o``. - - -.. _ref_gc_tricolor: +.. _ref_gc_intro_tricolor: Abstracción tricolor ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -610,8 +615,8 @@ que todas las celdas parten pintadas de blanco, es decir, el conjunto blanco contiene todas las celdas de memoria y los conjuntos negro y gris están vacíos):: - mark_phase() - for r in root_set + function mark_phase() is + foreach r in root_set gray_set.add(r) while not gray_set.empty() v = gray_set.pop() @@ -626,7 +631,7 @@ por sí ya presenta una ventaja sobre el marcado *bicolor*. -.. _ref_gc_services: +.. _ref_gc_intro_services: Servicios ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -635,6 +640,18 @@ En general todos los algoritmos de recolección de basura utilizan servicios de una capa inferior [#gclowlayer]_ y proveen servicios a una capa superior [#gchilayer]_. +.. [#gclowlayer] En general estos servicios están provistos directamente + por el sistema operativo pero también pueden estar dados por un + administrador de memoria de bajo nivel (o *low level allocator* en + inglés). + +.. [#gchilayer] En general estos servicios son utilizados directamente por + el lenguaje de programación, pero pueden ser utilizados directamente por + el usuario del lenguaje si éste interatúa con el recolector, ya sea por + algún requerimiento particular o porque el lenguaje no tiene soporte + diercto de recolección de basura y el recolector está implementado como + una biblioteca de usuario. + A continuación se presentan las primitivas en común que utilizan todos los recolectores a lo largo de este documento. @@ -697,20 +714,9 @@ recolector, aunque en ciertas circunstancias pueden ser utilizados por el usuario también. -.. [#gclowlayer] En general estos servicios están provistos directamente - por el sistema operativo pero también pueden estar dados por un - administrador de memoria de bajo nivel (o *low level allocator* en - inglés). -.. [#gchilayer] En general estos servicios son utilizados directamente por - el lenguaje de programación, pero pueden ser utilizados directamente por - el usuario del lenguaje si éste interatúa con el recolector, ya sea por - algún requerimiento particular o porque el lenguaje no tiene soporte - diercto de recolección de basura y el recolector está implementado como - una biblioteca de usuario. - -.. _ref_gc_clasic: +.. _ref_gc_classic: Algoritmos clásicos ---------------------------------------------------------------------------- @@ -780,31 +786,63 @@ teóricamente la complejidad de eliminar una referencia puede ser Las primitivas implementadas para este tipo de recolector son las siguientes (acompañadas de una implementación básica):: - new() + function new() is cell = alloc() if cell is null throw out_of_memory cell.rc = 1 return cell - del(cell) + function del(cell) is cell.rc = cell.rc - 1 if cell.rc is 0 - for child* in cell.children + foreach child* in cell.children del(*child) free(cell) - update(ref*, cell) + function update(ref*, cell) is cell.rc = cell.rc + 1 del(*ref) *ref = cell + .. _ref_gc_rc_cycles: Ciclos ^^^^^^ +El conteo de referencias tiene, sin embargo, un problema fundamental: +**falla con estructuras cíclicas**. Esto significa que siempre que haya un +ciclo en el grafo de conectividad, hay una pérdida de memoria potencial en +el programa. Un ciclo es un camino :math:`\underset{v \to v}{C}`, es decir, +el *vértice inicial* es el mismo que el *vértice final*. + +Cuando esto sucede, las celdas que participan del ciclo tienen siempre su +contador mayor que 0, sin embargo puede no haber ningún elemento del *root +set* que apunte a una celda dentro del ciclo, por lo tanto el ciclo es +*basura* (al igual que cualquier otra celda que sea referenciada por el +ciclo pero que no tenga otras referencias externas) y sin embargo los +contadores no son 0. Los ciclos, por lo tanto, *rompen* la invariante del +conteo de referencia. + +Hay formas de solucionar esto, pero siempre recaen en un esquema que va por +fuera del conteo de referencias puro. En general los métodos para +solucionar esto son variados y van desde realizar un marcado del subgrafo +para detectar nodos hasta tener otro recolector completo de *emergencia*, +pasando por tratar los ciclos como un todo contar las referencias al ciclo +completo en vez de a cada celda en particular. + +Incluso con este problema, el conteo de referencia sin ningún tipo de +solución en cuanto a la detección y recolección de ciclos fue utilizado en +muchos lenguajes de programación sin que su necesidad sea tan evidente. Por +ejemplo Python_ agregó recolección de ciclos en la versión 2.0 [NAS00]_ +(liberada en octubre de 2000) y PHP_ recién agrega detección de ciclos en +la versión 5.3 (todavía no liberada al momento de escribir este documento) +[PHP081]_. + + + .. _ref_gc_rc_example: Ejemplo @@ -819,12 +857,6 @@ o cambiar una referencia (cambios en la conectividad del grafo). En un comienzo todas las celdas son accesibles desde el *root set* por lo tanto son todas parte del *live set*. -Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina -que ``h1`` se convirtió en *basura* (figura :vref:`fig:gc-rc-rm-1`). Esto -conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el -*live set* ya que sus contadores siguen siendo mayores a 0 (figura -:vref:`fig:gc-rc-rm-2`). - .. fig:: fig:gc-rc-rm-1 @@ -860,7 +892,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h1 [ label = "h1\n1| l| r" ]; h2 [ label = "h2\n2| l| r" ]; - h3 [ label = "h3\n2| l| r" ]; + h3 [ label = "h3\n3| l| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n1| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -873,6 +905,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } @@ -907,7 +940,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h1 [ label = "h1\n1| l| r" ]; h2 [ label = "h2\n2| l| r" ]; - h3 [ label = "h3\n2| l| r" ]; + h3 [ label = "h3\n3| l| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n1| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -920,6 +953,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } @@ -959,7 +993,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n2| l| r" ]; - h3 [ label = "h3\n2| l| r" ]; + h3 [ label = "h3\n3| l| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n1| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -972,11 +1006,13 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } .. fig:: fig:gc-rc-rm-2 + :padding: 0.5 Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2). @@ -1016,7 +1052,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n1| l| r" ]; - h3 [ label = "h3\n2| l| r" ]; + h3 [ label = "h3\n3| l| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n1| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -1029,6 +1065,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } @@ -1067,7 +1104,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n1| l| r" ]; - h3 [ label = "h3\n1| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n1| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -1080,20 +1117,16 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } -Luego se cambia una referencia (en vez de eliminarse) realizándose la -operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador -de referencias de ``h5`` para evitar confundirlo accidentalmente con -*basura* si se elimina alguna celda que apuntaba a ésta. Luego se procede -a decrementar el contador de ``h2`` que queda en 0, transformándose en -*basura* (figura :vref:`fig:gc-rc-up-1`). Lo mismo pasa cuando se desciende -a ``h4``, pero al descender a ``h5`` y decrementar el contador, éste sigue -siendo mayor que 0 (pues ``h3`` va a apuntar a ``h5``) así que permanece en -el *live set*. Finalmente se termina de actualizar la referencia ``h3.l`` -para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). +Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina +que ``h1`` se convirtió en *basura* (ver figura :vref:`fig:gc-rc-rm-1`). Esto +conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el +*live set* ya que sus contadores siguen siendo mayores a 0 (ver figura +:vref:`fig:gc-rc-rm-2`). .. fig:: fig:gc-rc-up-1 @@ -1136,7 +1169,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n1| l| r" ]; - h3 [ label = "h3\n1| l\n*| r" ]; + h3 [ label = "h3\n2| l\n*| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n2| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -1150,6 +1183,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h3:l -> h2; h3:l -> h5 [ style = dotted, color = black ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1188,7 +1222,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n1| l| r" ]; - h3 [ label = "h3\n1| l\n*| r" ]; + h3 [ label = "h3\n2| l\n*| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n2| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -1202,6 +1236,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h3:l -> h2 [ style = bold, color = black ]; h3:l -> h5 [ style = dotted, color = black ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1241,7 +1276,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n1| l| r" ]; - h3 [ label = "h3\n1| l\n*| r" ]; + h3 [ label = "h3\n2| l\n*| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n2| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -1255,6 +1290,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h3:l -> h2 [ style = invis ]; h3:l -> h5 [ style = dotted, color = black ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1300,7 +1336,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n1| l| r" ]; - h3 [ label = "h3\n1| l\n*| r" ]; + h3 [ label = "h3\n2| l\n*| r" ]; h4 [ label = "h4\n0| l| r" ]; h5 [ label = "h5\n2| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -1314,6 +1350,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h3:l -> h2 [ style = invis ]; h3:l -> h5 [ style = dotted, color = black ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1352,7 +1389,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n1| l| r" ]; - h3 [ label = "h3\n1| l\n*| r" ]; + h3 [ label = "h3\n2| l\n*| r" ]; h4 [ label = "h4\n0| l| r" ]; h5 [ label = "h5\n1| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -1366,6 +1403,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h3:l -> h5 [ style = bold, color = black ]; h3:l -> h2 [ style = invis ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1406,7 +1444,7 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h1 [ label = "h1\n0| l| r" ]; h1 [ label = "h1\n0| l| r" ]; h2 [ label = "h2\n0| l| r" ]; - h3 [ label = "h3\n1| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; h4 [ label = "h4\n0| l| r" ]; h5 [ label = "h5\n1| l| r" ]; h6 [ label = "h6\n1| l| r" ]; @@ -1420,9 +1458,153 @@ para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`). h3:l -> h5; h3:l -> h2 [ style = invis ]; h3:r -> h6; + h6:r -> h3:r; + + } + + +Luego se cambia una referencia (en vez de eliminarse) realizándose la +operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador +de referencias de ``h5`` para evitar confundirlo accidentalmente con +*basura* si se elimina alguna celda que apuntaba a ésta. Luego se procede +a decrementar el contador de ``h2`` que queda en 0, transformándose en +*basura* (ver figura :vref:`fig:gc-rc-up-1`). Lo mismo pasa cuando se +desciende a ``h4``, pero al descender a ``h5`` y decrementar el contador, +éste sigue siendo mayor que 0 (pues ``h3`` va a apuntar a ``h5``) así que +permanece en el *live set*. Finalmente se termina de actualizar la +referencia ``h3.l`` para que apunte a ``h5`` (ver figura +:vref:`fig:gc-rc-up-2`). + + +.. fig:: fig:gc-rc-cycle + :padding: 0.5 + + Eliminación de la referencia ``r1`` :math:`\to` ``h3`` (pérdida de + memoria debido a un ciclo). + + .. subfig:: + + El ejecutarse ``update(r1, null)`` se visita la celda ``h3``. + + .. digraph:: g4_6 + + margin = 0; + ratio = fill; + size = "1.9,2.6"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1\n*", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; h4; + }; + + h1 [ label = "h1\n0| l| r" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n0| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n0| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; + + root:r0 -> h1 [ style = invis ]; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + root:r1 -> h3 [ style = bold, color = black ]; + h2:l -> h4 [ style = invis ]; + h2:r -> h5 [ style = invis ]; + h3:l -> h5; + h3:l -> h2 [ style = invis ]; + h3:r -> h6; + h6:r -> h3:r; } + .. subfig:: + + Se decrementa el contador de ``h3`` pero sigue siendo mayor que 0 por + el ciclo. + + .. digraph:: g5_2 + + margin = 0; + ratio = fill; + size = "1.9,2.6"; + edge [ color = gray40 ]; + node [ + shape = record, + width = 0, + height = 0, + style = filled, + fillcolor = gray25, + fontcolor = white + ]; + + subgraph cluster_all { + + root [ + label = "root\nset| r0| r1\n*", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + subgraph marked { + node [ fillcolor = white, fontcolor = black ]; + h1; h2; h4; + }; + + h1 [ label = "h1\n0| l| r" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n0| l| r" ]; + h3 [ label = "h3\n1| l| r" ]; + h4 [ label = "h4\n0| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; + + root:r0 -> h1 [ style = invis ]; + h1:l -> h2 [ style = invis ]; + h1:r -> h3 [ style = invis ]; + root:r1 -> h3 [ style = invis ]; + h2:l -> h4 [ style = invis ]; + h2:r -> h5 [ style = invis ]; + h3:l -> h5; + h3:l -> h2 [ style = invis ]; + h3:r -> h6; + h6:r -> h3:r; + + } + + +Finalmente se presenta lo que sucede cuando se elimina la última referencia +a un ciclo (en este caso un ciclo simple de 2 celdas: ``h3`` y ``h6``). Se +elimina la única referencia externa al ciclo (``r1``), por lo que se visita +la celda ``h3`` decrementando su contador de referencias, pero éste +continúa siendo mayor que 0 porque la celda ``h6`` (parte del ciclo) la +referencia. Por lo tanto el ciclo, y todas las celdas a las que apunta que +no tienen otras referencias externas y por lo tanto deberían ser *basura* +también (``h5``), no pueden ser recicladas y su memoria es perdida (ver +figura :vref:`fig:gc-rc-cycle`). + + + +.. _ref_gc_mark_sweep: Marcado y barrido ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -1438,13 +1620,18 @@ TODO +.. _ref_gc_art: -TODO +Estado del arte +---------------------------------------------------------------------------- +.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos + ejemplos. +TODO Clasificación ----------------------------------------------------------------------------- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ La cantidad de clasificaciones que pueden hacerse respecto a algoritmos de recolección de basura son muy grandes. Muchas de estas clasificaciones se @@ -1458,7 +1645,7 @@ pudieron observar en la investigación sobre el `estado del arte`_. .. _ref_gc_direct: Directa / indirecta -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +^^^^^^^^^^^^^^^^^^^ Generalmente se llama recolección **directa** a aquella en la cual el compilador o lenguaje instrumenta al *mutator* de forma tal que la @@ -1488,7 +1675,7 @@ Estas son las dos grandes familias de recolectores, también conocidos como .. _ref_gc_inc: Incremental -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +^^^^^^^^^^^ Recolección incremental es aquella que se realiza de forma intercalada con el *mutator*. En general el propósito es disminuir el tiempo de las pausas @@ -1516,7 +1703,7 @@ incremental, aunque el tiempo de pausa de una recolección sea menor. .. _ref_gc_concurrent: Concurrente / *stop-the-world* -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Los recolectores concurrentes son aquellos que pueden correr en paralelo con el *mutator*. Por el contrario, aquellos que pausan el *mutator* para @@ -1534,15 +1721,6 @@ Esto también trae como consecuencia el incremento en el tiempo total que consume el recolector, debido a la necesidad de re-escanear sub-grafos que han sido modificados. -.. _ref_gc_art: - -Estado del arte ----------------------------------------------------------------------------- - -.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos - ejemplos. - -TODO Cloning @@ -1600,4 +1778,4 @@ http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html .. include:: links.rst -.. vim: set ts=3 sts=3 sw=3 et tw=75 : +.. vim: set ts=3 sts=3 sw=3 et tw=78 :