А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 118
Текст из файла (страница 118)
1. Свободен. Блок памяти, находящийся в состоянии Свободная, готов для выделения. Таким образом, свободный блок не должен хранить достижимый объект. 2. Недостижим. Блоки считаются недостижимыми, если только их достижимость не доказана путем отслеживания. Пока его достижимость не установлена, блок памяти в процессе сборки мусора находится в состоянии Недосгп иж им. 3. Несканирован. Блоки памяти, достижимость которых установлена, могут находиться в одном их двух состояний — Несканирован или Сканирован.
Блок находится в состоянии Несканирован, если известно, что он достижим, но указатели в нем еще не просканированы. Переход в состояние Несканирован из состояния Недос«пижии осуществляется при определении достижимости блока (см. рис. 7.23, б). 4. Сканирован. Каждый несканированный объект в конечном счете должен быть просканирован и перейти в состояние Сканировал. Для сканирования обьекта в нем отслеживаются все указатели и объекты, на которые они указывают.
Если обнаружена ссылка на объект в состоянии Недостижим, он 581 7.б. Введение в сборку на основе отслеживания Выделение памяти Свободен Недостижим а) Перед отслеживанием: действие мутатора вимо невого ества б) Отслеживаниедостижимости Освобождение Свобо дев Подготовка к следующей сборке Скоиировои в) утилизация памяти Рис.
7.23. Состояния памяти в цикле сборки мусора переходит в состояние Несканирован. По завершении сканирования объект переходит в состояние Скгтнирован (см. нижнюю часть рис. 7.23, б). Сканированный объект может содержать ссылки только на другие объекты в состоянии Сканирован или Несканирован и никогда — на объекты в состоянии Недостижим. Когда больше не остается объектов в состоянии Несканнрован, вычисление достижимости завершается.
Объекты, оставшиеся после этого в состоянии Недостилсим, являются действительно недостижимыми объектами. Сборщик мусора утилизирует занимаемую имн память и помещает соответствующие блоки памяти в состояние Свободен, что показано сплошной линией на рис.
7.23, в. Для подготовки к следующей сборке мусора объекты из состояния Сканирован переходят в состояние Недостижим (пунктирная линия на рис. 7.23, в). Помните, что на самом деле сейчас все эти объекты достижимы; состояние Недослтижим потребуется при следующем цикле сборки мусора, поскольку к тому моменту достижимые в настоящее время объекты могут превратиться в недостижимые. 582 Глава 7. Среды времени выполнения Пример 7.13. Рассмотрим, как структуры данных алгоритма 7.12 связаны с четырьмя описанными состояниями.
Членство в списках аггее и 1улзеаппес) и бит достижимости позволяют однозначно идентифицировать все четыре состояния. На рис. 7.24 приведены всех четыре состояния в терминах структур данных алгоритма 7.12. Е Рис. 7.24. Представление состояний в алгоритме 7.12 7.6.3 Оптимизация алторитма "пометить и подмести" Последний шаг базового алгоритма дорогостоящ в силу отсутствия простого способа поиска только недостижимых объектов без просмотра всей кучи.
Усовершенствованный алгоритм Бейкера (Ва1сег) поддерживает список всех обьектов, для которых выделена память. Для того чтобы найти множество недостижимых объектов, память которых следует освободить, необходимо вычислить разность множества всех объектов и множества достижимых объектов. Алгоритм 7.14. Сборщик мусора "пометить и подмести" Бейкера Вход: корневое множество объектов, куча, список свободных блоков аггее и список 17лгеаспеИ объектов, для которых выделена память. Выход: модифицированные списки свободных блоков атее и выделенной памяти Ии.еаелес1. Метод: В этом алгоритме, показанном на рис.
7.25, структуры данных сборщика мусора представляют собой четыре списка, Ггее, (/пгеаслес1, 17лзсаппег! и Бсаплеа', каждый из которых хранит все обьекты с состоянием, соответствующим имени списка. Эти списки могут быть реализованы как встроенные дважды связанные списки из раздела 7.4.4. Бит достижимости объекта не используется, но мы считаем, что у каждого объекта имеются биты, указывающие, в каком из четырех состояний находится этот обьект. Изначально аггее представляет собой список, поддерживаемый диспетчером памяти, а все объекты, для которых выделена память, находятся в списке Ии.еасЬеа' (также поддерживаемом диспетчером памяти при выделении памяти для объектов).
В строках 1 и 2 инициализируются список бсаппег7, представляющий собой пустое множество, и список 17пясалпес1, который содержит объекты, достижи- 583 7.6. Введение в сборку на основе отслеживания Ясаппей = И; Ппксаппей = множество объектов, на которые есть ссылки из корневого множества. Объекты, помещенные в множество Утеаппей, удаляются из множества 17пгеаслей; иЫ!е (Уптеаппей ~ О) ( переместить объект о из (Гпзсаппей в Всаппей; !ог (Каждый объект о', на который есть ссылки из о) ( !! (о' е 17пгеаслей) Переместить о' из (упгеаепей в 17пзсаппей; 1) 2) 3) 4) 5) 6) 7) 8) ггее = ггее 0 Ипгеаелей; 9) Ииеасйей = Бсаппей; Рис. 7.25.
Алгоритм "пометить н подмести" Бейкера В обоих алгоритмах этого раздела считается, что блоки, которые возврашаются в список свободных, остаются такими же, какими были до освобождения. Однако, как говорилось в разделе 7.4.4, объединение смежных свободных блоков в ббльшие блоки имеет свои преимущества.
Если мы хотим делать это, то всякий раз при возврате блока в список свободных блоков в строке 10 на рис. 7.21 или в строке 8 на рис. 7.25 следует проверить, не свободны ли блоки слева н справа от освобождаемого, и выполнить слияние, если имеется смежный свободный блок. 7.6.4 Сборщики мусора "пометить и сжать" Перемещающие (ге!оса1гн8) сборщики переносят достижимые объекты в куче таким образом, чтобы устранить фрагментацию памяти.
Обычно занятое достижимыми объектами пространство существенно меньше освобожденной памяти. Таким образом, после идентификации всех "дыр" между достижимыми объектами мые из корневого множества. Заметим, что эти объекты ранее предположительно находились в списке Упгеасйей, из которого они должны быть удалены. Строки 3 — 7 представляют собой непосредственную реализацию базового алгоритма маркировки с использованием упомянутых списков.
Цикл Бог в строках 5 — 7 просматривает ссылки в несканированном объекте о, и, если какие-то из этих ссылок о' не были достижимы, в строке 7 состояние о' изменяется на несканированное. В конце строка 8 берет множество объектов, все еше остающихся в списке Упгеаспей, и освобождает их память, перенося их в список ггее. Строка 9 берет все отсканированные объекты и инициализирует список ~/пгеасйей этими объектами.
При создании новых объектов диспетчер памяти будет изымать соответствующие блоки из списка ггее и добавлять их в список 17пгеасйей. а 584 Глава 7. Среды времени выполнения можно не освобождать их индивидуально, а просто переместить все достижимые объекты в один конец кучи, оставив всю остальную память кучи в виде одного большого блока свободной памяти. В конце концов, сборщик все равно анализирует все ссылки в достижимых объектах, так что обновить их так, чтобы они указывали на новые местоположения объектов, — не такая уж большая работа. К ним следует только не забыть добавить ссылки из корневого множества, которые также должны быть обновлены.
Сборка всех достижимых объектов в смежных позициях снижает фрагментацию памяти, упрощая размещение крупных объектов. Кроме того, данные при этом занимают меньше строк кэша и страниц, так что перемещение повышает временную и пространственную локальность приложения. Это связано с тем, что новые объекты создаются примерно в одно и то же время и в близко расположенных блоках памяти. Объекты в близких блоках памяти используют преимущества предвыборки при совместном использовании. При перемещении упрощается также структура для управления свободной памятью: все, что нам надо вместо списка свободных блоков, — указатель атее на начало свободного блока.
Перемещающие сборщики различаются: одни выполняют перемещение без привлечения дополнительной памяти, "на месте", другие резервируют пространство для перемещения. ° Сборщик "пометить и сжать", описанный в этом разделе, выполняет уплотнение "на месте". Такое уплотнение снижает количество необходимой для сжатия памяти. ° Более эффективный и популярный копирующий сборщик нз раздела 7.6.5 перемещает объекты из одной области памяти в другую.
Резервирование дополнительной памяти позволяет перемещать объекты по мере их обнаружения. Сборщик "пометить и сжать" из алгоритма 7.15 состоит из трех фаз. 1. Первая фаза — маркировка, аналогичная такой же фазе из ранее рассматривавшихся алгоритмов "пометить и подмести". 2. Во второй фазе алгоритм сканирует выделенный раздел кучи и вычисляет новые адреса для каждого достижимого объекта.
Новые адреса назначаются с нижнего конца кучи так, чтобы между достижимыми объектами не было неиспользованных промежутков. Новые адреса каждого объекта записываются в структуру Феи~Еосаг1ол. 3. Наконец, алгоритм копирует объекты в их новые позиции, параллельно обновляя все ссылки в этих объектах так, чтобы они указывали на новые положения в памяти. Необходимые адреса можно найти в структуре МеиЛосайол.
7.6. Введение в сборку на основе отслеживания 585 Алгоритм 7.15. Сборщик мусора "пометить и сжать" Вход: корневое множество объектов, куча и указатель аггее на начало свободного пространства. Выход: новое значение указателя7гее. Метод: алгоритм на рис. 7.26, использующий следующие структуры данных. !. Список !7тсалпег), как и в алгоритме 7.12. 2.
Биты достижимости во всех объектах, как в алгоритме 7.12. Для того чтобы упростить описание алгоритма, будем называть объекты достижимыми или недостижимыми, имея в виду равенство их битов достижимости соответственно ! или О. Изначально все объекты недостижимы. 3. Указатель аггее, который отмечает начало нераспределенной памяти в куче. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
