Гради Буч - Объектно-ориентированный анализ и проектирование с примерами приложений на С++ (1158635), страница 68
Текст из файла (страница 68)
Часто это означает немного больше, чем простая передачаобязанности классу более низкого уровня 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;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; эта ассоциация будет уточненапри конкретном инстанцирова-нии классов.Физическая компоновка классов поддержки тоже является частьюархитектурного решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
