un breve recorrido sobre el estado del arte.
ESTADO: SIN EMPEZAR
-
.. _ref_gc:
Recolección de basura
Basura = V - Live \thickspace set
-Esto es, efectivamente, una partición del *heap*.
-
-.. TODO: figure
+Esto es, efectivamente, una partición del *heap* (ver figura
+:vref:`fig:gc-heap-parts`).
-.. raw:: latex
- \begin{figure}[htp] \centering
+.. fig:: fig:gc-heap-parts
-.. digraph:: g1
+ Distintas partes de la memoria, incluyendo relación entre *basura*,
+ *live set*, *heap* y *root set*.
- margin = 0;
- ratio = fill;
- size = "4.6,3.6";
- node [ shape = record, width = 0, height = 0 ];
+ .. digraph:: g1
- subgraph cluster_heap {
- label = "Heap";
- style = dashed;
- color = gray40;
- fontcolor = gray40;
+ margin = 0;
+ ratio = fill;
+ size = "4.6,3.6";
+ node [ shape = record, width = 0, height = 0 ];
- subgraph cluster_live {
- label = "Live set";
+ subgraph cluster_heap {
+ label = "Heap";
style = dashed;
color = gray40;
fontcolor = gray40;
- node [
- style = filled,
- fillcolor = gray25,
- fontcolor = white,
- ];
- h1; h2; h4; h5; h6;
+
+ subgraph cluster_live {
+ label = "Live set";
+ style = dashed;
+ color = gray40;
+ fontcolor = gray40;
+ node [
+ style = filled,
+ fillcolor = gray25,
+ fontcolor = white,
+ ];
+ h1; h2; h4; h5; h6;
+ }
+
+ subgraph cluster_garbage {
+ label = "Basura";
+ style = dashed;
+ color = gray40;
+ fontcolor = gray40;
+ node [ style = filled, fillcolor = white ];
+ h7; h3;
+ }
}
- subgraph cluster_garbage {
- label = "Basura";
+ subgraph cluster_root {
+ label = "Root set";
style = dashed;
color = gray40;
fontcolor = gray40;
- node [ style = filled, fillcolor = white ];
- h7; h3;
+ node [ style = filled, fillcolor = gray96 ];
+ r0; r1; r2;
}
- }
-
- subgraph cluster_root {
- label = "Root set";
- style = dashed;
- color = gray40;
- fontcolor = gray40;
- node [ style = filled, fillcolor = gray96 ];
- r0; r1; r2;
- }
-
- r0 -> h1 -> h2 -> h5;
- r1 -> h5 -> h6 -> h1;
- r2 -> h4;
- h5 -> h4;
- h7 -> h1;
- h7 -> h3;
-
-.. raw:: latex
-
- \caption{Distintas partes de la memoria, incluyendo relación entre
- basura, live set, heap y root set.}
- \end{figure}
+
+ r0 -> h1 -> h2 -> h5;
+ r1 -> h5 -> h6 -> h1;
+ r2 -> h4;
+ h5 -> h4;
+ h7 -> h1;
+ h7 -> h3;
+
Al proceso de visitar los vértices *conectados* desde el *root set* se lo
denomina *marcado*, *fase de marcado* o *mark phase* en inglés, debido
literatura se habla muchas veces de *colorear* las celdas. En general, una
celda sin marcar es de color blanco y una marcada de color negro.
-.. TODO: figure
+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
+:vref:`fig:gc-mark-2`), concluyendo con el marcado del grafo completo,
+dejando sin marcar solamente las celdas *basura* (en blanco).
-.. raw:: latex
- \begin{figure}[htp]
- \centering
- \subfigure[TODO texto más largo y más largo y larguísimo porque tiene
- muchas cosas que decir]{
+.. fig:: fig:gc-mark-1
-.. digraph:: g2_1
+ Ejemplo de marcado del grafo de conectividad (parte 1).
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0];
- edge [ color = gray40 ];
+ .. subfig::
- subgraph cluster_all {
+ Se comienza a marcar el grafo por la raíz r0.
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- ];
+ .. digraph:: g2_1
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1;
- };
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0];
+ edge [ color = gray40 ];
- root:r0 -> h1 [ style = bold, color = black ];
- h1 -> h2 -> h5 -> h1;
- root:r1 -> h6 -> h2;
- h4 -> h3;
- h3 -> h5;
+ subgraph cluster_all {
- }
+ root [
+ label = "root\nset|<r0> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ ];
-.. raw:: latex
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1;
+ };
- }
- \subfigure[TODO]{
+ root:r0 -> h1 [ style = bold, color = black ];
+ h1 -> h2 -> h5 -> h1;
+ root:r1 -> h6 -> h2;
+ h4 -> h3;
+ h3 -> h5;
-.. digraph:: g2_2
+ }
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ .. subfig::
- subgraph cluster_all {
+ Luego de marcar el nodo ``h1``, se procede al ``h2``.
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- ];
+ .. digraph:: g2_2
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2;
- };
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
- root:r0 -> h1 [ color = gray10 ];
- h1 -> h2 [ style = bold, color = black ];
- h2 -> h5 -> h1;
- root:r1 -> h6 -> h2;
- h4 -> h3;
- h3 -> h5;
+ subgraph cluster_all {
- }
+ root [
+ label = "root\nset|<r0> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ ];
-.. raw:: latex
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2;
+ };
- }
- \subfigure[TODO]{
+ root:r0 -> h1 [ color = gray10 ];
+ h1 -> h2 [ style = bold, color = black ];
+ h2 -> h5 -> h1;
+ root:r1 -> h6 -> h2;
+ h4 -> h3;
+ h3 -> h5;
-.. digraph:: g2_3
+ }
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ .. subfig::
- subgraph cluster_all {
+ Luego sigue el nodo h5.
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- ];
+ .. digraph:: g2_3
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2; h5;
- };
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
- root:r0 -> h1 [ color = gray10 ];
- h1 -> h2 [ color = gray10 ];
- h2 -> h5 [ style = bold, color = black ];
- h5 -> h1;
- root:r1 -> h6 -> h2;
- h4 -> h3;
- h3 -> h5;
+ subgraph cluster_all {
- }
+ root [
+ label = "root\nset|<r0> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ ];
-.. raw:: latex
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2; h5;
+ };
- }
- \caption{TODO, part 1}
- \end{figure}
+ root:r0 -> h1 [ color = gray10 ];
+ h1 -> h2 [ color = gray10 ];
+ h2 -> h5 [ style = bold, color = black ];
+ h5 -> h1;
+ root:r1 -> h6 -> h2;
+ h4 -> h3;
+ h3 -> h5;
- \begin{figure}[htp]
- \centering
- \subfigure[TODO]{
-
-.. digraph:: g2_4
-
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ }
- subgraph cluster_all {
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- ];
+.. fig:: fig:gc-mark-2
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2; h5;
- };
+ Ejemplo de marcado del grafo de conectividad (parte 2).
- root:r0 -> h1 [ color = gray10 ];
- h1 -> h2 [ color = gray10 ];
- h2 -> h5 [ color = gray10 ];
- h5 -> h1 [ style = bold, color = black ];
- root:r1 -> h6 -> h2;
- h4 -> h3;
- h3 -> h5;
+ .. subfig::
- }
+ El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo
+ tanto no se visita nuevamente.
-.. raw:: latex
+ .. digraph:: g2_4
- }
- \subfigure[TODO]{
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
-.. digraph:: g2_5
+ subgraph cluster_all {
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ root [
+ label = "root\nset|<r0> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ ];
- subgraph cluster_all {
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2; h5;
+ };
- root [
- label = "root\nset|<r0> r0|<r1> r1\n*",
- style = filled,
- fillcolor = gray96,
- ];
+ root:r0 -> h1 [ color = gray10 ];
+ h1 -> h2 [ color = gray10 ];
+ h2 -> h5 [ color = gray10 ];
+ h5 -> h1 [ style = bold, color = black ];
+ root:r1 -> h6 -> h2;
+ h4 -> h3;
+ h3 -> h5;
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2; h5; h6;
- };
+ }
- root:r0 -> h1 [ color = gray10 ];
- h1 -> h2 [ color = gray10 ];
- h2 -> h5 [ color = gray10 ];
- h5 -> h1 [ color = gray10 ];
- root:r1 -> h6 [ style = bold, color = black ];
- h6 -> h2;
- h4 -> h3;
- h3 -> h5;
+ .. subfig::
- }
+ Se concluye el marcado del sub-grafo al que conecta r0, se procede
+ a marcar el sub-grafo al que conecta r1, marcando al nodo h6.
-.. raw:: latex
+ .. digraph:: g2_5
- }
- \subfigure[TODO]{
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
-.. digraph:: g2_6
+ subgraph cluster_all {
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ root [
+ label = "root\nset|<r0> r0|<r1> r1\n*",
+ style = filled,
+ fillcolor = gray96,
+ ];
- subgraph cluster_all {
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2; h5; h6;
+ };
- root [
- label = "root\nset|<r0> r0|<r1> r1\n*",
- style = filled,
- fillcolor = gray96,
- ];
+ root:r0 -> h1 [ color = gray10 ];
+ h1 -> h2 [ color = gray10 ];
+ h2 -> h5 [ color = gray10 ];
+ h5 -> h1 [ color = gray10 ];
+ root:r1 -> h6 [ style = bold, color = black ];
+ h6 -> h2;
+ h4 -> h3;
+ h3 -> h5;
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2; h5; h6;
- };
+ }
- root:r0 -> h1 [ color = gray10 ];
- h1 -> h2 [ color = gray10 ];
- h2 -> h5 [ color = gray10 ];
- h5 -> h1 [ color = gray10 ];
- root:r1 -> h6 [ color = gray10 ];
- h6 -> h2 [ style = bold, color = black ];
- h4 -> h3;
- h3 -> h5;
+ .. subfig::
- }
+ El nodo h6 tiene una arista al h2, pero éste ya fue marcado por lo
+ que no se vuelve a visitar. No hay más raíces, se finaliza el marcado
+ del grafo.
-.. raw:: latex
+ .. digraph:: g2_6
- }
- \caption{TODO, parte 2}
- \end{figure}
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
+
+ subgraph cluster_all {
+
+ root [
+ label = "root\nset|<r0> r0|<r1> r1\n*",
+ style = filled,
+ fillcolor = gray96,
+ ];
+
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2; h5; h6;
+ };
+
+ root:r0 -> h1 [ color = gray10 ];
+ h1 -> h2 [ color = gray10 ];
+ h2 -> h5 [ color = gray10 ];
+ h5 -> h1 [ color = gray10 ];
+ root:r1 -> h6 [ color = gray10 ];
+ h6 -> h2 [ style = bold, color = black ];
+ h4 -> h3;
+ h3 -> h5;
+
+ }
.. [#gccycle] Un ciclo es un camino donde el *vértice inicial* es el mismo
El método consiste en tener un contador asociado a cada celda que contenga
la cantidad de celdas **vivas** que apuntan a ésta. Es decir, es la
cardinalidad del conjunto de aristas que tienen por destino a la celda.
-Formalmente podemos definir el contador math:`rc(v)` (de *reference
+Formalmente podemos definir el contador :math:`rc(v)` (de *reference
counter* en inglés) de la siguiente manera:
.. math::
^^^^^^^
A continuación se presenta un ejemplo gráfico para facilitar la comprensión
-del algoritmo.
-
-Por simplicidad se asumen celdas de tamaño fijo con dos punteros, ``left``
-y ``right`` (estructura clásica para representar un árbol binario) y se
-muestra el contador de referencias abajo del nombre de cada celda. Se parte
-con una pequeña estructura ya construída y se muestra primero lo que ocurre
-al eliminar la referencia :math:`r0 \to h1`:
-
-.. TODO: figure
-
-.. raw:: latex
-
- \begin{figure}[htp]
- \centering
- \subfigure[TODO]{
-
-.. digraph:: g3_1
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- h1 [ label = "h1\n1|<l> left|<r> right" ];
- h2 [ label = "h2\n2|<l> left|<r> right" ];
- h3 [ label = "h3\n2|<l> left|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r0 -> h1 [ style = bold, color = black ];
- root:r1 -> h3;
- h1:l -> h2;
- h1:r -> h3;
- h2:l -> h4;
- h2:r -> h5;
- h3:l -> h2;
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \subfigure[TODO]{
-
-.. digraph:: g3_2
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- h1;
- };
-
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n2|<l> left|<r> right" ];
- h3 [ label = "h3\n2|<l> left|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r0 -> h1 [ style = invis ];
- root:r1 -> h3;
- h1:l -> h2 [ style = bold, color = black ];
- h1:r -> h3;
- h2:l -> h4;
- h2:r -> h5;
- h3:l -> h2;
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \caption{TODO, part 1}
- \end{figure}
-
- \begin{figure}[htp]
- \centering
- \subfigure[TODO]{
-
-.. digraph:: g3_3
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- h1;
- };
-
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n1|<l> left|<r> right" ];
- h3 [ label = "h3\n2|<l> left|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r0 -> h1 [ style = invis ];
- root:r1 -> h3;
- h1:l -> h2 [ style = invis ];
- h1:r -> h3 [ style = bold, color = black ];
- h2:l -> h4;
- h2:r -> h5;
- h3:l -> h2;
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \subfigure[TODO]{
-
-.. digraph:: g3_4
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- h1;
- };
-
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n1|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r0 -> h1 [ style = invis ];
- root:r1 -> h3;
- h1:l -> h2 [ style = invis ];
- h1:r -> h3 [ style = invis ];
- h2:l -> h4;
- h2:r -> h5;
- h3:l -> h2;
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \caption{TODO, parte 2}
- \end{figure}
-
-Como se observa, la celda ``h1`` queda con el contador en 0, por lo tanto
-pasa a ser *basura*. Los contadores de las celdas a las que apuntaban
-``h1.left`` y ``h1.right`` son decrementados, pero no se detecta más basura
-porque sigue existiendo un camino del *root set* a aquellas celdas, y por
-transitividad a todas aquellas celdas apuntadas por éstas. Es por esto que
-no es necesario seguir recorriendo el grafo de conectividad.
-
-A continuación se muestra como opera el algoritmo al cambiar a donde apunta
-``h3.left``, haciéndola apuntar a ``h5``. Es decir, que pasa luego de la
-operación ``update(h3.left, h5)`` (por simplicidad no se muestra más la
-celda ``h1`` que ahora es *basura*):
-
-.. TODO: figure
-
-.. raw:: latex
-
- \begin{figure}[htp]
- \centering
- \subfigure[TODO]{
-
-.. digraph:: g4_1
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- };
-
- h2 [ label = "h2\n1|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r1 -> h3;
- h2:l -> h4;
- h2:r -> h5;
- h3:l -> h2 [ style = bold, color = black ];
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \subfigure[TODO]{
-
-.. digraph:: g4_2
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- };
-
- h2 [ label = "h2\n1|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n2|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r1 -> h3;
- h2:l -> h4;
- h2:r -> h5;
- h3:l -> h2 [ style = bold, color = black ];
- h3:l -> h5 [ style = dotted, color = black ];
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \caption{TODO, part 1}
- \end{figure}
-
- \begin{figure}[htp]
- \centering
- \subfigure[TODO]{
-
-.. digraph:: g4_3
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- h2;
- };
-
- h2 [ label = "h2\n0|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n2|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r1 -> h3;
- h2:l -> h4 [ style = bold, color = black ];
- h2:r -> h5;
- h3:l -> h2 [ style = invis ];
- h3:l -> h5 [ style = dotted, color = black ];
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \subfigure[TODO]{
-
-.. digraph:: g4_4
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- h2; h4;
- };
-
- h2 [ label = "h2\n0|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n0|<l> left|<r> right" ];
- h5 [ label = "h5\n2|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r1 -> h3;
- h2:l -> h4 [ style = invis ];
- h2:r -> h5 [ style = bold, color = black ];
- h3:l -> h2 [ style = invis ];
- h3:l -> h5 [ style = dotted, color = black ];
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \caption{TODO, part 2}
- \end{figure}
-
- \begin{figure}[htp]
- \centering
- \subfigure[TODO]{
-
-.. digraph:: g4_5
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- h2; h4;
- };
-
- h2 [ label = "h2\n0|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n0|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r1 -> h3;
- h2:l -> h4 [ style = invis ];
- h2:r -> h5 [ style = invis ];
- h3:l -> h5 [ style = bold, color = black ];
- h3:l -> h2 [ style = invis ];
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \subfigure[TODO]{
-
-.. digraph:: g4_6
-
- margin = 0;
- ratio = fill;
- size = "3.0,3.8";
- edge [ color = gray40 ];
- node [
- shape = record,
- width = 0,
- height = 0,
- style = filled,
- fillcolor = gray25,
- fontcolor = white
- ];
-
- subgraph cluster_all {
-
- root [
- label = "root\nset|<r0> r0|<r1> r1",
- style = filled,
- fillcolor = gray96,
- fontcolor = black,
- ];
-
- subgraph marked {
- node [ fillcolor = white, fontcolor = black ];
- h2; h4;
- };
-
- h2 [ label = "h2\n0|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left|<r> right" ];
- h4 [ label = "h4\n0|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
-
- root:r1 -> h3;
- h2:l -> h4 [ style = invis ];
- h2:r -> h5 [ style = invis ];
- h3:l -> h5;
- h3:l -> h2 [ style = invis ];
- h3:r -> h6;
-
- }
-
-.. raw:: latex
-
- }
- \caption{TODO, parte 3}
- \end{figure}
+del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos
+punteros, ``left`` (``l``) y ``right`` (``r``) y se muestra el contador de
+referencias abajo del nombre de cada celda. Se parte con una pequeña
+estructura ya construída y se muestra como opera el algoritmo al eliminar
+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
+
+ Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
+
+ .. subfig::
+
+ Estado inicial del grafo de conectividad.
+
+ .. digraph:: g3_1
+
+ 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> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ h1 [ label = "h1\n1|<l> l|<r> r" ];
+ h2 [ label = "h2\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1;
+ root:r1 -> h3;
+ h1:l -> h2;
+ h1:r -> h3;
+ h2:l -> h4;
+ h2:r -> h5;
+ h3:l -> h2;
+ h3:r -> h6;
+
+ }
+
+ .. subfig::
+
+ Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
+ ``h1``.
+
+ .. digraph:: g3_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> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ h1 [ label = "h1\n1|<l> l|<r> r" ];
+ h2 [ label = "h2\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = bold, color = black ];
+ root:r1 -> h3;
+ h1:l -> h2;
+ h1:r -> h3;
+ h2:l -> h4;
+ h2:r -> h5;
+ h3:l -> h2;
+ h3:r -> h6;
+
+ }
+
+ .. subfig::
+
+ Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser
+ *basura*). Se elimina primero ``h1.l`` y luego ``h1.r``.
+
+ .. digraph:: g3_3
+
+ 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> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ root:r1 -> h3;
+ h1:l -> h2 [ style = bold, color = black ];
+ h1:r -> h3;
+ h2:l -> h4;
+ h2:r -> h5;
+ h3:l -> h2;
+ h3:r -> h6;
+
+ }
+
+
+.. fig:: fig:gc-rc-rm-2
+
+ Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
+
+ .. subfig::
+
+ Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en
+ el *live set*).
+
+ .. digraph:: g3_4
+
+ 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> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ root:r1 -> h3;
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = bold, color = black ];
+ h2:l -> h4;
+ h2:r -> h5;
+ h3:l -> h2;
+ h3:r -> h6;
+
+ }
+
+ .. subfig::
+
+ El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.
+
+ .. digraph:: g3_5
+
+ 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> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ root:r1 -> h3;
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ h2:l -> h4;
+ h2:r -> h5;
+ h3:l -> h2;
+ h3:r -> h6;
+
+ }
+
+
+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`).
+
+
+.. fig:: fig:gc-rc-up-1
+
+ Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
+ :math:`\to` ``h5`` (parte 1).
+
+ .. subfig::
+
+ Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.
+
+ .. digraph:: g4_1
+
+ 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> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n2|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ root:r1 -> h3;
+ h2:l -> h4;
+ h2:r -> h5;
+ h3:l -> h2;
+ h3:l -> h5 [ style = dotted, color = black ];
+ h3:r -> h6;
+
+ }
+
+ .. subfig::
+
+ Luego se procede a visitar las hijas de ``h3``, comenzando por ``h2``.
+
+ .. digraph:: g4_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> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n2|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ root:r1 -> h3;
+ h2:l -> h4;
+ h2:r -> h5;
+ h3:l -> h2 [ style = bold, color = black ];
+ h3:l -> h5 [ style = dotted, color = black ];
+ h3:r -> h6;
+
+ }
+
+ .. subfig::
+
+ Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser
+ *basura*). Se eliminan las referencias a las hijas.
+
+ .. digraph:: g4_3
+
+ 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> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1; h2;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n2|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ root:r1 -> h3;
+ h2:l -> h4 [ style = bold, color = black ];
+ h2:r -> h5;
+ h3:l -> h2 [ style = invis ];
+ h3:l -> h5 [ style = dotted, color = black ];
+ h3:r -> h6;
+
+ }
+
+
+.. fig:: fig:gc-rc-up-2
+
+ Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
+ :math:`\to` ``h5`` (parte 2).
+
+ .. subfig::
+
+ Se decrementa el contador de ``h4`` quedando en 0, pasa a ser
+ *basura*. Se continúa con ``h5``.
+
+ .. digraph:: g4_4
+
+ 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> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1; h2; h4;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n0|<l> l|<r> r" ];
+ h5 [ label = "h5\n2|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ root:r1 -> h3;
+ h2:l -> h4 [ style = invis ];
+ h2:r -> h5 [ style = bold, color = black ];
+ h3:l -> h2 [ style = invis ];
+ h3:l -> h5 [ style = dotted, color = black ];
+ h3:r -> h6;
+
+ }
+
+ .. subfig::
+
+ Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.
+
+ .. digraph:: g4_5
+
+ 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> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1; h2; h4;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n0|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ root:r1 -> h3;
+ h2:l -> h4 [ style = invis ];
+ h2:r -> h5 [ style = invis ];
+ h3:l -> h5 [ style = bold, color = black ];
+ h3:l -> h2 [ style = invis ];
+ h3:r -> h6;
+
+ }
+
+ .. subfig::
+
+ Se termina por actualizar la referencia de ``h3.l`` para que apunte
+ a ``h5``.
+
+ .. 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> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ subgraph marked {
+ node [ fillcolor = white, fontcolor = black ];
+ h1; h2; h4;
+ };
+
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n0|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l|<r> r" ];
+ h4 [ label = "h4\n0|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1 [ style = invis ];
+ h1:l -> h2 [ style = invis ];
+ h1:r -> h3 [ style = invis ];
+ root:r1 -> h3;
+ h2:l -> h4 [ style = invis ];
+ h2:r -> h5 [ style = invis ];
+ h3:l -> h5;
+ h3:l -> h2 [ style = invis ];
+ h3:r -> h6;
+
+ }
+
.. _ref_gc_cycles:
projects / z.facultad / 75.00 / informe.git / blobdiff