X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/aa8eff50c89900e85fe1b37f48e84decca03e534..5f79318a52fc6ada10154cb148008bd9d44fa22e:/source/gc.rst

diff --git a/source/gc.rst b/source/gc.rst
index 661a578..bf22c92 100644
--- 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).
 
+.. [#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
@@ -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]_.
 
+.. [#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
@@ -64,26 +86,6 @@ puntos de falla no controlados por el programador, volviendo mucho más
 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
@@ -121,6 +123,13 @@ Registros:
    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
@@ -173,13 +182,6 @@ programa en sí son los cambios al grafo de conectividad de las celdas,
 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
@@ -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é*.
 
+.. [#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]_::
@@ -331,6 +338,14 @@ el siguiente (asumiendo que partimos con todos los vértices sin marcar)
       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
@@ -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:
 
@@ -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]_.
 
+.. [#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.
 
@@ -697,17 +711,6 @@ recolector, aunque en ciertas circunstancias pueden ser utilizados por el
 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:
@@ -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
-----------------------------------------------------------------------------
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 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
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+^^^^^^^^^^^^^^^^^^^
 
 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
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+^^^^^^^^^^^
 
 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*
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 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.
 
-.. _ref_gc_art:
-
-Estado del arte
-----------------------------------------------------------------------------
-
-.. explicar la cantidad de cosas que hay (que son muchas) y dar algunos
-   ejemplos.
-
-TODO
 
 Cloning
 
@@ -1600,4 +1599,4 @@ http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html
 
 .. 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 :