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

Неперемещающая GC Не изменяет инвариантов других нитей, может работать параллельно Выделение памяти при помощи списка свободных блоков Сохранение локальности данных (spatial locality) Фрагментация памяти При подсчете ссылок немедленная возможность возврата памяти при обнулении счетчика Подметающий (Sweep) алгоритм последовательное сканирование кучи и возврат памяти последовательное сканирование кучи и возврат памяти Сложность O(objectsCount) Сложность O(objectsCount) Частичная очистка Частичная очистка Распараллеливание по блокам Распараллеливание по блокам Последовательный доступ к памяти (кэширование) Последовательный доступ к памяти (кэширование)

Копирующая GC Требует изменения ссылок Любой алгоритм выделения памяти Возможность объединения свободных блоков Возможно изменение локальности данных (spatial locality) Сложность O(liveObjectSize) Случайный доступ к памяти Упирается в скорость копирования памяти, следовательно минимальный выигрыш от распараллеливания на архитектурах с общей памятью

Mark&Sweep Алгоритм Остановка пользовательских нитей Остановка пользовательских нитей (Mark) Перечисление живых объектов методом трассировки ссылок (tracing) (Mark) Перечисление живых объектов методом трассировки ссылок (tracing) (Sweep) последовательное сканирование кучи и возврат памяти (Sweep) последовательное сканирование кучи и возврат памяти Возобновление пользовательских нитей Возобновление пользовательских нитей Используются параллельные версии сканирования и подметания Возможность переполнения стека при сканировании ссылок При возможности возврат страниц памяти OS

Concurrent Mark&Sweep (вариант) Алгоритм Конкурентная разметка Конкурентная разметка Конкурентный подбор изменений сохраняющий трехцветный инвариант Конкурентный подбор изменений сохраняющий трехцветный инвариант Остановка нитей Остановка нитей Завершение разметки Завершение разметки Возобновление нитей Возобновление нитей Параллельное подметание кучи Параллельное подметание кучи

Mark&Compact Уплотнение кучи – объединение свободных блоков в непрерывную область Алгоритм Остановка пользовательских нитей Остановка пользовательских нитей (Mark) Перечисление живых объектов методом трассировки ссылок (tracing) (Mark) Перечисление живых объектов методом трассировки ссылок (tracing) (Compact) уплотнение кучи и обновление ссылок (Compact) уплотнение кучи и обновление ссылок Возобновление пользовательских нитей Возобновление пользовательских нитей Сложность распараллеливания

Compact: 2 fingers Алгоритм Указатель свободных блоков сканирует свободные блоки с начала кучи Указатель свободных блоков сканирует свободные блоки с начала кучи Указатель занятых сканирует занятые с конца кучи Указатель занятых сканирует занятые с конца кучи Занятые блоки из конца копируются на свободное место в начале Занятые блоки из конца копируются на свободное место в начале При перемещении блока на старом месте остается ссылка на новое положение При перемещении блока на старом месте остается ссылка на новое положение Заканчивается при встрече указателей Заканчивается при встрече указателей Все ссылки в сжатой куче обновляются при помощи обратных ссылок Все ссылки в сжатой куче обновляются при помощи обратных ссылок Линейное время, 2 прохода по куче – сжатие и обновление ссылок Не полностью сжимает кучу из блоков различного размера Разрушает локальность данных free live copy forward reference

Compact: Break Table Алгоритм Непрерывные занятые блоки последовательно сдвигаются к началу кучи Непрерывные занятые блоки последовательно сдвигаются к началу кучи При сдвиге блока с номером i в таблицу заносится (a i, s i ) При сдвиге блока с номером i в таблицу заносится (a i, s i ) a i – адрес начала блока до сдвига s i – сдвиг Для каждой ссылки r двоичным поиском в таблице находится блок a i, такой a i r < a i+1 Для каждой ссылки r двоичным поиском в таблице находится блок a i, такой a i r < a i+1 Значение ссылки заменяется на r = r – s i Значение ссылки заменяется на r = r – s i Для хранения таблицы используются пустые блоки кучи Для ускорения поиска в таблице используется хеш- таблица по старшим битам ссылки

Mark&Sweep&Compact M&C может использоваться совместно M&S при обнаружении избыточной фрагментации Избыточная фрагментация – невозможность разместить непрерывный блок в памяти при наличии достаточного свободного места в блоках меньшего размера

Полупространственный копирующий GC (Semi-space copying GC) Алгоритм Остановка нитей Остановка нитей Перечисление живых объектов методом трассировки ссылок Перечисление живых объектов методом трассировки ссылок Живые объекты копируются из From в То во время трассировки Живые объекты копируются из From в То во время трассировки Восстановление ссылок используя обратные ссылки Восстановление ссылок используя обратные ссылки From и To меняются местами From и To меняются местами Возобновление нитей Возобновление нитей From To copy forward reference

Полупространственный копирующий GC: Свойства Одно из полупространств всегда пусто Возможно нерациональное использование виртуальной памяти Возможно нерациональное использование виртуальной памяти Долгоживущие объекты копируются при каждой GC Разрушение локальности данных при копировании

Одновременное использование нескольких GC Класс объекта известен при создании – возможность выбора стратегии размещения и сборки мусора для объекта Возможные варианты: Обычный – маленькие объекты, копирующая GC Обычный – маленькие объекты, копирующая GC Large Object Space – пространство больших объектов – неперемещающая GC Large Object Space – пространство больших объектов – неперемещающая GC Primitive Large Object Space – пространство больших массивов примитивных типов, неперемещающая GC, не содержит ссылок, не требует трассировки Primitive Large Object Space – пространство больших массивов примитивных типов, неперемещающая GC, не содержит ссылок, не требует трассировки Primitive Object Space – пространство массивов и маленьких объектов с полями примитивных типов, копирующая GC, не содержит ссылок, не требует трассировки Primitive Object Space – пространство массивов и маленьких объектов с полями примитивных типов, копирующая GC, не содержит ссылок, не требует трассировки Old Space – пространство старых маленьких объектов, неперемещающая GC, трассировка внешних ссылок при помощи запомненного множества (remember set) Old Space – пространство старых маленьких объектов, неперемещающая GC, трассировка внешних ссылок при помощи запомненного множества (remember set) Недостаток: неэффективное использование виртуальной памяти на 32 бит платформе при большом количестве пространств

Конкурентная эвакуация Эвакуация объектов производится одновременно с исполнением пользовательского кода То инвариантТо инвариант Пользовательский код видит только объекты в целевом пространстве Пользовательский код видит только объекты в целевом пространстве Реализуется с помощью Read/Write барьера отслеживающего ссылку на новое положение в заголовке объекта Реализуется с помощью Read/Write барьера отслеживающего ссылку на новое положение в заголовке объекта Пример: Metronome Пример: Metronome Эквивалентность объектов в From и То Объекты в целевом и исходном пространстве гарантированно имеют одинаковые значения полей Объекты в целевом и исходном пространстве гарантированно имеют одинаковые значения полей Реализуется при помощи Write барьера обновляющего значения полей в обоих пространствах при наличии ссылки на новое положение в заголовке объекта Реализуется при помощи Write барьера обновляющего значения полей в обоих пространствах при наличии ссылки на новое положение в заголовке объекта Пример: Sapphire Пример: Sapphire

Sun Generational GC Память разделена на Новую область (New Region) и Старую область (Old Region) Новая область разбита на Кущи (Eden) и 2 полупространства для выживших (Survivor semi-spaces) From и To Во всех частях Новой области используется последовательное выделение памяти Новые объекты создаются в кущах При заполнении Кущей живые объекты копируются в To To и From меняются местами В следующий раз При заполнении Кущей, живые объекты из Кущей и From копируются в To Существует время владения (Tenuring Threshold) определяющее количество раз объект может быть скопирован между полупространствами для выживших перед перемещением в Старую область

Пример EdenSS1SS2Old EdenSS1SS2Old EdenSS1SS2Old EdenSS1SS2Old First GC Second GC EdenSS1SS2Old New Object RegionOld Object Region