Примеры или документация для специализированного распределителя хранилища в c?

Question

Я выделяю большую область памяти, чтобы сказать x из 1000 байтов.

// I am using c language and all of this is just pseudo code(function prototypes mostly) so far. 
pointer = malloc(size(1000 units)); // this pointer points to region of memory we created. 

теперь выбрать эту область с помощью указателя и выделить память внутри него на более мелкие блоки, как

void *allocate_from_region(size_of_block1(300)); //1000-300=700 (left free) 
void *allocate_from_region(size_of_block2(100)); //700-100 =600 
void *allocate_from_region(size_of_block3(300)); //600-300 =300 
void *allocate_from_region(size_of_block4(100)); //300-100 =200 
void *allocate_from_region(size_of_block5(150)); //200-150 =50 
// here we almost finished space we have in region (only 50 is left free in region) 


boolean free_from_region(pointer_to_block2);  //free 100 more 
//total free = 100+50 but are not contiguous in memory 

void *allocate_from_region(size_of_block6(150)); // this one will fail and gives null as it cant find 150 units memory(contiguous) in region. 

boolean free_from_region(pointer_to_block3); // this free 300 more so total free = 100+300+50 but contiguous free is 100+300 (from block 2 and 3) 

void *allocate_from_region(size_of_block6(150); // this time it is successful 

Есть ли какие-либо примеры о том, как управлять памятью, как это?

До сих пор я делал только примеры, где я мог бы размещать блоки рядом друг с другом в области памяти и заканчивать его, как только у меня закончится память внутри региона. Но как искать блоки, свободные внутри области, а затем проверить, имеется ли достаточная непрерывная память. Я уверен, что в c должна быть какая-то документация или примеры, в которых показано, как это сделать.

Answer 1

Несомненно. То, что вы предлагаете, более или менее точно соответствует некоторым реализациям malloc. Они поддерживают «бесплатный список». Изначально один большой блок находится в этом списке. Когда вы делаете запрос, алгоритм выделить п байт:

search the free list to find a block at B of size m >= n 
Remove B from the free list. 
Return the block from B+n through B+m-1 (size m-n) to the free list (unless m-n==0) 
Return a pointer to B 

Чтобы освободить блок в B размера п, мы должны положить его обратно в свободный список. Однако это еще не конец. Мы также должны «объединять» его со смежными свободными блоками, если они есть, либо выше, либо ниже, или и то, и другое. Это алгоритм.

Let p = B; m = n; // pointer to base and size of block to be freed 
If there is a block of size x on the free list and at the address B + n, 
    remove it, set m=m+x. // coalescing block above 
If there is a block of size y on the free list and at address B - y, 
    remove it and set p=B-y; m=m+y; // coalescing block below 
Return block at p of size m to the free list. 

Оставшийся вопрос состоит в том, чтобы создать свободный список, чтобы сделать это быстро, чтобы найти блоки нужного размера во время распределения и найти соседние блоки для коалесценции во время бесплатных операций. Самый простой способ - это одиночный список. Но существует много возможных альтернатив, которые могут обеспечить лучшую скорость, как правило, при некоторой стоимости дополнительного пространства для структур данных.

Кроме того, существует выбор того, какой блок выделить, когда более одного достаточно большого. Обычный выбор - это «первое соответствие» и «наилучшее соответствие». Для первой подгонки просто возьмите первый из них. Часто лучший метод (вместо того, чтобы начинать с самых низких адресов каждый раз) запоминать свободный блок после только что выделенного и использовать его в качестве отправной точки для следующего поиска. Это называется «вращающейся первой посадкой».

Для достижения наилучшего соответствия, пойдите, пересечь столько блоков, сколько необходимо, чтобы найти тот, который наиболее точно соответствует требуемому размеру.

Если распределения случайны, первое соответствие фактически выполняет бит лучше, чем лучше всего подходит в терминах фрагментации памяти. Фрагментация - это ошибка всех некомпактных распределителей.