del *heap* [#gcheap]_ una vez que el programa ha dejado de hacer referencia
a ella (y por lo tanto, ha dejado de utilizarla).
+.. [#gcheap] *Heap* es un área de memoria que se caracteriza por ser
+ dinámica (a diferencia del área de memoria estática que está disponible
+ durante toda la ejecución de un programa). Un programa puede reservar
+ memoria en tiempo de ejecución según sea necesario y liberarla cuando ya
+ no la necesita. A diferencia del *stack*, la duración de la *reserva* no
+ está atada a un bloque de código.
+
A medida que el tiempo pasa, cada vez los programas son más complejos y es
más compleja la administración de memoria. Uno de los aspectos más
importantes de un recolector de basura es lograr un mayor nivel de
(como *buffer overflows* [#gcbuff]_ o *dangling pointers* [#gcdang]_) son
la causa más frecuente de problemas de seguridad [BEZO06]_.
+.. [#gcbuff] Un *buffer overflow* (*desbordamiento de memoria* en
+ castellano) se produce cuando se copia un dato a un área de memoria que
+ no es lo suficientemente grande para contenerlo. Esto puede producir que
+ el programa sea abortado por una violación de segmento, o peor,
+ sobreescribir un área de memoria válida, en cuyo caso los resultados son
+ impredecibles.
+
+.. [#gcdang] Un *dangling pointer* (*puntero colgante* en castellano) es un
+ puntero que apunta a un área de memoria inválida. Ya sea porque el
+ elemento apuntado no es el mismo tipo o porque la memoria ya ha sido
+ liberada. Al ser desreferenciado, los resultados son impredecibles, el
+ programa podría abortarse por una violación de segmento o podrían pasar
+ peores cosas si el área de memoria fue realocada para almacenar otro
+ objeto.
+
La recolección de basura nació junto a Lisp_ a finales de 1950 y en los
siguientes años estuvo asociada principalmente a lenguajes funcionales,
pero en la actualidad está presente en prácticamente todos los lenguajes de
difícil la búsqueda de errores.
-.. [#gcheap] *Heap* es un área de memoria que se caracteriza por ser
- dinámica (a diferencia del área de memoria estática que está disponible
- durante toda la ejecución de un programa). Un programa puede reservar
- memoria en tiempo de ejecución según sea necesario y liberarla cuando ya
- no la necesita. A diferencia del *stack*, la duración de la *reserva* no
- está atada a un bloque de código.
-.. [#gcbuff] Un *buffer overflow* (*desbordamiento de memoria* en
- castellano) se produce cuando se copia un dato a un área de memoria que
- no es lo suficientemente grande para contenerlo. Esto puede producir que
- el programa sea abortado por una violación de segmento, o peor,
- sobreescribir un área de memoria válida, en cuyo caso los resultados son
- impredecibles.
-.. [#gcdang] Un *dangling pointer* (*puntero colgante* en castellano) es un
- puntero que apunta a un área de memoria inválida. Ya sea porque el
- elemento apuntado no es el mismo tipo o porque la memoria ya ha sido
- liberada. Al ser desreferenciado, los resultados son impredecibles, el
- programa podría abortarse por una violación de segmento o podrían pasar
- peores cosas si el área de memoria fue realocada para almacenar otro
- objeto.
-
Conceptos básicos
celda [#gccelda]_ alocada antes que otra nunca puede ser liberada antes
que aquella.
+ .. [#gccelda] En general en la literatura se nombra a una porción de
+ memoria alocada individualmente *celda*, *nodo* u *objeto*
+ indistintamente. En este trabajo se utilizará la misma nomenclatura
+ (haciendo mención explícita cuando alguno de estos términos se
+ refiera a otra cosa, como al nodo de una lista o a un objeto en el
+ sentido de programación orientada a objetos).
+
*Heap*:
A diferencia del *stack*, el *heap* provee un área de memoria que puede
ser obtenida dinámicamente pero sin limitaciones de orden. Es el tipo de
normalmente se lo llama *mutator* (mutador).
-.. [#gccelda] En general en la literatura se nombra a una porción de
- memoria alocada individualmente *celda*, *nodo* u *objeto*
- indistintamente. En este trabajo se utilizará la misma nomenclatura
- (haciendo mención explícita cuando alguno de estos términos se refiera
- a otra cosa, como al nodo de una lista o a un objeto en el sentido de
- programación orientada a objetos).
-
Recorrido del grafo de conectividad
y de esta manera tener un mejor comportamiento de la memoria virtual o del
*caché*.
+.. [#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
+ completamente arbitrarios, ya que cualquier *vértice interior* puede ser
+ un *vértice terminal*.
+
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]_::
for r in root_set
mark(r)
+.. [#gcpseudo] Para presentar los algoritmos se utiliza una forma simple de
+ pseudo-código. El pseudo-código se escribe en inglés para que pueda ser
+ más fácilmente contrastado con la literatura, que está en inglés. Para
+ diferenciar posiciones de memoria y punteros de las celdas en sí, se usa
+ la misma sintaxis que C, ``r*`` denota una referencia o puntero y ``*r``
+ denota "objeto al que apunta ``r``\ ". Se sobreentiende que ``r = o``
+ siempre toma la dirección de memoria de ``o``.
+
Una vez concluido el marcado, sabemos que todos los vértices con la marca
son parte del *live set* y que todos los vértices no marcados son *basura*.
Esto es conocido también como **abstracción bicolor**, dado que en la
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
+``r0``. Luego se marca el sub-grafo al que apunta ``r1`` (ver figura
:vref:`fig:gc-mark-2`), concluyendo con el marcado del grafo completo,
dejando sin marcar solamente las celdas *basura* (en blanco).
}
-.. [#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
- completamente arbitrarios, ya que cualquier *vértice interior* puede ser
- un *vértice terminal*.
-.. [#gcpseudo] Para presentar los algoritmos se utiliza una forma simple de
- pseudo-código. El pseudo-código se escribe en inglés para que pueda ser
- más fácilmente contrastado con la literatura, que está en inglés. Para
- diferenciar posiciones de memoria y punteros de las celdas en sí, se usa
- la misma sintaxis que C, ``r*`` denota una referencia o puntero y ``*r``
- denota "objeto al que apunta ``r``\ ". Se sobreentiende que ``r = o``
- siempre toma la dirección de memoria de ``o``.
-
-
.. _ref_gc_tricolor:
de una capa inferior [#gclowlayer]_ y proveen servicios a una capa superior
[#gchilayer]_.
+.. [#gclowlayer] En general estos servicios están provistos directamente
+ por el sistema operativo pero también pueden estar dados por un
+ administrador de memoria de bajo nivel (o *low level allocator* en
+ inglés).
+
+.. [#gchilayer] En general estos servicios son utilizados directamente por
+ el lenguaje de programación, pero pueden ser utilizados directamente por
+ el usuario del lenguaje si éste interatúa con el recolector, ya sea por
+ algún requerimiento particular o porque el lenguaje no tiene soporte
+ diercto de recolección de basura y el recolector está implementado como
+ una biblioteca de usuario.
+
A continuación se presentan las primitivas en común que utilizan todos los
recolectores a lo largo de este documento.
usuario también.
-.. [#gclowlayer] En general estos servicios están provistos directamente
- por el sistema operativo pero también pueden estar dados por un
- administrador de memoria de bajo nivel (o *low level allocator* en
- inglés).
-.. [#gchilayer] En general estos servicios son utilizados directamente por
- el lenguaje de programación, pero pueden ser utilizados directamente por
- el usuario del lenguaje si éste interatúa con el recolector, ya sea por
- algún requerimiento particular o porque el lenguaje no tiene soporte
- diercto de recolección de basura y el recolector está implementado como
- una biblioteca de usuario.
-
.. _ref_gc_clasic:
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
.. fig:: fig:gc-rc-rm-2
+ :padding: 0.5
Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 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* (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`).
+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-up-1
}
+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`).
+
+
Marcado y barrido
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. include:: links.rst
-.. vim: set ts=3 sts=3 sw=3 et tw=75 :
+.. vim: set ts=3 sts=3 sw=3 et tw=78 :
projects / z.facultad / 75.00 / informe.git / blobdiff