А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 120
Текст из файла (страница 120)
Первый подход известен как инкрементная сборка (1псгешепга! со11есйоп), а второй — как частичная сборка (рапба! со!!есбоп). Инкрементный сборщик мусора разбивает анализ достижимости на небольшие модули, позволяя мутатору работать в промежутках между работой этих модулей. В процессе работы мутатора множество объектов изменяется, так что инкрементная сборка мусора усложняется.
Из раздела 7.7.1 вы узнаете, что поиск несколько более консервативного ответа может повысить эффективность отсле- живания. Наилучший из известных алгоритмов частичной сборки — сборка мусора яо локолсниям (йепегайопа! 8агЬайе со1!есбоп). Он разбивает объекты в соответствии с тем, как давно они были созданы, и выполняет сборку мусора среди недавно созданных объектов более часто, поскольку, как правило, в среднем их время жизни меньше. Альтернативой является алгоритм поезда (!га(п а18ог(1Ьш), также собирающий мусор в подмножествах объектов, но этот алгоритм дает лучшие результаты при работе с более старыми объектами.
Два указанных алгоритма могут использоваться совместно для разработки частичного сборщика мусора, который по-разному обрабатывает более молодые и более старые объекты. Базовый алгоритм, лежащий в основе частичной сборки, будет рассмотрен в раздслс 7.7.3, а затем более детально будет рассмотрена работа алгоритма сборки по поколениям и алгоритма поезда. Идеи инкрементной и частичной сборки могут использоваться для создания алгоритма, который в многопроцессорной среде выполняет параллельную сборку мусора (см.
раздел 7.8.1). 7.7.1 Инкрементная сборка мусора Инкрементные сборщики мусора консервативны. Сборщик мусора не только не должен собирать объекты, не являющиеся мусором, но и не обязан собирать 592 Глава 7. Среды времени выполнения весь мусор при каждом запуске. Будем говорить о мусоре, остающемся после сборки, как о плавающем мусоре (1)оа11пк кагЬаяе).
Конечно, желательно минимизировать плавающий мусор. В частности, инкрементный сборщик не должен оставлять никакой мусор, который был недостижим в начале цикла сборки. Если сборщик гарантирует такое поведение, то любой мусор, не собранный в некотором цикле, будет собран в следующем, так что при таком подходе нет никаких утечек памяти.
Другими словами, инкрементные сборщики обеспечивают безопасность определенной переоценкой множества достижимых объектов. Сначала они автоматически обрабатывают корневое множество программы, не взаимодействуя с мутатором. После определения начального множества несканированных объектов действия мутатора чередуются с отслеживанием. В это время любые действия мутатора, которые могут изменить достижимость, кратко записываются в дополнительной таблице, так что сборщик может внести необходимые изменения при возобновлении работы. Если память оказывается исчерпанной до завершения отслеживания, мутатор останавливается и сборщик завершает свою работу без перерывов. В любом варианте по завершении отслеживания утилизация памяти выполняется автоматически. Точность инкрементной сборки После того как объект становится недостижимым, его невозможно сделать достижимым вновь.
Таким образом, в процессе работы сборщика и мутатора множество достижимых объектов может только 1, расти благодаря выделению памяти для новых объектов после начала сборки мусора; 2. уменьшаться из-за потери ссылок на объекты. Пусть Л вЂ” множество достижимых объектов в начале сборки мусора, Меи— множество объектов, для которых выделена намять в процессе сборки мусора, и 7,овг — множество объектов, которые стали недостижимыми из-за потери ссылок после начала отслеживания. Множество достижимых объектов по завершении отслеживания— ( 1т' О Феи ) — Х ов1 Определять достижимость объекта всякий раз, когда мутатор теряет ссылку на объект, — задача дорогостоящая, так что инкрементные сборщики не пытаются собрать весь мусор по окончании отслеживания.
Любой остающийся мусор— плавающий мусор — должен быть подмножеством Аовс Выражаясь формально, множество найденных при отслеживании объектов Я должно удовлетворять соотношению (ЙОЖеи) — 7овгС Я С (Я Оапек) 593 7.7, Распределенная сборка мусора Простое инкрементное отслеживание Рассмотрим сначала простой алгоритм отслеживания, который находит верхнюю границу Н О №и. Поведение мутатора изменяется в процессе отслеживания следующим образом.
° Все ссылки„существовавшие до сборки мусора, сохраняются; т.е. прежде чем мутатор перепишет ссылку, ее старое значение запоминается и рассматривается как дополнительный несканированный объект, содержащий только одну эту ссылку. ° Все созданные объекты немедленно рассматриваются как достижимые„ и им назначается состояние Несканирпван. Такая схема консервативна, но корректна, поскольку она находит множество Н всех достижимых до начала сборки мусора объектов, плюс множество №и всех вновь созданных объектов. Однако стоимость такого метода высока, поскольку алгоритм перехватывает все операции записи и запоминает все перезаписанные ссылки. Часть этой работы излишня, поскольку может включать объекты, недостижимые в конце сборки мусора.
Можно избежать выполнения некоторой доли этой работы и повысить точность и эффективность алгоритма, если удастся определить, когда переписанные ссылки указывают на объекты, недостижимые в конце текущего цикла сборки мусора. В описанном ниже алгоритме используются указанные идеи. 7.7.2 Инкрементный анализ достижимости Если работа мутатора чередуется с работой базового алгоритма отслеживания, такого как алгоритм 7.12, то некоторые достижимые объекты могут быть ошибочно классифицированы как недостижимые. Проблема в том, что действия мутатора способны нарушить ключевой инвариант алгоритма, а именно — то, что Сканированный объект может содержать ссылки только на другие Сканированные или Несканированные объекты, но никогда — на объекгы Недостижимые.
Рассмотрим слелукнпий сценарий. 1. Сборщик мусора выясняет, что объект о1 -- достижимый, и сканирует ука- затели внутри оы помещая при этом объект о1 в состояние Сканирован. 2. Мутатор сохраняет ссылку на объект о, находящийся в состоянии Недостижим (но при этом достижимый), в объекте о1 в состоянии Сканирован. Это делается путем копирования ссылки на о из объекта оз, который в настоящий момент находится в состоянии Недостижим или Несканирован. 3. Мутатор теряет ссылку на о в объекте оз. Эта ссылка может быть переписана до того, как она будет сканирована, или оя может стать недостижимым 594 Глава 7.
Среды времени выполнения и не оказаться в состоянии Нескапирован, так что указанная ссылка так и не будет просканирована. Итак, объект о достижим через объект оы но сборщик мусора не может найти ссылку на о ни в объекте оы ни в объекте огь Ключом к более точному инкрементному отслеживанию является запись всех копирований ссылок на недостижимые в настоящий момент объекты из объектов, которые еще не были сканированы, в уже просканированные. Для перехвата проблемных пересылок ссылок алгоритм может изменять действия мутатора в процессе отслеживания любым из приведенных ниже способов.
° Барьеры записи. Перехватываются записи ссылок на объект о в состоянии Недостижим в объект о1 в состоянии Скапирован. В этом случае о классифицируется как достижимый объект и помещается в множество (7пвсаппей. Другим способом является помещение объекта о1 назад в список (7пвсаппва для повторного сканирования. ° Барьергя чтения. Перехватываются чтения ссылок из объектов в состоянии Недостижим или Несканироваи. Когда мутатор читает ссылку на объект о из объекта в состоянии Недостижим или Несканирован, объект о классифицируется как достижимый и помещается в множество ~Упвсаппед.
° Барьеры пересылки. Перехватываются потери исходных ссылок в обьектах в состоянии Недостижим или Нескапироваи. Когда мутатор переписывает ссылку в объекте в состоянии Недостижим или Несканирован, перепнсываемая ссылка сохраняется, классифицируется как достижимая н помещается в множество (7пвсаппей. Ни один из указанных вариантов не позволяет найти наименьшее множество достижимых объектов. Если в процесс отслеживания выясняется, что объект является достижимым, то он остается достижимым, даже если все ссылки на него будут переписаны до завершения отслеживания. Таким образом, найденное множество достижимых объектов находится между (Л О №ю) — 7.ов( и (Н ш №и).
Наиболее эффективным из предложенных выше вариантов является барьер записи. Барьер чтения более дорогостоящий, поскольку обычно в программе выполняется болыпе чтений, чем записей. Барьер пересылки неконкурентоспособен; поскольку многие объекты "умирают молодыми", этот подход оставляет много недостижимых объектов.
Реализация барьера записи Реализовать барьер записи можно двумя способами. Первый способ состоит в запоминании в фазе мутатора всех новых ссылок, записанных в объекты 595 7.7. Распределенная сборка мусора в состоянии Сканировал. Можно поместить все эти ссылки в список; размер такого списка пропорционален количеству операций записи в объекты в состоянии Сканировал, если только не удалять из списка дубликаты. Заметим, что ссылки в списке могут быть переписаны и потенциально проигнорированы. Второй, более эффективный, подход состоит в запоминании позиций, в которых выполнялась запись. Эти места могут быть запомнены в виде списка позиций с возможным устранением дубликатов. Заметим, что точность в указании позиций записи не важна, поскольку все они будут сканированы заново.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
