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

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

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

В результате данный параллельный и конкурентный шаг нормально завершится до того, как на следующем шаге будет завершен процесс отслеживания. 4. Последний шаг гарантирует, что все достижимые объекты будут найдены и соответствующим образом помечены. Все мутаторы в этот момент остановлены, так что корневые множества всех потоков могут быть быстро найдены с использованием всех процессоров системы. Поскольку достижимость большинства объектов уже отслежена, в состояние Нескииирован, как ожидается, будет помещено только небольшое количество объектов. После этого все потоки принимают участие в определении оставшихся достижимых объектов и повторном сканировании всех карт.

Важно управлять скоростью отслеживания. Этот процесс напоминает гонку— мутаторы создают новые объекты и новые ссылки, которые должны быть сканированы, а отслеживающие потоки в это же время пытаются сканировать все достижимые объекты и повторно сканировать помечаемые мутаторами карты. Плохо, если отслеживание начинается задолго до того, когда требуется выполнение сборки мусора, поскольку это приводит к увеличению количества плавающего мусора.

С другой стороны, нельзя ожидать исчерпания памяти, поскольку в этом случае мутаторы не смогут продолжать свою работу и конкурентная сборка мусора выродится в обычную сборку при блокированном выполнении основной программы. Следовательно, алгоритм должен уделить особое внимание выбору времени начала сборки мусора и скорости отслеживания. При принятии данно- 608 1лава 7.

Среды времени выполнения го решения можно воспользоваться данными о работе мутаторов в предыдущих циклах сборки мусора. 7.82 Частичное перемещение объектов Как говорилось выше, начиная с раздела 7.6.4, копирующие или уплотняюшие сборщики мусора обладают тем преимуществом, что устраняют фрагментацию памяти. Однако для таких сборщиков характерны существенные накладные расходы.

Уплотняющий сборщик мусора должен переместить все объекты и обновить все ссылки по окончании сборки. Копирующий сборщик выясняет новое местоположение объекта в процессе отслеживания; при инкрементном отслеживании требуется либо транслировать все обращения мутатора к объекту, либо перемешать все объекты и обновлять все ссылки на них по окончании сборки. И тот, и другой подходы очень дорогостоящи, в особенности для кучи больших размеров. Однако можно воспользоваться копирующим сборщиком мусора по поколениям.

Он весьма эффективен для сборки молодых объектов и снижения фрагментации, но при сборке старых объектов может оказаться дорогостоящим. Для ограничения количества старых объектов, анализируемых таким сборщиком, можно использовать алгоритм поезда. Однако накладные расходы алгоритма поезда весьма чувствительны к размеру запомненного множества каждого раздела. Существует гибридная схема сборки мусора, которая использует конкурентное отслеживание для утилизации всех недостижимых объектов и в то же время перемещает только часть объектов. Такой метод снижает фрагментацию с меньшими расходами, чем полное перемещение всех объектов в каждом цикле сборки мусора.

1. Перед началом сборки выберите часть кучи, которая будет освобождена. 2. При маркировке достижимого объекта следует также запомнить все ссылки, указывающие на объекты в выбранной части. 3. По завершении отслеживания выполняется параллельное освобождение памяти, занятой недостижимыми объектами. 4. Наконец переносятся все достижимые объекты из выбранной части и исправляются все запомненные ссылки на них. 7.8.3 Консервативная сборка мусора для небезопасных языков программирования Как говорилось в разделе 7.5.1, невозможно создать сборщик мусора, который гарантировал бы работу во всех программах на С и С+'-. Поскольку адрес 7.8.

Дополнительные вопросы сборки мусора может быть вычислен при помощи арифметических операций, никакая ячейка памяти в программе на С илн С++ не может считаться недостижимой. Однако многие программы на этих языках программирования никогда не создают адреса подобным образом. Можно показать, что для данного класса программ возможно построение вполне работоспособного на практике консервативного сборщика мусора (который необязательно удаляет весь мусор).

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

Перемещение объектов, требующее обновления всех ссылок на старое местоположение объекта, не совместимо с принципом действия консервативного сборщика мусора. Поскольку такой сборщик мусора не знает, является ли конкретная битовая последовательность ссылкой на реальный адрес нли это просто совпадение, он не имеет права изменять такие последовательности. Вот как работает консервативный сборщик мусора. Сначала диспетчер памяти модифицируется таким образом, чтобы поддерживать карту данных (да1а шар) для всех выделенных блоков памяти. Эта карта позволяет легко определять границы блока памяти по адресу любой ячейки памяти этого блока.

Отслеживание начинается со сканирования корневого множества программы, чтобы определить все битовые последовательности, имеющие вид адресов (не беспокоясь при этом об их реальном типе). Проверяя эти потенциальные адреса с использованием карты данных, можно определить начальные адреса блоков памяти, которые достижимы с использованием указанных адресов, и перевести эти блоки в состояние Несканирован. Затем выполняется сканирование всех несканированных блоков памяти для поиска новых (вероятно) достижимых блоков памяти и помещения их в список блоков для сканирования, и так до тех пор, пока список не опустеет.

После этого выполняется освобождение всех недостижимых блоков памяти с применением карты данных. 7.8.4 Слабые ссылки Иногда программисты используют языки со сборкой мусора, но при этом хотят управлять памятью (или ее частями) самостоятельно. Иначе говоря, программист б10 Глава 7. Среды времени выполнения может знать, что к некоторым объектам обращений больше не будет, несмотря на наличие ссылок на них. Пример из области компиляции поясняет сказанное. Пример 7Л7. Мы уже сталкивались с тем, что лексический анализатор работает с таблицей символов, создавая объект для каждого обнаруженного идентификатора. Эти объекты могут быть, например, лексическими значениями, связанными с представляющими соответствующие идентификаторы листьями дерева разбора. Однако для поиска этих объектов стоит создать также хеш-таблицу, ключом в которой является строка идентификатора.

Такая таблица ускоряет поиск объекта лексическим анализатором, когда последний встречает лексему, представляющую собой идентификатор. После того как компилятор выходит за пределы области видимости идентификатора 1, в дереве разбора (или в любой иной промежуточной структуре, используемой компилятором) не остается ссылок на соответствующий объект в таблице символов. Однако в хеш-таблице ссылка на данный объект все еще остается. Поскольку хеш-таблица является частью корневого множества компилятора, объект не может быть утилизирован сборщиком мусора.

Если в программе встретится другой идентификатор с той же лексемой 1, то выяснится, что 1 находится вне области видимости, и ссылка на его объект будет удалена. Однако, если такой лексемы в программе больше нет, то при том, что объект идентификатора 1 будет невостребованным в процессе компиляции, сборщик мусора не сможет освободить выделенную ему память. а Если проблема, описанная в примере 7.17, оказывается существенной, то разработчик компилятора может пойти по пути удаления из хеш-таблицы всех ссылок на объекты при завершении их областей видимости.

Однако метод, известный как метод слабых ссылок (веак геГегепсеа), позволяет программисту положиться на автоматическую сборку мусора, чтобы освобождать кучу от достижимых, но на самом деле не используемых объектов. Такая система позволяет объявлять некоторые ссылки как "слабые". Примером могут служить только что рассмотренные ссылки в хеш-таблице. Когда сборщик мусора сканирует некоторый объект, он пропускает слабые ссылки в этом объекте и не делает объекты, на которые они указывают, достижимыми.

Само собой, такие объекты могут быть достижимыми, если на них имеются другие ссыпки, не являющиеся слабыми. 7.8.5 Упражнения к разделу 7.8 ! Упражнение 7.8Л. В разделе 7.8.3 было сказано, что в программе на С сборка мусора возможна, если выражения, которые указывают на место в блоке памяти, могут быть в программе только при условии наличия в той же программе адреса некоторого места в том же блоке памяти. Таким образом, мы исключаем код наподобие 611 7ти Резюме к главе 7 р = 12345г х = *рг поскольку р может случайно указывать на некоторый блок памяти при отсутствии других указателей на память в этом блоке. С другой стороны, высока вероятность, что р указывает "в никуда", так что выполнение указанного кода приведет к ошибке обращения к несуществующей памяти.

Тем не менее в С можно написать такой код, в котором переменная типа р будет гарантированно указывать на некоторый блок памяти, при том, что указателя на этот блок памяти в программе не будет. Напишите такую программу. 7.9 Резюме к главе 7 + Организация времени выполнения. Для реализации абстракций, воплощенных в определении исходного языка программирования, компилятор создает среду времени выполнения во взаимодействии с операционной системой и целевой машиной и управляет ею. Среда времени выполнения имеет статические области данных для объектного кода и статические объекты данных, созданные в процессе компиляции.

В ней также имеются динамические области стека и кучи для управления объектами, создаваемыми и уничтожаемыми в процессе выполнения целевой программы. + Стек управления. Вызовы процедур и возвраты из них обычно осуществляются с использованием стека времени выполнения, именуемого стеком управления. Применение стека обусловливается тем, что вызовы процедур, или активации, вложены во времени, т.е. если процедура р вызывает процедуру д, то данная активация д вложена в активацию р. + Выделение памяти в стеке.

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

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