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.
+ área de memoria fue re-asignada 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
utilizar recursividad y tener un esquema simple de memoria dinámica. Sin
embargo este esquema es muy limitado porque el orden de reserva
y liberación de memoria tiene que estar bien establecido. Una celda
- [#gccelda]_ alocada antes que otra nunca puede ser liberada antes que
+ [#gccelda]_ asignada 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*
+ memoria asignada 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
.. fig:: fig:gc-heap-parts
+ Distintas partes de la memoria *heap*.
+
Distintas partes de la memoria, incluyendo relación entre *basura*, *live
set*, *heap* y *root set*.
.. fig:: 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::
.. fig:: 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::
.. fig:: fig:gc-rc-up-1
+ Ejemplo de conteo de referencias: actualización de una referencia (parte 1).
+
Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l`` :math:`\to`
``h5`` (parte 1).
.. fig:: fig:gc-rc-up-2
+ Ejemplo de conteo de referencias: actualización de una referencia (parte 2).
+
Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l`` :math:`\to`
``h5`` (parte 2).
.. fig:: 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).
Este algoritmo consiste en hacer una partición del *heap* en 2 mitades
o *semi-espacios*, llamados usualmente *Fromspace* y *Tospace*. El primero se
-utiliza para alocar nuevas celdas de forma lineal, asumiendo un *heap*
+utiliza para asignar nuevas celdas de forma lineal, asumiendo un *heap*
contiguo, incrementando un puntero (ver figura :vref:`fig:gc-copy`). Esto se
conoce como *pointer bump allocation* y es, probablemente, la forma más
-eficiente de alocar memoria (tan eficiente como alocar memoria en el *stack*).
+eficiente de asignar memoria (tan eficiente como asignar memoria en el
+*stack*).
.. fig:: fig:gc-copy
espacio en el *Fromspace*; en ese momento comienza el proceso de recolección
de basura que consiste en recorrer el grafo de conectividad, copiando las
celdas *vivas* del *Fromspace* al *Tospace* de manera contigua, como si
-estuvieran alocando por primera vez. Como la posición en memoria de las celdas
-cambia al ser movidas, es necesario actualizar la dirección de memoria de
-todas las celdas *vivas*. Para esto se almacena una dirección de memoria de
+estuvieran asignando por primera vez. Como la posición en memoria de las
+celdas cambia al ser movidas, es necesario actualizar la dirección de memoria
+de todas las celdas *vivas*. Para esto se almacena una dirección de memoria de
redirección, *forwarding address*, en las celdas que mueven. La *forwarding
address* sirve a su vez de marca, para no recorrer una celda dos veces (como
se explica en :ref:`gc_intro_mark`). Cuando se encuentra una celda que ya fue
A continuación se presenta una implementación sencilla de los servicios
provistos por este tipo de recolectores. Cabe destacar que este tipo de
recolectores deben estar íntimamente relacionados con el *low level
-allocator*, ya que la organización del *heap* y la forma de alocar memoria es
+allocator*, ya que la organización del *heap* y la forma de asignar memoria es
parte fundamental de este algoritmo. Se asume que ya hay dos áreas de memoria
del mismo tamaño destinadas al *Fromspace* y *Tospace*, y la existencia de
4 variables: ``fromspace`` (que apunta a la base del *Fromspace*), ``tospace``
comienza la memoria libre). También vale aclarar que este algoritmo soporta
inherentemente celdas de tamaño variable, por lo que los servicios ``alloc()``
y ``new()`` [#gccopynew]_ reciben como parámetro el tamaño de la celda
-a alocar::
+a asignar::
function alloc(size) is
if free + size > fromspace + spacesize
algunos :ref:`recolectores incrementales <gc_inc>` que a veces necesitan
instrumentar el *mutator* pero no para mantener el estado del grafo de
conectividad completo). La recolección se dispara usualmente cuando el
-*mutator* requiere alocar memoria pero no hay más memoria libre conocida
+*mutator* requiere asignar memoria pero no hay más memoria libre conocida
disponible y el recolector se encarga de generar la información de
conectividad desde cero para determinar qué celdas son *basura*.
básica es el :ref:`conteo de referencias <gc_rc>`. Otros recolectores pueden
hacerse incrementales de diversas maneras, pero en general consta de hacer
parte del trabajo de escanear el grafo de conectividad cada vez que el
-*mutator* aloca memoria. En general para hacer esto es también necesario
+*mutator* asigna memoria. En general para hacer esto es también necesario
instrumentar al *mutator* de forma tal que informe al recolector cada vez que
cambia el grafo de conectividad, para que éste pueda marcar al sub-grafo
afectado por el cambio como *desactualizado* y así re-escanearlo nuevamente en
desenlaza de la lista de libres. Por otro lado, cuando el recolector detecta
una celda *muerta*, la vuelve a enlazar en la lista de libres. Este es un
esquema simple pero con limitaciones, entre las principales, el costo de
-alocar puede ser alto si hay muchos tamaños distintos de celda y soportar
+asignar puede ser alto si hay muchos tamaños distintos de celda y soportar
tamaño de celda variable puede ser complejo o acarrear muchas otras
ineficiencias. :ref:`gc_mark_sweep` en general usa este esquema, al igual que
:ref:`gc_rc`.
Otro forma de organizar el *heap* es utilizándolo como una especie de *stack*
-en el cual para alocar simplemente se incrementa un puntero. Este esquema es
+en el cual para asignar simplemente se incrementa un puntero. Este esquema es
simple y eficiente, si el recolector puede mover celdas (ver
-:ref:`gc_moving`); de otra manera alocar puede ser muy costoso si hay que
+:ref:`gc_moving`); de otra manera asignar puede ser muy costoso si hay que
buscar un *hueco* en el heap (es decir, deja de reducirse a incrementar un
puntero). El clásico ejemplo de esta familia es :ref:`gc_copy`.
Dentro de una región se utiliza un esquema de *pointer bump allocation* pero
las regiones en sí se administran como una lista de libres (como por ejemplo
[BLAC08]_). Otra variación (más común) de este esquema son los *two level
-allocators* que alocan páginas completas (similar a las regiones) y dentro de
-cada página se alocan las celdas. Ambas, páginas y celdas, se administran como
-listas de libres (ejemplos que utilizan este esquema son [BOEHWD]_ y el
+allocators* que asignan páginas completas (similar a las regiones) y dentro de
+cada página se asignan las celdas. Ambas, páginas y celdas, se administran
+como listas de libres (ejemplos que utilizan este esquema son [BOEHWD]_ y el
:ref:`recolector actual de D <dgc_actual>`).
celdas o no. En general el movimiento de celdas viene de la mano del esquema
de :ref:`pointer bump allocation <gc_free_list>`, ya que *compacta* todas las
celdas *vivas* al comienzo del *heap* luego de una recolección, permitiendo
-este esquema para alocar nuevas celdas, pero puede utilizarse en esquemas
+este esquema para asignar nuevas celdas, pero puede utilizarse en esquemas
híbridos como recolectores basados en *regiones* (por ejemplo [BLAC08]_).
Además los recolectores con movimiento de celdas deben ser :ref:`precisos
.. _gc_part:
-Recolección particionada
+Recolección particionada / generacional
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Otra forma de reducir la cantidad de pausas y la cantidad de trabajo realizado
projects / z.facultad / 75.00 / informe.git / blobdiff