Фрагментация памяти
От: Dr.Gigabit  
Дата: 21.11.04 16:52
Оценка:
Hello all!
У Эккеля(Thinking in C++) проскакивает такая фраза:

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


Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
... << RSDN@Home 1.1.4 @@subversion >>
Re: Фрагментация памяти
От: _Winnie Россия C++.freerun
Дата: 21.11.04 17:30
Оценка: 4 (3) +1
Здравствуйте, Dr.Gigabit, Вы писали:

DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?


Сталкивался. В Debug-build игрушки, которая требовала около полутора гигабайт оперативки. Получил самый настоящий std::bad_alloc.
Надавали по рогам дизайнерам уровней.

В windows правильней говорить о фрагментации адресного пространства, а не самой памяти. OS может незаметно для приложения таскать блоки памяти размером 4096 байт туда-сюда, см. в MSDN как работает VirtualAlloc и свопинг.

В обычных приложениях с потребленим памяти 50-200 Мб. нужны довольно патологические синтетические тесты, что бы память не смогла выделится из-за фрагментации.

Примерно так: выдяем много "маленьких" блоков по мегабайту, так что они занимают почти все адресное пространство (да, при этом будет жестокий swap).
Вот так:
****************************************************************

Затем освобждаем так, что бы остались вот такие пустые блоки:
*      *     *      *      *    *      *   *         *         *

При попытке выделить такой "большой" блок
*********************************


попытка провалится, так как просто не будет адресного пространства, куда его поместить. Хотя в общей сумме места полно.
Обычно до этого момента программы не доходят, так как пользователь считает, что они зависли, и вырубает их.
Правильно работающая программа — просто частный случай Undefined Behavior http://rsdn.org/File/23256/catsmiley.gif
Re[2]: Фрагментация памяти
От: Dr.Gigabit  
Дата: 21.11.04 18:21
Оценка:
Здравствуйте, _Winnie, Вы писали:

_W>Здравствуйте, Dr.Gigabit, Вы писали:


DG>>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?


_W>Сталкивался. В Debug-build игрушки, которая требовала около полутора гигабайт оперативки. Получил самый настоящий std::bad_alloc.

_W>Надавали по рогам дизайнерам уровней.

... << RSDN@Home 1.1.4 @@subversion >>
Re: Фрагментация памяти
От: Шахтер Интернет  
Дата: 21.11.04 21:55
Оценка:
Здравствуйте, Dr.Gigabit, Вы писали:

DG>Hello all!

DG> У Эккеля(Thinking in C++) проскакивает такая фраза:

DG>

DG> В результате многочисленных операций выделения и освобождения памяти может произойти фрагментация: куча будет содержать много свободной памяти, но ни одного блока, размер которого был бы достаточен для удовлетворения текущего запроса.


DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?


Эта проблема может возникать при кривой реализации хипа. Если не ошибаюсь, в VC++ 5.0 такое было.
В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает.
... << RSDN@Home 1.1.0 stable >>
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re: Фрагментация памяти
От: kozlov_miass  
Дата: 22.11.04 04:38
Оценка:
DG> В результате многочисленных операций выделения и освобождения памяти может произойти фрагментация: куча будет содержать много свободной памяти, но ни одного блока, размер которого был бы достаточен для удовлетворения текущего запроса.
DG>[/q]

DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?


Бывает довольно часто если процесс длительный и происходит интенсивное выделение и освобождение памяти.
Лечиться переодическим вызовом функции _heapmin.
Re: Фрагментация памяти
От: TheCat Россия abokov.livejournal.com
Дата: 22.11.04 09:09
Оценка: 1 (1) +1
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?
Ситуация имеет место быть — при достаточно большом объеме памяти ( 2 Гб ) приложению фактически
требовалось ( суммарно ) около 400- 500 мб в каждый конкретный момент времени, но после некоторого
периода работы ( более 2 суток ) иногда возникала подобная ситуация когда new не мог выделить память из-за
отсутсвия свободного куска в 200 кб, при этом свободно было около 1 Гб. Решили проблему тем, что под наиболее часто выделяющиеся блоки фиксированного размера завели свой отдельный хип размером в ХХХ Мб.
Re[2]: Фрагментация памяти
От: Dr.Gigabit  
Дата: 22.11.04 17:15
Оценка:
Здравствуйте, 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.

... << RSDN@Home 1.1.4 @@subversion >>
Re[2]: Фрагментация не зависит от реализации
От: babur Россия  
Дата: 24.11.04 05:36
Оценка: +1
Ш>Эта проблема может возникать при кривой реализации хипа. Если не ошибаюсь, в VC++ 5.0 такое было.
Ш>В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает.

Не верно. При освобождении блока его соседи по памяти снизу и сверху могут быть заняты и этот блок не может быть ни с кем объединен.

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

Таким образом, для того чтобы дефрагментировать любую кучу до состояния когда она не способна разместить N байт достаточно в ней занять TotalMem / (N-1) байт памяти. Занятые байты должны следовать через каждые N-1 байт памяти. В соседнем посте написано как такое легко устроить.

Никакой компилятор вас не спасет.
Re[2]: _heapmin никого не спасет
От: babur Россия  
Дата: 24.11.04 05:44
Оценка:
_>Бывает довольно часто если процесс длительный и происходит интенсивное выделение и освобождение памяти.
_>Лечиться переодическим вызовом функции _heapmin.

_heapmin всего лишь вернет не используемую менеджером кучи память Вашей операционной системе. В противном случае она остается занята менеджером кучи и используется им при последующих к нему запросах.

_heapmin от фрагментации не спасает поскольку менеджер кучи не может выделить память по причине не нехватки физической памяти, а нехватки адресного пространства в куче при этом по видимому куча уже дальше расширена быть не может.
Re: Фрагментация памяти
От: babur Россия  
Дата: 24.11.04 06:03
Оценка:
DG>Кто нибудь с этим в реальных системах сталкивался? Или проблема носит чисто академический характер?

Фрагментация кучи реальна. Возникает из-за нехватки адресного пространства у менеджера кучи, то есть последовательного набора адресов памяти для размещения Вашего блока. Говорят, что адресное пространство менеджера кучи — дефрагментировано. При этом, по каким-то причинам, менеджер кучи не может расширить свое адресное пространство:
1. Либо в нем не предусмотрена такая возможность
2. Либо менеджер кучи может работать только в последовательном адресном пространтсве, то есть куча не может быть разбита на блоки.
3. Либо операционная система не дает больше адресного пространства менеджеру кучи.

Подавляющее большинство реализаций кучи не могут расширить свое адресное пространство во время очередного запроса исключительно по третьей причине.

Само же дефрагментирование адресного пространства внутри кучи может быть вызвано:
1. либо специфической проследовательностью вызовов аллокации/деаллокации блоков разного размера.
2. либо ошибками в менеджере кучи.

Была недавно ветка
Автор: babur
Дата: 18.10.04
про фрагментацию адресного пространства. Вывод был сделан такой: VS 5.0, менеджер кучи СRT при выделениях блоков больших 1к допускает образования фрагментации адресного пространства в кучи ПРИ СОВЕРШЕННО НОРМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫДЕЛЕНИЯ/ОСВОБОЖДЕНИЯ БЛОКОВ ПАМЯТИ.
Re[2]: Фрагментация памяти
От: babur Россия  
Дата: 24.11.04 06:10
Оценка:
TC>Решили проблему тем, что под наиболее часто выделяющиеся блоки фиксированного размера завели свой отдельный хип размером в ХХХ Мб.

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

Для примера:
VS5.0 СRT куча N=1К
Delphi5.0 куча N=4К

Если в Вашей программе существует большое количество мелких блоков все же превышающих этот N, используемого Вами менеджера то следует реализовать под эти блоки отдельную кучу.
Re[3]: Фрагментация не зависит от реализации
От: LaptevVV Россия  
Дата: 24.11.04 06:21
Оценка: -4
Здравствуйте, babur, Вы писали:

Ш>>Эта проблема может возникать при кривой реализации хипа. Если не ошибаюсь, в VC++ 5.0 такое было.

Ш>>В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает.

B>Не верно. При освобождении блока его соседи по памяти снизу и сверху могут быть заняты и этот блок не может быть ни с кем объединен.


B>Фрагментация возможна при любой реализации менеджера кучи, до тех пор пока менеджеру кучи запрещено двигать по своему усмотрению блоки занятой памяти. Но этого он делать не может иначе ссылки на эти блоки станут не валидными. Для того чтобы безопасно организовать такое движение менеджер кучи должен также обеспечивать проксирование доступа к памяти чего в его обязанности обычно не входит.

Ерунда! Ничего двигать не требуется. Во-первых, существует два давно известных метода борьбы с фрагментацией.
1. Метод Кнута (и Пряника ).
В этом метода каждый блок имеет в начале и конце меточку "занят-свободен". При освобождении блока смежные проверяются. Свободные — сливаются. Bad_alloc получается только в случае отсутствия возврата памяти.
2. Метод близнецов. Память выделяется блоками. кратными 2 (наименьшее кратное, большее запрошенного. Если такого блока нет — делится двойной блок на 2 (эти блоки называются близнецами — у них адрес различается на 1 бит) и один выделяется. При возврате близнецы объединяются.
Так что никакой фрагментации. Опять же bad_alloc получается. если память не возвращать.
B>Таким образом, для того чтобы дефрагментировать любую кучу до состояния когда она не способна разместить N байт достаточно в ней занять TotalMem / (N-1) байт памяти. Занятые байты должны следовать через каждые N-1 байт памяти. В соседнем посте написано как такое легко устроить.
B>Никакой компилятор вас не спасет.
Это только в случае кривой реализации — без слияния смежных блоков..
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[4]: Фрагментация не зависит от реализации
От: Вадим Никулин Россия Здесь
Дата: 24.11.04 06:33
Оценка:
Здравствуйте, LaptevVV, Вы писали:

B>>Таким образом, для того чтобы дефрагментировать любую кучу до состояния когда она не способна разместить N байт достаточно в ней занять TotalMem / (N-1) байт памяти. Занятые байты должны следовать через каждые N-1 байт памяти. В соседнем посте написано как такое легко устроить.

B>>Никакой компилятор вас не спасет.
LVV>Это только в случае кривой реализации — без слияния смежных блоков..

Нет. Советую еще раз перечитать это
Автор: _Winnie
Дата: 21.11.04
.
Re[4]: Фрагментация не зависит от реализации
От: babur Россия  
Дата: 24.11.04 06:41
Оценка:
LVV>Ерунда! Ничего двигать не требуется. Во-первых, существует два давно известных метода борьбы с фрагментацией.
LVV>1. Метод Кнута (и Пряника ).
LVV>2. Метод близнецов.

Это методы действительно известные, и борятся они действительно с фрагментацией и реально реализованы в менеджерах кучи. Но от всех ситуаций они не спасают. И при определенной последовательности выделения/освобождения блоков разных размеров фрагментация возникнет вне зависимости от реализации менеджера кучи.
Re[5]: Фрагментация не зависит от реализации
От: LaptevVV Россия  
Дата: 24.11.04 06:45
Оценка:
Здравствуйте, Вадим Никулин, Вы писали:

ВН>Здравствуйте, LaptevVV, Вы писали:


B>>>Таким образом, для того чтобы дефрагментировать любую кучу до состояния когда она не способна разместить N байт достаточно в ней занять TotalMem / (N-1) байт памяти. Занятые байты должны следовать через каждые N-1 байт памяти. В соседнем посте написано как такое легко устроить.

B>>>Никакой компилятор вас не спасет.
LVV>>Это только в случае кривой реализации — без слияния смежных блоков..

ВН>Нет. Советую еще раз перечитать это
Автор: _Winnie
Дата: 21.11.04
.

Да, читал — это все понятно. Но ведь в приведенном фрагменте запрашивается неизмеримо БОЛЬШЕ, чем возвращается. О чем я и упомянул в своем посте.
Во-вторых, как обычно, чтобы управляться с малентькими объектами лучше написать свой аллокатор — хотя бы такой как у Александреску. И работать быстрее будет и проблема фрагметации из=за маленьких объектов просто исчезнет.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[6]: Фрагментация не зависит от реализации
От: babur Россия  
Дата: 24.11.04 06:50
Оценка:
LVV>Да, читал — это все понятно. Но ведь в приведенном фрагменте запрашивается неизмеримо БОЛЬШЕ, чем возвращается. О чем я и упомянул в своем посте.

Естественно больше, а иначе как может наступить дефрагментация если менеджером почти вся память которая была запрошена уже освобождена. Дефрагментация удел граничных случаев — когда памяти вроде бы еще есть маленько, но выделить ее уже нельзя.

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


Обычно высокоуровневые менеджеры кучи (например CRT куча в VS) сами реализуют отдельное хранилище для мелких объектов, но это от проблемы не спасает, а только сужает круг потенциально опасных ситуаций.
Re[5]: Фрагментация не зависит от реализации
От: LaptevVV Россия  
Дата: 24.11.04 06:50
Оценка: +1
Здравствуйте, babur, Вы писали:

LVV>>Ерунда! Ничего двигать не требуется. Во-первых, существует два давно известных метода борьбы с фрагментацией.

LVV>>1. Метод Кнута (и Пряника ).
LVV>>2. Метод близнецов.

B>Это методы действительно известные, и борятся они действительно с фрагментацией и реально реализованы в менеджерах кучи. Но от всех ситуаций они не спасают. И при определенной последовательности выделения/освобождения блоков разных размеров фрагментация возникнет вне зависимости от реализации менеджера кучи.

Ну да, конечно — если сначала запрашивается ОЧЕНЬ МНОГО мелких блоков, потом возвращается част мелких блоков, но "в решетку". Тогда запрос БОЛЬШОГО блока — не проходит. Это понятно. ИМХО метод борьбы — написать свой аллокатор для мелких объектов.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[6]: Фрагментация не зависит от реализации
От: Вадим Никулин Россия Здесь
Дата: 24.11.04 08:56
Оценка: 1 (1)
Здравствуйте, LaptevVV, Вы писали:

B>>Это методы действительно известные, и борятся они действительно с фрагментацией и реально реализованы в менеджерах кучи. Но от всех ситуаций они не спасают. И при определенной последовательности выделения/освобождения блоков разных размеров фрагментация возникнет вне зависимости от реализации менеджера кучи.

LVV>Ну да, конечно — если сначала запрашивается ОЧЕНЬ МНОГО мелких блоков, потом возвращается част мелких блоков, но "в решетку". Тогда запрос БОЛЬШОГО блока — не проходит. Это понятно. ИМХО метод борьбы — написать свой аллокатор для мелких объектов.

Как? Аллокатор от Александреску не спасет от вышеуказанного случая. Он также будет хранить ту самую "решетку" в разных частях памяти. Единственный способ борьбы с таким эффектом — прокси объект вместо указателя и возможность менять реальное расположение объекта.
Re[7]: Фрагментация не зависит от реализации
От: LaptevVV Россия  
Дата: 24.11.04 11:45
Оценка:
Здравствуйте, Вадим Никулин, Вы писали:

ВН>Здравствуйте, LaptevVV, Вы писали:


B>>>Это методы действительно известные, и борятся они действительно с фрагментацией и реально реализованы в менеджерах кучи. Но от всех ситуаций они не спасают. И при определенной последовательности выделения/освобождения блоков разных размеров фрагментация возникнет вне зависимости от реализации менеджера кучи.

LVV>>Ну да, конечно — если сначала запрашивается ОЧЕНЬ МНОГО мелких блоков, потом возвращается част мелких блоков, но "в решетку". Тогда запрос БОЛЬШОГО блока — не проходит. Это понятно. ИМХО метод борьбы — написать свой аллокатор для мелких объектов.

ВН>Как? Аллокатор от Александреску не спасет от вышеуказанного случая. Он также будет хранить ту самую "решетку" в разных частях памяти. Единственный способ борьбы с таким эффектом — прокси объект вместо указателя и возможность менять реальное расположение объекта.

Просто у нас два разных аллокатора: для больших используем стандартный, для малых — свой. Конечно, гарантированно избежать фрагментации можно именно тем способом, что вы предлагаете. Но везде ли нужны АБСОЛЮТНЫЕ гарантии? А в случае наличия двух аллокаторов мы фрагментацию СУЩЕСТВЕННО уменьшаем. И попутно ускоряем работу с маленькими объектами.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[3]: Фрагментация не зависит от реализации
От: Шахтер Интернет  
Дата: 25.11.04 01:26
Оценка:
Здравствуйте, babur, Вы писали:

Ш>>Эта проблема может возникать при кривой реализации хипа. Если не ошибаюсь, в VC++ 5.0 такое было.

Ш>>В правильном хипе при освобождении блока он объединяется со свободными блоками-соседями. Проблема фрагментации памяти при этом не возникает.

B>Не верно. При освобождении блока его соседи по памяти снизу и сверху могут быть заняты и этот блок не может быть ни с кем объединен.


Читаем внимательно написанное.
... << RSDN@Home 1.1.0 stable >>
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.