X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/3b699164f331334ca98b9b3345a6f7b839d71ff9..refs/heads/master:/source/gc.rst?ds=sidebyside diff --git a/source/gc.rst b/source/gc.rst index 70cf2d0..66c64bd 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -1,10 +1,4 @@ -.. Introducción a la importancia de la recolección de basura y sus - principales técnicas, con sus ventajas y desventajas. También se da - un breve recorrido sobre el estado del arte. - ESTADO: TERMINADO - - .. _gc: Recolección de basura @@ -593,10 +587,11 @@ y se las pinta de negro, pintando sus hijas directas de gris. Una vez que no hay más celdas grises, tenemos la garantía de que las celdas negras serán el *live set* y las celdas blancas *basura*. Esto se debe a que siempre se mantiene esta invariante: **ninguna celda negra apunta directamente -a una celda blanca**. Las celdas blancas siempre son apuntadas por celdas -blancas o grises. Entonces, siempre que el conjunto de celdas grises sea -vacío, no habrán celdas negras conectadas a blancas, siendo las celdas blancas -*basura*. +a una celda blanca** (considerando como atómica la operación de pintar una +celda de negro y a sus hijas directas de gris). Las celdas blancas siempre son +apuntadas por celdas blancas o grises. Entonces, siempre que el conjunto de +celdas grises sea vacío, no habrán celdas negras conectadas a blancas, siendo +las celdas blancas *basura*. El algoritmo básico para marcar con tres colores es el siguiente (asumiendo que todas las celdas parten pintadas de blanco, es decir, el conjunto blanco @@ -1268,7 +1263,7 @@ contador de ``h2`` que queda en 0, transformándose en *basura* (ver figura }; h1 [ label = "h1\n0| l| r" ]; - h2 [ label = "h2\n1| l| r" ]; + h2 [ label = "h2\n0| l| r" ]; h3 [ label = "h3\n2| l\n*| r" ]; h4 [ label = "h4\n1| l| r" ]; h5 [ label = "h5\n2| l| r" ]; @@ -1336,7 +1331,7 @@ de actualizar la referencia ``h3.l`` para que apunte a ``h5`` (ver figura }; h1 [ label = "h1\n0| l| r" ]; - h2 [ label = "h2\n1| l| r" ]; + h2 [ label = "h2\n0| l| r" ]; h3 [ label = "h3\n2| l\n*| r" ]; h4 [ label = "h4\n0| l| r" ]; h5 [ label = "h5\n2| l| r" ]; @@ -1389,7 +1384,7 @@ de actualizar la referencia ``h3.l`` para que apunte a ``h5`` (ver figura }; h1 [ label = "h1\n0| l| r" ]; - h2 [ label = "h2\n1| l| r" ]; + h2 [ label = "h2\n0| l| r" ]; h3 [ label = "h3\n2| l\n*| r" ]; h4 [ label = "h4\n0| l| r" ]; h5 [ label = "h5\n1| l| r" ]; @@ -1735,13 +1730,13 @@ recolectores deben estar íntimamente relacionados con el *low level 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`` -(que apunta a la base del *Tospace*), ``spacesize`` (que contiene el tamaño de -un semi-espacio) y ``free`` (que apunta al lugar del *Fromspace* donde -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 asignar:: +4 variables globales: ``fromspace`` (que apunta a la base del *Fromspace*), +``tospace`` (que apunta a la base del *Tospace*), ``spacesize`` (que contiene +el tamaño de un semi-espacio) y ``free`` (que apunta al lugar del *Fromspace* +donde 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 asignar:: function alloc(size) is if free + size > fromspace + spacesize @@ -1769,6 +1764,7 @@ a asignar:: function copy(cell) is if cell.forwarding_address is null cell.forwarding_address = free + cell.copy_to(free) free = free + cell.size foreach child in cell child = copy(child) @@ -2333,17 +2329,17 @@ y barrido ` no lo hacen. Además hay otro algoritmo bastante básico que mueve celdas, el **marcado y compactado**. Éste no tiene 2 semi-espacios, directamente mueve las celdas compactándolas al comienzo del *heap*. El algoritmo es un poco más complejo que la :ref:`copia de -semi-espacios ` pero suele poder proveer una mayor localidad de -referencia y *desperdicia* un semi-espacio que está inutilizado salgo en el -momento de la recolección. Por ejemplo para Mono_, que antes usaba un -recolector conservativo sin movimiento ([BOEHWD]_) se está implementando un -recolector de este tipo [MOLAWE]_ [MOLA06]_. +semi-espacios ` pero suele proveer una mayor localidad de referencia +y no *desperdicia* un semi-espacio que está inutilizado salvo en el momento de +la recolección. Por ejemplo para Mono_, que antes usaba un recolector +conservativo sin movimiento ([BOEHWD]_) se está implementando un recolector de +este tipo [MOLAWE]_ [MOLA06]_. .. _gc_conserv: -Recolectores conservativos vs precisos +Recolectores conservativos versus precisos ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Los recolectores *conservativos* son aquellos que tienen la capacidad de poder @@ -2354,8 +2350,8 @@ o no. Esto trae una variada cantidad de problemas, como retención de celdas que en realidad son *basura* simplemente porque hay algún dato que coincide con la dirección de memoria en la que está almacenada esa celda *basura* [#gcflasepos]_. Además los recolectores puramente conservativos no puede mover -celdas (ver :ref:`gc_moving`), porque no pueden arriesgarse a actualizar los -punteros por el riesgo que existe de que sean *falsos positivos*. +celdas (ver :ref:`gc_moving`), dado que no pueden actualizar los supuestos +punteros por la posibilidad de que sean *falsos positivos*. .. [#gcflasepos] Esto es lo que se conoce como un *falso positivo*, algo que aparenta ser un puntero pero en realidad no lo es. @@ -2452,7 +2448,7 @@ completo). Sin embargo, a pesar de ser este el esquema más difundido para dividir el *heap* y realizar una recolección parcial sobre un área de alta concentración -de basura no es la única. Otros recolectores proponen hacer un análisis +de basura, no es la única. Otros recolectores proponen hacer un análisis estático del código revisando la conectividad entre los objetos según sus tipos (esto es posible solo en lenguajes con *tipado* estático), de manera tal de separar en distintas áreas grupos de tipos que no pueden tener referencias