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

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

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

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

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Проверка ссылок

Из книги автора

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


Покупка ссылок

Из книги автора

Покупка ссылок Сейчас покупка ссылок является наиболее популярным и быстрым способом набора ссылочной массы, однако это вовсе не означает, что она идеальна. На самом деле у нее есть как неоспоримые достоинства, так и серьезные недостатки.Достоинства покупки ссылок:?


R.4.7 Преобразования ссылок

Из книги автора

R.4.7 Преобразования ссылок Всюду, где ссылки (§R.8.2.2) инициализируются (включая передачу параметров (§R.5.2.2) и возврат значения функции (§R.6.6.3)) или используются иным образом, возможны следующие преобразования:Ссылка на данный класс может быть преобразована в ссылку на


2.28. Подсчет числа символов в строке

Из книги автора

2.28. Подсчет числа символов в строке Метод count подсчитывает число вхождений в строку символов из заданного набора:s1 = "abracadabra"a = s1.count("с")   # 1b = s1.count("bdr") # 5Строковый параметр ведет себя как простое регулярное выражение. Если он начинается с символа ^, то берется дополнение к


4.18. Подсчет вхождений каждого слова в текстовом файле

Из книги автора

4.18. Подсчет вхождений каждого слова в текстовом файле ПроблемаТребуется подсчитать количество вхождений в текстовом файле каждого слова.РешениеДля чтения из текстового файла непрерывных фрагментов текста используйте operator>>, определенный в <string>, а для сохранения


11.1. Подсчет количества элементов в контейнере

Из книги автора

11.1. Подсчет количества элементов в контейнере ПроблемаТребуется найти количество элементов в контейнере.РешениеПодсчитать количество элементов в контейнере можно при помощи функции-члена size или функции distance, определенной в заголовочном файле <algorithm>, как это


Подсчет (Count)

Из книги автора

Подсчет (Count) template ‹class InputIterator, class T, class Size›void count(InputIterator first, InputIterator last, const T& value, Size& n);template ‹class InputIterator, class Predicate, class Size›void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);count добавляет к n число итераторов i в диапазоне [first, last), для которых соблюдаются следующие


Локальность ссылок

Из книги автора

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


Пример A-8. days-between: Подсчет числа дней между двумя датами

Из книги автора

Пример A-8. days-between: Подсчет числа дней между двумя датами #!/bin/bash# days-between.sh: Подсчет числа дней между двумя датами.# Порядок использования: ./days-between.sh [M]M/[D]D/YYYY [M]M/[D]D/YYYYARGS=2 # Ожидается два аргумента из командной строки.E_PARAM_ERR=65 # Ошибка в числе ожидаемых


21.4.5. Команда wc — подсчет слов в файле

Из книги автора

21.4.5. Команда wc — подсчет слов в файле Команда wc используется:? для подсчета слов в текстовом файле: wc /var/log/messages ? для подсчета количества строк (если задан параметр -1): wc — l /var/log/messages ? для подсчета количества символов (параметр — c): wc — c


18.5.9. Подсчет с помощью циклов

Из книги автора

18.5.9. Подсчет с помощью циклов При обсуждении команды expr отмечалось, что эта команда применяется, если в циклы необходимо ввести счетчики. Ниже рассматривается пример, в котором цикл for обрабатывает файлы, а вывод и подсчет количества файлов осуществляется с помощью


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

Из книги автора

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