From: Leandro Lucarella Date: Mon, 15 Jun 2009 21:13:10 +0000 (-0300) Subject: Completar asignación de memoria del recolector actual X-Git-Tag: entrega-2010-10-08~47 X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/commitdiff_plain/ade63acf6c8d0abf0afa54e1eeb0f4fcc8f514e6?ds=sidebyside Completar asignación de memoria del recolector actual --- diff --git a/source/dgc.rst b/source/dgc.rst index f7e42ea..e12b9df 100644 --- a/source/dgc.rst +++ b/source/dgc.rst @@ -569,6 +569,180 @@ 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. + + .. _dgc_impl: