Разработка сред управляемого исполнения на примере виртуальной машины Java Занятие 5 Салищев С.И.

Менеджер памяти Задачи Выделение памяти под объекты Выделение памяти под объекты Обнаружение живых объектов Обнаружение живых объектов Сборка мусора Сборка мусора Свойства приложений Структура выделения памяти (allocation pattern) Структура выделения памяти (allocation pattern) количество и размер выделяемых объектов Коэффициент смертности (mortality ratio) Коэффициент смертности (mortality ratio) процент объектов не переживших сборку мусора

Метрики Скорости Производительность выделения памяти Объектов в сек, Кб в секунду Объектов в сек, Кб в секунду Задержка выделения памяти Среднее и максимальное время выделения объекта Среднее и максимальное время выделения объекта Производительность сборки мусора Объектов в сек, Кб в секунду Объектов в сек, Кб в секунду Задержка сборки мусора Среднее и максимальное время выделения объекта приостановки нити для сборки мусора Среднее и максимальное время выделения объекта приостановки нити для сборки мусора

Способы достижения скорости Уменьшение сложности 2 шаговые алгоритмы – быстрый частый шаг (fast path), медленный редкий шаг (slow path) 2 шаговые алгоритмы – быстрый частый шаг (fast path), медленный редкий шаг (slow path) Распараллеливание операций с памятью (parallel GC, Thread local allocation) Уменьшение синхронизации Уменьшение синхронизации Использование локальных данных нити Использование локальных данных нити Вынесение синхронизации в медленный шаг Вынесение синхронизации в медленный шаг Разбиение на порции (incremental GC) Параллельное исполнение с основным кодом (concurrent GC)

Выделение памяти Двух шаговое выделение памяти Медленный шаг. Выделение буфера памяти для нити из глобальной кучи с синхронизацией Медленный шаг. Выделение буфера памяти для нити из глобальной кучи с синхронизацией Быстрый шаг. Выделение памяти под объект из буфера нити без синхронизации Быстрый шаг. Выделение памяти под объект из буфера нити без синхронизации Список свободных блоков (free list) Список или дерево блоков различного размера. При выделении находится первый подходящий блок. Остаток вставляется в список. Список или дерево блоков различного размера. При выделении находится первый подходящий блок. Остаток вставляется в список. Раздельный список свободных блоков по размерам, обычно 2 n (segregated free list). Остаток блока разбивается на куски нужного размера и вставляется в список. Раздельный список свободных блоков по размерам, обычно 2 n (segregated free list). Остаток блока разбивается на куски нужного размера и вставляется в список. Последовательное выделение (bump pointer) Вершина кучи сдвигается на размер нового объекта Вершина кучи сдвигается на размер нового объекта

Перечисление живых объектов: Сканирование кучи Алгоритм 1. Остановка нитей 2. Перечисление корневых ссылок 3. Трассировка ссылок начиная с корневых для построения транзитивного замыкания Достоинства Прост в реализации Прост в реализации Не зависит от других подсистем Не зависит от других подсистем Не влияет на производительность управляемого кода Не влияет на производительность управляемого кодаНедостатки Требует остановки нитей (Stop the World) Требует остановки нитей (Stop the World) Не может быть разбит на порции (All or nothing) Не может быть разбит на порции (All or nothing)

Перечисление корневых ссылок С помощью карт ссылок (GC Maps) Требует генерации карт ссылок Требует генерации карт ссылок Обеспечивает точное перечисление живых объектов (strict GC) Обеспечивает точное перечисление живых объектов (strict GC) Позволяет использовать поле в заголовке объекта при трассировке ссылок Позволяет использовать поле в заголовке объекта при трассировке ссылок Консервативное сканирование стека (conservative stack scanning) Не требует поддержки других подсистем Не требует поддержки других подсистем Не различает ссылку на объект от примитивного типа с тем же численным значением. Ссылки на необъекты. Не различает ссылку на объект от примитивного типа с тем же численным значением. Ссылки на необъекты. Не позволяет использовать поле в заголовке объекта при трассировке ссылок из за ссылок на необъекты. Не позволяет использовать поле в заголовке объекта при трассировке ссылок из за ссылок на необъекты.

Параллельная трассировка ссылок Один бит в заголовке объекта Алгоритм 1. В начале все объекты белые 2. Каждая нить начинает со своего множества корневых ссылок 3. Посещенные объекты красятся черным 4. Отслеживаются ссылки на белые объекты (поиск в ширину или глубину) 5. Алгоритм завершается когда не осталось ссылок на белые объекты у всех нитей Оставшиеся в куче белые объекты мертвы Не требуется синхронизация поскольку результат инвариантен относительно нити Фоновая синхронизация кэша процессоров для оптимизации

Перечисление живых объектов: Трехцветная раскраска (tri-color marking)* Три цвета объекта – белый, серый, черный (2 бита в заголовке) Алгоритм Вначале все объекты белые Вначале все объекты белые Корневые ссылки нитей красятся в серый Корневые ссылки нитей красятся в серый Отслеживаются ссылки из серых объектов на белые Отслеживаются ссылки из серых объектов на белые Найденные белые объекты перекрашиваются в серый Найденные белые объекты перекрашиваются в серый Когда у объекта не осталось ссылок на белых соседей он красится в черный Когда у объекта не осталось ссылок на белых соседей он красится в черный Алгоритм завершается, когда не осталось серых объектов Алгоритм завершается, когда не осталось серых объектов Во время работы алгоритма другие нити могут добавлять новые объекты и изменять ссылки при сохранении инварианта Требует поддержки со стороны управляемого кода * Dijkstra et all, On-the-fly Garbage Collection: An Exercise in Cooperation

Трехцветный инвариант Условие утери ссылки Ссылка на белый объект записывается в черный объект Ссылка на белый объект записывается в черный объект Не существует пути в этот белый объект из какого-то серого Не существует пути в этот белый объект из какого-то серого При изменении графа объектов не никогда не выполняется условие утери ссылки

Варианты реализации модификации Последовательное изменение (incremental-update) (Dijkstra) При записи в черный объект ссылки на белый, белый перекрашивается в серый (Dijkstra) При записи в черный объект ссылки на белый, белый перекрашивается в серый (Steel) При записи в черный объект ссылки на белый, черный перекрашивается в серый (Steel) При записи в черный объект ссылки на белый, черный перекрашивается в серый (Boehm) При записи в черный объект ссылки, черный перекрашивается в серый (Boehm) При записи в черный объект ссылки, черный перекрашивается в серый (Baker) При чтении из серого объекта, ссылка перекрашивается в серый (Baker) При чтении из серого объекта, ссылка перекрашивается в серый (Appel) При чтении из серого объекта завершить сканирование объекта и перекрасить его в черный (Appel) При чтении из серого объекта завершить сканирование объекта и перекрасить его в черный Слепок на старте (snapshot-at-the-beginning) (Abraham & Patel) При записи ссылки в серый или белый объект старое значение перекрашивается в серый (Abraham & Patel) При записи ссылки в серый или белый объект старое значение перекрашивается в серый Прямая реализация требует синхронной памяти На практике используются групповые механизмы синхронизации

Синхронизационные механизмы Другие барьеры (barrier) Write barrier – исключение по записи Write barrier – исключение по записи Read barrier – исключение по чтению Read barrier – исключение по чтению Реализуются при помощи механизма защиты страниц виртуальной памяти Реализуются при помощи механизма защиты страниц виртуальной памяти Грязный бит (dirty bit) Устанавливается в 1 если произошла запись в страницу памяти Устанавливается в 1 если произошла запись в страницу памяти

Перечисление живых объектов: Подсчет ссылок Счетчик ссылок для каждого объекта Алгоритм Установка ссылки – увеличение счетчика Установка ссылки – увеличение счетчика Разрушение ссылки – уменьшение счетчика Разрушение ссылки – уменьшение счетчика Объект с 0 ссылок мертв Объект с 0 ссылок мертвДостоинства Не требует остановки нитей Не требует остановки нитей Работает только с локальными объектами, 0 задержка Работает только с локальными объектами, 0 задержкаНедостатки Дополнительная память для каждого объекта Дополнительная память для каждого объекта Требует инструментации управляемого кода изменением счетчиков Требует инструментации управляемого кода изменением счетчиков Не отслеживает циклические ссылки, например двусвязный список Не отслеживает циклические ссылки, например двусвязный список Фоновое сканирование циклов Модификация счетчика – атомарная операция Модификация счетчика – атомарная операция Журналирование операций каждой нити. Требует регулярного объединения журналов. Создает ненулевую задержку.

Сборка мусора (Garbage Collection) По остановка управляемых нитей Останавливающая (Stop the world) Останавливающая (Stop the world)Задержка Конкурентная (concurrent) Конкурентная (concurrent) Сложность кода Уменьшение производительности из-за необходимости синхронизации с управляемым кодом По области сборки Полная (full) Полная (full) Частичная (incremental) Частичная (incremental) По изменению положения объектов в памяти Копирующая (copying) Копирующая (copying) Неперемещающая (non-copying) Неперемещающая (non-copying)

Поколения объектов (Generational GC) При достаточно редких GC коэффициент смертности для первой GC 85 – 95% для типичных приложений Поколение объекта – количество GC которое он пережил Объекты делятся на короткоживущие и долгоживущие При сборке объектов младших поколений освобождается наибольше количество памяти Нет смысла часто собирать объекты старшего поколения При GC требуется разделять объекты по поколениям

Поколения объектов: реализация Nursery Object Old Space Object GC External reference map new ref page, dirty bit = 1 rescan page