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

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

Занятие 5
Салищев С.И.

2. Менеджер памяти

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

3. Метрики Скорости

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

4. Способы достижения скорости

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

5. Выделение памяти

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

6. Перечисление живых объектов: Сканирование кучи

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

7. Перечисление корневых ссылок

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

8. Параллельная трассировка ссылок

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

9. Перечисление живых объектов: Трехцветная раскраска (tri-color marking)*

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

10. Трехцветный инвариант

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

11. Варианты реализации модификации

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

12. Синхронизационные механизмы

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

13. Перечисление живых объектов: Подсчет ссылок

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

14. Сборка мусора (Garbage Collection)

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

15. Поколения объектов (Generational GC)

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

16. Поколения объектов: реализация

Object
Object
new ref
Nursery
GC
Old Space
page, dirty bit = 1
rescan page
External reference map