Задача 20. Контейнеры в памяти.

Часть 1: уровни управления памятью Сложность: 3

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

Вопрос для новичка

1. Что такое диспетчеры памяти (известные также как распределители памяти), и в чем заключается их основная функция? Вкратце опишите две основные стратегии управления динамической памятью в С++.

Вопрос для профессионала

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

Решение

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

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

внутренние структуры данных, используемые контейнерами, такими как vector, deque, list, set/multiset и map/multimap; и

как работает распределение динамической памяти.

Давайте начнем с распределения- динамической памяти, а затем разберемся, что это означает для стандартной библиотеки.

Диспетчеры памяти и их стратегии: краткий обзор

1. Что такое диспетчеры памяти (известные также как распределители памяти), и в чем заключается их основная функция? Вкратце опишите две основные стратегии управления динамической памятью в С++.

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

- Строго говоря, здесь рассматривается только частная задача распределения памяти, а именно задача выделения памяти (allocation). Однако в силу того, что выделение памяти тесно связано с ее освобождением (deallocation) в одну задачу распределения (которая, в свою очередь, является частью глобальной задачи управления памятью (memory management)), и распространенностью термина распределение в русскоязычной литературе, в дальнейшем в книге будет использован именно этот термин, а из контекста его использования будет понятно, о какой именно подзадаче идет речь. - Прим. перев.

poro диспетчера памяти, а этот диспетчер, в свою очередь, должен решить, как разделить доступную память, опираясь на некоторую стратегию управления памятью.

Вот как выглядит краткое описание двух распространенных стратегий управления памятью в С++. Более подробное рассмотрение данного вопроса выходит за рамки нашей книги; дополнительную информацию вы найдете в описании вашей операционной системы.

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

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

Третья важная стратегия, распределение со сборкой мусора, не полностью совместима с указателями С и С+ + , функциями типа mall ос, new и потому не имеет прямого отношения к рассматриваемому нами вопросу. Сборка мусора становится все более популярна и постепенно приходит и в С++ (но не для работы с указателями и оператором new). Я планирую рассмотреть этот вопрос в своей будущей книге, а сейчас вы можете обратиться к [C++CLI04] и [Jones96] .

На практике мы часто сталкиваемся с комбинацией этих стратегий. Например, возможно, ваш диспетчер памяти использует схему общего назначения для всех запросов размером больше некоторого значения б, а в качестве оптимизации для всех запросов размером меньше S используется выделение блоков памяти фиксированного размера. Обычно достаточно неудобно иметь отдельные области памяти для запросов размером 1 байт, 2 байта и так далее, так что большинство диспетчеров используют отдельные области для выделения блоков, размер которых кратен некоторому числу, скажем, 16 байтам. Если вы запрашиваете блок размером 16 байтов, все отлично; но если вы запросите 17 байтов, то память будет выделена из области для 32-байтовых блоков, и 15 байтов памяти пропадут впустую. Это источник дополнительных расходов памяти, но об этом мы поговорим чуть позже.

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

Выбор стратегии

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

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

Кроме того, за дополнительной информацией о распределении памяти можно порекомендовать обратиться, например, к разделу 2.S книги Д. Клут Искусство программирования, том 1. Основные алгоритмы, 3-е изд. - М.: Издательский дом Вильяме , 2000. - Прим. ред.

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

Библиотека времени выполнения компилятора, используемая по умолчанию, содержит собственные средства работы с памятью, такие как оператор new в С++ или функция mall ос в С, которые работают с использованием собственных служб распределения памяти. Эти службы, предоставляемые компилятором, могут представлять собой всего лишь небольшую обертку вокруг соответствующих служб операционной системы и наследовать их свойства. Возможно и другое решение, когда система управления памятью, предоставляемая компилятором, перекрывает стратегию операционной системы, получая от нее блоки большого размера, которые затем перераспределяет в соответствии с собственной стратегией.

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

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

Все эти уровни показаны на рис. 20.1.

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

Стандартные контейнеры и распределители

Оператор new и функция malice

Ядро операционной системы

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

Таким образом, распределение памяти осуществляется различными способами и может варьироваться от операционной системы к операционной системе, от компилятора к компилятору в пределах одной операционной системы, от контейнера к контейнеру - и даже от объекта к объекту. Так, в случае использования объекта vec-tor<int> применяется стратегия, реализованная в allocator<int>, а в случае объекта vector<int, MyAllocatoo может использоваться совершенно иная стратегия выделения памяти.

> Рекомендация

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