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

Подход на уровне компонентов

(Этот раздел описывает решение, полезное только для специального случая; его можно пропустить при первом чтении книги.)

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

Это решение применимо только для ОО-программирования "снизу-вверх", где структуры данных создаются не для нужд конкретной программы, а строятся как повторно используемые классы.

Что предлагает ОО-подход по отношению к управлению памятью? Одна из новинок скорее организационная, чем техническая: в этом подходе большое внимание уделяется повторному использованию библиотек. Между разработчиками приложения и создателями системных средств - компилятора и среды разработки - стоит третья группа людей, отвечающих за написание повторно используемых компонентов, реализующих основные структуры данных. Членов третьей группы, которые, конечно могут иногда выступать и в двух других ипостасях, принято называть производителями компонентов (component manufacturers).

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

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

Управление памятью связного списка

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

Допустим, класс LINKED_LIST имеет только две процедуры вставки: put_right и put_left, вставляющие новый элемент справа или слева от текущей позиции курсора. Каждой процедуре вставки необходимо создать ровно один новый LINKABLE объект. Типичная реализация приведена ниже:

put_right (v: ELEMENT_TYPE) is
- Вставка элемента со значением v правее позиции курсора.
require
...
local
new: LINKABLE
do
create new.make (v)
active.put_linkable_right (new)
... Инструкции по изменению других связей...
end

Рис. 9.11.  Связный список

Инструкция создания create new.make (v) дает указание уровню реализации языка разместить в памяти новый объект.

Точно так же, как мы управляем тем, где создавать объекты, мы точно знаем, где они становятся недостижимыми, - в процедурах удаления. Пусть в нашем классе три такие процедуры: remove, remove_right, remove_left. Могут быть также и другие процедуры, такие как remove_all_occurrences (которая удаляет все экземпляры с определенным значением) и wipe_out (удаляет все элементы списка). Допустим, что если они присутствуют, то используют первые три процедуры удаления. Процедура remove, например, может иметь следующую форму:

remove is
- удаляет элемент текущей позиции курсора.
do
...
previous.put_linkable_right (next)
... Инструкции по изменению других связей...
active := next
end

Рис. 9.12.  Удаление объекта

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

Предположим, экземпляры LINKABLE хранятся в структуре данных, называемой available. Она будет представлена ниже. Тогда можно заменить инструкции создания типа create new.make (v) в put_right и put_left на

new := fresh (v)

где fresh закрытая функция класса LINKED_LIST, возвращающая готовый к использованию экземпляр linkable. Функция fresh пытается получить память из available списка, и выполнит создание нового элемента только, когда этот список пуст.

Элементы будут попадать в available в процедурах удаления. Например, тело процедуры remove теперь должно быть:

do
recycle (active)
- остальное без изменений:
... Инструкции по обновлению связей: previous, next, first_element, active...

где recycle новая процедура LINKED_LIST играет роль, противоположную fresh, добавляя свой аргумент в available. Эта процедура будет закрытой, она нужна только для внутреннего использования.

Работа с утилизированными объектами

Для реализации fresh и recycle, можно среди других возможных вариантов представить available как стек: fresh будет удалять элемент из стека, а recycle будет помещать элемент в стек. Создадим класс STACK_OF_LINKABLES для этого случая и добавим следующие закрытые компоненты в класс LINKED_LIST (В упражнении У23.1. требуется определить, будет ли корректным появление у функции fresh побочных эффектов.):

available: STACK_OF_LINKABLES
fresh (v: ELEMENT_TYPE): LINKABLE is
- Новый элемент со значением v, для повторного
- использования во вставке
do
if available.empty then
- Создание нового элемента
create Result.make (v)
else
- Повторное использование linkable
Result := available.item; Result.put (v); available.remove
end
end
recycle (dead: LINKABLE) is
-Возвращает dead в список достижимых элементов.
require
dead /= Void
do
available.put (dead)
end

Мы можем объявить класс STACK_OF_LINKABLES следующим образом:

class
STACK_OF_LINKABLES
feature {LINKED_LIST}
item: LINKABLE
- Элемент в вершине стека
empty: BOOLEAN is
- нет элементов в стеке?
do
Result := (item = Void)
end
put (element: LINKABLE) is
- Добавить элемент в вершину стека.
require
element /= Void
do
element.put_right (item); item := element
end
remove is
- Удалить последний добавленный элемент.
require
not empty
do
item := item.right
end
end

Рис. 9.13.  STACK_OF_LINKABLES

Представление стека использует все преимущества поля right, присутствующего в каждом элементе LINKABLE, связывая все утилизированные элементы и предоставляя, тем самым, дополнительную память для размещения новых элементов списка LINKED_LIST. Класс LINKABLE должен экспортировать свои компоненты right и put_right в класс STACK_OF_LINKABLES.

Компонент available является атрибутом класса. Это означает, что каждый связный список будет иметь свой собственный стек. Конечно, память можно было бы использовать эффективнее в системе, содержащей несколько списков и единственный стек для всех удаленных элементов. Такая техника однократных функций (once functions), будет представлена позже; применение ее для available означает, что только один экземпляр класса STACK_OF_LINKABLES будет существовать до конца выполнения системы, что означает достижение поставленной цели. ( Упражнение У9.3. и У9.4. Об однократных функциях см. лекцию 18)

Дискуссия

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

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

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