X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/50ff008fcd00e0c8d6b4a3bea94bb44afcac251b..7024d6c53ac7bf2f10720fa6693c1d24329bdac1:/source/gc.rst?ds=sidebyside diff --git a/source/gc.rst b/source/gc.rst index 5d21433..96da51b 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -10,6 +10,8 @@ Recolección de basura ============================================================================ +.. _ref_gc_intro: + Introducción ---------------------------------------------------------------------------- @@ -183,6 +185,7 @@ normalmente se lo llama *mutator* (mutador). +.. _ref_gc_intro_mark: Recorrido del grafo de conectividad ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -328,14 +331,14 @@ 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 @@ -583,7 +586,7 @@ dejando sin marcar solamente las celdas *basura* (en blanco). -.. _ref_gc_tricolor: +.. _ref_gc_intro_tricolor: Abstracción tricolor ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -612,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() @@ -628,7 +631,7 @@ por sí ya presenta una ventaja sobre el marcado *bicolor*. -.. _ref_gc_services: +.. _ref_gc_intro_services: Servicios ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -713,7 +716,7 @@ usuario también. -.. _ref_gc_clasic: +.. _ref_gc_classic: Algoritmos clásicos ---------------------------------------------------------------------------- @@ -783,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 @@ -857,7 +892,7 @@ son todas parte del *live set*. 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" ]; @@ -870,6 +905,7 @@ son todas parte del *live set*. h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } @@ -904,7 +940,7 @@ son todas parte del *live set*. 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" ]; @@ -917,6 +953,7 @@ son todas parte del *live set*. h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } @@ -956,7 +993,7 @@ son todas parte del *live set*. 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" ]; @@ -969,6 +1006,7 @@ son todas parte del *live set*. h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } @@ -1014,7 +1052,7 @@ son todas parte del *live set*. 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" ]; @@ -1027,6 +1065,7 @@ son todas parte del *live set*. h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } @@ -1065,7 +1104,7 @@ son todas parte del *live set*. 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" ]; @@ -1078,6 +1117,7 @@ son todas parte del *live set*. h2:r -> h5; h3:l -> h2; h3:r -> h6; + h6:r -> h3:r; } @@ -1129,7 +1169,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\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" ]; @@ -1143,6 +1183,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h3:l -> h2; h3:l -> h5 [ style = dotted, color = black ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1181,7 +1222,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\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" ]; @@ -1195,6 +1236,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h3:l -> h2 [ style = bold, color = black ]; h3:l -> h5 [ style = dotted, color = black ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1234,7 +1276,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\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" ]; @@ -1248,6 +1290,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h3:l -> h2 [ style = invis ]; h3:l -> h5 [ style = dotted, color = black ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1293,7 +1336,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\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" ]; @@ -1307,6 +1350,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h3:l -> h2 [ style = invis ]; h3:l -> h5 [ style = dotted, color = black ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1345,7 +1389,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\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" ]; @@ -1359,6 +1403,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h3:l -> h5 [ style = bold, color = black ]; h3:l -> h2 [ style = invis ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1399,7 +1444,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el 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" ]; @@ -1413,6 +1458,7 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h3:l -> h5; h3:l -> h2 [ style = invis ]; h3:r -> h6; + h6:r -> h3:r; } @@ -1430,6 +1476,136 @@ 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 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~