Главная » Java, Структуры данных и алгоритмы » Применение графов. Сбор мусора в Java

0

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

памятью на рабочую среду. Java-программисту не нужно самому освобождать память, если располагавшиеся в ней объекты более не нужны. Вместо этого в дело^ вступает механизма сбора мусора (garbage collector).

Напомним, что в Java память под большинство объектов выделяется динамически (см. п. 4.2.3). Кроме того, выполняющие потоки заданий в Java-программах (см. п. 4.2.2) сохраняют текущее пространство для своих переменных экземпляров в соответствующих им Java-стеках (см. п. 4.1.3). Поскольку переменные экземпляров в Java-стеках могут ссылаться на объекты в динамической памяти, все переменные и объекты в Java-стеках выполняющихся потоков называются корневыми объектами (root objects). Каждый из этих объектов, к. которому можно обратиться посредством объектных ссылок из корневых объектов, называется живым объектом (live object). Живым объектом называется активный объект, используемый в данный момент работающей программой, и этот объект не может быть удален из памяти. Например, работающая Java-nporpaMMa может хранить в переменной ссылку на последовательность S, реализованную с помощью двусвязного списка. Ссылочная переменная последовательности S — это корневой объект, а объект для S — живой объект, как и все объекты узлов, на которые осуществляется ссылка из^этого объекта, и как все элементы, на которые имеются ссылки из объектов узлов.

Время от времени виртуальная Java-машина (JVM) замечает, что доступного свободного места в памяти становится недостаточно. В этом случае она решает очистить память от объектов, которые уже не используются. Такая операция получила название сборки мусора. Существует несколько алгоритмов выполнения этой операции. Но наиболее популярным считается алгоритм выноса «мертвецов» (mark-sweep).

Алгоритм удаления неиспользуемых объектов

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

Выполнение внутреннего поиска в глубину

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

Основная идея выполнения внутреннего DFS-алгоритма заключается в эмуляции рекурсивного стека с помощью путей графа (которые в случае сбора мусора соответствуют ссылкам на объекты). При прохождении пути от пройденного узла v до нового узла w изменяем направление пути (v,w), хранящегося в списке смежности узла v, чтобы указать обратно на родительский узел v в DFS-дереве. При возвращении обратно в v (имитируя возвращение из рекурсивного вызова в w) снова изменяем направление модифицированного пути т&к, чтобы он вел обратно в w, как это было изначально. Естественно, следует иметь несколько способов определения ветви, направление которой необходимо изменять. Одним из таких способов является нумерация ссылок, исходящих из v, числами от 1 и далее и хранение вместе с битом метки (которая используется как пометки пройденных узлов) идентификатора, сообщающего, какой из путей модифицирован.

Использование счетчика-идентификатора, конечно, требует хранения дополнительного слова для каждого объекта. Это дoпoлниteльнoe слово, однако, в некоторых реализациях можно опустить. Например, многие реализации виртуальной Java-машины представляют объект в виде комбинации ссылки и идентификатора типа (определяющего, относится ли "объект к Integer, или Vector, или другому типу), используемой в качестве ссылки на другие объекты или поля этих объектов. Поскольку ссылка на тип всегда является первым элементом такого сочетания, используем ее в качестве метки измененного при выходе из объекта v в некоторый объект w пути. Для этого просто меняем местами ссылку в v, указывающую на тип v, со ссылкой в v, указывающей на тип w. При возвращении в v можно быстро определить измененный путь (v,w), поскольку он будет

первой ссылкой в комбинации для v, а позиция ссылки на тип v укажет место, к которому этот путь относится в списке смежности v. Таким образом, используя либо прием с обменом путей, либо счетчик-идентификатор, реализуется внутренний DFS без изменения его асимптотического времени выполнения.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии