Что такое фрагментация памяти?

Я слышал, как термин «фрагментация памяти» несколько раз использовался в контексте динамического выделения памяти в C ++. Я нашел несколько вопросов о том, как бороться с фрагментацией памяти, но не могу найти прямой вопрос, который касается самой этой проблемы. Так:

• Что такое фрагментация памяти?
• Как я могу определить, является ли фрагментация памяти проблемой для моего приложения? Какая программа больше всего страдает?
• Каковы хорошие распространенные способы борьбы с фрагментацией памяти?

Также:

• Я слышал, что использование динамических распределений может увеличить фрагментацию памяти. Это правда? Я понимаю, что в контексте C ++ все стандартные контейнеры (std :: string, std :: vector и т. Д.) Используют динамическое распределение памяти. Если они используются во всей программе (особенно std :: string), является ли проблема фрагментации памяти более вероятной?
• Как можно бороться с фрагментацией памяти в приложениях с интенсивным использованием STL?

Представьте, что у вас есть «большое» (32 байта) пространство свободной памяти:

----------------------------------
|                                |
----------------------------------

Теперь выделим некоторые из них (5 выделений):

----------------------------------
|aaaabbccccccddeeee              |
----------------------------------

Теперь освободите первые четыре распределения, но не пятое:

----------------------------------
|              eeee              |
----------------------------------

Теперь попробуйте выделить 16 байтов. Ой, я не могу, хотя там почти вдвое больше свободных.

В системах с виртуальной памятью фрагментация представляет собой меньшую проблему, чем вы думаете, потому что большие выделения должны быть непрерывными только в виртуальном адресном пространстве, а не в физическом адресном пространстве. Так что в моем примере, если бы у меня была виртуальная память с размером страницы 2 байта, я мог бы без проблем выполнить распределение в 16 байтов. Физическая память будет выглядеть так:

----------------------------------
|ffffffffffffffeeeeff            |
----------------------------------

тогда как виртуальная память (будучи намного больше) может выглядеть так:

------------------------------------------------------...
|              eeeeffffffffffffffff                   
------------------------------------------------------...

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

Тактика для предотвращения фрагментации памяти в C ++ работает путем выделения объектов из разных областей в соответствии с их размером и / или ожидаемым временем жизни. Поэтому, если вы собираетесь создать много объектов и затем уничтожить их все вместе, выделите их из пула памяти. Любые другие распределения, которые вы делаете между ними, не будут из пула, следовательно, не будут располагаться между ними в памяти, поэтому память не будет фрагментирована в результате.

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

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

Что такое фрагментация памяти?

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

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

Теперь представьте, что стена - это ваша (куча) памяти, а картинки - это объекты. Это фрагментация памяти.

Как я могу определить, является ли фрагментация памяти проблемой для моего приложения? Какая программа больше всего страдает?

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

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

Каковы хорошие распространенные способы борьбы с фрагментацией памяти?

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

Фрагментация памяти - это та же концепция, что и фрагментация диска: она относится к неиспользуемому пространству, потому что используемые области не собраны достаточно близко друг к другу.

Предположим для простого игрушечного примера, что у вас есть десять байтов памяти:

 |   |   |   |   |   |   |   |   |   |   |
   0   1   2   3   4   5   6   7   8   9

Теперь давайте выделим три трехбайтовых блока с именами A, B и C:

 | A | A | A | B | B | B | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Теперь освободите блок B:

 | A | A | A |   |   |   | C | C | C |   |
   0   1   2   3   4   5   6   7   8   9

Что произойдет, если мы попытаемся выделить четырехбайтовый блок D? Ну, у нас есть четыре байта свободной памяти, но у нас нет четырех смежных свободных байтов памяти, поэтому мы не можем выделить D! Это неэффективное использование памяти, потому что мы должны были хранить D, но мы не смогли. И мы не можем переместить C, чтобы освободить место, потому что очень вероятно, что некоторые переменные в нашей программе указывают на C, и мы не можем автоматически найти и изменить все эти значения.

Откуда ты знаешь, что это проблема? Ну, самый большой признак в том, что размер виртуальной памяти вашей программы значительно больше, чем объем памяти, который вы фактически используете. В реальном примере у вас было бы намного больше, чем десять байтов памяти, поэтому D просто выделялся бы, начиная с байта 9, а байты 3-5 оставались бы неиспользованными, если позже вы не выделите что-нибудь длиной три байта или меньше.

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

Как вы это предотвращаете? Наихудшие случаи, как правило, возникают, когда вы часто создаете и уничтожаете небольшие объекты, поскольку это имеет тенденцию вызывать эффект "швейцарского сыра", когда множество мелких объектов разделено множеством маленьких отверстий, что делает невозможным размещение более крупных объектов в этих отверстиях. Когда вы знаете, что собираетесь это делать, эффективная стратегия состоит в том, чтобы предварительно выделить большой блок памяти в качестве пула для ваших небольших объектов, а затем вручную управлять созданием небольших объектов в этом блоке, вместо того, чтобы Распределитель по умолчанию обрабатывать его.

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

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

• Что такое фрагментация памяти?

Фрагментация памяти - это проблема того, что память становится непригодной для использования, хотя она теоретически доступна. Существует два вида фрагментации: внутренняя фрагментация - это память, которая выделена, но не может использоваться (например, когда память выделяется в 8-байтовых блоках, но программа многократно выполняет отдельные операции, когда ей требуется всего 4 байта). Внешняя фрагментация - это проблема разделения свободной памяти на множество маленьких порций, так что большие запросы на выделение ресурсов не могут быть удовлетворены, хотя в целом достаточно свободной памяти.

• Как я могу определить, является ли фрагментация памяти проблемой для моего приложения? Какая программа больше всего страдает?

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

• Каковы хорошие распространенные способы борьбы с фрагментацией памяти?

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

• Пол Р. Уилсон, Марк С. Джонстон, Майкл Нили и Дэвид Болес. Динамическое распределение памяти: обзор и критический обзор. В материалах международного семинара 1995 года по управлению памятью, Springer Verlag LNCS, 1995
• Марк С. Джонстон, Пол Р. Уилсон. Проблема фрагментации памяти: решена? В уведомлениях ACM SIG-PLAN, том 34 № 3, стр. 26-36, 1999
• MR Garey, RL Graham и JD Ullman. Наихудший анализ алгоритмов выделения памяти. В четвертом ежегодном симпозиуме ACM по теории вычислений, 1972

Обновление:
Google TCMalloc: Malloc с кэшированием потоков
Было обнаружено, что он довольно хорошо справляется с фрагментацией в длительном процессе.

Я разрабатывал серверное приложение, в котором были проблемы с фрагментацией памяти в HP-UX 11.23 / 11.31 ia64.

Это выглядело так. Был процесс, который делал выделения памяти и освобождения и работал в течение нескольких дней. И хотя утечек памяти не было, потребление памяти процессом продолжало расти.

О моем опыте. В HP-UX очень легко обнаружить фрагментацию памяти с помощью HP-UX GDB. Вы устанавливаете точку останова, и когда вы нажимаете на нее, вы запускаете эту команду: info heapи видите все выделения памяти для процесса и общий размер кучи. Затем продолжите свою программу, а через некоторое время снова достигните точки останова. Вы делаете снова info heap. Если общий размер кучи больше, но количество и размер отдельных выделений одинаковы, вероятно, у вас есть проблемы с выделением памяти. При необходимости сделайте эту проверку несколько раз.

Мой способ улучшить ситуацию заключался в следующем. После того, как я провел некоторый анализ с HP-UX GDB, я увидел, что проблемы с памятью были вызваны тем, что я использовал std::vectorдля хранения некоторых типов информации из базы данных. std::vectorтребует, чтобы его данные были сохранены в одном блоке. У меня было несколько контейнеров на основе std::vector. Эти контейнеры были регулярно воссозданы. Часто возникали ситуации, когда новые записи добавлялись в базу данных, а затем контейнеры создавались заново. А так как воссозданные контейнеры были больше, они не помещались в доступные блоки свободной памяти, и среда выполнения запросила новый больший блок от ОС. В результате, несмотря на отсутствие утечек памяти, потребление памяти процессом возросло. Я улучшил ситуацию, когда менял контейнеры. Вместо того, чтобы std::vectorя начал использоватьstd::deque который имеет другой способ выделения памяти для данных.

Я знаю, что одним из способов избежать фрагментации памяти в HP-UX является использование Small Block Allocator или MallocNextGen. В RedHat Linux распределитель по умолчанию, кажется, довольно хорошо справляется с распределением множества маленьких блоков. На Windows есть Low-fragmentation Heapи она решает проблему большого количества небольших выделений.

Насколько я понимаю, в приложении, интенсивно использующем STL, вы должны сначала выявить проблемы. Распределители памяти (как в libc) на самом деле решают проблему большого количества небольших выделений, что типично для std::string(например, в моем серверном приложении есть много строк STL, но, как я вижу, info heapони не вызывают проблем). У меня сложилось впечатление, что вам нужно избегать частых крупных выделений. К сожалению, бывают ситуации, когда вы не можете избежать их и должны изменить свой код. Как я сказал в моем случае, я улучшил ситуацию, когда переключился на std::deque. Если вы определили фрагментацию вашей памяти, возможно, можно будет поговорить об этом более точно.

Фрагментация памяти наиболее вероятна, когда вы выделяете и освобождаете много объектов разных размеров. Предположим, у вас есть следующий макет в памяти:

obj1 (10kb) | obj2(20kb) | obj3(5kb) | unused space (100kb)

Теперь, когда obj2освобождается, у вас есть 120 КБ неиспользуемой памяти, но вы не можете выделить полный блок в 120 КБ, потому что память фрагментирована.

Обычные методы, позволяющие избежать этого эффекта, включают кольцевые буферы и пулы объектов . В контексте STL такие методы std::vector::reserve()могут помочь.

Очень подробный ответ о фрагментации памяти можно найти здесь.

http://library.softwareverify.com/memory-fragmentation-your-worst-nightmare/

Это кульминация 11-летних ответов о фрагментации памяти, которые я предоставляю людям, задающим мне вопросы о фрагментации памяти на softwareverify.com

Что такое фрагментация памяти?

Когда ваше приложение использует динамическую память, оно выделяет и освобождает куски памяти. В начале все пространство памяти вашего приложения представляет собой непрерывный блок свободной памяти. Однако, когда вы выделяете и освобождаете блоки различного размера, память начинает фрагментироваться , то есть вместо большого непрерывного свободного блока и количества смежных выделенных блоков будут смешиваться выделенные и свободные блоки. Поскольку свободные блоки имеют ограниченный размер, их сложно использовать повторно. Например, у вас может быть 1000 байтов свободной памяти, но вы не можете выделить память для 100-байтового блока, потому что все свободные блоки имеют длину не более 50 байтов.

Другой, неизбежный, но менее проблемный источник фрагментации состоит в том, что в большинстве архитектур адреса памяти должны быть выровнены с границами байтов 2, 4, 8 и т. Д. (Т. Е. Адреса должны быть кратны 2, 4, 8 и т. Д.). Это означает, что даже если у вас есть, например, структура, содержащая 3 charполя, ваша структура может иметь размер 12 вместо 3 из-за того, что каждое поле выровнено по 4-байтовой границе.

Как я могу определить, является ли фрагментация памяти проблемой для моего приложения? Какая программа больше всего страдает?

Очевидный ответ: вы получаете исключение нехватки памяти.

По-видимому, не существует хорошего портативного способа обнаружения фрагментации памяти в приложениях C ++. Смотрите этот ответ для более подробной информации.

Каковы хорошие распространенные способы борьбы с фрагментацией памяти?

Это сложно в C ++, поскольку вы используете прямые адреса памяти в указателях и не можете контролировать, кто ссылается на конкретный адрес памяти. Таким образом, перераспределение выделенных блоков памяти (как это делает сборщик мусора Java) не вариант.

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

Это супер упрощенная версия для чайников.

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

Если объект, который не находится в конце используемой части памяти, удален, то есть этот объект находился между двумя другими объектами, он создаст «дыру».

Это то, что называется фрагментацией.

Когда вы хотите добавить элемент в кучу, происходит следующее: компьютер должен выполнить поиск места, чтобы соответствовать этому элементу. Вот почему динамическое распределение, когда оно не выполняется в пуле памяти или с помощью распределенного пула, может «замедлить» процесс. Для тяжелых приложений STL, если вы выполняете многопоточность, есть распределитель Hoard или версия TBB Intel .

Теперь, когда память фрагментирована, могут произойти две вещи:

1. Должно быть больше поисков, чтобы найти хорошее место для размещения «больших» объектов. То есть, с множеством мелких объектов, разбросанных по поиску хорошего непрерывного куска памяти, при определенных условиях может быть сложно (это экстремально).
2. Память не легко читаемый объект. Процессоры ограничены тем, сколько они могут держать и где. Они делают это, меняя страницы, если нужный элемент находится в одном месте, а текущие адреса - в другом. Если вам постоянно приходится менять страницы, обработка может замедлиться (опять же, в экстремальных ситуациях, когда это влияет на производительность.) Посмотрите эту публикацию о виртуальной памяти .

Фрагментация памяти происходит потому, что запрашиваются блоки памяти разных размеров. Рассмотрим буфер в 100 байт. Вы запрашиваете два символа, затем целое число. Теперь вы освобождаете два символа, а затем запрашиваете новое целое число, но это число не может поместиться в пространство двух символов. Эта память не может быть повторно использована, потому что она не находится в достаточно большом непрерывном блоке для перераспределения. Кроме того, вы вызвали много накладных расходов для своих символов.

По сути, память поступает только в блоки определенного размера на большинстве систем. Как только вы разделите эти блоки, они не смогут присоединиться, пока не освободится весь блок. Это может привести к использованию целых блоков, когда фактически используется только небольшая часть блока.

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

Следует помнить, что в 32-битной настольной системе x86 у вас есть целых 2 ГБ памяти, которая разделена на 4 КБ «страницы» (почти наверняка размер страницы одинаков во всех системах x86). Вам придется вызвать некоторую фрагментацию omgwtfbbq, чтобы иметь проблему. Фрагментация на самом деле является проблемой прошлого, поскольку современные кучи чрезмерно велики для подавляющего большинства приложений, и существует преобладание систем, способных противостоять этому, таких как управляемые кучи.

Какая программа больше всего страдает?

Хорошим (= ужасающим) примером проблем, связанных с фрагментацией памяти, была разработка и выпуск "Elemental: War of Magic" , компьютерной игры от Stardock .

Игра была разработана для 32-битной / 2 ГБ памяти и должна была оптимизировать управление памятью, чтобы игра работала в этих 2 ГБ памяти. Поскольку «оптимизация» приводила к постоянному выделению и удалению, со временем происходила фрагментация кучи памяти и каждый раз происходил сбой игры .

На YouTube есть интервью "История войны" .