Hello all!
У Эккеля(Thinking in C++) проскакивает такая фраза:
В результате многочисленных операций выделения и освобождения памяти может произойти фрагментация: куча будет содержать много свободной памяти, но ни одного блока, размер которого был бы достаточен для удовлетворения текущего запроса.
Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
Сталкивался. В Debug-build игрушки, которая требовала около полутора гигабайт оперативки. Получил самый настоящий std::bad_alloc.
Надавали по рогам дизайнерам уровней.
В windows правильней говорить о фрагментации адресного пространства, а не самой памяти. OS может незаметно для приложения таскать блоки памяти размером 4096 байт туда-сюда, см. в MSDN как работает VirtualAlloc и свопинг.
В обычных приложениях с потребленим памяти 50-200 Мб. нужны довольно патологические синтетические тесты, что бы память не смогла выделится из-за фрагментации.
Примерно так: выдяем много "маленьких" блоков по мегабайту, так что они занимают почти все адресное пространство (да, при этом будет жестокий swap).
Вот так:
Затем освобждаем так, что бы остались вот такие пустые блоки:
* * * * * * * * * *
При попытке выделить такой "большой" блок
*********************************
попытка провалится, так как просто не будет адресного пространства, куда его поместить. Хотя в общей сумме места полно.
Обычно до этого момента программы не доходят, так как пользователь считает, что они зависли, и вырубает их.
Правильно работающая программа — просто частный случай Undefined Behavior
Здравствуйте, _Winnie, Вы писали:
_W>Здравствуйте, Dr.Gigabit, Вы писали:
DG>>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
_W>Сталкивался. В Debug-build игрушки, которая требовала около полутора гигабайт оперативки. Получил самый настоящий std::bad_alloc. _W>Надавали по рогам дизайнерам уровней.
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Hello all! DG> У Эккеля(Thinking in C++) проскакивает такая фраза:
DG>
DG> В результате многочисленных операций выделения и освобождения памяти может произойти фрагментация: куча будет содержать много свободной памяти, но ни одного блока, размер которого был бы достаточен для удовлетворения текущего запроса.
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
Эта проблема может возникать при кривой реализации хипа. Если не ошибаюсь, в VC++ 5.0 такое было.
В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает.
DG> В результате многочисленных операций выделения и освобождения памяти может произойти фрагментация: куча будет содержать много свободной памяти, но ни одного блока, размер которого был бы достаточен для удовлетворения текущего запроса. DG>[/q]
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
Бывает довольно часто если процесс длительный и происходит интенсивное выделение и освобождение памяти.
Лечиться переодическим вызовом функции _heapmin.
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
Ситуация имеет место быть — при достаточно большом объеме памяти ( 2 Гб ) приложению фактически
требовалось ( суммарно ) около 400- 500 мб в каждый конкретный момент времени, но после некоторого
периода работы ( более 2 суток ) иногда возникала подобная ситуация когда new не мог выделить память из-за
отсутсвия свободного куска в 200 кб, при этом свободно было около 1 Гб. Решили проблему тем, что под наиболее часто выделяющиеся блоки фиксированного размера завели свой отдельный хип размером в ХХХ Мб.
Здравствуйте, kozlov_miass, Вы писали:
DG>> В результате многочисленных операций выделения и освобождения памяти может произойти фрагментация: куча будет содержать много свободной памяти, но ни одного блока, размер которого был бы достаточен для удовлетворения текущего запроса. DG>>[/q]
DG>>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
_>Бывает довольно часто если процесс длительный и происходит интенсивное выделение и освобождение памяти. _>Лечиться переодическим вызовом функции _heapmin.
Note In Visual C++ version 4.0, the underlying heap structure was moved to the C run-time libraries to support the new debugging features. As a result, the only Win32 platform that is supported by _heapmin is Windows NT.
Ш>Эта проблема может возникать при кривой реализации хипа. Если не ошибаюсь, в VC++ 5.0 такое было. Ш>В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает.
Не верно. При освобождении блока его соседи по памяти снизу и сверху могут быть заняты и этот блок не может быть ни с кем объединен.
Фрагментация возможна при любой реализации менеджера кучи, до тех пор пока менеджеру кучи запрещено двигать по своему усмотрению блоки занятой памяти. Но этого он делать не может иначе ссылки на эти блоки станут не валидными. Для того чтобы безопасно организовать такое движение менеджер кучи должен также обеспечивать проксирование доступа к памяти чего в его обязанности обычно не входит.
Таким образом, для того чтобы дефрагментировать любую кучу до состояния когда она не способна разместить N байт достаточно в ней занять TotalMem / (N-1) байт памяти. Занятые байты должны следовать через каждые N-1 байт памяти. В соседнем посте написано как такое легко устроить.
_>Бывает довольно часто если процесс длительный и происходит интенсивное выделение и освобождение памяти. _>Лечиться переодическим вызовом функции _heapmin.
_heapmin всего лишь вернет не используемую менеджером кучи память Вашей операционной системе. В противном случае она остается занята менеджером кучи и используется им при последующих к нему запросах.
_heapmin от фрагментации не спасает поскольку менеджер кучи не может выделить память по причине не нехватки физической памяти, а нехватки адресного пространства в куче при этом по видимому куча уже дальше расширена быть не может.
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
Фрагментация кучи реальна. Возникает из-за нехватки адресного пространства у менеджера кучи, то есть последовательного набора адресов памяти для размещения Вашего блока. Говорят, что адресное пространство менеджера кучи — дефрагментировано. При этом, по каким-то причинам, менеджер кучи не может расширить свое адресное пространство:
1. Либо в нем не предусмотрена такая возможность
2. Либо менеджер кучи может работать только в последовательном адресном пространтсве, то есть куча не может быть разбита на блоки.
3. Либо операционная система не дает больше адресного пространства менеджеру кучи.
Подавляющее большинство реализаций кучи не могут расширить свое адресное пространство во время очередного запроса исключительно по третьей причине.
Само же дефрагментирование адресного пространства внутри кучи может быть вызвано:
1. либо специфической проследовательностью вызовов аллокации/деаллокации блоков разного размера.
2. либо ошибками в менеджере кучи.
про фрагментацию адресного пространства. Вывод был сделан такой: VS 5.0, менеджер кучи СRT при выделениях блоков больших 1к допускает образования фрагментации адресного пространства в кучи ПРИ СОВЕРШЕННО НОРМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫДЕЛЕНИЯ/ОСВОБОЖДЕНИЯ БЛОКОВ ПАМЯТИ.
TC>Решили проблему тем, что под наиболее часто выделяющиеся блоки фиксированного размера завели свой отдельный хип размером в ХХХ Мб.
Обычно менеджер кучи по разному подходит к выделению малых и больших блоков памяти. Малые блоки размером до N байт хранятся в отдельной области кучи. Обычно они там хранятся сгрупированные по их размеру. Сделано это как раз для того чтобы недопустить фрагментации адресного пространства кучи когда выделение/освобождение маленьких кусков происходит вперемежку с большими.
Для примера:
VS5.0 СRT куча N=1К
Delphi5.0 куча N=4К
Если в Вашей программе существует большое количество мелких блоков все же превышающих этот N, используемого Вами менеджера то следует реализовать под эти блоки отдельную кучу.
Здравствуйте, babur, Вы писали:
Ш>>Эта проблема может возникать при кривой реализации хипа. Если не ошибаюсь, в VC++ 5.0 такое было. Ш>>В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает.
B>Не верно. При освобождении блока его соседи по памяти снизу и сверху могут быть заняты и этот блок не может быть ни с кем объединен.
B>Фрагментация возможна при любой реализации менеджера кучи, до тех пор пока менеджеру кучи запрещено двигать по своему усмотрению блоки занятой памяти. Но этого он делать не может иначе ссылки на эти блоки станут не валидными. Для того чтобы безопасно организовать такое движение менеджер кучи должен также обеспечивать проксирование доступа к памяти чего в его обязанности обычно не входит.
Ерунда! Ничего двигать не требуется. Во-первых, существует два давно известных метода борьбы с фрагментацией.
1. Метод Кнута (и Пряника ).
В этом метода каждый блок имеет в начале и конце меточку "занят-свободен". При освобождении блока смежные проверяются. Свободные — сливаются. Bad_alloc получается только в случае отсутствия возврата памяти.
2. Метод близнецов. Память выделяется блоками. кратными 2 (наименьшее кратное, большее запрошенного. Если такого блока нет — делится двойной блок на 2 (эти блоки называются близнецами — у них адрес различается на 1 бит) и один выделяется. При возврате близнецы объединяются.
Так что никакой фрагментации. Опять же bad_alloc получается. если память не возвращать. B>Таким образом, для того чтобы дефрагментировать любую кучу до состояния когда она не способна разместить N байт достаточно в ней занять TotalMem / (N-1) байт памяти. Занятые байты должны следовать через каждые N-1 байт памяти. В соседнем посте написано как такое легко устроить. B>Никакой компилятор вас не спасет.
Это только в случае кривой реализации — без слияния смежных блоков..
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
B>>Таким образом, для того чтобы дефрагментировать любую кучу до состояния когда она не способна разместить N байт достаточно в ней занять TotalMem / (N-1) байт памяти. Занятые байты должны следовать через каждые N-1 байт памяти. В соседнем посте написано как такое легко устроить. B>>Никакой компилятор вас не спасет. LVV>Это только в случае кривой реализации — без слияния смежных блоков..
LVV>Ерунда! Ничего двигать не требуется. Во-первых, существует два давно известных метода борьбы с фрагментацией. LVV>1. Метод Кнута (и Пряника ). LVV>2. Метод близнецов.
Это методы действительно известные, и борятся они действительно с фрагментацией и реально реализованы в менеджерах кучи. Но от всех ситуаций они не спасают. И при определенной последовательности выделения/освобождения блоков разных размеров фрагментация возникнет вне зависимости от реализации менеджера кучи.
Здравствуйте, Вадим Никулин, Вы писали:
ВН>Здравствуйте, LaptevVV, Вы писали:
B>>>Таким образом, для того чтобы дефрагментировать любую кучу до состояния когда она не способна разместить N байт достаточно в ней занять TotalMem / (N-1) байт памяти. Занятые байты должны следовать через каждые N-1 байт памяти. В соседнем посте написано как такое легко устроить. B>>>Никакой компилятор вас не спасет. LVV>>Это только в случае кривой реализации — без слияния смежных блоков..
ВН>Нет. Советую еще раз перечитать это
.
Да, читал — это все понятно. Но ведь в приведенном фрагменте запрашивается неизмеримо БОЛЬШЕ, чем возвращается. О чем я и упомянул в своем посте.
Во-вторых, как обычно, чтобы управляться с малентькими объектами лучше написать свой аллокатор — хотя бы такой как у Александреску. И работать быстрее будет и проблема фрагметации из=за маленьких объектов просто исчезнет.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
LVV>Да, читал — это все понятно. Но ведь в приведенном фрагменте запрашивается неизмеримо БОЛЬШЕ, чем возвращается. О чем я и упомянул в своем посте.
Естественно больше, а иначе как может наступить дефрагментация если менеджером почти вся память которая была запрошена уже освобождена. Дефрагментация удел граничных случаев — когда памяти вроде бы еще есть маленько, но выделить ее уже нельзя.
LVV>Во-вторых, как обычно, чтобы управляться с малентькими объектами лучше написать свой аллокатор — хотя бы такой как у Александреску. И работать быстрее будет и проблема фрагметации из=за маленьких объектов просто исчезнет.
Обычно высокоуровневые менеджеры кучи (например CRT куча в VS) сами реализуют отдельное хранилище для мелких объектов, но это от проблемы не спасает, а только сужает круг потенциально опасных ситуаций.
Здравствуйте, babur, Вы писали:
LVV>>Ерунда! Ничего двигать не требуется. Во-первых, существует два давно известных метода борьбы с фрагментацией. LVV>>1. Метод Кнута (и Пряника ). LVV>>2. Метод близнецов.
B>Это методы действительно известные, и борятся они действительно с фрагментацией и реально реализованы в менеджерах кучи. Но от всех ситуаций они не спасают. И при определенной последовательности выделения/освобождения блоков разных размеров фрагментация возникнет вне зависимости от реализации менеджера кучи.
Ну да, конечно — если сначала запрашивается ОЧЕНЬ МНОГО мелких блоков, потом возвращается част мелких блоков, но "в решетку". Тогда запрос БОЛЬШОГО блока — не проходит. Это понятно. ИМХО метод борьбы — написать свой аллокатор для мелких объектов.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
B>>Это методы действительно известные, и борятся они действительно с фрагментацией и реально реализованы в менеджерах кучи. Но от всех ситуаций они не спасают. И при определенной последовательности выделения/освобождения блоков разных размеров фрагментация возникнет вне зависимости от реализации менеджера кучи. LVV>Ну да, конечно — если сначала запрашивается ОЧЕНЬ МНОГО мелких блоков, потом возвращается част мелких блоков, но "в решетку". Тогда запрос БОЛЬШОГО блока — не проходит. Это понятно. ИМХО метод борьбы — написать свой аллокатор для мелких объектов.
Как? Аллокатор от Александреску не спасет от вышеуказанного случая. Он также будет хранить ту самую "решетку" в разных частях памяти. Единственный способ борьбы с таким эффектом — прокси объект вместо указателя и возможность менять реальное расположение объекта.
Здравствуйте, Вадим Никулин, Вы писали:
ВН>Здравствуйте, LaptevVV, Вы писали:
B>>>Это методы действительно известные, и борятся они действительно с фрагментацией и реально реализованы в менеджерах кучи. Но от всех ситуаций они не спасают. И при определенной последовательности выделения/освобождения блоков разных размеров фрагментация возникнет вне зависимости от реализации менеджера кучи. LVV>>Ну да, конечно — если сначала запрашивается ОЧЕНЬ МНОГО мелких блоков, потом возвращается част мелких блоков, но "в решетку". Тогда запрос БОЛЬШОГО блока — не проходит. Это понятно. ИМХО метод борьбы — написать свой аллокатор для мелких объектов.
ВН>Как? Аллокатор от Александреску не спасет от вышеуказанного случая. Он также будет хранить ту самую "решетку" в разных частях памяти. Единственный способ борьбы с таким эффектом — прокси объект вместо указателя и возможность менять реальное расположение объекта.
Просто у нас два разных аллокатора: для больших используем стандартный, для малых — свой. Конечно, гарантированно избежать фрагментации можно именно тем способом, что вы предлагаете. Но везде ли нужны АБСОЛЮТНЫЕ гарантии? А в случае наличия двух аллокаторов мы фрагментацию СУЩЕСТВЕННО уменьшаем. И попутно ускоряем работу с маленькими объектами.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, babur, Вы писали:
Ш>>Эта проблема может возникать при кривой реализации хипа. Если не ошибаюсь, в VC++ 5.0 такое было. Ш>>В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает.
B>Не верно. При освобождении блока его соседи по памяти снизу и сверху могут быть заняты и этот блок не может быть ни с кем объединен.
Читаем: Ш>>>В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает .
Я утверждаю, что фрагментация памяти при этом возникает (потому что не всегда есть свободные блоки сверху или снизу). Кривость написания кучи тут не при чем. Не существует алгоритма полностью устраняющего фрагментацию до тех пор пока куча не проксирует доступ к памяти и не может перемещать выделенные куски памяти по своему усмотрению.
Вывод был сделан такой: VS 5.0, менеджер кучи СRT при выделениях блоков больших 1к допускает образования фрагментации адресного пространства в кучи ПРИ СОВЕРШЕННО НОРМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫДЕЛЕНИЯ/ОСВОБОЖДЕНИЯ БЛОКОВ ПАМЯТИ.
Интересный вывод... Все-таки судя по топику, 100%-ных оснований нет. Или я не прав?
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Hello all! DG> У Эккеля(Thinking in C++) проскакивает такая фраза:
DG>
DG> В результате многочисленных операций выделения и освобождения памяти может произойти фрагментация: куча будет содержать много свободной памяти, но ни одного блока, размер которого был бы достаточен для удовлетворения текущего запроса.
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
Да, сталкивался. Правда, в мс-дос, т.е. 640к памяти
Здравствуйте, babur, Вы писали:
Ш>>Читаем внимательно написанное.
B>Читаем: Ш>>>>В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает .
B>Я утверждаю, что фрагментация памяти при этом возникает (потому что не всегда есть свободные блоки сверху или снизу). Кривость написания кучи тут не при чем. Не существует алгоритма полностью устраняющего фрагментацию до тех пор пока куча не проксирует доступ к памяти и не может перемещать выделенные куски памяти по своему усмотрению.
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Здравствуйте, babur, Вы писали:
DG>Вывод был сделан такой: VS 5.0, менеджер кучи СRT при выделениях блоков больших 1к допускает образования фрагментации адресного пространства в кучи ПРИ СОВЕРШЕННО НОРМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫДЕЛЕНИЯ/ОСВОБОЖДЕНИЯ БЛОКОВ ПАМЯТИ.
DG>Интересный вывод... Все-таки судя по топику, 100%-ных оснований нет. Или я не прав?
В VC 5.0 CRT делала так. Если происходило освобождение блока памяти, то он не объединялся немедленно со свободными соседями. Это процесс (подчистки хипа) запускался только при определённых условиях (то ли при нехватке памяти, то ли при каких-то иных, сейчас точно уже не помню). Такая реализация приводила к сильной фрагментации кучи.
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
На Dinkumware std::queue при интенсивной работе со многими очередями (при чём более 50 элементов ни в
одной из них одновременно не находилось, и очередей не более 100) получал bad_alloc довольно часто.
Вылечилось переходом на STLPort
