Mark-and-Sweep: алгоритм сборки мусора

Задний план

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

Марк и алгоритм развертки
Любой алгоритм сборки мусора должен выполнять 2 основные операции. Во-первых, он должен уметь обнаруживать все недостижимые объекты, а во-вторых, он должен освободить пространство кучи, используемое объектами мусора, и снова сделать это пространство доступным для программы.
Вышеупомянутые операции выполняются алгоритмом Mark и Sweep в два этапа:
1) Отметить фазу
2) Фаза развертки

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

• Корень - это переменная, которая ссылается на объект и напрямую доступна локальной переменной. Предположим, что у нас только один корень.
• Мы можем получить доступ к биту метки для объекта с помощью: markBit (obj).

Алгоритм - этап отметки:

Марка (корень)
    Если отмеченоBit (root) = false, то
        отмеченныйBit (корень) = истина
        Для каждого v, на который ссылается корень
             Марк (v)

Примечание: если у нас более одного корня, нам просто нужно вызвать Mark () для всех корневых переменных.

Фаза развертки
Как следует из названия, он «очищает» недостижимые объекты, то есть очищает память кучи для всех недостижимых объектов. Все те объекты, для которых установлено значение false, очищаются из памяти кучи, для всех других объектов (достижимые объекты) отмеченный бит устанавливается в true.
Теперь значение отметки для всех достижимых объектов установлено в false, поскольку мы запустим алгоритм (если требуется) и снова пройдем через фазу отметки, чтобы отметить все достижимые объекты.

Алгоритм - фаза развертки

 Сметать()
Для каждого объекта p в куче
    Если отмеченоBit (p) = true, то
        markBit (p) = ложь
    еще
        heap.release (p)

Алгоритм mark-and-sweep называется отслеживающим сборщиком мусора, потому что он отслеживает всю коллекцию объектов, которые прямо или косвенно доступны программе.

Пример:

a) У всех объектов помеченные биты установлены в значение false.

б) Доступные объекты помечены как истинные

c) Недостижимые объекты удаляются из кучи.

Преимущества алгоритма Mark and Sweep

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

Недостатки алгоритма Mark and Sweep

• Основным недостатком подхода «отметка и очистка» является тот факт, что нормальное выполнение программы приостанавливается на время работы алгоритма сборки мусора.
• Другой недостаток заключается в том, что после нескольких запусков алгоритма Mark and Sweep в программе достижимые объекты оказываются разделенными множеством небольших неиспользуемых областей памяти. Для лучшего понимания посмотрите на рисунок ниже.
  Фигура:

Здесь белые блоки обозначают свободную память, а серые блоки обозначают память, занятую всеми доступными объектами.
Теперь свободные сегменты (обозначенные белым цветом) имеют разный размер, скажем, 5 свободных сегментов имеют размер 1, 1, 2, 3, 5 (размер в единицах).
Теперь нам нужно создать объект, который занимает 10 единиц памяти, теперь предполагая, что память может быть выделена только в непрерывной форме блоков, создание объекта невозможно, хотя у нас есть доступное пространство памяти 12 единиц, и это вызовет Ошибка OutOfMemory. Эта проблема называется «фрагментация». У нас есть память, доступная в виде «фрагментов», но мы не можем использовать это пространство памяти.
Мы можем уменьшить фрагментацию путем уплотнения; мы перемешиваем содержимое памяти, чтобы разместить все свободные блоки памяти вместе, чтобы сформировать один большой блок. Теперь рассмотрим приведенный выше пример: после сжатия у нас есть непрерывный блок свободной памяти размером 12 единиц, поэтому теперь мы можем выделить память объекту размером 10 единиц.

Рекомендации:

• Структуры данных и алгоритмы с объектно-ориентированными шаблонами проектирования в Java
• https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na.C3.AFve_mark-and-sweep
• https://blogs.msdn.microsoft.com/abhinaba/2009/01/30/back-to-basics-mark-and-sweep-garbage-collection/

Автор статьи: Чираг Агарвал. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

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