А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 122
Текст из файла (страница 122)
Если бы выполнялась сборка мусора в более старшем поколении без сборки в младших поколениях, то более молодое поколение стало бы частью стабильного множества, и мы должны были бы запоминать ссылки, которые из более молодого поколения указывают на более старое. Итак, данная схема собирает мусор среди более молодых объектов болсе часто, причем такая сборка оказывается более эффективной по сравнению с полной, поскольку объекты "умирают молодыми". Сборка мусора в старших поколениях отнимает больше времени, поскольку она включает сборку во всех младших поколениях, а кроме того, старшие поколения содержат меньшее количество мусора. Тем не менее иногда требуется сборка мусора и в старших поколениях для удаления недостижимых объектов.
Самое старшее поколение содержит самые старые 599 7.7. Распределенная сборка мусора объекты, а сборка мусора в нем эквивалентна полной сборке мусора в куче. Иначе говоря, такая схема иногда приводит к необходимости полного отслеживания всех объектов в куче и, соответственно, к большим паузам в выполнении программы. Альтернативный способ обработки только старых объектов описывается в следующем разделе. 7.7.5 Алгоритм поезда Сборка мусора по поколениям очень эффективна для молодых объектов, но существенно менее эффективна в применении к старым объектам, поскольку старые объекты должны перемещаться всякий раз при охватывающей их сборке; кроме того, они редко бывают мусором.
Для повышения эффективности обработки старых объектов был разработан другой алгоритм инкрементной сборки мусора, получивший название алгоритм поезда (ггаш а!бог11Ьп), Он может применяться для сборки всего мусора, однако, пожалуй, лучше всего для работы с молодыми объектами использовать сборку мусора по поколениям, а объекты, пережившие несколько циклов таких сборок, переносить в другую кучу, которая управляется алгоритмом поезда. Еще одним преимуществом алгоритма поезда является то, что нам никогда не потребуется выполнять полную сборку мусора, что все же приходится время от времени делать при сборке мусора по поколениям.
Чтобы объяснить, откуда взялся алгоритм поезда„давайте рассмотрим простой пример, почему время от времени необходима полная сборка мусора при применении сборки по поколениям. На рис. 7.29 показаны два объекта с взаимными ссылками друг на друга, находящиеся в двух разделах, г и 7', где 7 > ю'. поскольку на оба объекта имеются ссылки извне раздела, сборка мусора только лишь в разделе г или только в разделе 7 никогда не подберет ни один из указанных объектов, которые на самом деле могут оказаться частью циклической структуры, не имеющей ссылок на нее извне и являющейся, таким образом, мусором.
В общем случае показанные связи между объектами могут быть сложнее и включать большее количество объектов и длинные цепочки ссылок. Рнс. 7.29. Циклическая структура, охватывающая разные поколения, может оказаться циклическим мусором В сборке мусора по поколениям рано или поздно происходит сборка в разделе 7', а поскольку г ( 7', в этот же момент выполняется сборка и в разделе г. Таким образом, рассматриваемая структура оказывается полностью содержащейся в ча- боо Глава 7. Среды времени выполнения сти кучи, в которой выполняется сборка мусора, и при этом точно выясняется, является ли она мусором.
Однако, если сборка мусора одновременно в блоках г.' и 7' не выполняется, мы получаем те же проблемы с циклическими ссылками, что и при использовании счетчиков ссылок. Алгоритм поезда использует разделы фиксированного размера, называющиеся вагонами (саг); вагон может представлять собой отдельный дисковый блок прн условии, что не существует объектов, размер которых больше размера дискового блока; вагон может быть и большего размера, но этот размер фиксирован раз и навсегда.
Вагоны собраны в поезда (Ггагп). Ограничений на количество вагонов в поезде нет, как не ограничено и количество поездов. Вагоны могут быть лексикографически упорядочены: сначала — по номеру поезда, а в пределах поезда— по номеру вагона, как показано на рис. 7.30. Поезд! ~~цкон11) [Вегон12 ~ Поезд2 ~Вагон 21~ [Вагон2]2 [Вагоон23~ ~ Ве он2Е1 ПоездЗ ~вегон31~ ~Вкон3~2 ~Ве..онзз] Рис. 7.30. Организация кучи лля алгоритма поезда Существует два способа сборки мусора алгоритмом поезда. ° Выполняется сборка мусора в первом вагоне в лексикографическом порядке (первый оставшийся вагон первого оставшегося поезда) за один шаг инкрементной сборки.
Этот шаг аналогичен сборке мусора в первом разделе алгоритма сборки мусора по поколениям, поскольку мы поддерживаем "запомненный" список всех указателей извне вагона. На этом шаге мы идентифицируем как объекты без внешних ссылок, так и циклические структуры, являющиеся мусором и полностью размещающиеся в пределах одного вагона. Достижимые объекты вагона всегда перемещаются в некоторый другой вагон, так что каждый вагон, в котором проведена сборка мусора, становится пустым и может быть "отцеплен" от поезда. ° Иногда первый поезд не содержит внешних ссылок на него, т.е. не существует указателей из корневого множества ни на один вагон поезда, а запомненные множества вагонов содержат только указатели от других вагонов поезда, но не от других поездов. В таком случае поезд представляет собой большую коллекцию циклического мусора и можно удалить весь поезд целиком.
601 7.7. Распределенная сборка мусора Запомненные множества Теперь рассмотрим детали алгоритма поезда. Каждый вагон имеет запомненное множество, состоящее из всех ссылок на объекты вагона из а) объектов вагонов того же поезда с ббльшими номерами; б) объектов поездов с ббльшими номерами.
Кроме того, каждый поезд имеет запомненное множество, состоящее из всех ссылок из поездов с ббльшими номерами, т.е. запомненное множество поезда представляет собой объединение запомненных множеств его вагонов, за исключением ссылок, являющихся внутренними для данного поезда. Оба типа запомненных множеств могут быть разделены на внутреннюю (ссылки из того же поезда) и внешнюю (ссылки из иных поездов) части. Заметим, что ссылки на объекты могут быть откуда угодно, а не только из объектов, следующих за данным в лексикографическом порядке.
Однако указанные два процесса сборки мусора работают соответственно с первым вагоном первого поезда и с первым поездом в целом. Таким образом, когда в процессе сборки мусора требуется использовать запомненные множества, все ссылки могут быть только из более поздних в лексикографическом порядке вагонов и поездов — просто потому, что работа идет с первым в этом порядке вагоном (поездом). А значит, нет необходимости в запоминании ссылок из более ранних в лексикографическом порядке вагонов (поездов) в более поздние. Конечно, следует аккуратно работать с запомненными множествами, внося в них изменения всякий раз, когда мутатор переписывает ссылки в любом объекте.
Управление поездами Наша цель — выявить в первом поезде все объекты, не являющиеся циклическим мусором. Затем либо в первом поезде не остается ничего, кроме циклического мусора, который будет утилизирован в следующем цикле сборки мусора, либо, если мусор не является циклическим, вагоны первого поезда могут быть обработаны по одному. Следовательно, время от времени нам надо начинать новые поезда, несмотря на то, что ограничений на количество вагонов в поезде нет (так что„когда требуется дополнительная память, в принципе, можно просто добавить новый вагон к единственному поезду).
Например, мы можем начинать новый поезд после каждых )г созданий обьектов, где )г — некоторое заранее выбранное число. Иначе говоря, в общем случае новый объект размещается в последнем вагоне последнего поезда, если в нем имеется достаточно памяти, или, если памяти не хватает, в новом вагоне, который добавляется в конец последнего поезда. Однако периодически следует вместо этого начинать новый поезд с одним вагоном, в котором и размещать создаваемый объект.
бйг Глава 7. Среды времени выполнения Сборка мусора в вагоне Ключевым моментом в алгоритме поезда является обработка первого вагона первого поезда в процессе выполнения цикла сборки мусора. Изначально в множество достижимых объектов входят те объекты вагона, на которые имеются ссылки из корневого множества и из запомненного множества этого вагона. Затем мы сканируем объекты вагона, как и в случае сборки мусора "пометить и подмести", но не сканируем ни один достижимый обьект вне обрабатываемого вагона.
После такого отслеживания некоторые объекты в вагоне могут быть идентифицированы как мусор. Утилизировать выделенную им память незачем, поскольку все равно весь вагон будет удален. Однако вполне вероятно наличие в вагоне и достижимых объектов, которые должны быть перенесены в другое место. Вот как выглядят правила перемещения объектов. ° Если в запомненном множестве имеется ссылка из некоторого другого ваюна (номер которого больше, чем номер вагона, в котором выполняется сборка), то обьект перемещается в один из вагонов, из которых на него есть ссылка.
Если имеется достаточное количество свободной памяти, объект может быть размешен в существуюшем ваюне поезда — источника ссылки; в противном случае объект может быть помещен в новый вагон. ° Если ссылок из других вагонов нет, но есть ссылка из корневого множества или нз первого вагона, то объект перемещается в любой другой вагон данного поезда (или в новый вагон, если памяти в имеющихся вагонах недостаточно). По возможности следует выбирать тот ваго, из которого имеется ссылка на перемешаемый объект, — это поможет локализации циклической структуры в пределах одного вагона.
После перемещения всех достижимых объектов из первого вагона этот вагон удаляется. Режим паники С приведенными выше правилами связана одна проблема. Чтобы быть уверенным, что в конечном итоге будет собран весь мусор, необходима гарантия, что каждый поезд рано или поздно станет первым, и если этот поезд не представляет собой просто циклический мусор, то в конце концов все вагоны поезда будут удалены и поезд исчезнет по одному вагону за раз. Однако в соответствии со вторым правилом сборка мусора в первом вагоне первого поезда может привести к появлению нового последнего вагона. Очевидно, что при сборке не могут быть созданы два и более новых вагонов, поскольку все, что размещалось в первом вагоне, вполне поместится в новом, последнем вагоне.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
