Ответ 1
Там довольно много хорошей литературы по реализации malloc и подобных вещей. но я замечаю, что вы включили С++ здесь - знаете ли вы, что вы можете написать собственную реализацию new и delete в С++? Это может быть полезно как способ сделать это легко.
В любом случае характеристики, которые вы хотите, будут в значительной степени зависеть от вашей рабочей нагрузки, то есть от характера использования с течением времени. Очевидно, что если у вас есть только mallocs и новые frees, это легко. Если у вас есть только mallocs одного или нескольких разных размеров блоков, это также просто.
В других языках вы получаете некоторый рычаг, имея возможность объединять память вместе, но C не настолько умный.
Основная реализация malloc просто выделяет заголовок, который содержит длину данных, "флаг использования" и многоязычную память. Затем Malloc создает новый заголовок в конце своего пространства, выделяет память и возвращает указатель. Когда вы освобождаете, он просто сбрасывает флаг использования.
Фокус в том, что, когда вы делаете много mallooc и бесплатно, вы можете быстро получить много небольших капель, которые не используются, но их сложно выделить. Таким образом, вам нужен какой-то bumpo gc для объединения блоков памяти.
Вы можете сделать более сложный gc, но помните, что это требует времени; вы не хотите свободно занимать много времени.
Там хорошая бумага в реализациях Solaris malloc, которые могут показаться вам интересными. Здесь еще один при создании альтернативного malloc, снова в Solaris, но основы те же. И вы должны прочитать статью Википедии о сборе мусора и следовать ей в некоторых более официальных документах.
Update
Вы знаете, вам действительно нужно взглянуть на коллекционеров мусора поколения. Основная идея заключается в том, что чем дольше что-то остается выделенным, тем более вероятно, что он останется выделенным. Это расширение упоминаемого вами "копирующего" GC. В принципе, вы выделяете новые вещи в одной части вашего пула памяти, назовите его g0. Когда вы достигнете отметки высокой воды, просмотрите выделенные блоки и скопируйте те, которые все еще используются в другой раздел памяти, назовите его g1. Затем вы можете просто очистить пространство g0 и начать выделение там. В конце концов g1 попадает на свой знак высокой воды, и вы исправляете это, очищая g0 и очищая g1, перемещая материал до g0, и когда вы закончите, вы переименуете старый g1 как g0 и наоборот и продолжаете.
Фокус в том, что в C особенно ручки, которые вы передаете в память malloc'ed, являются прямыми исходными указателями; вы не можете реально перемещать вещи без кучи большого лекарства.
Второе обновление
В комментариях @unknown спрашивает: "Не будет ли перемещение вокруг просто memcpy()". И действительно. но рассмотрите эту временную шкалу:
предупреждение: это не полная и непроверенная, просто для иллюстрации, только для развлечений, без явной или подразумеваемой гарантии
/* basic environment for illustration*/
void * myMemoryHdl ;
unsigned char lotsOfMemory[LOTS]; /* this will be your memory pool*/
Вы разделяете память
/* if we get past this, it succeded */
if((myMemoryHdl = newMalloc(SIZE)) == NULL)
exit(-1);
В вашей реализации malloc вы создаете память и возвращаете указатель на буфер.
unsigned char * nextUnusued = &lotsOfMemory[0];
int partitionSize = (int)(LOTS/2);
int hwm = (int) (partition/2);
/* So g0 will be the bottom half and g1 the top half to start */
unsigned char * g0 = &lotsOfMemory[0];
unsigned char * g1 = &lotsOfMemory[partitionSize];
void * newMalloc(size_t size){
void * rtn ;
if( /* memory COMPLETELY exhausted */)
return NULL;
/* otherwise */
/* add header at nextUnused */
newHeader(nextUnused); /* includes some pointers for chaining
* and a field with values USED or FREE,
* set to USED */
nextUnused += HEADERLEN ; /* this could be niftier */
rtn = nextUnused ;
nextUnused += size ;
}
Некоторые вещи освобождены
newFree(void * aHandle){
*(aHandle-offset) = FREE ; /* set the flag in the header,
* using an offset. */
}
Итак, теперь вы делаете все, и вы попадаете на свой знак высокой воды.
for( /* each block in your memory pool */ )
if( /* block header is still marked USED */ ) {
memcpy(/* block into other partition */);
}
/* clear the partition */
bzero(g0, partitionSize);
Теперь вернитесь к исходному дескрипту, сохраненному в myMemHdl. На что это указывает? (Ответ. Вы просто установили его в 0x00 с помощью bzero (3).)
То, где приходит волшебство. По крайней мере на C указатель, который вы вернули из вашего malloc, больше не находится под вашим контролем - вы не можете его перемещать после факта. В С++ с определенными пользователем типами указателей вы можете исправить это.