Основы объектно-ориентированного программирования - Бертран Мейер
Шрифт:
Интервал:
Закладка:
[x]. Язык C похож на Pascal, но дополнительно вводит динамические массивы и статические переменные, не являющиеся массивами, Язык С динамически размещает переменные типа указатель и массивы, используя библиотечную функцию malloc.
[x]. PL/I поддерживает все модели.
[x]. Lisp системы традиционно были высоко динамичны и полагались большей частью на динамический режим распределения памяти. Одна из наиболее важных операций Lisp, используемая многократно для представления списков, - CONS, создает структуру из двух полей. В первом поле хранится значение элемента, а во втором - указатель на следующий элемент. Здесь CONS, скорее источник новых объектов, чем инструкция их создания.
Повторное использование памяти в трех режимах
Для объектов, созданных как в основанном на стеке режиме, так и в динамическом режиме, возникает вопрос, что делать с неиспользуемыми объектами? Возможно ли память, занятую таким объектом, повторно использовать в более поздних инструкциях создания новых объектов?
В статической модели проблемы не существует: для каждого объекта есть одна навсегда присоединенная сущность. Выполнение требует поддерживать связь с объектом все время, пока сущность активна. Поэтому повторное использование памяти невозможно в настоящей трактовке этого понятия. Однако при острой нехватке памяти похожая технология иногда используется. Если вы уверены, что объекты, присоединенные к двум сущностям, никогда не нужны одновременно, и эти сущности не должны сохранять свои значения между последовательными использованиями, то можно на одной и той же памяти размещать две или более сущности, будучи совершенно увереными в безопасности того, что вы делаете. Эта техника, известная как перекрытие (overlay), достаточно ужасная, все еще практикуется при работе вручную.
Если все-таки использовать перекрытие, то, конечно, его следует выполнять автоматически, используя специальные инструменты, - слишком велика вероятность ошибки. Главной проблемой остается возможность изменений: решение о перекрытии двух переменных может быть корректным на определенном этапе жизни программы. Неожиданное изменение может сделать его неправильным. Мы столкнемся с похожей проблемой ниже, в технологии сборки мусора.В режиме, основанном на стеке, объекты, присоединенные к сущностям, могут быть размещены в стеке. В языках с блочной структурой ситуация упрощается: размещение объектов происходит одновременно для всех сущностей данного блока, допуская использование одного стека для всей программы. Схема действительно элегантна, потому что использует два множества сопутствующих событий:
Динамическое свойство (событие времени выполнения) Статическое свойство (положение в тексте программы) Техника реализации Размещение объекта Начало блока Вталкивание объектов (один для каждой локальной сущности блока) в стек Удаление объекта Конец блока Выталкивание объектов из стекаТаблица 9.1.Размещение и удаление объектов в языках с блочной структурой
Простота и эффективность этой техники реализации является одной из причин успешности языков с блочной структурой. В динамическом режиме все не так просто. Проблема связана с мощью самого механизма: в период компиляции ничего нельзя сказать о создании объекта, невозможно предсказать, когда данный объект может стать ненужным.
Отсоединение
В динамическом режиме объекты могут стать ненужными в непредсказуемые моменты периода выполнения; раз так, то некоторый механизм (определяемый позже в этом обсуждении) может освобождать занятую ими память.
Причина - присутствие в этом режиме выполнения операции отсоединения (detachment), обратной к операции присоединения. В предыдущей лекции изучалось, как сущности присоединяются к объектам, но не рассматривались детали отсоединения. Пора это исправить.
Отсоединение распространяется только на объекты x ссылочного типа. Если x развернутого типа - значением x является объект O, то нет способа отсоединить x от O. Заметьте, однако, если x развернутый атрибут некоторого класса, O представляет подобъект некоторого большого объекта BO. Тогда BO, а вместе с ним и O, может стать недостижимым по одной из причин, изучаемых ниже. Посему в оставшейся части этой лекции можно ограничиться рассмотрением сущностей ссылочного типа.Рис. 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 и "живые" для первых двух. (У программистов принята более прозаическая терминология, и процесс удаления мертвых объектов, изучаемый ниже, называется просто сборкой мусора.)
Для объектов наряду с термином "оригинал" используется термин "корень". Первый термин предпочтительнее, поскольку сама ОО-система имеет "корневой объект" и "корневой класс". Однако результат возможной двусмысленности не сильно вредит делу, потому что корневой объект, как будет видно далее, является одним из оригиналов.Первый шаг к решению проблемы управления памятью при использовании динамического режима - выделение достижимых и недостижимых объектов. Для идентификации достижимых объектов нужно начать с оригиналов и пройти по всем многократно возникающим ссылкам. Так что первый вопрос, - как найти оригиналы? Ответ зависит от структуры периода выполнения, определяемой лежащим в ее основе языком программирования.