Ручная сборка мусора а-ля C++

В языках сравнительно низкого уровня, таких как C++ или Delphi, обычно применяется ручная сборка мусора. Иными словами, выделив некоторый участок памяти и сохранив его адрес в переменную, программист сам должен позаботиться о его высвобождении в дальнейшем:

скопировать код в буфер обмена Листинг 1

// выделяем блок памяти длиной 1024 байта char *p = new char[1024]; ... // работаем с ним ... // освобождаем эту память delete p;

Однако здесь есть три момента. Во-первых, если операторов выделения памяти много, то вполне можно забыть освободить какой-то участок, что рано или поздно приведет к нехватке памяти или обычному «раздуванию» процесса.

Во-вторых, если код, который обозначен в листинге многоточием, находится в процедуре и внезапно возбудит исключение или выполнит обыкновенную инструкцию return, то память также не будет освобождена. В Delphi для решения таких проблем есть блок try...finally, но даже его использование не освобождает от первого недостатка.

Наконец, в-третьих, программы редко когда бывают линейными, и особенно это относится к объектно-ориентированному программированию. Выделив когда-то память под объект, мы не знаем точно, в какой момент времени ее можно будет освободить. Особенно это характерно для ситуаций, когда один и тот же объект A используется несколькими другими объектами X, Y, Z (последние, например, содержат указатели на первый). Предположим, что X уже не нуждается в A, но мы не можем тут же его удалить, ведь, возможно, A все еще используется объектами Y и Z. Иными словами, память (и объект) A нельзя удалять, пока на него кто-то ссылается. Ручное отслеживание таких ситуаций является обычной рутиной, а значит, потенциально приводит к ошибкам.

Таким образом, видно, что ручная сборка мусора (какой бы она ни была совершенной) в крупных программах оказывается непригодной, а значит, язык программирования должен поддерживать автоматическую сборку мусора, руководствуясь правилом: память можно освободить, когда в программе на нее больше нет ссылок.

По-видимому, задача создания идеального автоматического сборщика мусора алгоритмически неразрешима (скоро вы поймете, что я имел в виду). Тем не менее, кое-что предложить все-таки можно. Давайте рассмотрим два наиболее популярных алгоритма на примерах языков Perl и Java.

Алгоритм со счетчиком а-ля Perl

В Perl не существует указателей, как в C++, но зато есть такое понятие, как ссылка. О ссылках я писал в предыдущих наблах, так что рекомендую ознакомиться. Объекты, на которые в программе не осталось ссылок, Perl немедленно удаляет из памяти. Вся специфика заключена в словах «не осталось ссылок» и «немедленно».

Вернемся к «гардеробной теории» из двадцать первой наблы, где в качестве объекта выступает пальто, а в качестве ссылки — номерок, выдаваемый гардеробщиком. Что произойдет с пальто, если человек уничтожит свой номерок (обнулит ссылку на объект)?.. Наверное, через некоторое время гардеробщик сообразит (как именно — см. ниже), что пальто больше не нужно и лишь занимает вешалку, и отправит его на утилизацию (сборщик мусора удалит объект-пальто). Однако Perl гораздо шустрее: если гардеробщику требуется некоторое время на принятие решения, то интерпретатор сразу же обнаруживает объекты, на которые нет ссылок, и удаляет их, не задерживаясь.

Сложности начинаются, когда на некоторый объект имеется более одной ссылки. В этом случае, конечно же, уничтожение нужно провести только при обнулении последней ссылки, но ни в коем случае — промежуточных. Но как же определить, ссылается ли кто-то еще на объект, или же нет?..

В этом и заключена специфика алгоритма со счетчиком ссылок, одновременно его сила и слабость. Каждый объект (вернее блок памяти) содержит в себе скрытое поле, хранящее так называемый счетчик ссылок. Каждый раз, когда в программе появляется новая ссылка на объект, этот счетчик увеличивается на 1 (обычно это происходит при выполнении операции присваивания $a=$b: раньше ссылка хранилась только в $b, а теперь — и в $a, и в $b). Соответственно, при удалении ссылки счетчик уменьшается на 1 (например, операция $a=undef или выход лексической переменной за область видимости приводит к потери ссылки на объект, которая раньше находилась в $a). Ясно, что при обнулении счетчика на объект больше никто не ссылается, а потому его можно спокойно удалить из памяти, что Perl и делает. Таким образом, объект удаляется после некоторой операции присваивания, приводящей к потере последней ссылки.

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

Удаление объекта — это довольно сложная процедура. Необходимо:

• Удалить все ссылки, которые содержит сам этот объект (например, при удалении массива необходимо обнулить все скаляры, которые в нем содержатся). Если в процессе этой операции какой-то другой подчиненный объект теряет последнюю ссылку, то он также будет удален, и т. д. — рекурсивно.
• Вызвать деструктор (специальную функцию, связанную с объектом), если объект является объектно-ориентированным (такая вот тавтология, но лучше не сказать). Деструкторы играют весьма важную роль в ООП, так что полная их поддержка в алгоритме со счетчиком ссылок — это сильная сторона метода.
• Освободить занимаемую память. Эта операция выполняется в самый последний момент и может рассматриваться как низкоуровневая.

Казалось бы, все замечательно, но дело в том, что алгоритм Perl имеет один очень существенный недостаток, который сильно ограничивает его применимость. Речь идет о циклических ссылках. Давайте рассмотрим такой код:

скопировать код в буфер обмена Листинг 2

# ссылка на структуру-дерево my $tree; { my (%parent,%child); # отец ссылается на сына $parent{children}[0] = \%child; # сын ссылается на отца $child{parent} = \%parent; # сохраняем ссылку на отца - ссылку на дерево $tree = \%parent; # (*) }

Здесь %parent не превращается в мусор, потому что на него есть ссылка $tree, а %child — потому что на него ссылается один из элементов %parent. Вроде бы все верно. Но теперь возьмем и удалим ссылку $tree:

скопировать код в буфер обмена Листинг 3

# отсоединяем ссылку от %parent $tree = undef; # теперь к %parent никак нельзя обратиться!

А теперь — сюрприз: несмотря ни на что, память для этих двух хэшей все же не освобождается, и они остаются «висеть» мертвым грузом, хотя к ним уже и нельзя получить доступ!

Все дело в злополучных счетчиках ссылок. Смотрите: %parent ссылается на %child, а %child — на %parent. Это значит, что и у того, и у другого счетчик равен 1. При подсоединении к %parent ссылки $tree счетчик у него увеличивается еще на 1 и становится равным 2 в строке, помеченной (*). Далее, мы отсоединяем ссылку $tree от %parent, в результате чего счетчик снова становится равным 1. Стоит ли удивляться, что сборщик мусора не сработал?.. Ведь нет ни одного объекта с нулевым счетчиком ссылок!

Вы сдаете в гардероб свое пальто и чужое (которое взяли только что по поддельному номерку). При этом для конспирации номерок от своего пальто кладете в карман чужого, а от чужого — в карман своего. Вы обнаружите, что не можете больше получить одежду.

Теперь нетрудно сделать общий вывод: алгоритм попросту не срабатывает, когда в программе имеются кольцевые ссылки (первый объект ссылается на второй, а второй — на первый). При этом то, как именно ссылаются друг на друга объекты, не имеет значения: конструкция «A ссылается на B, B ссылается на C, С ссылается на A» тоже «тупиковая». Еще более примечателен следующий код:

скопировать код в буфер обмена Листинг 4

{ my $a; $a = \$a; # ссылка сама на себя! }

Чем не замкнутая внутри себя вселенная?.. Мы получили лексическую переменную, которая, несмотря на окончание блока, все равно продолжает существовать в памяти, занимая место, но не будучи доступна.

Напоминаю, что лексическая переменная далеко не обязательно удаляется при выходе из блока. Можно сказать, что выход из блока для лексической переменной равносильно уменьшению счетчика ссылок на 1, не более того. Так что инструкция my в чем-то очень схожа с оператором new языков C++ и Java.

Можно ли каким-либо способом обойти эту проблему?.. Очевидно, нет: даже если интерпретатор и заподозрит, что пара %parent и %child «вошла в клинч» и «не видна» извне, он все равно не сможет разрушить объекты и освободить память. Ведь он не знает, в каком порядке это делать.

Например, он уничтожит вначале первый,а потом — второй. Но вдруг в деструкторе %child ведется работа с объектом %parent — к примеру, опрашивается, сколько у него осталось «живых» потомков?..

Так что единственный способ — это разрывать кольцевые ссылки явно, примерно вот так:

скопировать код в буфер обмена Листинг 5

# удаляем кольцевые ссылки delete $tree->{children}; # отсоединяем ссылку от %parent $tree = undef;

Излишне даже заикаться, что этот способ «ручной», а значит, потенциально подвержен ошибкам.

Но что же все-таки происходит с «повисшими» в памяти объектами, на которые больше никто не ссылается?.. Перед окончанием работы программы они принудительно удаляются в произвольном (!) порядке. До сих пор все объекты были простыми хэшами, не содержащими деструкторов, поэтому такой вариант для них вполне подходил. Ситуация меняется при использовании ООП и деструкторов. «Произвольность» чистки мусора в этом случае дает о себя знать сообщением вроде «error during global destruction», что, например, происходит при попытке в деструкторе обратиться к объекту, уже не существующему (что невозможно в обычной программе).

Вывод: Perl полностью поддерживает деструкторы, однако его сборщик мусора работает не ахти как при наличии кольцевых ссылок в программе.

Алгоритм обхода а-ля Java

Можно ли решить проблему «повисших» объектов?.. Оказывается, можно, но решение это не дастся легко, а потребует серьезных жертв. Эти жертвы — «застопоривание» программы и невозможность создания деструкторов у объектов.

Нередко эти жертвы оказываются чрезмерными (особенно отказ от деструкторов). Тем не менее, правильная работа с кольцевыми ссылками в некоторых классах приложений (особенно GUI, очень редко — Web-приложения) настолько важна, что можно пойти на уступки.

Чтобы понять, в чем же дело, рассмотрим вкратце, как работает «обходной» алгоритм сборки мусора на примере «гардеробной теории».

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

Сборка мусора в программе происходит следующим образом. Периодически (например, раз в секунду) программа приостанавливается и начинает выполняться сборщик мусора. Первым делом он обходит все объекты, существующие в программе, и обозначает их как необработанные (для этого, как и в алгоритме подсчетка ссылок, у объекта есть специальное поле пометки). Затем сборщик мусора берет все переменные, доступные в текущем контексте (где только что остановилась программа), и помечает каждый объект, на который они ссылаются, как обработанный. Но ведь объекты тоже включают в себя поля, являющиеся ссылками! Поэтому, найдя очередной объект, сборщик мусора извлекает из него все ссылки и также проходится по ним рекурсивно. При этом, если он наткнется на уже помеченный объект, он его пропускает. Зачем делать дважды одну и ту же работу? Неудивительно, что в конце всего этого длинного обхода непомеченными оказываются только те объекты, на которые в программе больше нет ссылок. Остается только их удалить, что и делается (в произвольном порядке, как во время финальной «чистки» в Perl). Обратите внимание, что кольцевые ссылки алгоритмом отслеживаются без каких-либо проблем.

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

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

Говорят, что алгоритм со счетчиком ссылок дает небольшую, но равномерную нагрузку на процессор, в то время как алгоритм обхода — взрывообразную. Это можно заметить в некоторых сложных программах на Java, которые иногда вдруг начинают периодически «подтормаживать» (например, при простом редактировании текста), хотя никакой видимой работы при этом не происходит.

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

Тем не менее, практически все языки позволяют создавать функцию, которая будет вызвана при фактическом освобождении памяти. Ее обычно называют финализатором, чтобы не путать с деструктором (ибо это несколько разные вещи). Финализаторы применяются очень редко (вы, наверное, не раз прочтете об этом в любой книге по Java или C#), а реальное разрушение объекта (вызов деструктора) возлагается на программиста. То есть, последний должен написать свою функцию, выполняющую роль деструктора, и вызвать ее, когда в объекте отпадает необходимость. Излишне говорить, что это «лобовое» решение недалеко ушло от «ручного» способа сборки мусора, а потому крайне неудобно (возникают те же самые проблемы с совместным использованием объекта, что и прежде).

Конечно, изложенный алгоритм обхода обычно реализуется со значительными оптимизациями, которые я здесь опускаю из соображений бессмысленности.

Вывод: единственное достоинство алгоритма обхода — корректное обнаружение кольцевых ссылок. Это достигается ценой взрывообразной сборки мусора и отказом от деструкторов. Задача с корректным порядком разрыва кольцевых ссылок также остается нерешенной.

Заключение

Итак, какой же из последних двух алгоритмов лучше?..

К сожалению, в общем случае на этот вопрос ответа нет. Оба алгоритма обладают взаимоисключающими достоинствами и недостатками, поэтому там, где хорош один, плох другой, и наоборот.

Например, если в программе требуется активно работать со связанными списками и гипердеревьями (когда некоторые вершины могут ссылаться на своих предков), выгоднее будет применять Java и алгоритм сборки мусора с обходом (потому что он умеет разрывать кольцевые ссылки). Как показывает практика, GUI-приложения почти всегда связаны с необходимостью создания кольцевых ссылок (Java и C# весьма популярны в GUI-программировании).

Если же требуется работа с линейными или ветвящимися структурами (обычными деревьями), но критично наличие деструкторов, следует предпочесть алгоритм, основанный на счетчиках ссылок. Web-программирование является хорошим примером области, удовлетворяющей этому требованию (в частности, механизм работы модуля CGI::WebOut существенно основан на деструкторах).

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