Книга: Основы объектно-ориентированного программирования

Что происходит с объектами

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

Создание объектов

Мы рассмотрели базовые операции размещения новых объектов. Простейший способ размещения записывается как

create x

и его эффект был определен триадой: создать новый объект; связать его со ссылкой x; и инициализировать его поля.

Вариант этой инструкции вызывает процедуру инициализации; можно также создать новый объект с помощью подпрограмм clone и deep_clone. Так как все эти формы размещения основаны на одной и той же базисной инструкции создания, можно без потери общности ограничиться рассмотрением create x .

Рассмотрим эффект, создаваемый инструкциями управления памятью.

Три режима управления объектами

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

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

Рис. 9.1.  Статический режим

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

[x]. Препятствует рекурсии. Рекурсивной программе необходимо иметь несколько одновременно активных копий, каждой со своими экземплярами сущностей.

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

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

Рис. 9.2.  Режим, основанный на стеке

Основанное на стеке управление объектами сделало популярным Algol 60 и с тех пор поддерживается (часто вместе с другими двумя режимами) в большинстве языков. Такой способ поддерживает рекурсию и динамические массивы, границы которых выясняются в процессе выполнения. В Pascal и C этот механизм не применяется к массивам, как это делается в Algol. Однако разработчикам хотелось бы чаще всего именно массивы распределять таким способом. Тем не менее, даже если этот механизм и может быть применен к массивам, размещение в стеке большинства сложных структур данных невозможно.^9.1)

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

Рис. 9.3.  Динамический режим

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

Использование динамического режима

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

[x]. Pascal использует статический режим для массивов, режим, основанный на стеке, для переменных, не являющихся массивами и указателями, динамический режим для указателей. В последнем случае создание объекта выполняется с помощью вызова специальной процедуры создания new.

[x]. Язык C похож на Pascal, но дополнительно вводит динамические массивы и статические переменные, не являющиеся массивами, Язык С динамически размещает переменные типа указатель и массивы, используя библиотечную функцию malloc.

[x]. PL/I поддерживает все модели.

[x]. Lisp системы традиционно были высоко динамичны и полагались большей частью на динамический режим распределения памяти. Одна из наиболее важных операций Lisp, используемая многократно для представления списков, - CONS, создает структуру из двух полей. В первом поле хранится значение элемента, а во втором - указатель на следующий элемент. Здесь CONS, скорее источник новых объектов, чем инструкция их создания.

Повторное использование памяти в трех режимах

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

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

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

Таблица 9.1.Размещение и удаление объектов в языках с блочной структурой

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

Отсоединение

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

Причина - присутствие в этом режиме выполнения операции отсоединения (detachment), обратной к операции присоединения. В предыдущей лекции изучалось, как сущности присоединяются к объектам, но не рассматривались детали отсоединения. Пора это исправить.

Рис. 9.4.  Отсоединение

Основные причины отсоединения следующие. Предположим, x и y сущности ссылочного типа вначале присоединены к объектам O1 и O2. Рисунок иллюстрирует случаи D1 и D2.

[x]. (D1) Присваивание вида x := Void, или x := v где v типа void, отсоединяет x от O1.

[x]. (D2) Присваивание вида y := z, где z не присоединен к объекту O2, отсоединяет y от O2.

[x]. (D3) Завершение подпрограммы отсоединяет формальные аргументы от присоединенных к ним объектов.

[x]. (D4) Инструкция создания create x , присоединяет x к вновь созданному объекту и, следовательно, отсоединяет x, если он ранее был присоединен к объекту O1.

Случай D3 соответствует ранее данному правилу: инициализация формального аргумента a подпрограммы r во время вызова t.r(..., b, ...), где позиция b в вызове соответствует позиции a в объявлении r, в точности соответствует семантике присваивания a := b.

Недостижимые объекты

Значит ли отсоединение объектов, например O1 или O2 (рис.9.4 ), что они становятся бесполезными и, следовательно, механизмы периода исполнения могут освободить занимаемое ими место в памяти? Это было бы слишком просто! Сущность, для которой объект был первоначально создан, могла уже потерять интерес к объекту, но из-за динамических псевдонимов другие ссылки могут быть все еще подсоединены к нему. Например, рис.9.4 возможно отражает лишь частное видение связей между объектами. Рассматривая более широкий контекст, (рис.9.5 ) можно обнаружить, что O1 и O2 все еще достижимы для других объектов.

Но и эта картина все еще не дает полного видения структуры всех связей между объектами. Расширяя контекст, можно, например, выяснить, что O4 и O5 сами не нужны, так что в отсутствии других ссылок, O1 и O2 не нужны тоже.

Таким образом, ответ на вопрос: "Какие объекты можно удалить?" должен следовать из глобального анализа множества всех созданных объектов. Выделим три типа объектов:

[x]. (C1) Объекты, напрямую присоединенные к сущностям, известны (из правил языка программирования) как необходимые.

[x]. (C2) Зависимые от объектов категории C1. (Напомним, наряду с непосредственно зависимыми объектами, имеющими ссылки на объекты C1, зависимые объекты могут рекурсивно иметь ссылки на непосредственно зависимые объекты.) Здесь рассматривается прямая и косвенная зависимость.

Рис. 9.5.  Отсоединение - не всегда смерть объекта

[x]. C3 Объекты, не относящиеся к предыдущим двум категориям.

Объекты первой категории могут называться оригиналами (origins). Вместе с объектами категории С2 они составляют множество достижимых (reachable) объектов. Объекты категории С3 недостижимы (unreachable). Они ранее неформально назывались ненужными или бесполезными. В другой более мрачной терминологии используются термины "мертвые объекты" для категории С3 и "живые" для первых двух. (У программистов принята более прозаическая терминология, и процесс удаления мертвых объектов, изучаемый ниже, называется просто сборкой мусора.)

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

Достижимые объекты в классическом подходе

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

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

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

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

Рис. 9.6.  Живые и мертвые объекты в комбинированной модели - стек и динамическая память (живые объекты окрашены в серый цвет)

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

[x]. (O1) Значение локальных сущностей или аргументов функции ссылочного типа (как две верхних начальных ссылки на рисунке).

[x]. (O2) Поля ссылочного типа объектов, расположенных в стеке (ниже лежащая ссылка на рисунке).

Рассмотрим пример объявления типа и процедуры, написанный на смеси Pascal и нотации, используемой в этой книге ( reference G - ссылка, которая может быть подсоединена к объекту типа G):

type
COMPOSITE =
record
m:INTEGER
r:reference COMPOSITE
end
...
procedure p is
local
n: INTEGER
c: COMPOSITE
s: reference COMPOSITE
do
...
end

При каждом вызове процедуры p три значения вталкиваются в стек:

Рис. 9.7.  Размещение сущностей для процедуры

Тремя новыми значениями являются: целое n, не влияющее на проблему управления объектами (оно исчезнет при завершении процедуры и не ссылается на другие объекты); ссылка s, являющаяся примером категории О1; и объект с типа COMPOSITE. Сам объект содержится в стеке и занятая объектом память может быть использована по завершении работы процедуры. Но он содержит ссылочное поле r, являющееся примером категории О2.

Итак, для определения достижимости объекта в классическом подходе, комбинирующем стековую и динамическую память, следует начать со ссылок в стеке (переменные ссылочного типа и ссылочные поля комбинированных объектов), и последовательно просмотреть все ссылочные поля присоединенных объектов, если они существуют.

Достижимые объекты в ОО-модели

ОО-структура данных, представленная в предыдущих лекциях, имеет некоторые отличия от рассмотренной выше структуры.

Рис. 9.8.  Достижимость в ОО-модели

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

Другое множество оригиналов возникает из-за возможного присутствия локальных переменных в подпрограмме. Рассмотрим подпрограмму вида

some_routine is
local
rb1, rb2: BOOK3
eb: expanded BOOK3
do
. . .
create rb1
. . .Операции, возможно использующие rb1, rb2 и eb . . .
end

При любом вызове и выполнении подпрограммы some_routine, инструкции в теле подпрограммы могут ссылаться на rb1, rb2, eb и на присоединенные к ним объекты, если они есть. Это значит, что такие объекты должны быть частью множества достижимых объектов, но не обязательно зависимы от корня. Заметим, для eb всегда есть присоединенный объект, а rb1 и rb2 могут при некоторых запусках иметь значение void.

Локальные сущности ссылочного типа, такие как rb1 и rb2, подобны переменным подпрограммы, которые в предыдущей модели были размещены в стеке. Локальные сущности развернутого типа, как eb, подобны объектам, расположенным в стеке.

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

Допустим, например, что а - это атрибут рассматриваемого класса и что полный текст подпрограммы имеет вид:

some_routine is
local
rb1, rb2: BOOK3
eb: expanded BOOK3
do
create rb1;create rb2
a := rb1
end

На следующем рисунке показаны объекты, создаваемые вызовом some_routine, и ссылки с присоединенными объектами.

Рис. 9.9.  Объекты, присоединенные к локальным сущностям

Когда вызов some_routine завершается, объект О, представляющий цель вызова, все еще доступен (иначе не было бы этого вызова). Поле а этого объекта О в результате вызова присоединено к объекту B1 класса BOOK3, созданного первой инструкцией создания нашей подпрограммы. Поэтому объект B1 остается достижимым по завершении вызова. Напротив, объекты B2 и EB, которые были присоединены к rb2 и eb во время вызова, теперь становятся недостижимыми: в соответствии с текстом процедуры невозможно, чтобы какой-либо другой объект "запомнил" В2 или ЕВ.

Проблема управления памятью в ОО-модели

Подводя итог предшествующего анализа, определим оригиналы и соответственно достижимые объекты:

Определение: начальные, достижимые и недостижимые объекты

В каждый момент времени выполнения системы множество оригиналов включает:

[x]. Корневой объект системы.

[x]. Любой объект, присоединенный к локальной сущности, или формальному аргументу, выполняемой в данный момент подпрограммы (для функции включается локальная сущность Result).

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

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

Такое предсказание возможно в некоторых случаях для строго управляемых структур данных. Примером является библиотечный класс, задающий список, - LINKED_LIST, рассматриваемый позже, и связанный с ним класс LINKABLE, описывающий элементы этого списка. Экземпляр LINKABLE создается только с помощью специальных процедур класса LINKED_LIST и может становиться недостижимым только в результате выполнения процедуры remove, удаляющей элементы списка. Для подобных классов можно представить себе особенную процедуру управления памятью. (Такой подход будет изучен позднее в этой лекции.)

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

Три ответа

С недостижимыми объектами можно поступать тремя способами:

[x]. Проигнорировать проблему и надеяться, что хватит памяти для размещения всех объектов: достижимых и недостижимых. Это можно назвать несерьезным (casual) подходом.

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

[x]. Включить в среду разработки (как часть исполняемой системы (runtime system)) механизм, автоматически определяющий и утилизирующий недостижимые объекты. Этот подход принято называть автоматической сборкой мусора (automatic garbage collection).

Остаток лекции посвящен этим подходам.

Оглавление книги