Agregar referencia a tesis de Vladimir Panteleev

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

diff --git a/source/dgc.rst b/source/dgc.rst
index 4fbdf2901400121bf1c0c072f8ab96eb4890350f..804d554aae4c6ff22226c0a55a2b08622ee8db2a 100644 (file)
--- a/source/dgc.rst
+++ b/source/dgc.rst
@@ -461,7 +461,9 @@ algoritmo::
       mark_free_lists()
       mark_static_data()
       push_registers_into_stack()
       mark_free_lists()
       mark_static_data()
       push_registers_into_stack()

+      thread_self.stack.end = get_stack_top()

       mark_stacks()
       mark_stacks()

+      pop_registers_from_stack()

       mark_user_roots()
       mark_heap()
       start_the_world()
       mark_user_roots()
       mark_heap()
       start_the_world()


@@ -471,15 +473,24 @@ debe finalizar: la función ``mark_range()`` (que veremos más adelante) lo pone
 en ``true`` cuando una nueva celda debe ser visitada, por lo tanto la
 iteración se interrumpe cuando no hay más celdas por visitar.
 
 en ``true`` cuando una nueva celda debe ser visitada, por lo tanto la
 iteración se interrumpe cuando no hay más celdas por visitar.
 

-Las funciones ``stop_the_world()`` y ``start_the_world()`` sencillamente
-pausan y reanudan todos los hilos respectivamente::
+Las funciones ``stop_the_world()`` y ``start_the_world()`` pausan y reanudan
+todos los hilos respectivamente (salvo el actual). Al pausar los hilos además
+se guardan los registros del procesador en el *stack* y se guarda la posición
+actual del *stack* para que la fase de marcado pueda recorrerlos::

 
    function stop_the_world() is
       foreach thread in threads
 
    function stop_the_world() is
       foreach thread in threads

+         if thread is thread_self
+            continue

          thread.pause()
          thread.pause()

+         push_registers_into_stack()
+         thread.stack.end = get_stack_top()

 
    function start_the_world() is
       foreach thread in threads
 
    function start_the_world() is
       foreach thread in threads

+         if thread is thread_self
+            continue
+         pop_registers_from_stack()

          thread.resume()
 
 La función ``clear_mark_scan_bits()`` se encarga de restablecer todos los
          thread.resume()
 
 La función ``clear_mark_scan_bits()`` se encarga de restablecer todos los


@@ -526,6 +537,13 @@ en el *stack* a través de la función::
       foreach register in registers
          push(register)
 
       foreach register in registers
          push(register)
 

+Y luego se descartan (no es necesario ni correcto restablecer los valores ya
+que podrían tener nuevos valores) al sacarlos de la pila::
+
+   function pop_registers_from_stack() is
+      foreach register in reverse(registers)
+         pop()
+

 Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos
 los threads para terminar de marcar el *root set*::
 
 Una vez hecho esto, basta marcar (de forma conservativa) los *stacks* de todos
 los threads para terminar de marcar el *root set*::
 


@@ -660,9 +678,9 @@ objetos grandes se marcan todas las páginas que utilizaban como ``FREE``::
    function free_big_object(pool, page) is
       pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
       do
    function free_big_object(pool, page) is
       pool_end = cast(byte*) pool.pages + (PAGE_SIZE * pool.number_of_pages)
       do

-         page = cast(byte*) page + PAGE_SIZE

          page.block_size = FREE
          page.block_size = FREE

-      while page.block_size is CONTINUATION and page < pool_end
+         page = cast(byte*) page + PAGE_SIZE
+      while page < pool_end and page.block_size is CONTINUATION

 
 Además, los bloques que tienen en atributo ``final`` son finalizados llamando
 a la función ``finalize()``. Esta función es un servicio que provee la
 
 Además, los bloques que tienen en atributo ``final`` son finalizados llamando
 a la función ``finalize()``. Esta función es un servicio que provee la


@@ -741,16 +759,15 @@ suficientemente grande como para poder almacenar el tamaño solicitado). Una
 vez más el algoritmo distingue objetos grandes de pequeños. Los pequeños se
 asignan de las siguiente manera::
 
 vez más el algoritmo distingue objetos grandes de pequeños. Los pequeños se
 asignan de las siguiente manera::
 

-      function new_small(block_size) is
+   function new_small(block_size) is
+      block = find_block_with_size(block_size)
+      if block is null
+         collect()

          block = find_block_with_size(block_size)
          if block is null
          block = find_block_with_size(block_size)
          if block is null

-            collect()
+            new_pool()

             block = find_block_with_size(block_size)
             block = find_block_with_size(block_size)

-            if block is null
-               new_pool()
-               block = find_block_with_size(block_size)
-               return null
-         return block
+      return block

 
 Se intenta reiteradas veces conseguir un bloque del tamaño correcto libre,
 realizando diferentes acciones si no se tiene éxito. Primero se intenta hacer
 
 Se intenta reiteradas veces conseguir un bloque del tamaño correcto libre,
 realizando diferentes acciones si no se tiene éxito. Primero se intenta hacer


@@ -760,39 +777,41 @@ pidiendo memoria al *low level allocator* (el sistema operativo generalmente).
 
 Para intentar buscar un bloque de memoria libre se realiza lo siguiente::
 
 
 Para intentar buscar un bloque de memoria libre se realiza lo siguiente::
 

-      function find_block_with_size(block_size) is
+   function find_block_with_size(block_size) is
+      block = free_lists[block_size].pop_first()
+      if block is null
+         assign_page(block_size)

          block = free_lists[block_size].pop_first()
          block = free_lists[block_size].pop_first()

-         if block is null
-            assign_page(block_size)
-            block = free_lists[block_size].pop_first()
-         return block
+      return block

 
 Si no se puede obtener un bloque de la lista de libres correspondiente, se
 busca asignar una página libre al tamaño de bloque deseado de forma de
 *alimentar* la lista de libres con dicho tamaño::
 
 
 Si no se puede obtener un bloque de la lista de libres correspondiente, se
 busca asignar una página libre al tamaño de bloque deseado de forma de
 *alimentar* la lista de libres con dicho tamaño::
 

-      function assign_page(block_size) is
-         foreach pool in heap
-            foreach page in pool
-               if page.block_size is FREE
-                  page.block_size = block_size
-                  foreach block in page
-                     free_lists[page.block_size].link(block)
+   function assign_page(block_size) is
+      foreach pool in heap
+         foreach page in pool
+            if page.block_size is FREE
+               page.block_size = block_size
+               foreach block in page
+                  free_lists[page.block_size].link(block)

 
 Cuando todo ello falla, el último recurso consiste en pedir memoria al sistema
 operativo, creando un nuevo *pool*::
 
 
 Cuando todo ello falla, el último recurso consiste en pedir memoria al sistema
 operativo, creando un nuevo *pool*::
 

-      funciones new_pool(number_of_pages = 1) is
-         pool = alloc(pool.sizeof)
-         if pool is null
-            return null
-         pool.number_of_pages = number_of_pages
-         pool.pages = alloc(number_of_pages * PAGE_SIZE)
-         if pool.pages is null
-            free(pool)
-            return null
-         heap.add(pool)
-         return pool
+   function new_pool(number_of_pages = 1) is
+      pool = alloc(pool.sizeof)
+      if pool is null
+         return null
+      pool.number_of_pages = number_of_pages
+      pool.pages = alloc(number_of_pages * PAGE_SIZE)
+      if pool.pages is null
+         free(pool)
+         return null
+      heap.add(pool)
+      foreach page in pool
+         page.block_size = FREE
+      return pool

 
 Se recuerda que la función ``alloc()`` es un :ref:`servicio
 <gc_intro_services>` provisto por el *low level allocator* y en la
 
 Se recuerda que la función ``alloc()`` es un :ref:`servicio
 <gc_intro_services>` provisto por el *low level allocator* y en la


@@ -808,22 +827,22 @@ Si el tamaño de bloque necesario para cumplir con la asignación de memoria es
 de una página, entonces se utiliza otro algoritmo para alocar un objeto
 grande::
 
 de una página, entonces se utiliza otro algoritmo para alocar un objeto
 grande::
 

-      function new_big(size) is
-         number_of_pages = ceil(size / PAGE_SIZE)
+   function new_big(size) is
+      number_of_pages = ceil(size / PAGE_SIZE)
+      pages = find_pages(number_of_pages)
+      if pages is null
+         collect()

          pages = find_pages(number_of_pages)
          if pages is null
          pages = find_pages(number_of_pages)
          if pages is null

-            collect()
-            pages = find_pages(number_of_pages)
-            if pages is null
-               minimize()
-               pool = new_pool(number_of_pages)
-               if pool is null
-                  return null
-               pages = assign_pages(pool, number_of_pages)
-         pages[0].block_size = PAGE
-         foreach page in pages[1..end]
-            page.block_size = CONTINUATION
-         return pages[0]
+            minimize()
+            pool = new_pool(number_of_pages)
+            if pool is null
+               return null
+            pages = assign_pages(pool, number_of_pages)
+      pages[0].block_size = PAGE
+      foreach page in pages[1..end]
+         page.block_size = CONTINUATION
+      return pages[0]

 
 De forma similar a la asignación de objetos pequeños, se intenta encontrar una
 serie de páginas contiguas, dentro de un mismo *pool*, suficientes para
 
 De forma similar a la asignación de objetos pequeños, se intenta encontrar una
 serie de páginas contiguas, dentro de un mismo *pool*, suficientes para


@@ -849,34 +868,34 @@ completamente libres::
 Volviendo a la función ``new_big()``, para hallar una serie de páginas
 contiguas se utiliza el siguiente algoritmo::
 
 Volviendo a la función ``new_big()``, para hallar una serie de páginas
 contiguas se utiliza el siguiente algoritmo::
 

-      function find_pages(number_of_pages) is
-         foreach pool in heap
-            pages = assign_pages(pool, number_of_pages)
-            if pages
-               return pages
-         return null
+   function find_pages(number_of_pages) is
+      foreach pool in heap
+         pages = assign_pages(pool, number_of_pages)
+         if pages
+            return pages
+      return null

 
 Como se dijo, las páginas deben estar contenidas en un mismo *pool* (para
 tener la garantía de que sean contiguas), por lo tanto se busca *pool* por
 *pool* dicha cantidad de páginas libres consecutivas a través del siguiente
 algoritmo::
 
 
 Como se dijo, las páginas deben estar contenidas en un mismo *pool* (para
 tener la garantía de que sean contiguas), por lo tanto se busca *pool* por
 *pool* dicha cantidad de páginas libres consecutivas a través del siguiente
 algoritmo::
 

-      function assign_pages(pool, number_of_pages) is
-         pages_found = 0
-         first_page = null
-         foreach page in pool
-            if page.block_size is FREE
-               if pages_found is 0
-                  pages_found = 1
-                  first_page = page
-               else
-                  pages_found = pages_found + 1
-               if pages_found is number_of_pages
-                  return [first_page .. page]
+   function assign_pages(pool, number_of_pages) is
+      pages_found = 0
+      first_page = null
+      foreach page in pool
+         if page.block_size is FREE
+            if pages_found is 0
+               pages_found = 1
+               first_page = page

             else
             else

-               pages_found = 0
-               first_page = null
-         return null
+               pages_found = pages_found + 1
+            if pages_found is number_of_pages
+               return [first_page .. page]
+         else
+            pages_found = 0
+            first_page = null
+      return null

 
 Una vez más, cuando todo ello falla (incluso luego de una recolección), se
 intenta alocar un nuevo *pool*, esta vez con una cantidad de páginas
 
 Una vez más, cuando todo ello falla (incluso luego de una recolección), se
 intenta alocar un nuevo *pool*, esta vez con una cantidad de páginas


@@ -1312,6 +1331,8 @@ a ningún destructor), para el usuario puede ser una garantía muy débil
 y proveer finalización asegurada puede ser muy deseable.
 
 
 y proveer finalización asegurada puede ser muy deseable.
 
 

+.. _dgc_committed:
+

 Memoria *encomendada*
 ^^^^^^^^^^^^^^^^^^^^^
 El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada*
 Memoria *encomendada*
 ^^^^^^^^^^^^^^^^^^^^^
 El algoritmo actual divide un *pool* en dos áreas: memoria *encomendada*


@@ -1464,15 +1485,16 @@ Las opciones más importantes son:
       Esquema de un bloque cuando está activada la opción ``SENTINEL``.
 
       .. aafig::
       Esquema de un bloque cuando está activada la opción ``SENTINEL``.
 
       .. aafig::

+         :textual:

 
          |              |              |                              |        |
          +-- Palabra ---+-- Palabra ---+-- Tamaño bloque de usuario --+- Byte -+
          |              |              |                              |        |
 
          +--------------+--------------+------------------------------+--------+
 
          |              |              |                              |        |
          +-- Palabra ---+-- Palabra ---+-- Tamaño bloque de usuario --+- Byte -+
          |              |              |                              |        |
 
          +--------------+--------------+------------------------------+--------+

-         |  Tamaño del  |     Pre      |                              |  Post  |
-         |  bloque  de  |              |      Bloque de usuario       |        |
-         |    usuario   |  0xF4F4F4F4  |                              |  0xF5  |
+         | "Tamaño del" |     Pre      |                              |  Post  |
+         |  "bloque de" |              |      Bloque de usuario       |        |
+         |   "usuario"  |  0xF4F4F4F4  |                              |  0xF5  |

          +--------------+--------------+------------------------------+--------+
                                        A
                                        |
          +--------------+--------------+------------------------------+--------+
                                        A
                                        |


@@ -1495,6 +1517,8 @@ participación y observación del grupo de noticias, de donde se obtuvieron los
 principales problemas percibidos por la comunidad que utiliza el lenguaje.
 
 
 principales problemas percibidos por la comunidad que utiliza el lenguaje.
 
 

+.. _dgc_bad_code:
+

 Complejidad del código y documentación
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 El análisis del código fue muy complicado debido a la falta de documentación
 Complejidad del código y documentación
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 El análisis del código fue muy complicado debido a la falta de documentación


@@ -1737,6 +1761,21 @@ recolector que permitan al usuario ajustarlo a las necesidades particulares de
 sus programas.
 
 
 sus programas.
 
 

+.. _dgc_bad_ocup:
+
+Factor de ocupación del *heap*
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+Otro problema potencialmente importante del recolector actual es que no se
+tiene ningún cuidado con respecto a que, luego de una recolección, se haya
+recuperado una buena parte del *heap*. Por lo tanto, en casos extremos, el
+recolector tiene que hacer una recolección por cada petición de memoria, lo
+que es extremadamente ineficiente.
+
+Para evitar esto, habría que usar algún esquema para evaluar cuando una
+recolección no fue lo suficientemente *exitosa* y en ese caso pedir más
+memoria al sistema operativo.
+
+

 Detalles
 ^^^^^^^^
 Finalmente hay varios detalles en la implementación actual que podrían
 Detalles
 ^^^^^^^^
 Finalmente hay varios detalles en la implementación actual que podrían