реализовать сбор мусора на основе перехода от класса к классу (class-by-class basis). Этот вариант, к сожалению, слишком офаничен, чтобы быть удовлетворительным.

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

1. Сосуществовать с встроенным в С++ способом управления. динамической памятью вручную.

2. Не нарушать уже существующий код. Более того, он не должен никак влиять на созданный ранее код.

3. Работать настолько незаметно, что приложения, использующие сбор мусора, должны функционировать точно так же, как и профаммы, его не применяющие.

4. Вьшелять память, используя операцию new тем же способом, что и встроенный в С++ метод управления динамической памятью вручную.

5. Работать со всеми типами данных, включая встроенные типы, такие как: int И double.

6. Быть простым в использовании.

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

Постановка задачи

Ключевой вопрос, который встает перед разработчиком сборщика мусора, - как узнать, когда фрагмент памяти становится неиспользуемым? Для того чтобы разобраться, рассмотрим следующий код:

int *р;

р = new int(99);

Р = new incdOO);

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

Далее приведем код некоторой разновидности проблемы, рассмотренной в предыдущем примере:

int *р. *q;

р = new int(99);

q = р; теперь q указывает на ту же область памяти, что и р р = new int(100);

В ЭТОМ случае q указывает на область памяти, которая первоначально была выделена для р. Хотя р далее ссылается на другой фрагмент памяти, память, первоначально отведенную для р, нельзя освобождать, потому что на нее указывает q. Но как об этом узнает сборщик мусора? Верный путь к получению ответов на эти вопросы укажет выбранный для сбора мусора алгоритм.

Выбор алгоритма сбора мусора

Прежде чем разрабатывать сборщик мусора для С++, следует решить, какой алгоритм сбора мусора использовать. Сбор мусора - это серьезная проблема, изучавшаяся в течение многих лет теоретической наукой. Для столь увлекательной задачи существуют разнообразные решения, на основе которых и был разработан ряд различных алгоритмов сбора мусора. В этой книге нет смысла анализировать подробно каждый из них. Однако существует три архитипичных подхода: подсчет ссылок (reference counting), маркировка и чистка (mark and sweep) и копирование (copying). Прежде чем остановиться на одном из них, стоит познакомиться со всеми тремя.

Подсчет ссылок

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

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

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

Маркировка и чистка

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

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

Копирование

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

Какой алгоритм выбрать?

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