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

При выборе ОО-среды - или просто компилятора ОО-языка - для разработки программного продукта ограничьте ваше внимание только теми решениями, которые предлагают автоматическое управление памятью.

Необходимость автоматических методов

Автоматическое управление памятью

Дискуссия

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

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

Ни один из рассмотренных подходов не является полностью удовлетворительным. Общее решение проблемы управления памятью предполагает серьезную работу на уровне реализации языка.

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

Предыдущее обсуждение достаточно ясно показало, как важно иметь возможность управлять памятью. По словам Михаила Швейцера (Michael Schweitzer) и Ламберта Стретра (Lambert Strether): "ОО-программа без автоматического управления памятью то же самое, что скороварка без клапана безопасности: рано или поздно она взорвется!" (Из [Schweitzer 1991])

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

Два главных подхода применимы при автоматическом управлении памятью: подсчет ссылок и сборка мусора. Они оба достойны внимания, хотя второй намного мощнее и обще применим.

Что в точности понимается под восстановлением?

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

[x]. Механизм может добавить память, занимаемую объектом, к постоянно поддерживаемому "списку свободных ячеек", в духе техники, использованной при рассмотрении подхода на уровне компонентов. Последующая инструкция создания (create x...) вначале обратится к этому списку для выделения памяти новому объекту. Только если этот список пуст или нет подходящих ячеек, инструкция запросит память у операционной системы. Этот подход может быть назван внутренний список свободной памяти.

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

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

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

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

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

Любая операция, создающая объект, инициализирует число ссылок, делая его равным единице. В частности, так должно происходить с инструкцией создания 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 до трех и только. Счетчики всех трех объектов останутся положительными, что не позволит определить необходимость их утилизации.

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

Дата добавления: 2014-01-07