А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 116
Текст из файла (страница 116)
Причина в том, что объекты часто "умирают молодыми*', так что если немного подождать, то многие из вновь распределенных объектов станут недостижимыми. Стоимость работы такого сборщика в среднем на один собранный объект оказывается меньшей. С другой стороны, редкая сборка мусора повышает расход памяти, уменьшает локальность данных и увеличивает продолжительность пауз.
В противоположность этому сборщик с подсчетом ссылок, внося постоянные накладные расходы для многих операций мутатора, может существенно замедлить работу программы в целом. Но, с другой стороны, подсчет ссылок не приводит к длинным паузам и эффективно использует память, поскольку мусор обнаруживается в момент его образования (за исключением определенных циклических структур, рассматриваюшихся в разделе 7.5.3). Дизайн языка программирования также влияет на характеристики использования памяти. Некоторые языки способствуют стилю программирования, генерирующему много мусора.
Например, программы на функциональных, или почти функциональных, языках программирования создают большое количество объек- 572 Глава 7. Среды времени выполнения тов, чтобы избежать изменения уже существующих объектов. В Зава все объекты не фундаментальных типов (наподобие целых чисел или ссылок) создаются в куче. а не в стеке, даже если их время жизни ограничено единственным вызовом функции.
Такой дизайн освобождает программиста от забот о времени жизни переменных ценой повышенной генерации мусора. Оптимизация в процессе компиляции может проанализировать время жизни переменной н, если это возможно, выделить для нее память в стеке. 7.5.2 Достижимость Мы говорим обо всех данных, которые могут быть доступны непосредственно из программы, без разыменовання какого-либо указателя, как о корневом множестве (гоп~ зе1). Например, в Зла корневое множество программы состоит из всех статических полей-членов и всех переменных в стеке. Очевидно, что программа в любой момент времени может достичь любого элемента корневого множества. Рекурсивно достижим любой объект, ссылка на который хранится в поле-члене или элементе массива достижимого объекта.
Достижимость существенно усложняется при оптимизации программы компилятором. Во-первых, компилятор может хранить ссылочную переменную в регистре. Такие ссылки также могут рассматриваться как часть корневого множества, Во-вторых, хотя безопасные с точки зрения типов языки и не работают с адресами памяти непосредственно, компилятор часто делает это для ускорения кода. Таким образом, регистры в скомпилированном коде могут указывагь на средину объекта или содержать значение, к которому следует добавить некоторое смешение для получения корректного адреса.
Вот что компилятор может делать для тою, чтобы обеспечить возможность сборщику мусора корректно определить корневое множество. ° Компилятор может ограничить вызов сборщика мусора только определенными точками в программе, в которых нет "скрытых" ссылок. ° Компилятор может записывать информацию, которая используется сбор- шиком мусора для восстановления всех ссылок, такую как указание, какие регистры содержат ссылки или как вычислить базовый адрес объекта по его внутреннему адресу. ° Компилятор может обеспечить существование ссылок на базовые адреса всех достижимых объектов в момент вызова сборщика мусора. Множество достижимых объектов изменяется в процессе выполнения программы.
Оно растет при создании новых объектов и уменьшается, когда объекты становятся недостижимы. Важно помнить, что когда объект становится недостижимым, он не может стать достижимым впоследствии. Есть четыре фунда- 573 7.5. Введение в сборку мусора ментальные операции, выполняемые мутатором, которые приводят к изменению множества достижимых объектов. ° Выделение памяти для объекта.
Эта операция выполняется диспетчером памяти, который возвращает ссылку на каждый выделенный блок памяти. Эта операция добавляет члены в множество достижимых объектов. ° Передача параметров и возврат значений. Ссылки на объекты передаются из фактических входных параметров в соответствующие формальные параметры, а также из возвращаемого результата обратно в вызывающую процедуру.
Объекты, на которые указывают эти ссылки, остаются достижимыми. ° Приеваиваяие ссылок. Присваивание вида ц = ч, где и и и являются ссылками, имеет два результата. Во-первых, и становится ссылкой на объект, на когорый указывает о. Если достижима переменная и, то, конечно же, достижим и объект. на который он указывает. Во-вторых, теряется исходная ссылка и. Если это была последняя ссылка на некоторый достижимый объект; то этот объект становится недостижимым.
Всякий раз, когда объект становится недостижимым, становятся недостижимыми и все объекты, достижимые только посредством ссылок в нем. ° Возврат из процедуры. При выходе из процедуры кадр, в котором хранятся ее локальные переменные, снимается со стека. Если кадр хранит единственные достижимые ссылки на некоторый объект, то этот объект становится недостижимым.
И вновь, если недостижимый теперь объект хранил единственные ссылки на некоторые другие объекты, те тоже становятся недостижимыми, и этот процесс продолжается далее по цепочке. Итак, новые объекты вводятся в программу путем выделения для них памяти. Передача параметров и присваивание могут распространять достижимость; присваивание и завершение процедуры могут прекращать достижимость. Когда некоторый объекг становится недостижимым, он может сделать таковыми некоторые другие объекты. Имеется два фундаментальных способа поиска недостижимых объектов: либо перехватываются превращения достижимых объектов в недостижимые, либо периодически выявляются все достижимые объекты, после чего все прочие объекты рассматриваются как недостижимые.
Подсчет ссьиок, упоминавшийся в разделе 7.4.5, представляет собой хорошее приближение первого подхода. Поддерживается счетчик ссылок на объект, отслеживающий действия мутатора, которые могут изменить множество достижимых объектов. Когда счетчик обнуляется, объект становится недостижимым. Этот подход более детально рассматривается в разделе 7.5.3. 574 Глава 7. Среды времени выполнения Жизнь и смерть стековых объектов При вызове процедуры указатели на локальную переменную н, объект которой находится в стеке, могут храниться в нелокальных переменных. Эти указатели продолжают существовать после возврата из процедуры, в то время, когда память для н уже освобождена, что приводит к появлению висящей ссылки.
Должны ли мы вообще располагать локальные переменные наподобие н в стеке, как это делается, например, в С? Ответ заключается в том, что семантика многих языков программирования требует, чтобы локальные переменные прекращали существование при завершении их процедур. Ссылки на такие переменные представляют собой ошибки программирования, и компилятор не обязан исправлять их в программе. Второй подход определяет достижимость путем транзитивного отслеживания всех ссылок. Сборщик мусора на основе отслеживания (1гасе-Ьазео) начинает с того, что помечает все объекты корневого множества как "достижимые", итеративно просматривает все ссылки в достижимых объектах в поисках других достижимых объектов и помечает их соответствующим образом.
При таком подходе перед тем, как считать некоторый объект недостижимым, должны быть отслежены все ссылки. Однако после того, как множество достижимых объектов вычислено, за один раз могут быть как обнаружены все недостижимые объекты, так и освобождена занимаемая ими память. Поскольку все ссылки анализируются в одно и то же время, имеется возможность перенесения объектов и снижения тем самым фрагментации памяти.
Существует множество различных алгоритмов отслеживания, и некоторые из них будут рассматриваться в разделах 7.6 и 7.7.1. 7.5.3 Сборщики мусора с подсчетом ссылок Теперь рассмотрим простой, хотя и несовершенный сборщик мусора, основанный на подсчете ссылок, который идентифицирует мусор, как объект, состояние которого меняется с достижимого на недостижимое. Объект может быть удален, когда количество ссылок на него падает до нуля.
В случае сборщика мусора с подсчетом ссылок каждый объект должен иметь поле для количества ссылок, работа с которыми может осуществляться следующим образом. 1. Создание объекта. Количество ссылок вновь созданного объекта устанавливается равным 1. 2. Передача параметров. Значение счетчика ссылок каждого передаваемого в процедуру объекта увеличивается на 1. 575 7.5. Введение в сборку мусора 3. Присваивание ссылок. В случае инструкции ц = тт, где и и и — ссылки, значение счетчика ссылок объекта, на который указывает и, увеличивается на 1, а объекта, на который указывала переменная и до присваивания, уменьшается на 1. 4.
Возврат из процедуры. При возврате из процедуры должны быть уменьшены на 1 значения счетчиков объектов, на которые ссылались локальные переменные в записи активации этой процедуры. Если ссылка на один и тот же объект хранилась в нескольких локальных переменных, его значение счетчика должно быть уменьшено на! для каждой из переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
