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

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

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

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

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

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

A1 L b := a (присваивание).

A2 L x.r(..., a, ...) , где r - некоторая подпрограмма (передача аргумента).

Любая операция, отсоединяющая ссылку от объекта О, должна уменьшать число ссылок О на единицу. Имеется два вида операций отсоединения:

[x]. (D1) Любое присваивание a := b. Заметим, что это также присоединяющая операция (А1) для объекта, присоединенного к b. (Поэтому если b также присоединен к О, необходимо как увеличить, так и уменьшить счетчик О, т.е. оставить его без изменения - приятный результат.)

[x]. (D2) Завершение вызова подпрограммы вида x.r(..., a, ...). (Если a встречается более одного раза в списке фактических аргументов, необходимо считать отсоединением каждое вхождение a.)

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

В заключение рассмотрим ситуацию с clone, требующую особого внимания. Операция a := clone (b) создает копию объекта ОВ, присоединенного к b, если ОВ существует. Вновь созданный объект ОA присоединяется к a. Счетчик ссылок ОA инициализируется единицей, естественно, не копируя счетчик ОВ. Если ОВ имеет непустые ссылочные поля, то при его копировании следует увеличить на единицу счетчик ссылок каждого объекта, присоединенного к каждому ссылочному полю, не исключено, что некоторые поля могут быть присоединены к одному и тому же объекту.

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

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

Рис. 9.14.  Неудаляемая при подсчете ссылок циклическая структура

Объекты О1, О2 и О3 содержат циклические ссылки друг на друга. Допустим, что нет объектов вне структуры кроме О, содержащих ссылки на какой-либо из объектов структуры. Соответствующий счетчик ссылок показан под каждым объектом.

Теперь допустим, что ссылка от О к О1 отрезана, например потому что подпрограмма вызываемая с целью О выполняет инструкцию:

а:=void

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

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