Usar identación de 3 espacios y 78 columnas

[z.facultad/75.00/informe.git] / source / gc.rst

diff --git a/source/gc.rst b/source/gc.rst
index 661a578fa41c3d73e5c9f33c9a11768c798ce8ab..bf22c924f59d10aabeb2fd6737d7cf517766160e 100644 (file)
--- a/source/gc.rst
+++ b/source/gc.rst
@@ -17,6 +17,13 @@ Introducción
 del *heap* [#gcheap]_ una vez que el programa ha dejado de hacer referencia
 a ella (y por lo tanto, ha dejado de utilizarla).
 
 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
 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


@@ -32,6 +39,21 @@ recolector de basura. Por ejemplo, los errores en el manejo de memoria
 (como *buffer overflows* [#gcbuff]_ o *dangling pointers* [#gcdang]_) son
 la causa más frecuente de problemas de seguridad [BEZO06]_.
 
 (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
 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


@@ -64,26 +86,6 @@ puntos de falla no controlados por el programador, volviendo mucho más
 difícil la búsqueda de errores.
 
 
 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
 
 
 Conceptos básicos


@@ -121,6 +123,13 @@ Registros:
    celda [#gccelda]_ alocada antes que otra nunca puede ser liberada antes
    que aquella.
 
    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
 *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


@@ -173,13 +182,6 @@ programa en sí son los cambios al grafo de conectividad de las celdas,
 normalmente se lo llama *mutator* (mutador).
 
 
 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
 
 
 Recorrido del grafo de conectividad


@@ -317,6 +319,11 @@ 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é*.
 
 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]_::
 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]_::


@@ -331,6 +338,14 @@ el siguiente (asumiendo que partimos con todos los vértices sin marcar)
       for r in root_set
          mark(r)
 
       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
 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


@@ -567,19 +582,6 @@ 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:
 
 
 .. _ref_gc_tricolor:
 


@@ -635,6 +637,18 @@ En general todos los algoritmos de recolección de basura utilizan servicios
 de una capa inferior [#gclowlayer]_ y proveen servicios a una capa superior
 [#gchilayer]_.
 
 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.
 
 A continuación se presentan las primitivas en común que utilizan todos los
 recolectores a lo largo de este documento.
 


@@ -697,17 +711,6 @@ recolector, aunque en ciertas circunstancias pueden ser utilizados por el
 usuario también.
 
 
 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:
 
 
 .. _ref_gc_clasic:


@@ -1438,13 +1441,18 @@ TODO
 
 
 
 
 
 

+.. _ref_gc_art:

 
 

-TODO
+Estado del arte
+----------------------------------------------------------------------------

 
 

+.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
+   ejemplos.

 
 

+TODO

 
 Clasificación
 
 Clasificación

-----------------------------------------------------------------------------
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 
 La cantidad de clasificaciones que pueden hacerse respecto a algoritmos de
 recolección de basura son muy grandes. Muchas de estas clasificaciones se
 
 La cantidad de clasificaciones que pueden hacerse respecto a algoritmos de
 recolección de basura son muy grandes. Muchas de estas clasificaciones se


@@ -1458,7 +1466,7 @@ pudieron observar en la investigación sobre el `estado del arte`_.
 .. _ref_gc_direct:
 
 Directa / indirecta
 .. _ref_gc_direct:
 
 Directa / indirecta

-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+^^^^^^^^^^^^^^^^^^^

 
 Generalmente se llama recolección **directa** a aquella en la cual el
 compilador o lenguaje instrumenta al *mutator* de forma tal que la
 
 Generalmente se llama recolección **directa** a aquella en la cual el
 compilador o lenguaje instrumenta al *mutator* de forma tal que la


@@ -1488,7 +1496,7 @@ Estas son las dos grandes familias de recolectores, también conocidos como
 .. _ref_gc_inc:
 
 Incremental
 .. _ref_gc_inc:
 
 Incremental

-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+^^^^^^^^^^^

 
 Recolección incremental es aquella que se realiza de forma intercalada con
 el *mutator*. En general el propósito es disminuir el tiempo de las pausas
 
 Recolección incremental es aquella que se realiza de forma intercalada con
 el *mutator*. En general el propósito es disminuir el tiempo de las pausas


@@ -1516,7 +1524,7 @@ incremental, aunque el tiempo de pausa de una recolección sea menor.
 .. _ref_gc_concurrent:
 
 Concurrente / *stop-the-world*
 .. _ref_gc_concurrent:
 
 Concurrente / *stop-the-world*

-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

 
 Los recolectores concurrentes son aquellos que pueden correr en paralelo
 con el *mutator*. Por el contrario, aquellos que pausan el *mutator* para
 
 Los recolectores concurrentes son aquellos que pueden correr en paralelo
 con el *mutator*. Por el contrario, aquellos que pausan el *mutator* para


@@ -1534,15 +1542,6 @@ Esto también trae como consecuencia el incremento en el tiempo total que
 consume el recolector, debido a la necesidad de re-escanear sub-grafos que
 han sido modificados.
 
 consume el recolector, debido a la necesidad de re-escanear sub-grafos que
 han sido modificados.
 

-.. _ref_gc_art:
-
-Estado del arte
-----------------------------------------------------------------------------
-
-.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
-   ejemplos.
-
-TODO

 
 Cloning
 
 
 Cloning
 


@@ -1600,4 +1599,4 @@ http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html
 
 .. include:: links.rst
 
 
 .. 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 :