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

Question

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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