Метод граничных маркеров (Boundary markers)

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

Алгоритм граничных маркеров хорошо подходит под выделение объектов произвольной длины, для сегмента же кода обычно используют другие алгоритмы. Алгоритм описан в книге Дэвида Кнута "Искусство программирование часть 1".

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

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

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

Выделение

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

· первый подходящий

· наилучший подходящий

· наихудший подходящий - в этом случае берется наибольший блок и от него вырезается требуемый размер.

Первый вариант быстрее, но второй и третий приводят к меньшей фрагментации памяти.

Освобождение

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

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

Утечки памяти, определяемые как сбой при освобождении ранее выделенной памяти, — это одна из наиболее трудно обнаруживаемых ошибок в приложениях C/C++. Небольшая утечка памяти сначала может остаться незамеченной, но постепенно нарастающая утечка памяти может приводить к различным симптомам, от снижения производительности до аварийного завершения приложения из-за нехватки памяти. Более того, приложение, в котором происходит утечка памяти, может использовать всю доступную память и привести к аварийному завершению другого приложения, в результате чего может быть непонятно, какое приложение отвечает за сбой. Даже безобидная на первый взгляд утечка памяти может быть признаком других проблем, требующих устранения.

Отладчик Visual Studio и библиотеки времени выполнения C (CRT) предоставляют средства для обнаружения утечек памяти.

Основным средством для обнаружения утечек памяти является отладчик и отладочные функции кучи библиотеки времени выполнения C (CRT).

Чтобы включить отладочные функции кучи, вставьте в программу следующие операторы:

Для правильной работы функций CRT операторы #include должны следовать в приведенном здесь порядке.

Включение заголовочного файла crtdbg.h сопоставляет функции malloc и free с их отладочными версиями, _malloc_dbg и free, которые отслеживают выделение и освобождение памяти. Это сопоставление используется только в отладочных построениях, в которых определен _DEBUG. В окончательных построениях используются первоначальные функции malloc и free.

Оператор #define сопоставляет базовые версии функций кучи CRT соответствующим отладочным версиям. Если оператор #define не используется, дамп утечки памяти будет менее подробным.

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

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

Функция _CrtMemCheckpoint поместит в структуру снимок текущего состояния памяти.

Чтобы вывести содержимое структуры _CrtMemState, передайте ее функции _ CrtMemDumpStatistics:

Функция _ CrtMemDumpStatistics выводит дамп состояния памяти

Поиск по сайту: