Работа с фрагментацией в пуле памяти?

Предположим, что у меня есть объект пула памяти с конструктором, который берет указатель на большой кусок памяти ptr и размер N. Если я делаю много случайных выделений и освобождений различных размеров, я могу получить память в таком состоянии, что я не могу выделить объект M байт последовательно в памяти, даже если там может быть много свободного места! В то же время я не могу сжать память, потому что это вызовет болтающийся указатель на потребителях. Как можно разрешить фрагментацию в этом случае?

5 13
c++ pool fragmentation

5 ответов:

Я хотел добавить свои 2 цента только потому, что никто другой не указал, что из вашего описания это звучит так, как будто вы реализуете стандартный распределитель кучи (то есть то, что все мы уже используем каждый раз, когда мы вызываем malloc() или operator new).

Куча-это именно такой объект, который отправляется в диспетчер виртуальной памяти и запрашивает большой кусок памяти (то, что вы называете "пулом"). Тогда он имеет все виды различных алгоритмов для работы с наиболее эффективным способом распределения различных размеров куски и освобождение их. Кроме того, многие люди модифицировали и оптимизировали эти алгоритмы на протяжении многих лет. Долгое время Windows была снабжена опцией под названием Low-fragmentation heap (LFH), которую приходилось включать вручную. Начиная с Vista LFH используется для всех куч по умолчанию.

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

При выделении памяти единственный раз, когда вы можете повысить производительность, не просто используя кучу, - это отказаться от некоторых других аспектов (накладные расходы на выделение, продолжительность жизни распределения....) что не важно для вашего конкретного приложения.

Например, в нашем приложении мы имели требование для многих выделений менее 1 КБ, но эти выделения использовались только в течение очень коротких периодов времени (миллисекунд). Для оптимизации приложения я использовал библиотеку пула Boost, но расширил ее так, что мой "распределитель" фактически содержал коллекцию объектов пула boost, каждый из которых отвечал за выделение одного определенного размера от 16 байт до 1024 (в шагах 4). Это обеспечило почти свободное(O (1) сложность) выделение / свободное от этих объектов, но загвоздка в том, что a) использование памяти всегда велико и никогда не уменьшается, даже если у нас нет ни одного выделенного объекта, b) Boost Pool никогда не освобождает память, которую он использует (по крайней мере, в режиме, в котором мы его используем), поэтому мы используем это только для объектов, которые не задерживаются очень долго.

Итак, от какого аспекта(ов) нормального распределения памяти вы готовы отказаться в своем приложении?

8

В зависимости от системы есть несколько способов сделать это.

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

Другим способом является передача указателей на указатели ваших данных (например, int **). Затем вы можете переупорядочить память под программой (потокобезопасно, я надеюсь) и сжать распределение так, чтобы вы могли выделять новые блоки и все еще хранить данные из старых блоков (как только система достигает этого состояния, хотя это становится тяжелым бременем, но редко должно быть сделано).

Существуют также способы "привязки" памяти так, чтобы у вас были смежные страницы, например, выделите только 1 страницу выделениям 512 и меньше, другим по 1024 и меньше и т.д... Это облегчает принятие решений о том, какую ячейку использовать, и в худшем случае вы разделяете из следующей самой высокой ячейки или объединяете из нижней ячейки, что уменьшает вероятность фрагментации по нескольким страницам.

6

Реализацияпулов объектов для объектов, которые вы часто выделяете, значительно снизит фрагментацию без необходимости менять распределитель памяти.

3

Было бы полезно знать более точно, что вы на самом деле пытаетесь сделать, потому что есть много способов справиться с этим.
Но первый вопрос: происходит ли это на самом деле, или это теоретическая проблема?

Следует иметь в виду, что обычно адресное пространство виртуальной памяти намного больше, чем физическая память, поэтому, даже если физическая память фрагментирована, все равно остается много непрерывной виртуальной памяти. (Конечно, физическая память-это неразрывно внизу, но ваш код этого не видит.)

Я думаю, что иногда существует неоправданный страх фрагментации памяти, и в результате люди пишут пользовательский распределитель памяти (или хуже, они придумывают схему с дескрипторами и подвижной памятью и уплотнением). Я думаю, что они редко нужны на практике, и иногда можно улучшить производительность, чтобы выбросить это и вернуться к использованию malloc.
1
  • Запишите пул для работы в виде списка выделений, который затем можно расширить и уничтожить по мере необходимости. это может уменьшить фрагментацию.
  • и / или реализовать поддержку переноса распределения (или перемещения), чтобы можно было компактировать активные распределения. объект / держатель может помочь вам, так как пул не обязательно знает, как передавать типы самостоятельно. если пул используется с типом коллекции, то гораздо проще выполнить сжатие / перенос.
0