Понимаем основы Java garbage collection

Статья - часть шпаргалки по мотивам книги “Java Performance”.

Начал замечать интересную вещь. Чем больше в чем то начинаю разбираться, тем чаще задаю себе вопросы о фундаментальных вещах, и не всегда могу дать хороший ответ на эти вопросы. Таким образом в знании образуются темные пятна. Можно, конечно, жить и с пятнами, но как–то не хочется.

Одним из таких вопросов был: “Как работает сборщик мусора в Java? Как сборщик мусора отличает мусор?” Попробую собрать и систематизировать информацию. Объяснить себе, и, возможно, кому то еще, основы роботы “Java GC”.

За что отвечает Garbage Collector ?

Garbage Collector должен делать всего две вещи:

  • Обнаруживать мусор
  • Очищать память от мусора

Ясно, теперь нужно ответить на два вопроса: “Как Garbage Collector обнаруживает мусор?” и “Как очищает память?”

Как Garbage Collector обнаруживает мусор?

Существует два подхода к обнаружению мусора:

  • Reference counting
  • Tracing

Reference counting

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

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

В общем, Reference counting редко используется из за недостатков. Во всяком случае HotSpot VM его не использует. По этому мы можем отложить в памяти, что такой подход есть, и продолжить дальше.

Tracing

В “Tracing” главная идея состоит в мысли: “Живые объект - те до которых мы можем добраться с корневых точек (GC Root), все остальные - мусор. Все что доступно с живого объекта - также живое”.

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

gc

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

HotSpot VM использует именно такой подход.

Все хорошо, но возникает вопрос: Что такое корневая точка (GC Root)?

Литература говорит что существует 4 типа корневых точек:

  • Локальные переменные и параметры методов
  • Java Потоки
  • Статические переменные
  • Ссылки из JNI

Самое простое java приложение будет иметь такие корневые точки:

  • Локальные переменные внутри main метода, параметры main метода.
  • Поток который выполняет main.
  • Статические переменные класса, внутри которого находится main метод.

Как GC очищает память от мусора?

Теперь мы понимаем, какой механизм используется для обнаружения мусора. Нужно разобраться как именно GC очищает память.

Рассмотрим известные человечеству подходы.

###Copying collectors Память делится на две части “from-space” “to-space”.

Принцип работы такой:

  • Объекты аллоцируются в “from-space”
  • “from-space” заполняется, нужно собрать мусор
  • Приложение приостанавливается
  • Запускается сборщик мусора. Находятся живые объекты в “from-space” и копируются в “to-space”
  • Когда все объекты скопированы “from-space” полностью очищается
  • “to-space” и “from-space” меняются местами

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

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

В итоге, плюс в том, что память используется эффективно. Но при этом приложение должно прекращать свою работу на время сборки мусора. Также очень не эффективно используется память, так как в худшем случае “from-space” должен быть равен “to-space”.

В чистом виде такой алгоритм в HotSpot VM не используется.

###Mark-and-sweep

Алгоритм можно описать так:

  • Объекты аллоцируются в памяти
  • Нужно запустить GC
  • Приложение приостанавливается
  • Сборщик проходится по дереву объектов, помечая живые объекты
  • Сборщик проходится по всей памяти, находя все не отмеченные куски памяти, сохраняя их в “free list”
  • Когда новые объекты начинают аллоцироватся они аллоцируются в память доступную в “free list”

Минусы:

  • Приложение не работает пока происходит сборка мусора
  • Время работы зависит от размеров памяти и количества объектов
  • Если не использовать “compacting” память будет использоваться не эффективно

В чистом виде такой подход для сборки мусора в Hotspot VM тоже не используется.

##Какой подход используется в HotSpot VM?

Сборщики мусора HotSpot VM используют подход “Generational Garbage Collection”. Как мы увидим, этот подход позволяет использовать разные алгоритмы для разных этапов сборки мусора. Это позволяет использовать наиболее подходящий алгоритм.

Было замечено, что большинство приложений удовлетворяют двум правилам (weak generational hypothesis):

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

Именно на эти правила опирается подход “Generational Garbage Collection”.

В HotSpot VM реализовано четыре сборщика мусора основанных на идее “Generational Garbage Collection”:

  • Serial GC
  • Parallel GC
  • CMS GC
  • G1 GC

Для того, что бы разобраться с принципом работы “Generational Garbage Collection”, рассмотрим “Serial GC”.

Serial GC был одним из первых сборщиков мусора в HotSpot VM. Во время работы этого сборщика приложения приостанавливается и продолжает работать после прекращение сборки мусора.

Память делится на три пространства:

  • Young generation. Объекты аллоцируются в этом участке. Обычно имеет сравнительно не большой размер. Очищается часто. Предполагается, что количество объектов переживших сборку будет мало (основывая на “weak generational hypothesis”). Сборку мусора в этом участке называют “minor garbage collection”. В общем, “minor garbage collection” проходит часто, быстро и уничтожает кучу мусора, так как происходит на сравнительно не большом участке памяти который скорее всего содержит много мусора.
  • The old generation. Объекты которые переживают “minor collection” перемещаются в участок памяти называемый “old generation”. Обычно “old generation” больше чем “young generation”. Заполняется этот участок сильно медленней, так как большинство объектов живут не долго. В итоге, сборка мусора в “old generation” (major garbage collection) происходит не часто, но когда происходит, занимает много времени.
  • Permanent generation. Тут хранятся метаданные, классы, интернированные строки, итд. Дальше рассматривать его не будем.

В итоге, мы знаем, что память делится на части. Нас интересует “young generation” и “old generation”. Новые объекты создаются в “young generation”, пережившие сборку мусора попадают в “old generation”. Существует “minor GC” и “major GC”.

  • “minor GC” - проходит часто и быстро, в основном работает с “young generation”.
  • “major GC” - проходит редко и долго, в основном работает с “old generation”.

minor GC

Для того, что бы “minor GC” проходил быстро, нужно что бы при нем не приходилось сканировать “old generation”. Возникает вопрос: “Как выявить ссылки на объекты c “old generation” на объекты в “young generation” не сканируя “old generation””

Как мы помним, соответствуя “weak generational hypothesis” их должно быть мало, но они могут быть.

Для решения этой проблемы HotSpot VM содержит структуру “card table”.

Память в “old generation” разбивается на карты (cards).

Card table - это массив с однобайтной ячейкой, каждая ячейка массива соответствует куску памяти (карте) в “old generation”. Когда в каком то поле объекта обновляется ссылка, то в “card table” нужная карта помечается как “грязная” (для этого нужна однобайтная ячейка). В итоге при “minor GC” для выявления ссылок “old-to-new” сканируется не весь “old-generation”, а только объекты которые находятся в “грязных” картах.

“Young generation” делится на:

  • Eden. Кусок памяти, где объекты алоцируются. После сборки мусора “Eden” пустой, мусор должен удалится, а выжившие объекты попасть в “Survivor space”
  • Survivor space 1,2. То, что в разделе “Copying collectors” называлось “from-space” и “to-space”. Тут находятся объекты, которые выжили при предыдущей сборке мусора, но перед отправкой в “old generation” им дан шанс стать мусором во время следующей сборки.

Survivor space 1 будем называть “from space”, Survivor space 2 - “to space”.

Алгоритм работы очень похож на “Copying collectors”, отличие в том, что появился “Eden”:

  • Начало сборки мусора, приложение приостанавливается.
  • Живые объекты из “Eden” копируются в “to space”.
  • Живые объекты из “from space” копируются в “to space” или в “old generation”, если они достаточно старые.
  • “Eden” и “from space” очищаются, так как в них остался только мусор.
  • “to space” и “from space” меняются местами
  • Приложение продолжает работу.

Коричневый - мусор.

Зеленый - живой объект.

Сборка мусора:

yg

После сборки мусора:

yg

После “minor gc” “Eden” и “to space” пустые, в “from space” лежат объекты пережившие сборку, немного долгоживущих объектов перекочевало в “old generation”.

major GC

“major GC” работает по принципу “sliding compacting mark-sweep”. Принцип работы похож на “Mark-and-sweep”, но добавляется процедура “compacting”, которая позволяет более эффективно использовать память.

Процедура заключается в перемещении живых объектов к началу “old generation space”, таким образом мусор остается в конце. Для аллокации нужно иметь указатель на последний живой объекты и дальше просто аллоцировать и сдвигать указатель к концу “old generation”.

  • Запускается GC
  • Приложение приостанавливается
  • Сборщик проходится по дереву объектов в “old generation”, помечая живые объекты
  • Сборщик проходится по всей памяти, находя все не отмеченные куски памяти, они помечаются как мусор
  • Все живые объекты сдвигаются к началу “old generation”, мусор становится одним куском памяти, который находится сразу за последним живым объектом
  • Приложение возобновляет свою роботу.

Находим мусор:

yg

После “compacting”:

yg

##Материалы

Written on May 4, 2014