particular, si el programa fue diseñado con el recolector de basura en
mente en ciertas circunstancias puede ser incluso más eficiente que uno que
hace manejo explícito de la memoria. Muchos recolectores mejoran la
-localidad de referencia, haciendo que el programa tenga un mejor
-comportamiento con el caché y la memoria virtual.
+localidad de referencia [#gcreflocal]_, haciendo que el programa tenga un
+mejor comportamiento con el caché y la memoria virtual.
+
+.. [#gcreflocal] Localidad de referencia es la medida en que los accesos
+ sucesivos de memoria cercana espacialmente son cercanos también en el
+ tiempo. Por ejemplo, un programa que lee todos los elementos de una matriz
+ contigua de una vez o que utiliza la misma variable repetidamente tiene
+ buena localidad referencia. Una buena localidad de referencia interactúa
+ bien con la memoria virtual y caché, ya que reduce el conjunto de trabajo
+ (o *working set*) y mejora la probabildad de éxito (*hit rate*).
El recolector de basura debe tener un comportamiento correcto y predecible
para que sea útil, si el programador no puede confiar en el recolector
o *primero a lo alto* (*depth-first*) del grafo, el marcado de un grafo
también puede realizarse de ambas maneras. Cada una podrá o no tener
efectos en la eficiencia, en particular dependiendo de la aplicación puede
-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é*.
+convenir uno u otro método para lograr una mejor localidad de referencia.
.. [#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
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
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()
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
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* (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-rm-1
}
-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`).
+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`).
.. fig:: 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-up-2
Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
}
-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`).
-
+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`).
.. fig:: fig:gc-rc-cycle
:padding: 0.5
}
-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
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-TODO
+Este algoritmo es el más parecido a la teoría sobre recolección de basura.
+Consiste en realizar la recolección en 2 fases: marcado y barrido. La primera
+fase consiste en el proceso de marcar el grafo de conectividad del *heap* para
+descubrir qué celdas son alcanzables desde el *root set*, tal y como se
+describió en :ref:`ref_gc_intro_mark`.
+
+Una vez marcadas todas las celdas, se sabe que las celdas *blancas* son
+*basura*, por lo tanto el paso que queda es el *barrido* de estas celdas,
+liberándolas. Esto se efectúa recorriendo todo el *heap*. Por lo tanto cada
+recolección es :math:`O(\lvert Heap \rvert)`, a diferencia del conteo de
+referencia que dijimos que en el peor caso es :math:`O(\lvert Live \thickspace
+set \rvert)`. Sin embargo el conteo de referencias se ejecuta **cada vez que
+se actualiza una referencia** mientras que la recolección en el marcado
+y barrido se realiza típicamente solo cuando el *mutator* pide una celda pero
+no hay ninguna libre. Esto hace que la constante del conteo de referencias sea
+típicamente varios órdenes de magnitud mayores que en el marcado y barrido.
+
+A continuación se presentan los servicios básicos de este algoritmo::
+
+ function new() is
+ cell = alloc()
+ if cell is null
+ collect()
+ cell = alloc()
+ if cell is null
+ throw out_of_memory
+ return cell
+
+ function collect() is
+ mark_phase()
+ sweep_phase()
+
+ function sweep_phase() is
+ foreach cell in heap
+ if cell.marked
+ cell.marked = false
+ else
+ free(cell)
+
+El algoritmo ``mark_sweep()`` es exactamente igual al presentado en
+:ref:`ref_gc_intro_mark`. Es preciso notar que la fase de barrido
+(``sweep_phase()``) debe tener una comunicación extra con el *low level
+allocator* para poder obtener todas las celdas de memoria que existen en el
+*heap*.
+
+A diferencia del conteo de referencias, este algoritmo es :ref:`indirecto
+<ref_gc_direct>` y :ref:`no incremental <ref_gc_inc>`, ya que se realiza un
+recorrido de todo el *heap* de forma espaciada a través de la ejecución del
+programa. En general el *mutator* sufre pausas considerablemente mayores (en
+promedio) que con el conteo de referencias, lo que puede ser problemático para
+aplicaciones con requerimientos rígidos de tiempo, como aplicaciones
+*real-time*. Debido a la percepción de las pausas grandes, este tipo de
+colectores se conocen como :ref:`stop-the-world <ref_gc_concurrent>` (o
+*detener el mundo*).
+
+Una ventaja fundamental sobre el conteo de referencias es la posibilidad de
+reclamar estructuras cíclicas sin consideraciones especiales. Podemos observar
+como esto es posible analizando el ejemplo en las figuras
+:r:`fig:gc-mark-1` y :vref:`fig:gc-mark-2`. Si se eliminaran las referencias
+:math:`r0 \to h1` y :math:`h6 \to h2`, la fase de marcado consistiría
+solamente en marcar la celda :math:`h6`, pues es la única alcanzable desde el
+*root set*. Todas las demás celdas permanecerían blancas y por lo tanto pueden
+ser liberadas sin inconvenientes en la fase de barrido, que recorre el *heap*
+linealmente.
+
projects / z.facultad / 75.00 / informe.git / blobdiff