Технология Клиент-Сервер 2004'4
	Home Поиск Издания Контакты k-press.ru

Продолжается подписка на наши издания! Вы не забыли подписаться?

Заметки о сборщике мусора в Rotor

Я публикую документ о GC Rotor, написанный Patrick Dussud (он – архитектор в команде CLR). В первую версию Rotor входил упрощенный GC, управляемый FJIT (обычно производится в точке вызова метода), сильно отличающийся от того, который вошел в релиз CLR. Одно из архитектурных отличий состоит в том, что в релизе GC может работать в фоновом режиме (и на нескольких процессорах в случае серверного GC), а в Rotor – нет.

Сверхупрощенная модель

Для начала рассмотрим сверхупрощенную модель кучи и сборки мусора. Это не та схема, что используется на самом деле.

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

Объекты делятся на поколения. Объекты одного поколения имеют примерно одинаковый возраст. Поколения – это непрерывная часть кучи, так что определить поколение, к которому принадлежит объект, можно сравнением его адреса с адресами границ поколений. Полная сборка мусора работает со всей кучей и выполняет не уплотняющую (non compacting) Mark and Sweep сборку. Эфемерная сборка работает с поднабором поколений, лежащих выше определенного адреса, и не затрагивает старые объекты, лежащие ниже.

Модель реальной кучи

Память под все подвергаемые сборке мусора объекты, которые меньше определенного размера (т.н. маленькие объекты) выделяется из кучи, которая состоит из одного или более сегментов. Сегмент кучи – это единый непрерывный интервал адресов, обычно размером в 16 мегабайт. Для каждого из сегментов кучи хранится два значения – размер виртуальной памяти, которая зарезервирована (reserved), но не распределена (применительно к Win32 это означает, что память выделена с помощью функции VirtualAlloc c параметром MEM_RESERVE – прим.ред.) и размер выделенной и подтвержденной памяти (committed, применительно к Win32 это означает, что память выделена с помощью функции VirtualAlloc c параметром MEM_COMMIT – прим.ред.), который может быть меньше зарезервированного. Подтвержденная часть сегмента кучи состоит из заголовка, за которым следуют чередующиеся использованные и неиспользованные области. Зарезервированная часть состоит из страниц виртуальной памяти, находящихся вверху сегмента кучи.

Сегменты кучи упорядочены от старшего к младшему, что может не совпадать с порядком следования их адресов. Наиболее старые объекты находятся в старших сегментах кучи, а новые создаются в младших. В сегменте кучи самые старые объекты обычно находятся по самым низким адресам, но порядок может нарушаться из-за использования mark-sweep алгоритма сборки мусора или вследствие фиксации (pinning) объектов.

Куча может расти или уменьшаться за счет добавления или удаления младших сегментов.

Большие объекты размещаются с помощью распределителя памяти типа malloc и освобождаются сборщиком мусора, когда становятся недоступными. Есть два двунаправленных связанных списка больших объектов, один – для объектов, содержащих указатели, другой – для объектов, не содержащих указателей. В списке объектов с указателями поддерживается сортировка по адресам. Минимальным размером большого объекта считается 20К. Периодически куча подвергается сборке мусора. При этом определяются мертвые объекты, и их последовательности превращаются в неиспользованные области, которые затем могут быть использованы для размещения других объектов. Порой интерфейс взаимодействия с неуправляемым кодом запрещает перемещение некоторых объектов, чтобы обеспечить неуправляемому коду нормальный доступ к ним. Если объект фиксирован во время сборки мусора, он называется фиксированным (pinned) объектом. Фиксированные объекты при уплотнении кучи могут помешать объединению неиспользуемых областей сегмента кучи. Поскольку фиксация объектов относительно редка, это несущественно вредит производительности.

Поколения

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

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

Алгоритмы сборки мусора

Распределитель: Структура данных распределителя состоит из allocation_context, который содержит указатели на начало и конец следующего свободного участка. Распределитель увеличивает значение указателя и сравнивает его с предельным значением. Если значение указателя достигает предела или выходит за него, указатель откатывается к прежнему положению и вызывает GC для получения дополнительного пространства. Если свободное место есть, GC очищает некоторое количество памяти – обычно 8К – и помещает ссылку на нее в allocation_context. Если места нет, запускается сборка мусора.

Операции выделения памяти защищаются глобальной блокировкой. На SMP-машинах эта блокировка быстро становится узким местом, так что каждый поток хранит локальный контекст размещения в своем Thread Local Stoage.

Эфемерная сборка мусора состоит из одной фазы.

Остановка и копирование (Stop and Copy): Смысл фазы пометки в копировании живых объектов подвергающегося сборке поколения из того места, где они были размещены изначально, в место, непосредственно примыкающее к старшему поколению. Достижимый граф объектов исследуется. Корневые объекты копируются первыми, после чего копируемые объекты сканируются в поисках ссылок, затем копируются объекты, упомянутые в ссылках, и так до тех пор, пока все копируемые объекты не будут просканированы.

Полная сборка мусора включает две фазы:

“Пометка” (Mark): Цель фазы пометки – отделить в подвергаемых сборке поколениях мертвые объекты от живых.

По окончании этой фазы у всех живых маленьких объектов оказывается установленным бит пометки (Mark bit) и так же, если объект был зафиксирован (pinned), бит фиксации (Pinned bit). После этого запускается процесс финализации и обнуляются слабые ссылки (weak references). Мертвые объекты большого размера изымаются из связанного списка, и отведенная под них память освобождается.

“Уборка” (Sweep): Цель фазы уборки – превратить мертвые объекты в списки свободной памяти, готовые к размещению живых объектов младших поколений при последующих сборках.

Схематическое устройство объекта

Схематическое устройство объектов можно изобразить следующим образом:

Первое длинное слово в объекте – это заголовок, экземпляр класса CJavaObject. Два нижних бита адреса Таблицы методов заняты флагами Pinned (P) и Marked (M). Эти флаги всегда, кроме периодов сборки мусора, равны нулю, поэтому их не нужно маскировать при обращениях к Таблице методов, за исключением момента сборки мусора.

Если объект не является массивом, остальные длинные слова – это слоты. Если у объекта нет слотов, в нем создается фиктивный слот, чтобы его размер составлял хотя бы 8 байт. Сборщику мусора нужно, чтобы минимальный размер объекта составлял 8 байт – для реализации дерева перераспределения (Relocation Tree).

Второе и третье длинные слова в MethodTable – новые. Они содержат следующие поля:

• flags – 16 бит – "содержит указатели", "large-object", и кое-что еще, здесь несущественное;
• type – 8 бит;
• component_size – 8 бит – количество байт в компоненте массива, и 0, если это не массив;
• size – 32 бит – размер экземпляра в байтах, кроме компонентов массивов.

GC Descs

Экземпляры объектов содержат ссылки на другие объекты. Внутри объекта ссылки располагаются по возможности смежно, эта группа смежных ссылок называется "reference site".

GCDesc – это структура, описывающая ссылки, содержащиеся в объекте. Она размещается как часть таблицы методов (перед указателем на EEClass). Ее можно изобразить так:

N entries – число reference site, описанных в gcdesc. Каждый дескриптор reference site содержит:

• ref offset – смещение от начала объекта до первой ссылки в reference site.
• number of ref – количество ссылок в reference site.

Хендлы

Кроме статических переменных, ссылок в стеке и ссылок, содержащихся в объектах, поддерживаются внешние ссылки на объекты – хендлы. Они используются unmanaged-кодом для связи с объектом. Хендлы неперемещаемы, они явно создаются и уничтожаются из unmanaged-кода. Типы хендлов:

Строгий (Strong) – то же, что обычная объектная ссылка, безусловно сохраняющая объект в живых.

Фиксированный (Pinned) – объект фиксируется на время жизни хендла.

Слабый короткий (Weak short) – не равен null до тех пор, пока объект жив благодаря другой, строгой ссылке. Иначе – null.

Слабый длинный (Weak long) – не равен null до тех пор, пока объект не удален сборщиком мусора.

Различия между слабой длинной и слабой короткой ссылками проистекают из семантики финализации, слабая короткая ссылка на freachable-объект равна null, а слабая длинная по-прежнему указывает на freachable-объект.

Финализация объектов

Когда объект связан с unmanaged-ресурсом, который требуется явно освобождать, хорошо бы убедиться, что ресурс освобожден, до того, как объект будет удален сборщиком мусора. По этой причине языки вроде Java и VB поддерживают финализацию. Финализируемые объекты при создании помещаются в отдельный список слабых ссылок. GC отслеживает этот список, и, когда все сильные ссылки на финализируемый объект исчезают, GC удаляет ссылку из этого списка и переносит ее в список финализации, сохраняющий объект в живых; такой объект называют "freachable". После завершения сборки поток финализации обойдет список freachable-объектов и вызовет метод финализации для каждого из них. Если объект не становится доступным снова, он будет удален при следующей сборке мусора в следующем поколении. Если же он снова станет доступным, он не попадет во freachable-состояние, когда все строгие ссылки на него исчезнут.

Внутренние ссылки

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

Copyright © 1994-2016 ООО "К-Пресс"