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

Значит ли отсоединение объектов, например 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.

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