Краткий конспект реализации Garbage Collector в Java

Теги: Java, Философия, Garbage Collector

Функции

Garbage Collector (GB) часть JVM, который призван очищать память, выделенную приложению. Он должен:

  • найти мусор (неиспользуемые объекты)
  • удалить мусор

Есть различные реализации GB.

Поиск мусора

Два способа:

  • Reference counting - у каждого объекта счетчик ссылок. Когда он равен нулю, объект считается мусором. Проблема такого подхода в том, что могут быть цикличные ссылки у объектов друг на друга, в то время как они фактически мусор и не используются программой.
  • Tracing - объект считается не мусором, если до него можно добраться с корневых точек (GC Root: локальные переменные и параметры методов, java-потоки, статичные переменные, ссылки из JNI.

Организация памяти JVM

Делится на две части:

  • Heap - куча. Основной сегмент памяти, где содержатся все объекты и происходит сборка мусора.
  • Permanent Generation - содержит мета-данные классов.

Сразу про Permanent Generation. Может менять размер во время выполнения, и это довольно дорогостоящая операция. Размер настраивается (-XX: PermSize - мин размер, -XX: MaxSize - макс размер). Часто мин = макс.

Heap. Куча. Тут и работает GC.

Делится на две области:

  • New (Yang) Generation - объекты, кот. тут считаются короткоживущими.
  • Old Generation (Tenured) - обекты считаются долгоживущими.

Алгоритм GC исходит из того предположения, что большинство java-объектов живут недолго. Быстро становятся мусором. От них необходимо довольно оперативно избавляться. Что и происходит в New Generation. Там сбор мусора гораздо чаще, чем в Old Generation, где хранятся долгоживущие объекты. После создания объект попадает в New Generation и имеет шанс попасть в Old Generation по прошествии некоторого времени (циклов GC).

Heap состоит из:

  • Eden - переводится как Едем (?). Сюда аллоцируются объекты. Если нет места запускается GC.
  • Survivor - точнее их два, S1 и S2, и они меняются ролями. Хранятся объекты, которые признаются живыми во время GC.

Размер Heap настраивается.

Принцип работы 4 сборщиков HotSpot VM (одна из JVM)

Виды сборщиков:

  • Serial
  • Parallel
  • Concurent Mark Sweep (CMS)
  • Garbage-First (G1)

Serial. Когда нет места в Eden, запускается GC, живые объекты коприруются в S1. Вся область Eden очищается. S1 и S2 меняются местами. При последующих циклах в S1 будут записаны живые объекты как из Eden, так и из S2. После нескольких циклов обмена S1 и S2 или заполнения области S2, обекты, которые живут достаточно долго перемещаются в Old Greneration.

Следует сказать, что не всегда объекты при создании аллоцируюся в Eden. Если объект слишком велик, он сразу идет в Old Generation.

Когда после очередной сборки мусора места нехватает уже в New Generation, то запускается сбор мусора в Old Generation (наряду со сборкой New Generation). В old Generation объекты уплотняются (алгоритм Mark-Sweep-Compact).

Если после полной сборки мусора места нехватает, то вылетает Java.lang.OutOfMemoryError.

Но во время работы VW может запрашивать увеличение памяти и Heap может увеличиваться.

Как правило, Old Generation занимает 2/3 объема Heap.

Эффективоность алгоритма сборки мусора считается по параметру STW (Stop The World) - время, когда все процессы кроме GC останавливаются. Serial в этом смысле не слишком эффективен, т.к. делает свою работу не торопясь, в одном потоке.

Parallel. То же, что и Serial, но использует для работы несколько потоков. Таким образом STW чуть меньше.

Concurent Mark Sweep. Принцип работы с New Generation такой же, как и в случае алгоритмов Serial и Parallel, отличия в том, что данный алгоритм разделяет младшую (New Generation) и старшую (Old Generation) сборку мусора во времени. Причем сбор мусора в Old Generation происходит в отдельном потоке, независимо от младшей сборки. При этом сначала приложение останавливается, сборщик помечает все живые объекты доступные из GC Root (корневых точек) напрямую, затем приложение вновь начинает работу, а сбощик проверяет объекты доступные по ссылкам из этих самых помеченных, и также помечает их как живые. Эта особенность создает так называемые плавающие объекты, которые помечены как живые, но таковыми по факту не являющимися. Но они будут удалены в следующих циклах. Т.е. пропускная способность растет, STW уменьшается, но требутся больше места для хранения плавающих объектов.

В этом алгоритме уплотнения нет. Т.е. область Old Generation дефрагментированна.

Garbage-First. G1 сильно отличается от своих предшественников. Он делит область Heap не физически, а скорее логически на те же области: Eden, Survivor, Old Generation. Причем дефрагментированно. Физически область Heap делится на регионы одинакового размера, каждый из которых может быть Eden, Survivor или Old Generation + область для больших объектов (громадный регион).

Над очисткой регионов Eden работает сразу несколько потоков, объекты переносятся в регионы Survivor или регионы старшего поколения (Tenured). Это знакомый по предыдущим алгоритмам очистки подход. На время очистки работа приложения останавливается. Отличие в том, что очистка производится не по всем регионам Eden, а только по некоторым, которые более всего в ней нуждаются, таким образом регулируется время очистки. Отсюда название алгоритма - в первую очередь мусор.

А с полной сборкой (точнее, здесь она называется смешанной (mixed)) все немного хитроумнее, чем в рассмотренных ранее сборщиках. В G1 существует процесс, называемый циклом пометки (marking cycle), который работает параллельно с основным приложением и составляет список живых объектов. За исключением последнего пункта, этот процесс выглядит уже знакомо для нас:

  • Initial mark. Пометка корней (с остановкой основного приложения) с использованием информации, полученной из малых сборок.
  • Concurrent marking. Пометка всех живых объектов в куче в нескольких потоках, параллельно с работой основного приложения.
  • Remark. Дополнительный поиск не учтенных ранее живых объектов (с остановкой основного приложения).
  • Cleanup. Очистка вспомогательных структур учета ссылок на объекты и поиск пустых регионов, которые уже можно использовать для размещения новых объектов. Первая часть этого шага выполняется при остановленном основном приложении.

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

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

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

Громадные регионы. С точки зрения JVM объекты которые превышают размер половины региона являются громадными. Особенности:

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

Громадные объекты в силу небольшого размера регионов могут порождать проблемы с точки зрения STW.

G1 выигрывает по времени STW, но расплатой является меньшая пропускная способность (около 90%, ср., например у Paraller ок. 99%) т.е. большие затраты ресурсов процессора.

Bonus

Вопрос: Расскажите почему именно два региона survival и зачем перекладывать объекты между ними?

Ответ:
Представьте себя на месте сборщика. У вас есть регион памяти, который нужно очистить. После удаления мусора регион оказывается сильно дефрагментированным и если вы хотите это исправить, то у вас есть два варианта: либо уплотнять объекты в рамках этого же региона, либо скопировать их в другой, пока еще пустой регион, располагая один-к-одному, а старый регион объявить пустым. Но задача осложняется тем, что объекты ссылаются друг на друга и при перемещении любого объекта необходимо производить обновление всех имеющихся на него ссылок. И вот эту задачу намного легче решать при копировании, причем сразу объединяя ее с задачей поиска живых объектов:

Вы просто заводите два указателя на начало новой области. Первый указатель (назовем его T) смещается вправо каждый раз, когда в новую область копируется объект, то есть он всегда указывает на первый свободный блок новой области. При этом на том месте старой области, где находился перемещаемый объект, мы делаем пометку о том, что он был перемещен, и там же оставляем его новый адрес. Первым делом перемещаем таким образом все руты из старой области в новую. И вот тут вступает в действие второй указатель (назовем его R). Он тоже начинает смещаться вправо по уже размещенным в новой области объектам. В каждом объекте он ищет ссылки на другие объекты и смотрит на то место в старом регионе, куда они указывают. Если там стоит метка о перемещении и новый адрес, то этот адрес используется для подмены. Если же там лежит объект, то он перемещается в новый регион, на его месте ставится метка и новый адрес, на который так же заменяется ссылка, по которой его нашли, при этом T опять смещается вправо. Как только R догонит T, окажется, что мы собрали все живые объекты в новой области, размещенные компактно, да еще и с корректно обновленными ссылками, а старый регион можем объявить пустым. Все быстро и просто.

29 06 2017

Теги заметки: