А. Александреску - Современное проектирование на C++ (1119444), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

Бывалые программисты на С++ инстинктивно избегают конструкций, ориентированных на использование динамической памяти, поскольку они по опыту знают о связанных с этим лополнительных затратах. Таким образом, у программистов возникает некий психологический барьер. 4.2. Как работает стандартный механизм распределения динамической памяти Изучать тенденции, связанные с использованием памяти, как показал Кнут (Кпц!)з, !998), очень интересно. Он разработал много основных стратегий распределения памяти, а после опубликования его работы их появилось еше больше.

Часть!. Методы Как работает стандартный механизм распределения памяти? Он управляет пулом байтов и может выделять из него участки памяти любого размера. В качестве вспомогательной структуры может применяться простой блок управления. зсгцст мещсопсго1в1оск ( эсб::з1хе т азге ; Ьоо1 ача11аЫе ; Память, которой управляет структура мещсопсго1в1оск, располагается сразу за ним, а ее объем, выраженный в байтах, определяется переменной злхе .

Вслед за этим участком памяти располагается следующая структура мещСопсго1в1оск и тл. Во время запуска программы в начале пула располагается только одна структура мещСопсго1в1оск, которая управляет всей памятью как одним большим участком. Это — корневой блок управления, который никогда никуда не перемешается. На рис.

4.1 показана схема распределения памяти для пула, имеющего объем 1 Мбайт, в момент запуска программы. Рис. 4. 1 Карта расирсосяеиия яамяти а момсят заяусиа ирограммы При каждом запросе на выделение памяти выполняется линейный поиск подходящего блока, размер которого либо равен требуемому, либо превышает его.

Поразительно, как много существует стратегий, позволяющих удовлетворить эти запросы, и как странно все они работают! Срели подходящих блоков памяти можно найти первый, наилучший, наихудший и лаже случайно выбранный. Как ни странно, наихудший блок оказывается лучше наилучшего — как вам этот оксюморон?! Кажлое улаление объекта из памяти влечет за собой новый линейный поиск блока, предшествующего удаляемому, и последующее выравнивание его размера. Как видим, эта стратегия не слишком эффективна с точки зрения затрат времени, однако лополнительные затраты памяти довольно малы -- в каждом блоке нужно разместить две переменные типа з)ае с и Ьоо1 соответственно. Иногда можно лаже сэкономить один бит на каждой переменной типа эзге с, использовав его лля размегдения переменной ача)1аЫе .

Сжатая структура мещсоптго1в1оск имеет следующий вил. // код, зависящий от платформы и компилятора атгцсс мевсопсго1в1оск ( Бто::ззхе т 512е: 31; Ьоо1 ача11аЫе: 1; ); Если в каждом объекте мещсоптго1в1оск хранить указатели на предылуший и следувнций объекты этого типа, время, необходимое лля освобождения памяти, может стать постоянным.

Это происходит потому, что удаляемый блок связан со смежными 101 Глава 4. Размещение в памяти небольших объектов блоками и может их выравнивать соответствующим образом. Для этого необходима такая структура блока управления. этгцст метсоптго1в1ос(с ( Ьоо1 ача)1аЬ)е; метсоптго1в1ос!с' ргеч; метсоптго1в1ос!сь пехт ; ) На рис. 4.2 показано распределение пула памяти в виде дважды связанно~о списка блоков.

Переменная-член з!ге больше не нужна, поскольку размер блока можно вычислить с помощью выражения тЫз- пехт — тЬ1э. Дополнительные затраты памяти, связанные с необходимостью хранить два указателя и переменную типа Ьоо1, по-прежнему существуют. (Как и ранее, можно прибегнуть к системно-зависимым трюкам и запаковать булевскую переменную в один из указателей.) Рис.

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

4.3. Распределитель памяти для небольших обьектов Распределитель памяти для небольших объектов работает с четырехслойной структурой, показанной на рис. 4.3. Ее верхние слои используют функциональные возможности, предоставляемые нижними слоями. На дне структуры расположен тип сбцп(с. Каждый объект типа СЬцп!с содержит участок памяти (сйцп)с), состоящий из целого числа блоков фиксированного размера, и управляет им. Объекты типа сбцп(с позволяют выделять и освобождать блоки памяти. Если в объекте типа Сбцп(с не осталось свободных блоков, функция распределения памяти вернет нуль, В следующем слое расположен класс р1хес)д11осатог.

Объекты этого класса используют участки памяти в качестве строительных блоков. Основное предназначение класса р)хес)д11осатог — удовлетворять запросы на выделение памяти, объем которой превышает размер участка. Для этого объекты класса р!хес)д11осатог образовывают массив объектов типа СЬцп(с. Если поступил запрос на выделение памяти и все существующие участки памяти заняты, объект класса р1хес(д11осатог создает новый обьект типа Сбцп!с и записывает его в массив. Затем он выполняет запрос на выделение памяти, переадресовывая его этому объекту. Часть Ь Методы 8гпаИОЬ~вст ' Предоставляет функциональные вазможности нв уровне объектов ' Прозрачен — классы наследуют аваяствв только абъвктав класса ЗтввОЬГвст 5гпаИОьуЯИасатаг ' Пазвапявт размещать в памяти небольшие объекты рвзнага размера ' Канфигурвцию параметров махна изменять ВхедАИасатаг ' Размещает объекты только одного фиксированного размера СЬОПК * Размещает абъекгы только одного фиксираввннага размера ' Максимально вазмажнав количество размещаемых абъектав фиксировано Рис.

4.Д Мнагаслаиная структура распределителя памяти для небальших абьектае Класс 5юа11оЬ)А11осатог выполняет общие функции, связанные с выделением и освобождением памяти. Объекты этого класса состоят из нескольких объектов класса Рт хедд11осатог, каждый из которых специализирован для выделения объектов определенного размера. В зависимости от требуемого количества байтов объекты класса 5ма!10Ь)А11осатог направляют запрос одному из объектов класса Рдхедд11осатог или стандартному оператору г горегатог пеш, если запрашиваемый объем памяти слишком велик. На верхнем уровне расположен класс 5ща110Ь)ест, представляющий собой оболочку класса Рбхедд11осатог.

Он инкапсулирует все функциональные возможности, связанные с распределением динамической памяти, и предоставляет их другим классам. Класс 5юа1- 10Ь) ест перегружает операторы пеп и де1ете и передает их объектам класса 5юа! 1оЬ)А1- 1осатог. Таким образом, объекты, создаваемые программистом, могут наследовать функции для работы с динамической памятью от класса 5юа110Ь) есц Кроме того, можно непосредственно использовать классы 5юа110Ь)А11осатог и Ртхедд11осатог, (Класс сЬОПК слишком примитивен и ненадежен, поэтому он определяется в закрытом разделе класса Ртхедд!1осатог.) Большей частью, однако, программы пользователей просто наследуют свойства базового класса 5юа11оЬ)А11осасог, приобретая функциональные возможности для распределения динамической памяти.

Интерфейс этого класса достаточно прост. 4.4. Класс СМпК Каждый объект класса СЬОП1с содержит участок памяти, состоящий из фиксированного числа блоков, и управляет им. Размер и количество блоков указываются при создании объекта класса сЬОПЬ. Объекты типа сЬОПЬ позволяют выделять и освобождать блоки памяти. Если в объекте типа сЬОПИ не осталось свободных блоков, функция распределения памяти вернет нуль. Ниже приведено определение класса сЬОПК. // В классе нет закрытых полей — класс СЬОПК представляет собой // структуру старых простых данных (Р1атп о1д овса — РОО). // Структура определяется внутри класса Ртхедя!1осатог // и управляется только им.

втгмст СЬОпк ( тготд тптт(всд::зтхе с Ыоск5тхе, Опзтдпед сЬаг ЫосИ5) ыобд* А11осасе(зтдтгзтве с Ыоск5тхе); ыот'д Оеа11осате(ыот'дь р, 5тдгтвт'ае т Ыоск5тхе); Опзтдпед сЬаг" ровса Глава 4. Размещение е памяти небольших объектов ипз(цпед сЬаг Н гзтлиаз1аЫев1оск , Ыоскзяуа41аЫе Кроме указателя на управляемый участок памяти объект класса сЬипк хранит следуюшие целочисленные величины. ° Переменная тзгзтлиаз1аЫев1оск хранит индекс первого доступного блока внутри порции памяти. ° Переменная Ыоскзлиа41аЫе представляет собой количество блоков, доступных в данной порции памяти. Интерфейс класса сЬипк очень прост.

Функция тпз т инициализирует обьект класса сЬипх, а функция яе1еазе — освобождает занятую памяп Функция л11осате выделяет блок памяти, а функция оеа11осате освобождает его. Функциям а11осате н пеа11осате нужно передавать размер памяти, поскольку в самом обьекте класса сЬипк эта величина не хранится, так как на верхних уровнях структуры размер блока неизвестен.

Характеристики

Список файлов книги