Основы объектно-ориентированного программирования - Бертран Мейер

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

Поскольку проблема недостижимости рассматривается в таких классических подходах, как 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) подходом.