Разработка компиляторов
Отслеживание свободной памяти с помощью подсчета ссылок
Самый простой способ отслеживания свободной памяти заключается в приписывании каждому объекту в памяти специального счетчика ссылок, показывающего количество "живых" переменных, использующих данный объект. При первичном выделении памяти в программе счетчику присваивается значение, равное единице; при создании новых указателей на данный фрагмент памяти, значение счетчика увеличивается на единицу. Если какая-то из переменных, указывающих на данный фрагмент памяти, перестает существовать, значение счетчика ссылок уменьшается на единицу. При достижении счетчиком нуля фрагмент памяти считается более не используемым и может быть утилизирован. Отметим также, что в эту схему легко вписывается и явное управление памятью: оператор free приводит к простому уменьшению счетчика ссылок на единицу.
Этот метод прост, понятен и легко реализуется, но, к сожалению, у этого метода есть серьезные недостатки. Во-первых, приведенный выше алгоритм в некоторых случаях не справляется с определением свободной памяти. Например, для циклического списка уничтожение внешнего указателя на эту структуру делает ее мусором, и в то же время счетчики ссылок циклического списка не становятся равными нулю, т.к. элементы списка указывают друг на друга.
Во-вторых, использование механизма счетчиков ссылок связано со значительной потерей эффективности во время исполнения, так как при каждом присваивании в программе необходимо производить соответствующие арифметические операции. Все эти действия могут оказаться совершенно бесполезными, если программе хватит исходного объема памяти, а это противоречит одному из принципов трансляции, согласно которому программы не должны терять в производительности из-за языковых или компиляторных механизмов, которыми они не пользуются.
Из-за этих проблем механизм счетчиков ссылок не получил широкого распространения. Сегодня он используется только в редких случаях и обычно для крупных объектов, т.к. для них дополнительные затраты памяти не так заметны, а проблема цикличности неактуальна (см., например, счетчики ссылок COM-объектов на платформе Windows).
Самый простой способ отслеживания свободной памяти заключается в приписывании каждому объекту в памяти специального счетчика ссылок, показывающего количество "живых" переменных, использующих данный объект. При первичном выделении памяти в программе счетчику присваивается значение, равное единице; при создании новых указателей на данный фрагмент памяти, значение счетчика увеличивается на единицу. Если какая-то из переменных, указывающих на данный фрагмент памяти, перестает существовать, значение счетчика ссылок уменьшается на единицу. При достижении счетчиком нуля фрагмент памяти считается более не используемым и может быть утилизирован. Отметим также, что в эту схему легко вписывается и явное управление памятью: оператор free приводит к простому уменьшению счетчика ссылок на единицу.
Этот метод прост, понятен и легко реализуется, но, к сожалению, у этого метода есть серьезные недостатки. Во-первых, приведенный выше алгоритм в некоторых случаях не справляется с определением свободной памяти. Например, для циклического списка уничтожение внешнего указателя на эту структуру делает ее мусором, и в то же время счетчики ссылок циклического списка не становятся равными нулю, т.к. элементы списка указывают друг на друга.
Во-вторых, использование механизма счетчиков ссылок связано со значительной потерей эффективности во время исполнения, так как при каждом присваивании в программе необходимо производить соответствующие арифметические операции. Все эти действия могут оказаться совершенно бесполезными, если программе хватит исходного объема памяти, а это противоречит одному из принципов трансляции, согласно которому программы не должны терять в производительности из-за языковых или компиляторных механизмов, которыми они не пользуются.
Из-за этих проблем механизм счетчиков ссылок не получил широкого распространения. Сегодня он используется только в редких случаях и обычно для крупных объектов, т.к. для них дополнительные затраты памяти не так заметны, а проблема цикличности неактуальна (см., например, счетчики ссылок COM-объектов на платформе Windows).
Другим методом отслеживания свободной памяти является механизм разметки памяти . При этом подходе все действия по поиску неиспользуемых переменных откладываются до возникновения недостатка памяти, т.е. до того момента, когда программа требует выделить фрагмент слишком большого размера. В этот момент стартует процесс сборки мусора, начинающийся именно с разметки памяти.
Разметка памяти начинается с обнаружения всех заведомо живых элементов программы. К таким причисляются все объекты за пределами кучи (на стеке, в регистрах процессора и т.д.), а также все объекты в куче, на которые они указывают. Все эти элементы помечаются как используемые. Затем мы перебираем все используемые элементы и помечаем все прочие объекты, на которые они ссылаются. Этот процесс повторяется рекурсивно до тех пор, пока мы не перестаем находить новые используемые элементы.
Следующий просмотр сборки мусора утилизирует все элементы, не помеченные как живые, а также уплотняет все живые элементы, сдвигая их в начало кучи. Очевидно, что затем сборщику мусора придется поменять все значения указателей, используемых в программе; в связи с этим на время сборки мусора все остальные процессы приостанавливаются.
В отличие от счетчиков ссылок, механизм разметки памяти не приводит к замедлению программ, не использующих сборку мусора. Но если потребность в сборке мусора все-таки возникает, то скорее всего, все процессы будут заморожены на некоторое время, которое, скорее всего, будет заметно даже пользователю.
