Буч Г. - Объектно-ориентированный анализ и проектирование с примерами приложений на C++ - 2001

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

Второй вариант связан с синхронизацией. Как было отмечено в главе 2, множество полезных приложений обходятся одним процессом. Их называют последовательными системами, потому что они используют один поток управления. Для других приложений (особенно это касается систем реального времени) требуется обеспечить синхронизацию нескольких одновременно выполняемых потоков. Такие системы называются параллельными, и в них каким-то образом должно обеспечиваться взаимное исключение процессов, конкурирующих за один и тот же ресурс. Ясно, что нельзя дать возможность управлять одним и тем же объектом одновременно нескольким потокам, это в конце концов приведет к нарушению его состояния. Рассмотрим, например, поведение двух агентов, которые одновременно пытаются добавить элемент одному и тому же объекту класса Queue. Первый агент, начавший добавление элемента, может быть прерван раньше, чем окончит данную операцию, и оставит объект второму агенту в незавершенном состоянии.

Рис. 9-3. Семейства классов

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

•последовательный

•защищенный

•синхронизированный.

Мы рассмотрим каждый из этих вариантов более подробно в следующем разделе. Обеспечение взаимодействия между абстрактным базовым классом, формами его представления и формами синхронизации порождает для каждой структуры семейство классов, подобное тому, которое приведено на рис. 9-3. Теперь можно понять, почему мы в свое время решили организовать библиотеку именно в виде семейств классов, а не в виде единого дерева. Это было сделано из-за того, что такая архитектура:

•Отражает общность различных форм.

•Позволяет осуществлять более простой доступ к элементам библиотеки.

•Позволяет избежать бесконечных метафизических споров о "чистом объектно-ориентированном подходе".

•Упрощает интеграцию системы с другими библиотеками.

Микроорганизация

В целях обеспечения простоты работы с системой выберем один общий стиль оформления структур и механизмов библиотеки:

template<...>

class Name : public Superclass { public:

//конструкторы // виртуальный деструктор

//операторы

//модификаторы

//селекторы

protected:

//данные

//служебные функции

private:

//Друзья

};

Описание абстрактного базового класса Queue начинается следующим образом:

template<class Item> class Queue {

Сигнатура шаблона template служит для задания аргументов параметризованного класса. Отметим, что в C++ шаблоны сознательно введены таким образом, чтобы передать достаточную гибкость (и ответственность) в руки разработчика, инстанцирующего шаблон в своем приложении.

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

Queue();

Queue(const Queue<Item>&); virtual -Queue() ;

Отметим, что мы описали деструктор виртуальным, чтобы обеспечить полиморфное поведение при уничтожении объектов класса. Далее объявим все операторы:

virtual Queue<Item>& operator=(const Queue<ltem>&) ; virtual int operator==(const Queue<Item>&) const; int operator!=(const Queue<Item>&) const;

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

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

Определим теперь модификаторы, позволяющие менять состояние объекта:

virtual void clear() = 0;

virtual void append(const Item&) = 0; virtual void pop() =0;

virtual void remove (unsigned int at) = 0;

Данные операции объявлены как чисто виртуальные, а это значит, что их описание является обязанностью подклассов. Наличие чисто виртуальных функций делает класс Queue абстрактным.

Спецификатор const указывает (компилятор может это проверить) на использование функций-селекторов, то есть функций, предназначенных исключительно для получения информации о состоянии объекта, но не для изменения состояния:

virtual unsigned int length() const = 0; virtual int isEmpty() const = 0; virtual const Item& front() const =0;

virtual int location(const Item&) const = 0;

Эти операции тоже определены как чисто виртуальные, потому что класс Queue не обладает достаточной информацией для их полного описания.

Защищенная часть каждого класса начинается с описания тех элементов, которые формируют основу его структуры и должны быть доступны подклассам.22 Абстрактный класс Queue, в. отличие от своих подклассов (см. ниже), подобных элементов не имеет.

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

virtual void purge () =0;

virtual void add(const Item&) = 0;

virtual unsigned int cardinality() const = 0; virtual const Item& itemAt (unsigned int) const =0; virtual void lock();

virtual void unlock();

Причины, по которым мы ввели именно эти функции, будут рассмотрены в следующем разделе.

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

friend class QueueActiveIterator<Item>; friend class Queuepassivelterator<ltem>;

Как мы увидим в дальнейшем, эти объявления друзей понадобятся для поддержки идиом итератора.

Семантика времени и памяти

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

Рассмотрим тот спектр требований, который должен учитываться при разработке библиотеки общего назначения. На рабочей станции, обладающей большим виртуальным адресным пространством, пользователь скорее всего будет расточать память ради более высокого быстродействия. С другой стороны, в некоторых встроенных системах, таких, как спутник или автомобильный мотор, ресурсы памяти часто ограничены, и разработчик вынужден выбирать в качестве рабочих те абстракции, которые используют меньше памяти (например, выделяя место под данные в стеке, а не в "куче"). Ранее мы различили эти две возможности как ограниченную и неограниченную формы соответственно.

Неограниченные формы применимы в тех случаях, когда размер структуры не может быть предсказан, а выделение и утилизация памяти из кучи не приводит ни к потере времени, ни к снижению надежности (как это бывает в некоторых приложениях, критичных по времени).23 Ограниченные формы лучше подходят для работы с небольшими структурами, размер которых достаточно хорошо предсказуем. Учтем также, что динамическое выделение памяти менее терпимо к ошибкам программиста.

Таким образом, все структуры данной библиотеки должны присутствовать в альтернативных вариантах; поэтому нам придется создать два низкоуровневых класса поддержки, Unbounded (неограниченный) и Bounded (ограниченный). Задачей класса unbounded является поддержка быстро работающего связного списка, элементы которого размещаются в памяти, выделенной из "кучи". Это представление эффективно по скорости, но не по памяти, так как каждый элемент списка должен, кроме своего значения, дополнительно содержать указатель на следующий элемент того же списка. Задача класса Bounded состоит в организации структур на базе массива, что эффективно с точки зрения памяти, но добиться большой производительности трудно, так как, например, при добавлении элемента в середину списка приходится последовательно копировать все последующие (или предыдущие) элементы массива.

Как видно из рис. 9-4, для включения этих классов нижнего уровня в иерархию основных абстракций мы используем агрегацию. Более точно, диаграмма показывает, что мы используем физическое включение по значению с защищенным Доступом, которое означает, что это низкоуровневое представление доступно только подклассам и друзьям. На раннем этапе проектирования мы хотели воспользоваться примесями и сделать unbounded и Bounded защищенными суперклассами.

Рис. 9-4. Ограниченная и неограниченная формы

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

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

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

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

хорошими кандидатами на это обычно являются селекторы, особенно те, которые возвращают простые переменные.

Рассмотрим, например, описание класса Bounded: template<class Item, unsigned int Size>

class Bounded { public:

Bounded();

Bounded(const Bounded<Item, Size>&); ~Bounded();

Bounded< Item, Size>& operator=(const Bounded<Item, Size>&);

int operator==(const Bounded<Item, Size>&) const; int operator!=(const Bounded<Item, Size>&) const; const Item& operator[](unsigned int index) const; Item& operator[](unsigned int index);

void clear();		Item&);
void	insert(const
void	insert(const	Item&, unsigned int before);
void	append(const	Item&);
void	append(const	Item&, unsigned int after);
void	remove(unsigned int at);
void	replace(unsigned int at, const Item&);

unsigned int available() const; unsigned int length() const; const Item& first() const; const Item& last() const;

const Item& itemAt(unsigned int) const; Item& itemAt(unsigned int);

int location(const Item&) const; static void* operator new(size_t);

static void operator delete(void*, size_t); protected:

Item rep[Size] ; unsigned int start; unsigned int stop;

unsigned int expandLeft(unsigned int from); unsigned int expandRight(unsigned int from); void shrinkLeft(unsigned int from);

void shrinkRight(unsigned int from);

};

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

Сердцем класса является защищенный массив rep постоянного размера Size. Рассмотрим следующее объявление:

Bounded<char, 100U> charSequence;

При создании соответствующего объекта в стеке образуется массив постоянного размера из 100 элементов. Защищенные члены класса start и

stop (индексы в этом массиве) указывают начало и конец последовательности. Тем самым мы использовали кольцевой буфер данных. Добавление нового элемента в начало или в конец последовательности не потребует перемещения данных, а добавление элемента в середину массива приводит к копированию не более чем половины его элементов.

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

В C++ ссылки являются механизмом, позволяющим улучшить производительность. Однако пользоваться ими следует предельно осторожно во избежание нарушения корректного доступа к оперативной памяти. В данной библиотеке мы используем ссылки для ускорения работы при передаче аргументов функциям-членам. Это касается, например, класса Bounded, где подобным образом передаются ссылки на объекты классов Bounded и Item. Ссылки, как правило, не используются для передачи примитивных объектов (например, целых чисел в описании функции-члена itemAt) - программа от этого будет работать только медленнее. Кроме того, семантика языка C++ порождает некоторые опасности при манипулировании с временными объектами.

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

Во-первых, встроенные типы данных можно без труда передавать по ссылке и копировать. Объявив типы аргумента постоянными ссылками, можно избежать неприятностей, связанных с появлением временных структур, возникающих при приведении типов [12].

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

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

Например, для класса BoundedQueue мы можем написать следующее: class Event ... typedef Event* EventPtr; BoundedQueue<int, 10U> intQueue;

BoundedQueue<Event, 50U> eventQueuel; BoundedQueue<EventPtr, 100U> eventQueue2;

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

подкласса Event произойдет "срезка", и полиморфное поведение такого экземпляра будет потеряно. С другой стороны, объект класса eventQueue2 содержит указатели на объекты класса Event, поэтому проблема "срезки" не возникает.

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

Посмотрим, как можно использовать класс Bounded при формировании конкретного класса BoundedQueue. Отметим, что абстракция BoundedQueue содержит защищенный элемент rep класса Bounded. template<class Item, unsigned int Size>

class BoundedQueue : public Queue<Item> { public:

BoundedQueue();

BoundedQueue(const BoundedQueue< Item, Size>&); virtual ~BoundedQueue() ;

virtual Queue<Item>& operator=(const Queue<Item>&); virtual Queue<Item>& operator=(const BoundedQueue<Item, Size>&) ;

virtual int operator==(const Queue<Item>&) const; virtual int operator" (const BoundedQueue<Item, Size>&)

const;

int operator!=(const BoundedQueue< Item, Size>&) const; virtual void clear();

virtual void append(const Item&); virtual void pop();

virtual void remove(unsigned int at); virtual unsigned int available() const; virtual unsigned int length() const; virtual int isEmpty() const;

virtual const Item& front() const; virtual int location(const Item&) const;

protected:

Bounded< Item, Size> rep; virtual void purge();

virtual void add(const Item&);

virtual unsigned int cardinality() const; virtual const Item& itemAt(unsigned int) const; static void* operator new(size_t);

static void operator delete(void*, size_t);

};

Основная задача данного класса - завершить протокол, определенный в базовом классе. Часто это означает немного больше, чем простая передача обязанности классу более низкого уровня Bounded, как предлагается в следующей реализации:

template<class Item, unsigned int Size>

unsigned int BoundedQueue<Item, Size>::length() const

{

return rep.length() ;

}

Отметим, что в описание класса BoundedQueue включены некоторые дополнительные операции, которых нет в его суперклассе. Добавлен селектор

available, возвращающий количество свободных элементов в структуре (вычисляется как разность Size - length()). Эта операция не включена в описание базового класса главным образом из-за того, что для неограниченной модели вычисление свободного места не очень осмысленно. Мы также переопределили оператор присваивания и проверку равенства. Как уже отмечалось ранее, это позволяет применить более эффективные алгоритмы по сравнению с базовым классом, так как подклассы лучше знают, что и как делать. Добавленные операторы new и delete определены в защищенной части класса, чтобы лишить клиентов возможности произвольно динамически размещать экземпляры BoundedQueue (что согласуется со статической семантикой этой конкретной формы).

Класс Unbounded имеет, в существенном, тот же протокол, что и класс Bounded, однако его реализация совершенно другая.

template<class Item, class StorageManager> class Unbounded {

public:

…

protected:

Node<Item, StorageManager>* rep; Node<Item, StorageManager>* last; unsigned int size;

Node<Item, StorageManager>* cache; unsigned int cacheIndex;

};

Форма Unbounded реализует очередь как связный список узлов, где узел (Node) реализован следующим образом:

template<class Item, class StorageManager> class Node {

public:

Node(const Item& i,

Node<ltem, StorageManager>* previous, Node<Item, StorageManager>* next);

Item item;

Node<Item, StorageManager>* previous; Node<ltem, StorageManager>* next; static void* operator new(size_t);

static void operator delete(void*, size_t);

};

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

Помня, что классы Bounded и Unbounded имеют практически идентичный внешний протокол, а, значит, их функциональные свойства во многом подобны, можно предположить, что и реализация будет схожей. Однако различие во внутреннем представлении классов приводит к существенно различной пространственно-временной семантике. Манипуляции с узлами связанного списка, например, осуществляются очень быстро, однако процедура нахождения нужного элемента будет занимать время порядка O(n). Поэтому наше представление кэширует последний узел, к которому было обращение, в надежде, что следующее обращение будет либо к этому же узлу, либо к его соседям. Схема же, базирующаяся на массивах, дает низкое быстродействие (в худшем случае порядка O(n/2) если элемент расположен в середине массива) при добавлении или удалении элементов, однако обеспечивает высокую скорость поиска (порядка O(1) ).

Управление памятью

Задача управления памятью возникает для неограниченных форм реализации. В этом случае разработчик библиотеки должен определить политику выделения и освобождения памяти из кучи при осуществлении операций над узлами. Наивный подход просто использует глобальные функции new и delete, что не может обеспечить достаточной производительности системы. Кроме того, на некоторых компьютерных платформах управление памятью крайне усложнено (например, при наличии сегментированного адресного пространства в некоторых операционных системах персональных компьютеров) и требует разработки специальной стратегии, жестко привязанной к определенной операционной среде. Для нашей библиотеки надо четко выделить подсистему управления памятью.

На рис. 9-5 приведен выбранный для данной библиотеки механизм управления памятью.24 Рассмотрим сценарий, иллюстрацией которого служит данная диаграмма:

•Клиент (aClient) вызывает операцию добавления (append) для экземпляра класса UnboundedQueue (более точно, экземпляра класса, инстанцированного из UnboundedQueue).

•UnboundedQueue, в свою очередь, передает выполнение операции своему элементу rep, который является экземпляром класса unbounded.

•Unbounded, вызывая свою статическую функцию new, выделяет необходимый объем адресного пространства для размещения нового экземпляра Node.

•Этот экземпляр Node, в свою очередь, делегирует ответственность за выделение памяти своему StorageManager, который доступен классу, инстанци-руемому из UnboundedQueue (и, следовательно, классам Unbounded и Node), как аргумент шаблона. StorageManager разделяется всеми экземплярами и служит для обеспечения последовательной политики выделения памяти на уровне класса.

Рис. 9-5. Механизм управления памятью

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

Единственное требование, предъявляемое к вариантам StorageManager, заключается в необходимости сохранения единого

протокола. В частности, все они должны содержать открытые функции-члены allocate и deallocate, предназначенные соответственно для выделения и освобождения памяти. Рассмотрим в качестве примера простейший вариант такого класса:

class Unmanaged { public:

static void* allocate(size_t s)

{return ::operator new(s);} static void deallocate(void* p, size_t) {::operator delete(p);}

private: Unmanaged() {}

Unmanaged(Unmanaged&) {} void operator=(Unmanaged&) {}

void operator==(Unmanaged&) {} void operator!=(Unmanaged&) {}

};

Обратите внимание на идиому, которая применяется, чтобы пользователь не мог копировать, присваивать и сравнивать экземпляры данного класса.

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

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

В соответствии с приведенными выше соображениями, соответствующий класс поддержки можно определить следующим образом: class Pool {

public:

Pool(size_t chunkSize); ~Pool();

void* allocate(size_t);

void deallocate(void*, size_t);

void preallocate(unsigned int numberOfChunks); void reclaimUnusedChunks();

void purgeUnusedChunks(); size_t chunkSize() const;

unsigned int totalChunks() const; unsigned int numberOfDirtyChunks() const; unsigned int numberOfUnusedChunks() const;

protected:

struct Element ... struct Chunk ...

Chunk* head;

Chunk* unusedChunks;