Я хотел бы выделить огромную динамическую память, а затем написать для себя свой собственный менеджер памяти. Т.е. когда и когда мой код нуждается в памяти, я бы выделил из этого пула памяти. Я хочу, чтобы алгоритм заботился о внутренней и внешней фрагментации. Каков наиболее эффективный алгоритм для этого?написать собственный менеджер памяти
Для этих критериев я бы пошел с http://g.oswego.edu/dl/html/malloc.html Doug Lea, в котором хранятся коллекции блоков хранения для каждого из разных размеров - это быстрый поиск нужного вам размера, а повторное использование блоков одного размера уменьшает фрагментацию , Примечание (http://entland.homelinux.com/blog/2008/08/19/practical-efficient-memory-management/), что это НЕ настроено для многопоточности.
Если бы я сам писал, я бы пошел на http://en.wikipedia.org/wiki/Buddy_memory_allocation, потому что он быстро и не используется в пространстве пользователя (обычно не используется, поскольку он ограничивает возможные размеры блоков, что приводит к внутренней фрагментации). Фактически, я сделал, некоторое время назад - http://www.mcdowella.demon.co.uk/buddy.html
Этот вопрос является неоднозначным, потому что термин «наиболее эффективный» не ясен. Вы не говорите, на каких условиях это должно быть наиболее эффективным.
В качестве примера: существует стратегия, называемая первой посадкой, которая может быть быстрее, чем лучше всего подходит, но может привести к большей фрагментации кучи (очень плохо). Лучшая подгонка, с другой стороны, несколько уменьшает внешнюю фрагментацию, но все еще страдает от нее, в то время как найти кусок свободной памяти занимает больше времени. Существует также стратегия, называемая кустарником, где вы не страдаете от внешней фрагментации, а от внутренней фрагментации. Но по крайней мере найти свободный блок, как правило, быстро там.
Вы видите, что выбор алгоритма зависит от ваших требований. Должно ли распределение быть быстрым или фрагментация низкая? Каково поведение распределения? Существуют ли небольшие неравномерные куски, выделенные и освобождаемые часто или только большие куски? И здесь есть еще больше факторов.
Возможно, вы хотели получить такой ответ. Если нет, я рекомендую вам уточнить ваши требования.
Да, лучше всего подходят, система первого соответствия и приятеля - это 3 алгоритма, которые могут использоваться каждый со своими достоинствами и недостатки. Требование состоит в том, чтобы иметь быстрое распределение и низкую фрагментацию. Возможно, я должен написать таким образом, что я называю разные алгоритмы в разных сценариях. – linuxfreak
@linuxfreak Вы можете делать то, что делает linux, например, и использовать кучу приятелей для получения «больших кусков», которые имеют размеры 2 и используют что-то вроде первой, подходящей для небольших кусков. Существует также статья Дж. М. Робсона («Границы для некоторых функций, связанных с распределением динамической памяти»), которая доказывает, что проблемы фрагментации не будут возникать, если размер распределения находится в определенном соотношении с наименьшим фрагментом, который может быть выделен. (конечно, только проблема нехватки свободного места в одном блоке для распределения, а не потеря памяти из-за внутренней фрагментации) – junix
@linuxfreak Но все же остается вопрос: можете ли вы сделать предположения о поведении распределения? Этот фактор оказывает большое влияние на выбор/проектирование распределителя. Как пример: если вы знаете, что все выделенные фрагменты имеют одинаковый размер, вы могли бы реализовать очень быстрый распределитель, используя «список свободных кусков». – junix
Лучший алгоритм? –
http://stackoverflow.com/faq#questions – Krishnabhadra
@ Krishnabhadra Часто задаваемые вопросы говорят, что это по теме: «программный алгоритм». – fuz