.. Introducción a la importancia de la recolección de basura y sus
principales técnicas, con sus ventajas y desventajas. También se da
un breve recorrido sobre el estado del arte.
- ESTADO: TERMINADO, CORREGIDO
+ ESTADO: TERMINADO
.. _gc:
:vref:`fig:gc-heap-parts`).
-.. fig:: fig:gc-heap-parts
+.. flt:: fig:gc-heap-parts
Distintas partes de la memoria *heap*.
function mark(v) is
if not v.marked
v.marked = true
- for (src, dst) in v.edges
+ foreach (src, dst) in v.edges
mark(dst)
function mark_phase() is
*basura* (en blanco).
-.. fig:: fig:gc-mark-1
+.. flt:: fig:gc-mark-1
Ejemplo de marcado del grafo de conectividad (parte 1).
- .. subfig::
+ .. subflt::
Se comienza a marcar el grafo por la raíz r0.
}
- .. subfig::
+ .. subflt::
Luego de marcar el nodo ``h1``, se procede al ``h2``.
}
- .. subfig::
+ .. subflt::
Luego sigue el nodo h5.
}
-.. fig:: fig:gc-mark-2
+.. flt:: fig:gc-mark-2
Ejemplo de marcado del grafo de conectividad (parte 2).
- .. subfig::
+ .. subflt::
El nodo h5 tiene una arista al h1, pero el h1 ya fue visitado, por lo
tanto no se visita nuevamente.
}
- .. subfig::
+ .. subflt::
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.
}
- .. subfig::
+ .. subflt::
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
while not gray_set.empty()
v = gray_set.pop()
black_set.add(v)
- for (src, dst) in v.edges
+ foreach (src, dst) in v.edges
if dst in white_set
white_set.remove(dst)
gray_set.add(dst)
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]_.
+[PHP530]_.
.. _gc_rc_example:
*live set* ya que sus contadores siguen siendo mayores a 0 (ver figura
:vref:`fig:gc-rc-rm-2`).
-.. fig:: fig:gc-rc-rm-1
+.. flt:: fig:gc-rc-rm-1
Ejemplo de conteo de referencias: eliminación de una referencia (parte 1).
Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
- .. subfig::
+ .. subflt::
Estado inicial del grafo de conectividad.
}
- .. subfig::
+ .. subflt::
Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
``h1``.
}
- .. subfig::
+ .. subflt::
Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser *basura*).
Se elimina primero ``h1.l`` y luego ``h1.r``.
}
-.. fig:: fig:gc-rc-rm-2
+.. flt:: fig:gc-rc-rm-2
:padding: 0.5
Ejemplo de conteo de referencias: eliminación de una referencia (parte 2).
Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
- .. subfig::
+ .. subflt::
Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en el
*live set*).
}
- .. subfig::
+ .. subflt::
El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.
contador de ``h2`` que queda en 0, transformándose en *basura* (ver figura
:vref:`fig:gc-rc-up-1`).
-.. fig:: fig:gc-rc-up-1
+.. flt:: fig:gc-rc-up-1
Ejemplo de conteo de referencias: actualización de una referencia (parte 1).
Cambio en la referencia ``h3.l`` :math:`\to` ``h2`` a ``h3.l`` :math:`\to`
``h5`` (parte 1).
- .. subfig::
+ .. subflt::
Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.
}
- .. subfig::
+ .. subflt::
Luego se procede a visitar la antigua referencia de ``h3.l`` (``h2``).
}
- .. subfig::
+ .. subflt::
Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser *basura*).
Se eliminan las referencias a las hijas.
de actualizar la referencia ``h3.l`` para que apunte a ``h5`` (ver figura
:vref:`fig:gc-rc-up-2`).
-.. fig:: fig:gc-rc-up-2
+.. flt:: fig:gc-rc-up-2
Ejemplo de conteo de referencias: actualización de una referencia (parte 2).
Cambio en la referencia ``h3.l`` :math:`\to` ``h2`` a ``h3.l`` :math:`\to`
``h5`` (parte 2).
- .. subfig::
+ .. subflt::
Se decrementa el contador de ``h4`` quedando en 0, pasa a ser *basura*.
Se continúa con ``h5``.
}
- .. subfig::
+ .. subflt::
Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.
}
- .. subfig::
+ .. subflt::
Se termina por actualizar la referencia de ``h3.l`` para que apunte
a ``h5``.
pueden ser recicladas y su memoria es perdida (ver figura
:vref:`fig:gc-rc-cycle`).
-.. fig:: fig:gc-rc-cycle
+.. flt:: fig:gc-rc-cycle
:padding: 0.5
Ejemplo de conteo de referencias: pérdida de memoria debido a un ciclo.
Eliminación de la referencia ``r1`` :math:`\to` ``h3`` (pérdida de memoria
debido a un ciclo).
- .. subfig::
+ .. subflt::
El ejecutarse ``update(r1, null)`` se visita la celda ``h3``.
}
- .. subfig::
+ .. subflt::
Se decrementa el contador de ``h3`` pero sigue siendo mayor que 0 por el
ciclo.
sucede y se acumulan muchos *huecos* se dice que la memoria está
*fragmentada*.
-.. fig:: fig:gc-copy
+.. flt:: fig:gc-copy
Estructura del *heap* de un recolector con copia de semi-espacios.
*forwarding address* a la nueva ubicación (ver figura
:vref:`fig:gc-copy-ex-1`).
-.. fig:: fig:gc-copy-ex-1
+.. flt:: fig:gc-copy-ex-1
Ejemplo de recolección con copia de semi-espacios (parte 1).
- .. subfig::
+ .. subflt::
Estructura inicial del *heap*. El *Fromspace* está complete y se inicial
la recolección.
| "Tospace" |
+--------------------------------------------------+
- .. subfig::
+ .. subflt::
Se sigue la referencia del *root set*, copiando ``h3`` al *Tospace*
y dejando una *forwarding address*.
ubicación de ``h2`` pero no se vuelve a copiar la celda (ver figura
:vref:`fig:gc-copy-ex-2`).
-.. fig:: fig:gc-copy-ex-2
+.. flt:: fig:gc-copy-ex-2
Ejemplo de recolección con copia de semi-espacios (parte 2).
- .. subfig::
+ .. subflt::
Se sigue :math:`h3 \to h2`, copiando ``h2`` al *Tospace* y dejando una
*forwarding address*.
| "Tospace" |
+--------------------------------------------------+
- .. subfig::
+ .. subflt::
Se sigue :math:`h2 \to h1`, copiando ``h1``. Luego :math:`h1 \to h2`
pero ``h2`` no se copia, sólo se actualiza la referencia con la
nueva ubicación de ``h3``, como se muestra en la figura
:vref:`fig:gc-copy-ex-3`.
-.. fig:: fig:gc-copy-ex-3
+.. flt:: fig:gc-copy-ex-3
Ejemplo de recolección con copia de semi-espacios (parte 3).
- .. subfig::
+ .. subflt::
Se sigue :math:`h1 \to h4` copiando `h4`` al *Tospace* y dejando una
*forwarding address*.
| "Tospace" \------/ |
+--------------------------------------------------+
- .. subfig::
+ .. subflt::
Se finaliza la recolección, se intercambian los roles de los
semi-espacios y se actualiza la referencia del *root set*.
disponibles para realizar la recolección (ver figura
:vref:`fig:gc-concurrent`).
-.. fig:: fig:gc-concurrent
+.. flt:: fig:gc-concurrent
Distintos tipos de recolectores según el comportamiento en ambientes
multi-hilo.
- .. subfig::
+ .. subflt::
*Stop-the-world*.
| HH Mutator ZZ Inactivo XX Recolector |
|___________________________________________________________________|
- .. subfig::
+ .. subflt::
Paralelo.
| HH Mutator ZZ Inactivo XX Recolector |
|___________________________________________________________________|
- .. subfig::
+ .. subflt::
Concurrente.
Entonces, si el recolector tiene algún mecanismo para identificar zonas de
alta concentración de *basura* puede hacer la recolección solo en ese área
-donde el trabajo va a ser mejor recompensado (ver :vref:`fig:gc-part`).
+donde el trabajo va a ser mejor recompensado (ver figura :vref:`fig:gc-part`).
-.. fig:: fig:gc-part
+.. flt:: fig:gc-part
Concentración de basura en distintas particiones del *heap*.
projects / z.facultad / 75.00 / informe.git / blobdiff