Implementación Malloc – Confundido

Estoy tratando de crear mi propio malloc () para la práctica. Tengo el código de abajo de este hilo.

typedef struct free_block { size_t size; struct free_block* next; } free_block; static free_block free_block_list_head = { 0, 0 }; // static const size_t overhead = sizeof(size_t); static const size_t align_to = 16; void* malloc(size_t size) { size = (size + sizeof(free_block) + (align_to - 1)) & ~ (align_to - 1); free_block* block = free_block_list_head.next; free_block** head = &(free_block_list_head.next); while (block != 0) { if (block->size >= size) { *head = block->next; return ((char*)block) + sizeof(free_block); } head = &(block->next); block = block->next; } block = (free_block*)sbrk(size); block->size = size; return ((char*)block) + sizeof(free_block); } void free(void* ptr) { free_block* block = (free_block*)(((char*)ptr) - sizeof(free_block )); block->next = free_block_list_head.next; free_block_list_head.next = block; } 

Estoy confundido acerca de tratar los trozos de memoria como una lista vinculada. Me parece que basicamente llamamos a sbrk () cada vez que necesitamos memoria y verificamos si parte de la memoria que solicitamos antes no se liberó mientras tanto.

Pero no tenemos forma de verificar otros fragmentos de memoria que pertenecen a otros procesos, solo verificamos la memoria que solicitamos antes y la agregamos a nuestra lista de enlaces.

Si este es el caso, ¿es esto óptimo? ¿Es así como funciona el estándar malloc ()? ¿Hay alguna manera de que trabajemos con toda la memoria en el montón?

Por favor explique que tengo 5 años, me cuesta mucho entender este concepto.

La extensión del segmento de datos de proceso no afecta a otros procesos. En la mayoría de las architectures (recientes), el modelo de memoria de proceso es plano, es decir, cada proceso tiene un espacio de direcciones virtual ( 2^32 o 2^64 bytes). Cuando el proceso solicita memoria adicional (página), se agrega una memoria virtual para procesar. De hecho, eso no significa que se produzca ninguna asignación de memoria física, ya que virtual memoria virtual puede asignarse a un archivo de intercambio o desasignarse antes de su uso total (la dirección se da para procesar, pero no se le asigna ningún recurso real). Kernel se encarga de asignar la dirección física a la virtual según la necesidad / la disponibilidad de recursos.

¿Qué hace el algoritmo?

Cuando el usuario llama a malloc el algoritmo intenta encontrar un bloque vacío disponible. Al principio, no hay ninguno, por lo que el algoritmo intenta extender el segmento de datos de proceso.

Sin embargo, puede ver que free no libera memoria virtual (ya que no es tan trivial como asignarla), en cambio, agrega este bloque released a una lista de bloques no utilizados.

Entonces, cuando hay bloques lanzados previamente , malloc intenta reutilizarlos en lugar de extender el segmento de datos.

Realice el trabajo estándar de malloc como se malloc arriba: no. El ejemplo que has proporcionado es simple, pero realmente ineficiente. Hay muchos algoritmos diferentes disponibles para la gestión de la memoria: pequeños bloques de bloques (cuando la asignación de datos hasta cierta cantidad tiene un rendimiento O(1) ), asignadores específicos de subprocesos (que reducen la congestión del acceso al montón de múltiples hilos), asignadores, que pre- asigne grandes porciones y luego utilícelas (similar a la anterior, pero aún más eficiente) y otras.

Puede intentar probar la “implementación del montón de memoria” para obtener más información