А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 117

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 117)

5. Транзитивная потеря дастижимасти. Когда значение счетчика ссылок некоторого объекта становится равным нулю, надо уменьшит значения счетчиков всех объектов, на которые указывают ссылки из исходного объекта. Счетчики ссылок имеют два основных недостатка: они не позволяют соби- рать недостижимые циклические структуры данных и их поддержка дорогостояща в плане эффективности работы программы. Циклические структуры данных достаточно распространены; например, структуры данных часто указывают на родительские узлы или друг на друга, что приводит к перекрестным ссылкам.

Пример 7.11. На рис. 7.18 показаны три объекта со ссылками между ними, но при отсутствии ссылок откуда-либо еще. Если ни один из этих объектов не является частью корневого множества, то они представляют собой мусор, однако при этом значения счетчиков ссылок каждого из объектов больше О. Такая ситуация при использовании подсчета ссылок для сборки мусора эквивалентна утечке памяти, Указателей извне нет Рнс. 7.18.

Недостижимая циклическая структура данных 576 Глава 7. Среды времени выполнения поскольку этот мусор, как и другие подобные структуры, никогда не будет удален из памяти. о Накладные расходы на подсчет ссылок достаточно высоки из-за наличия дополнительных операций при каждом присваивании ссылок„входе в процедуру и выходе из нее. Эти накладные расходы пропорциональны количеству вычислений в программе, а не только количеству объектов в системе. В особенности это касается обновлений ссылок в корневом множестве программы. В качестве средства снижения накладных расходов, связанных с обновлением счетчиков при обращениях к локальному стеку, была предложена концепция отложенного подсчета ссылок. Иными словами, счетчики ссылок не включают ссылки от корневого множества программы. Объект не рассматривается как мусор до тех пор, пока не будет просканировано все корневое множество и при этом не будут обнаружены ссылки на этот объект.

Преимушества подсчета ссылок заключаются в том, что сборка мусора выполняется инкрементно. Несмотря на высокие общие накладные расходы, операции распределены по всей программе. Хотя удаление одного объекта может привести к возникновению большого количества недостижимых объектов, операции рекурсивного обновления счетчиков ссылок могут легко быть отложены и выполнены по частям в разные моменты времени. Таким образом, подсчет ссылок особенно привлекателен в тех случаях, когда возникают вопросы работы в реальном времени, а также в интерактивных программах, в которых нежелательны длинные неожиданные паузы. Еще одним преимуществом подсчета ссылок является немедленная сборка мусора, обеспечиваюшая экономное использование памяти. 7.5.4 Упражнения к разделу 7.5 Упражнение 7.5Л.

Что произойдет со счетчиками ссылок объектов на рис. 7.! 9 при следующих действиях: а) удаляется указатель от А на В; б) удаляется указатель от Х на А; в) удаляется узел С. Упражнение 7.5.2. Что произойдет со счетчиками ссылок при удалении указателя на Р из А на рис. 7.20? 7.6 Введение в сборку на основе отслеживании Вместо сборки мусора в момент его образования сборщик мусора на основе отслеживания периодически запускается для поиска нелостижимых объектов 577 7.6. Введение в сборку на основе отслеживания Рис. 7.19.

Сеть объектов Рнс. 7.20. Еше одна сеть объектов и утилизации используемой ими памяти. Обычно такой сборщик мусора запускается при исчерпании свободной памяти илн когда ее количество становится меньше некоторого порогового значения. Мы начнем с рассмотрения простейшего алгоритма сборки мусора "пометить и подмести". Затем будут рассмотрены различные алгоритмы на основе отслеживания, использующие четыре состояния, в которых могут находиться блоки памяти.

В этом разделе вы также найдете массу усовершенствований базового алгоритма, включая те, в которых частью функции сборки мусора является перемещение объектов. 7.6.1 Базовый сборщик мусора Алгоритмы сборки мусора пометить и подмести (гпагк-апд-за еер) представляют собой простые алгоритмы, которые находят все недостижимые объекты и помещают их в список свободной памяти. Алгоритм 7.12 на первом этапе посещает и помечает все достижимые объекты, после чего "подметает" всю кучу, освобождая недостижимые объекты.

Алгоритм 7.14, который мы рассмотрим после общей схемы алгоритмов на основе отслеживания, представляет собой оптимизацию алгоритма 7.12. Используя дополнительный список для хранения всех объектов, для которых выделена память, он посещает достижимые объекты только один раз. 578 Глава 7. Среды времени выполнения /* Фаза маркировки *! Добавить в список Иисаннеа' все объекты, на которые имеется ссылка в корневом множестве, и установить бит достижимостн каждого такого объекта равным 1; туЬ!!е Япзсаппес! ф И) 1 Удалить некоторый обьект о из ИисанпеЫ; !ог (Каждый объект о', на который есть ссылка из о) 1 !!' (о' недостижим, т.е.

его бит достижимости равен 0) 1 Установить бит достижимости о' равным 1; Внести о' в список Бтсаппед; 2) 3) 4) 5) 6) 7) /* Фаза подметания *! 8) г'гее = о; 9) !ог (Каждый блок памяти о в куче) 1 10) !1 (о недостижим (бит достижимости равен 0)) Добавить о в список Ргее; 11) е!ве Установить бит достижимости о равным 0; Рнс.

7.21. Сборщик мусора методом "пометить н подмести" В строке 1 на рис. 7.21 выполняется инициализация списка с7нзсанпей пугем размещения в нем всех объектов, на которые имеются ссылки из корневого мно- Алгоритм 7.12. Сборка мусора "пометить и подмести" ВХОД: корневое множество объектов, куча и снисок свободной намяти (Ггее 1вй) Расе, в котором перечислены все свободные блоки кучи. Как и в разделе 7.4.4, все блоки памяти помечены при помощи дескрипторов границ, которые указывают их статус (занято/свободно) и размер.

ВыхОД: модифицированный список Ргее после удаления всего мусора. МЕТОД: алгоритм, приведенный на рис. 7.21, использует несколько простых структур данных. Список Ргее содержит обьекты, память которых должна быть освобождена. Список сутсанпег1 хранит объекты, которые определены как достижимые, но преемники которых пока что рассмотрены не были, т.е, мы пока что не сканировали эти объекты в поисках достижимых через них других объектов. Изначально список Инзсанпед пуст. Кроме того„каждый объект включает бит (бит достижимости — геасЬед-ЬЬ), который указывает, достижим ли данный объект. Перед началом алгоритма у всех объектов, для которых выделена память, данный бит устанавливается равным О.

579 7.6. Введение в сборку на основе отслеживания жества. Бит достижимости этих объектов устанавливается равным 1. Строки 2 — 7 представляют собой цикл, в котором поочередно проверяется каждый объект о, помещенный в список Ьлзсаппей.

Цикл )ог в строках 4-7 реализует сканирование объекта о. Мы просматриваем каждый объект о', на который в объекте о обнаруживается ссылка. Если о' уже был достигнут (его бит достижимости равен 1), то никаких действий с о' выполнять не требуется — либо этот объект уже был сканирован, либо он находится в списке Упзсаппет7 и будет сканирован позже. Однако если о' еше не был достигнут, то в строке 6 его бит достижимости устанавливается равным 1, а сам о' в строке 7 добавляется в список ГГтсаппет7. Этот процесс проиллюстрирован на рис. 7.22.

Здесь показан список 1.Гтсаппет7 из четырех объектов. Выполняется сканирование первого объекга в этом списке, соответствующего рассматривавшемуся выше обьекгу о. Пунктирные линии соответствуют трем видам объектов, которые могут быть достижимы из о. ттлтсаллел' Свободные и недостижимые объекты Бит достижимости = 0 Несканированные и ранее сканированные обьекты Бит достижимости = 1 Рнс. 7.22.

Соотношения между объектами на фазе маркировки сборщика мусора "пометить и подмести" 1. Ранее сканированный объект, который не требуется сканировать повторно. 2. Объект, находящийся в настоящий момент в списке Стлзсаллет7. 3. Достижимый элемент, который ранее считался недостижимым. Строки 8 — 11 представляют собой фазу подметания — утилизацию памяти всех объектов, которые остались недостижимыми по окончании фазы маркировки.

Заметим, что сюда входят все объекты, которые были в списке Ргее изначально. Поскольку непосредственное перечисление недостижимых объектов невозможно, алгоритм "подметает" всю кучу. Строка 10 по одному помещает свободные 580 Глава 7. Среды времени выполнения блоки памяти и недостижимые объекты в список ««ее, а строка 11 обрабатывает достижимые объекты. Их бит достижимости устанавливается равным О, чтобы при следующем выполнении алгоритма сборки мусора выполнялись необходимые предусловия. а 7.6.2 Базовая абстракция Все алгоритмы на основе отслеживания вычисляют множество достижимых объектов, а затем получают дополнение этого множества. Память используется следующим образом. а) Программа (мутатор) во время работы выполняют запросы на выделение памяти.

б) Сборщик мусора выясняет достижимость объектов путем отслеживания. в) Сборщик мусора утилизирует память недостижимых объектов. Этот цикл проиллюстрирован на рис. 7.23 с использованием четырех состояний блоков памяти; Свободен (««ее), Недостижим ((7п«еаспег7), Несканирован ЯтсаппеА и Сканировал (Зсаппег(). Состояние блока может храниться в самом блоке или в структуре данных, использующейся алгоритмом сборки мусора. Хотя реализации алгоритмов на основе отслеживания могут отличаться, все они могут быть описаны в терминах указанных состояний.

Характеристики

Список файлов книги