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

size_t repChunkSize; size_t usableChunkSize; Chunk* getChunk(size_t s);

};

Описание содержит два вложенных класса Element и chunk (отрезок). Каждый экземпляр класса Pool управляет связным списком объектов chunk, представляющих собой отрезки "сырой" памяти, но трактуемых как связные списки экземпляров класса Element (это один из важных аспектов, управляемых классом pool). Каждый отрезок может отводиться элементам разного размера и для эффективности мы сортируем список отрезков в порядке возрастания их размеров. Менеджер памяти может быть определен следующим образом:

class Managed { public:

static Pool& pool;

static void* allocate(size_t s)

{return pool.allocate(s); } static void deallocate(void* p, size_t s)

{pool.deallocate(p, s);} private:

Managed() {} Managed(Managed&) {}

void operator=(Managed&) {} void operator==(Managed&) {} void operator!=(Managed&) {} };

Этот класс имеет тот же внешний протокол, что и Unmanaged. Из-за того, что в C++ шаблоны сознательно недостаточно четко определены, соответствие данному протоколу проверяется только при трансляции инстанцированного класса типа UnboundedQueue, в тот момент, когда конкретный класс сопоставляется с формальным аргументом

StorageManager.

Объект класса Pool, принадлежащий классу Managed, является статическим. Это позволяет нескольким конкретным структурам (требующим управления) делить между собой единый пул памяти. Различные структуры, не требующие управления, могут, конечно, определить своего менеджера и свой пул памяти, предоставляя таким образом разработчику полный контроль над политикой выделения памяти.

Рис. 9-6. Классы управления памятью

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

Мы показали только ассоциативную связь между классом Managed и его клиентами Unbounded и UnboundedQueue; эта ассоциация будет уточнена при конкретном инстанцирова-нии классов.

Физическая компоновка классов поддержки тоже является частью архитектурного решения. Рис. 9-7 иллюстрирует их модульную архитектуру. Мы выбрали именно такую схему, чтобы изолировать классы, которые, повидимому, будут чаще всего подвергаться изменениям.

Рис. 9-7. Модули управления памятью

Исключения

Несмотря на то, что язык C++ можно заставить соблюдать многие статические предположения (нарушение которых повлечет ошибку компиляции), для выявления динамических нарушений (таких, как попытка добавить элемент к полностью заполненной ограниченной очереди или удалить элемент из пустого списка) приходится использовать и другие механизмы. В данной библиотеке используются средства обработки исключений, предоставляемые C++ [14]. Наша архитектура включает в себя иерархию классов исключений и, отдельно от нее, ряд механизмов по выявлению таких ситуаций.

Начнем с базового класса Exception (исключение), обладающего несложным протоколом:

class Exception { public:

Exception(const char* name, const char* who, const char*

what);

void display() const; const char* name() const; const char* who() const; const char* what() const;

protected:

…

};

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

Анализ различных классов нашей библиотеки подсказывает возможные типы исключений, которые можно оформить в виде подклассов базового класса Exception:

•ContainerError

•Duplicate

•IllegalPattern

•IsNull

•LexicalError

•MathError

•NotFound

•NotNull

•NotRoot

•Overflow

•RangeError

•StorageError

•Underflow

Объявление класса overflow (переполнение) может выглядеть следующим образом:

class Overflow : public Exception { public:

Overflow(const char* who, const char* what) : Exception("Overflow", who, what) {}

};

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

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

inline void _assert(int expression,const Exception& exception)

{

if (!expression) throw(exception);

}

Для эффективности мы определили эту функцию как встроенную. Преимущество подобной схемы состоит в том, что она локализует все исключения (в C++ throw имеет синтаксис вызова функции). Так, для трансляторов, которые до сих пор не поддерживают исключений, можно использовать специальную директиву (-D для большинства трансляторов C++) для переопределения вызова throw в вызов другой функции-не-члена, выводящей сообщение на экран и останавливающей выполнение программы: void _catch(const Exception& e)

{

cerr << "EXCEPTION: "; e.display();

exit(l);

}

Рассмотрим реализацию функции insert класса Bounded: template<class Item, unsigned int Size>

void Bounded<ltem, Size>::insert(const Item& item)

{

unsigned int count = length();

_assert((count < Size), Overflow("Bounded::Insert", "structure is full"));

if (!count) start = stop = 1; else

{

start--; if (!start)

start = Size;

}

rep[start - 1] = item;

}

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

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

Рис. 9-8 иллюстрирует схему взаимодействия классов, обеспечивающих реализацию механизма обработки исключений.

Рис. 9-8. Классы обработки исключений

Итерация

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

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

•Наличие выделенного итератора классов позволяет одновременно проводить несколько просмотров одного и того же объекта.

•Наличие итерационного механизма в самом классе несколько нарушает его инкапсуляцию; выделение итератора в качестве отдельного

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

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

Рассмотрим в качестве примера активный итератор для класса Queue: template <class Item> class QueueActiveIterator {

public:

QueueActiveIterator(const Queue<Item>&); ~QueueActiveIterator();

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

void reset(); int next() ;

int isDone() const;

const Item* currentltem() const; protected:

const Queue<Item>& queue; int index;

};

Каждому итератору в момент создания ставится в соответствие определенный объект. Итерация начинается с "верха" структуры, что бы это ни значило для данной абстракции.

С помощью функции currentItem клиент может получить доступ к текущему элементу; значение возвращаемого указателя может быть нулевым в случае, если итерация завершена или если массив пуст. Переход к следующему элементу последовательности происходит после вызова функции next (которая возвращает О, если дальнейшее движение невозможно, как правило, из-за того, что итерация завершена). Селектор isDone служит для получения информации о состоянии процесса: он возвращает 0, если итерация завершена или структура пуста. Функция reset позволяет осуществлять неограниченное количество итерационных проходов по объекту.

Например, при наличии следующего объявления:

BoundedQueue<NetworkEvent> eventQueue;

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

QueueActiveIterator<NetworkEvent> iter(eventQueue); while (!iter.isDone()) { iter.currentItem()->dispatch();

iter.next();

}

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

Конструктор класса QueueActiveIterator сначала устанавливает связь между итератором и конкретной очередью. Затем он вызывает защищенную функцию cardinality, которая определяет количество элементов в очереди. Таким образом, конструктор можно описать следующим образом:

template<class Item> QueueActiveIterator<ltem>::QueueActiveIterator(const Queue<Item>& q)

:queue(q), index(q.cardinality() ? О : -1) {}

Класс QueueActiveIterator имеет доступ к защищенной функции cardinality класса Queue, поскольку числится в дружественных ему.

Операция итератора isDone проверяет принадлежность текущего индекса допустимому диапазону, который определяется количеством элементов очереди:

template<class Item>

Рис. 9-9. Механизм итерации

int QueueActiveIterator<Item>::isDone() const

{

return ((index < 0) II (index >= queue.cardinality()));

}

Функция currentItem возвращает указатель на элемент, на котором остановился итератор. Реализация итератора в виде индекса объекта в очереди дает возможность в процессе итераций без труда добавлять и удалять элементы из очереди:

template<class Item>

const Item* QueueActiveIterator<Item>::currentItem () const

{

return isDone() ? 0 : &queue.itemAt(index);

}

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

Операция next увеличивает значение текущего индекса на единицу, что соответствует переходу к следующему элементу очереди, а затем проверяет допустимость нового значения индекса:

template<class Item>

int QueueActiveIterator<Item>::next()

{

index++;

return !isDone();

}

Итератор, таким образом, в процессе своей работы вызывает две защищенные функции класса Queue: cardinality и itemAt. Определив эти функции как чисто виртуальные, мы передали ответственность за их конкретную оптимальную реализацию классам, производным от Queue.

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

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

template<class Item>

Queue<Item>& Queue<Item>::operator=(const Queue<Item>& q)

{

if (this == &q) return *this;

((Queue<Item>&)q).lock(); purge(); QueueActiveIterator<Itea> iter(q); while (!iter.isDone()) { add(*iter.currentltem()); iter.next();

} ((Queue<Item>&)q).unlock(); return *this;

}

В данном алгоритме используется идиома блокирования, которая более подробно рассмотрена в следующем разделе.

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

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

template <class Item>

class QueuePassiveIterator { Public:

QueuePassiveIterator(const Queue<Item>&); ~QueuePassiveIterator();

int apply(int (*)(const Item&)); Protected:

const Queue<Item>& queue;

};

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

Синхронизация

При разработке любого универсального инструментального средства должны учитываться проблемы, связанные с организацией параллельных процессов. В операционных системах типа UNIX, OS/2 и Windows NT приложения могут запускать несколько "легких" процессов26. В большинстве случаев классы просто не смогут работать в такой среде без специальной доработки: когда две задачи взаимодействуют с одним и тем же объектом, они должны делать это согласованно, чтобы не разрушить состояния объекта. Как

уже отмечалось, существуют два подхода к задаче управления процессами; они находят свое отражение в существовании защищенной и синхронизированной форм класса.

При разработке данной библиотеки было сделано следующее предположение:

разработчики, планирующие использовать параллельные процессы, должны импортировать либо разработать сами по крайней мере класс Semaphore (семафор) для синхронизации легких процессов. Разработчики, которые не хотят связываться с параллельными процессами, будут свободны от необходимости поддерживать защищенные или синхронизованные формы классов (таким образом, не потребуется никаких дополнительных издержек). Защищенные и синхронизированные формы изолированы в библиотеке и основываются на своей внутренней реализации параллелизма. Единственная зависимость от локальной реализации сосредоточена в классе Semaphore, который имеет следующий интерфейс:

class Semaphore { public:

Semaphore ();

Semaphore (const Semaphore&); Semaphore (unsigned int count); ~Semaphore ();

void seize(); // захватить void release(); // освободить unsigned int nonePending() const;

protected:

};

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

Как показано на рис. 9-3, защищенный класс является прямым подклассом своего конкретного ограниченного либо неограниченного класса и содержит в себе объект класса Guard. Все защищенные классы имеют общедоступные функции-члены seize (захватить) и release (освободить), позволяющие получить эксклюзивный доступ к объекту. Рассмотрим в качестве примера класс GuardedUnboundedQueue, производный от

UnboundedQueue:

template<class Item, class StorageManager, class Guard> class GuardedUnboundedQueue : public UnboundedQueue<Item, StorageManager> {

public:

GuardedUnboundedQueue ();

virtual ~GuardedUnboundedQueue (); virtual void seize();

virtual void release(); protected:

Guard guard;

};

В нашей библиотеке предусмотрен интерфейс одного из предопределенных классов защиты: класса semaphore. Пользователи могут дополнить реализацию данного класса в соответствии с локальным определением легкого процесса.

На рис. 9-10 приведена схема работы данного варианта синхронизации; клиенты, использующие защищенные объекты, должны

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

Рис. 9-10. Процессы защищенного механизма

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

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

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

Альтернативный подход подразумевает возможность обслуживания одним семафором сразу нескольких защищенных объектов. Разработчику при этом нужно только создать новый класс-страж, имеющий тот же протокол, что и semaphore (но не обязательно являющийся его подклассом). Этот класс может содержать семафор в качестве статического члена; тогда семафор будет совместно использоваться всеми экземплярами класса. Инстанцируя защищенную форму с этим новым стражем, разработчик библиотеки вводит новую политику, поскольку все объекты инстанцированного класса пользуются общим стражем, вместо выделения отдельного стража каждому объекту. Преимущество данной схемы наиболее ясно проявляется, когда новый класс-страж используется для инстанцирования других структур:

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

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

class Monitor { public:

Monitor(); Monitor(const Monitor&); virtual ~Monitor();

virtual void seizeForReading() = 0;

virtual void seizeForWriting() = 0; virtual void releaseFromBeadingt() = 0; virtual void releaseFromWritingt() = 0;

protected:

…

};

С помощью мониторов можно реализовать два типа синхронизации:

• Одиночная Гарантирует семантику структуры в присутствии нескольких потоков управления, но с одним читающим или одним записывающим.

• Множественная Гарантирует семантику структуры в присутствии нескольких потоков управления, с несколькими читающими или одним записывающим.

Агент записи меняет состояние объекта; агенты записи вызывают функции-модификаторы. Агент чтения сохраняет состояние объекта; он вызывает только функции-селекторы. Как видно, множественная форма синхронизации обеспечивает наивысшую степень параллелизма процессов. Мы можем реализовать обе политики в виде подклассов абстрактного базового класса Monitor. Обе формы можно построить на основе класса

Semaphore.

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

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

class ReadLock { public:

ReadLock (const Monitor& m)

: monitor(m) {monitor.seizeForReadingt);} ~ReadLock () (monitor.releaseFromReading();}

private:

Monitor& monitor;

};