X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/8554af7b6c3350a7bd644661868b38aa4fdb924e..ade63acf6c8d0abf0afa54e1eeb0f4fcc8f514e6:/source/dgc.rst?ds=sidebyside diff --git a/source/dgc.rst b/source/dgc.rst index dc32223..e12b9df 100644 --- a/source/dgc.rst +++ b/source/dgc.rst @@ -494,7 +494,253 @@ dividirse en dos pasos básicos:: sweep() rebuild_free_lists() -El barrido se realiza con una pasada por sobre todo el heap +El barrido se realiza con una pasada por sobre todo el *heap* de la siguiente +manera:: + + function sweep() is + foreach pool in heap + foreach page in pool + if page.block_size <= PAGE // saltea FREE y CONTINUATION + foreach block in page + if block.mark is false + if block.final is true + finalize(block) + block.free = true + block.final = false + block.noscan = false + if page.block_size is PAGE // objeto grande + free_big_object(pool, page) + +Como se observa, se recorre todo el *heap* en busca de bloques y páginas +libres. Los bloques libres son marcados con el atributo ``free`` y las páginas +libres son marcadas con el tamaño de bloque simbólico ``FREE``. Para los +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 + page = cast(byte*) page + PAGE_SIZE + page.block_size = FREE + while page.block_size is CONTINUATION and page < pool_end + +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 +biblioteca *runtime* y en última instancia llama al destructor del objeto +almacenado en el bloque a liberar. + +Una vez marcados todos los bloques y páginas como libre, se procede +a reconstruir las listas de libres. En el proceso buscan las páginas que +tengan todos los bloques libres para marcar la página completa como libre (de +manera que pueda utilizarse para albergar otro tamaño de bloque u objetos +grandes de ser necesario):: + + function rebuild_free_lists() is + foreach free_list in heap + free_list.clear() + foreach pool in heap + foreach page in pool + if page.block_size < PAGE // objetos pequeños + if is_page_free(page) + page.block_size = FREE + else + foreach block in page + if block.free is true + free_lists[page.block_size].link(block) + +Esta reorganización de listas libres además mejoran la localidad de +referencia y previenen la fragmentación. La localidad de referencia se ve +mojorada debido a que asignaciones de memoria proximas en el tiempo serán +también próximas en espacio porque pertenecerán a la misma página (al menos si +las asignaciones son todas del mismo tamaño). La fragmentación se minimiza por +el mismo efecto, primero se asignarán todos los bloques de la misma página. + +A continuación se presenta la implementación de una de las funciones +suplementarias de la fase de barrido:: + + function is_page_free(page) is + foreach block in page + if block.free is false + return false + return true + +Las demás funciones suplementarias pertenecen a la manipulación de listas +libres que no son más que operaciones sobre una lista simplemente enlazada. En +la sección :ref:`dgc_impl` se verá con más detalles como las implementa el +recolector actual. + + +.. _dgc_algo_alloc: + +Asignación de memoria +^^^^^^^^^^^^^^^^^^^^^ +La asignación de memoria del recolector es relativamente compleja, excepto +cuando se asgina un objeto pequeño y ya existe algún bloque con el tamaño +preciso en la lista de libres. Para el resto de los casos la cantidad de +trabajo que debe hacer el recolector para asignar la memoria es considerable. + +El algoritmo de asignación de memoria se puede resumir así:: + + function new(size, attrs) is + block_size = find_block_size(size) + if block_size < PAGE + block = new_small(block_size) + else + block = new_big(size) + if block is null + throw out_of_memory + if final in attrs + block.final = true + if noscan in attrs + block.noscan = true + return cast(void*) block + +La función ``find_block_size()`` sencillamente busca el tamaño de bloque se +mejor se ajuste al tamaño solicitado (es decir, el bloque más pequeño lo +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 +asginan de las siguiente manera:: + + 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 + new_pool() + block = find_block_with_size(block_size) + return null + 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 +una :ref:`recolección ` y si no se puede encontrar +suficiente espacio luego de ella se intenta crear un nuevo *pool* de memoria +pidiendo memoria al *low level allocator* (el sistema operativo generalmente). + +Para intentar buscar un bloque de memoria libre se realiza lo siguiente:: + + 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() + 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:: + + 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*:: + + 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 + +Se recuerda que la función ``alloc()`` es un :ref:`servicio +` provisto por el *low level allocator* y en la +implementación actual de D_ en general es el sistema operativo (aunque +opcionalmente puede utilizarse la biblioteca estándar de C, que a su vez +utiliza el sistema operativo). + +Cualquier error en estas funciones es propagado y en última instancia, cuando +todo falla, la función ``new()`` termina lanzando una excepción indicando que +se agotó la memoria. + +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:: + + 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 + 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 contíguas, dentro de un mismo *pool*, suficientes para +almacenar el tamaño requerido y si esto falla, se realizan diferentes pasos +y se vuelve a intentar. Puede observarse que, a diferencia de la asignación de +objetos pequeños, si luego de la recolección no se pudo encontrar lugar +suficiente, se trata de minimizar el uso de memoria física utilizando la +siguiente función, que devuelve al *low level allocator* los *pools* +completamente libres:: + + function minimize() is + for pool in heap + all_free = true + for page in pool + if page.block_size is not FREE + all_free = false + break + if all_free is true + free(pool.pages) + free(pool) + heap.remove(pool) + +Volviendo a la función ``new_big()``, para hallar una serie de páginas +contíguas 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 + +Como se dijo, las páginas deben estar contenidas en un mismo *pool* (para +tener la garantía de que sean contíguas), 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] + 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 +suficientes como para almacenar el objeto grande y si esto falla el error se +propaga hasta la función ``new()`` que lanza una excepción.