Занятие 16. Динамический участок памяти процесса и сборщик мусора

План занятия:

• Динамический участок памяти процесса
• Особенности разработки распределителей памяти
• Фрагментация в случае динамического распределения памяти
• Структуры данных распределителей памяти
• Подсчет ссылок
• Сбор мусора

Динамический участок памяти процесса

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

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

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

Особенности разработки распределителей памяти

Распределитель памяти (memory allocator) - часть системной библиотеки или ядра системы, ответственный за динамическое распределение памяти.

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

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

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

Фрагментация в случае динамического распределения памяти

Динамическое распределение памяти может вызвать внешнюю и внутреннюю фрагментацию. Именно степень фрагментации является основным критерием оценки распределителей памяти.

Фрагментация возникает по двум причинам:

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

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

Структуры данных распределителей памяти

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

Подсчет ссылок

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

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

Сбор мусора

Сборщики мусора с маркировкой и очисткой (mark and sweep garbage collection), позволяют найти всю память, которую может адресовать процесс, начиная с некоторых заданных указателей. Всю остальную память при этом считают недостижимой, и она может быть высвобождена. Алгоритм такого сбора мусора выполняют в два этапа.

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