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).
+
+
+.. fig:: fig:gc-mark-1
+
+ Ejemplo de marcado del grafo de conectividad (parte 1).
-.. raw:: latex
+ .. subfig::
- \begin{figure}[htp]
- \centering
- \subfigure[TODO texto más largo y más largo y larguísimo porque tiene
- muchas cosas que decir]{
+ Se comienza a marcar el grafo por la raíz r0.
-.. digraph:: g2_1
+ .. digraph:: g2_1
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0];
- edge [ color = gray40 ];
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0];
+ edge [ color = gray40 ];
- subgraph cluster_all {
+ subgraph cluster_all {
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- ];
+ root [
+ label = "root\nset|<r0> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ ];
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1;
- };
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1;
+ };
- root:r0 -> h1 [ style = bold, color = black ];
- h1 -> h2 -> h5 -> h1;
- root:r1 -> h6 -> h2;
- h4 -> h3;
- h3 -> h5;
+ root:r0 -> h1 [ style = bold, color = black ];
+ h1 -> h2 -> h5 -> h1;
+ root:r1 -> h6 -> h2;
+ h4 -> h3;
+ h3 -> h5;
- }
+ }
-.. raw:: latex
+ .. subfig::
- }
- \subfigure[TODO]{
+ Luego de marcar el nodo ``h1``, se procede al ``h2``.
-.. digraph:: g2_2
+ .. digraph:: g2_2
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
- subgraph cluster_all {
+ subgraph cluster_all {
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- ];
+ root [
+ label = "root\nset|<r0> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ ];
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2;
- };
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2;
+ };
- root:r0 -> h1 [ color = gray10 ];
- h1 -> h2 [ style = bold, color = black ];
- h2 -> h5 -> h1;
- root:r1 -> h6 -> h2;
- h4 -> h3;
- h3 -> h5;
+ root:r0 -> h1 [ color = gray10 ];
+ h1 -> h2 [ style = bold, color = black ];
+ h2 -> h5 -> h1;
+ root:r1 -> h6 -> h2;
+ h4 -> h3;
+ h3 -> h5;
- }
+ }
-.. raw:: latex
+ .. subfig::
- }
- \subfigure[TODO]{
+ Luego sigue el nodo h5.
-.. digraph:: g2_3
+ .. digraph:: g2_3
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
- subgraph cluster_all {
+ subgraph cluster_all {
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- ];
+ root [
+ label = "root\nset|<r0> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ ];
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2; h5;
- };
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2; h5;
+ };
- 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;
+ 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;
- }
+ }
-.. raw:: latex
- }
- \caption{TODO, part 1}
- \end{figure}
+.. fig:: fig:gc-mark-2
- \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 ];
+ Ejemplo de marcado del grafo de conectividad (parte 2).
- subgraph cluster_all {
+ .. subfig::
- root [
- label = "root\nset|<r0> r0\n*|<r1> r1",
- style = filled,
- fillcolor = gray96,
- ];
+ El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo
+ tanto no se visita nuevamente.
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2; h5;
- };
+ .. digraph:: g2_4
- 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;
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
- }
+ subgraph cluster_all {
-.. raw:: latex
+ root [
+ label = "root\nset|<r0> r0\n*|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ ];
- }
- \subfigure[TODO]{
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2; h5;
+ };
-.. digraph:: g2_5
+ 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;
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ }
- subgraph cluster_all {
+ .. subfig::
- root [
- label = "root\nset|<r0> r0|<r1> r1\n*",
- style = filled,
- fillcolor = gray96,
- ];
+ 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.
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2; h5; h6;
- };
+ .. digraph:: g2_5
- 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;
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
- }
+ subgraph cluster_all {
-.. raw:: latex
+ root [
+ label = "root\nset|<r0> r0|<r1> r1\n*",
+ style = filled,
+ fillcolor = gray96,
+ ];
- }
- \subfigure[TODO]{
+ subgraph marked {
+ node [ style = filled, fillcolor = gray25, fontcolor = white ];
+ h1; h2; h5; h6;
+ };
-.. digraph:: g2_6
+ 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;
- margin = 0;
- ratio = fill;
- size = "2.0,2.6";
- node [ shape = record, width = 0, height = 0 ];
- edge [ color = gray40 ];
+ }
- subgraph cluster_all {
+ .. subfig::
- root [
- label = "root\nset|<r0> r0|<r1> r1\n*",
- style = filled,
- fillcolor = gray96,
- ];
+ 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.
- subgraph marked {
- node [ style = filled, fillcolor = gray25, fontcolor = white ];
- h1; h2; h5; h6;
- };
+ .. digraph:: g2_6
- 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;
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
+ node [ shape = record, width = 0, height = 0 ];
+ edge [ color = gray40 ];
- }
+ subgraph cluster_all {
-.. raw:: latex
+ root [
+ label = "root\nset|<r0> r0|<r1> r1\n*",
+ style = filled,
+ fillcolor = gray96,
+ ];
- }
- \caption{TODO, parte 2}
- \end{figure}
+ 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
^^^^^^^
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`` y ``right`` 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).
+
+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::
+
+ Se ejecuta ``update(r0, null)``.
+
+ .. 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;
+
+ }
+
+ .. subfig::
+
+ Se decrementa el contador de ``h1`` y éste queda en 0 (indicando
+ que es basura). Esto desencadena la eliminación de las referencias
+ ``h1.left`` y ``h1.right``.
+
+ .. 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;
+
+ }
+
+.. 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, por lo
+ tanto no es necesario descender a sus hijas; se continúa con
+ ``h3``.
+
+ .. 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;
+
+ }
+
+ .. subfig::
+
+ El contador de ``h3`` tampoco queda en 0; no hay necesidad de
+ descender a sus hijas y finaliza el proceso.
+
+ .. 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;
+
+ }
+
+
+Luego se cambia una referencia (en vez de eliminarse) realizándose la
+operación ``update(h3.left, h5)``. Para esto primero se incrementa el
+contador de referencias de ``h5`` para evitar confundirlo accidentalmente
+con *basura* (figura :vref:`fig:gc-rc-up-1`). Luego se procede
+a decrementar el contador de ``h2`` que queda en 0 (transformándose en
+*basura*) y lo mismo pasa cuando se desciende a ``h4`` (figura
+:vref:`fig:gc-rc-up-2`). Finalmente se decrementa el contador de ``h5``
+pero como esta celda va a ser apuntada por ``h3`` (por la operación que
+está ejecutándose) sobrevive y permanece en el *live set*. Finalmente se
+termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
+(figura :vref:`fig:gc-rc-up-3`).
+
+
+.. fig:: fig:gc-rc-up-1
+
+ TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
+
+ .. subfig::
+
+ 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 ];
+ h1;
+ };
+
+ h1 [ label = "h1\n0|<l> left|<r> right" ];
+ 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: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:r -> h6;
+
+ }
+
+ .. subfig::
+
+ 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 ];
+ h1;
+ };
+
+ h1 [ label = "h1\n0|<l> left|<r> right" ];
+ 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: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;
+
+ }
+
+.. fig:: fig:gc-rc-up-2
+
+ TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
+
+ .. subfig::
+
+ 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 ];
+ h1; h2;
+ };
+
+ h1 [ label = "h1\n0|<l> left|<r> right" ];
+ 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: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;
+
+ }
+
+ .. subfig::
+
+ 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 ];
+ h1; h2; h4;
+ };
+
+ h1 [ label = "h1\n0|<l> left|<r> right" ];
+ 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: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;
+
+ }
+
+.. fig:: fig:gc-rc-up-3
+
+ TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 3).
+
+ .. subfig::
+
+ 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 ];
+ h1; h2; h4;
+ };
+
+ h1 [ label = "h1\n0|<l> left|<r> right" ];
+ 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: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::
+
+ 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 ];
+ h1; h2; h4;
+ };
+
+ h1 [ label = "h1\n0|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> left|<r> right" ];
+ 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: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 / commitdiff