А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 121
Текст из файла (страница 121)
Таким образом, имеется несколько методов, которые позволяют обойтись запоминанием меньшего количества деталей. ° Вместо запоминания точного адреса записываемых объекта и поля можно запомнить только объект, в котором содержится это поле. ° Можно разделить память на блоки фиксированного размера, известные как карты (сапЬ), и использовать битовый массив для запоминания карт, в которые выполнялась запись. ° Можно запоминать страницы, которые содержат записываемые ячейки памяти.
Можно защитить только страницы, содержащие объекты в состоянии Сканировал. Тогда все записи в сканированные объекты будут обнаружены без явного выполнения каких-либо команд, поскольку они будут приводить к нарушению защиты, и операционная система будет генерировать соответствующие программные исключения. В общем случае огрубление уровня детализации, на котором выполняется запоминание записанных позиций, приводит к меньшему количеству требуемой памяти, но повышенным затратам на повторное сканирование.
В первой схеме должны быть сканированы все ссылки в измененных объектах, независимо от того, какая именно ссылка была модифицирована. В двух последних схемах в конце процесса отслеживания требуется повторно сканировать все достижимые обьекты в измененных картах или страницах. Объединение инкрементных и копирующих методов Описанных выше методов достаточно для сборки мусора "пометить и подмести". Копирующая сборка несколько более сложная из-за ее взаимодействия с мутатором. Объекты в состояниях Сканировал и Кесканирован имеют по два адреса: один — в полупространстве Р'гот, другой — в полупространстве То.
Как в алгоритме 7.16, мы должны поддерживать отображение старого адреса обьекта на его новый адрес после перемещения. Имеется два варианта обновления ссылок. Во-первых, можно заставить мутатор выполнять все изменения в полупространстве гогот и только в конце сборки 596 Глава 7.
Среды времени выполнения мусора обновить все указатели и скопировать все содержимое в полупространство То. Во-вторых, можно вносить все изменения в представление в полупространстве То. Когда мутатор разыменовывает указатель в полупространство Ггогп, этот указатель транслируется в новое положение в полупространстве То, если таковое существует. В конце все указатели должны быть транслированы таким образом, чтобы указывать в полупространство То. 7.7.3 Основы частичной сборки Фундаментальным является тот факт, что, как правило, объекты "умирают молодыми*'. Было обнаружено, что обычно от 80 до 98'Ь вновь созданных обьектов уничтожаются в пределах нескольких миллионов команд или до того, как будет выделен следующий мегабайт памяти.
Таким образом, очень часто объекты становятся недостижимыми еще до начала сборки мусора. Таким образом, достаточно выгодно часто выполнять сборку мусора новых объектов. Объекты, которые переживут одну сборку мусора, скорее всею, переживут и многие другие. При работе описанных до сих пор сборщиков мусора одни и те же "старые" объекты будут определяться как достижимые вновь н вновь и в случае копирующих сборщиков будут снова и снова, при каждом запуске сборщика, перемещаться в памяти с места на место. Сборка мусора по поколениям чаше всего работает в области кучи, содержащей самые молодые объекты, так что при этом, как правило, собирается мною мусора ценой относительно небольшой работы.
С другой стороны, алгоритм поезда не тратит большую часть времени на молодые объекты, но уменьшает паузы в работе программы, возникающие из-за сборки мусора. Таким образом, одна из неплохих стратегий состоит в объединении указанных алгоритмов, когда сборка мусора по поколениям применяется для молодых объектов; когда объект достаточно "стареет", он переносится в отдельную кучу под управлением алгоритма поезда. Будем говорить о множестве объектов, которые обрабатываются в одном цикле частичной сборки мусора, как о пеленам (гагйег) множестве, а об остальных обьектах — как о пиабильиам (згаЫе) множестве. В идеальном случае частичный сборщик мусора должен утилизировать все объекты целевого множества, которые недостижимы из корневого множества.
Однако это требует прохода по всем объектам, т.е, именно того, чего мы стремимся избежать. Поэтому частичные сборщики консервативно утилизируют только те объекты, которые не могут быть достигнуты ни из корневого, ни из стабильного множества. Поскольку некоторые объекты в стабильном множестве сами могут оказаться недостижимыми, может оказаться так, что достижимыми будут считаться некоторые объекты целевого множества, к которым на самом деле не существует путей из корневого множества. Можно адаптировать сборщики мусора, описанные в разделах 7.6.1 и 7.6.4, для работы в качестве частичных путем изменения определения корневого мно- 597 7.7. Распределенная сборка мусора жества.
Вместо того, чтобы рассматривать только объекты в регистрах, стеке и глобальных переменных, корневое множество теперь должно включать все объекты стабильного множества, которые указывают на объекты целевого множества. Как и раньше, для поиска всех достижимых объектов отслеживаются ссылки из целевых объектов на другие целевые объекты. Можно игнорировать все указатели на стабильные объекты, поскольку в данном запуске частичной сборки все эти объекты рассматриваются как достижимые. Чтобы определить стабильные объекты, имеющие ссылки на целевые объекты, можно применить методы, подобные использующимся в инкрементальной сборке мусора. В инкрементальной сборке требуется помнить все записи ссылок из сканированных объектов на недостижимые в процессе отслеживания.
Здесь же необходимо запоминать все записи ссылок из стабильных объектов на целевые во время работы мутатора. Когда мутатор сохраняет в стабильном объекте ссылку на обьект из целевого множества, надо запомнить либо ссылку, либо место записи. Будем говорить о множестве объектов, хранящих ссылки из стабильных объектов на целевые, как о зпподгнелном множестве (гешешЬегед зе1) для данного набора целевых объектов.
Как говорилось в разделе 7.7.2, можно уменьшить представление запомненного множества, если записывать только карту или страницу, содержащую объект, в который выполняется запись. Частичные сборщики мусора часто реализуются как копирующие. Некопирующие сборщики могут быть также реализованы с использованием связанных списков для отслеживания достижимых объектов. Описанная ниже схема "по поколениям" представляет собой пример комбинации копирования с частичной сборкой. 7.7.4 Сборка мусора по поколениям Сборка мусора по поколениям представляет собой эффективный способ использования того свойства, что большинство обьектов "умирают молодыми". Куча в этом случае разбивается на ряд разделов.
Будем использовать соглашение об их нумерации как О, 1,2,..., и, где разделы с малыми номерами хранят более молодые объекты. Первоначально объекты создаются в разделе О. По заполнении раздела О в нем выполняется сборка мусора, а все достижимые объекты переносятся в раздел 1. Теперь, когда раздел О вновь пуст, продолжим создание новых объектов в этом разделе. Когда же раздел О заполнится опятьч, в нем выполняется сборка мусора, и достижимые объекты из него копируются в раздел 1, где Технически раздел ие "заполняется", поскольку ири необходимости ои может быть расширен диспетчером памяти зв счет дополнительных блоков ив диске.
Однако обычно сушествует предельный размер раздела, отличный от указанного. Мы будем говорить о достижении этого предела квк о заполнении раздела. 598 Глава 7. Среды времени выполнения присоединяются к ранее скопированным объектам. Эти действия повторяются до заполнения раздела 1; в этот момент выполняется сборка мусора в разделах О и 1. В обшем случае в каждом цикле сборка мусора применяется ко всем разделам с номерами 1 и менее для некоторого 1.
Значение 1 — это максимальный номер заполнившегося к этому моменту раздела. Каждый раз, когда объект переживает сборку мусора (т.е. выясняется его достижимость), он переносится из своего раздела в раздел со следуюшим по величине номером, пока не достигнет раздела с наибольшим номером и. Пользуясь терминологией из раздела 7.7.3, можно сказать, что, когда выполняется сборка мусора в разделах с номерами 1 и меньших, разделы от О до 1 составляют целевое множество, а все разделы с номерами больше 1 — стабильное множество. Для обеспечения поиска корневых множеств для всех возможных частичных сборок мусора для каждого раздела 1 поддерживается започненное множество (гешешЬегед зе1), состоящее из всех объектов в разделах с номерами больше г, которые указывают на объекты в множестве 1. Корневое множество частичной сборки мусора, выполняемой над разделом 1, включает запомненные множества для раздела 1 и разделов с номерами, меньшими 1.
В такой схеме при выполнении сборки мусора в разделе 1 выполняется также сборка во всех разделах с номерами, меныпими 1. Такая стратегия основана на двух соображениях. 1. Поскольку более молодые поколения содержат большее количество мусора и сборка у них в любом случае выполняется более часто, ее имеет смысл выполнить и при сборке мусора в более старом поколении. 2. Следуя описанной стратегии, нам надо запоминать только ссылки, указывающие из объектов более старых поколений на объекты более молодые. Иными словами, ни запись объекта более молодого поколения, ни перенос объекта в следующее поколение не приводят к обновлению никакого из запомненных множеств.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
