Существуют две структуры данных, которые особенно полезны для предсказуемого выделения памяти.
• Стеки. Стек (stack) — это структура данных, в которой можно разместить любое количество данных (не превышающее максимального размера), причем удалить можно только данные, которые были размещены последними; т.е. стек может расти и уменьшаться только на вершине. Он не вызывает фрагментации памяти, поскольку между двумя его ячейками не может быть “дыр”.
• Пулы. Пул (pool) — это коллекция объектов одинаковых размеров. Мы можем
размещать объекты в пуле и удалять их из него, но не можем поместить в нем больше объектов, чем позволяет его размер. Фрагментация памяти при этом не возникает, поскольку объекты имеют одинаковые размеры.
Операции размещения и удаления объектов в стеках и пулах выполняются предсказуемо и быстро.
Таким образом, в системах с жесткими условиями реального времени и в системах, предъявляющих особые требования к обеспечению безопасности, при необходимости можно использовать стеки и пулы. Кроме того, желательно иметь возможность использовать стеки и пулы, разработанные, реализованные и протестированные независимыми поставщиками (при условии, что их спецификации соответствуют нашим требованиям).
Обратите внимание на то, что стандартные контейнеры языка С++ (
vector
,
map
и др.), а также стандартный класс
string
не могут использоваться во встроенных системах непосредственно, потому что они неявно используют оператор
new
. Для того чтобы обеспечить предсказуемость, можете создать (купить или позаимствовать) аналогичные стандартным контейнеры, но учтите, что обычные стандартные контейнеры, содержащиеся в вашей реализации языка С++, не предназначены для использования во встроенных системах.
Следует подчеркнуть, что встроенные системы обычно выдвигают очень строгие требования к надежности, поэтому, принимая решение, вы ни в коем случае не должны отказываться от нашего стиля программирования, опускаясь на уровень низкоуровневых средств. Программа, заполненная указателями, явными преобразованиями и другими подобными вещами, редко бывает правильной.
25.3.3. Пример пула
Пул — это структура данных, из которой мы можем доставать объекты заданного типа, а затем удалять их оттуда. Пул содержит максимальное количество объектов, которое задается при его создании. Используя темно-серый цвет для размещенного объекта и светло-серый для места, готового для размещения объекта, мы можем проиллюстрировать пул следующим образом.
Класс
Pool
можно определить так:
template<class T, int N>class Pool { // Пул из N объектов типа T
public:
Pool; // создаем пул из N объектов типа T
T* get; // берем объект типа T из пула;
// если свободных объектов нет,
// возвращаем 0
void free(T*); // возвращаем объект типа T, взятый
// из пула с помощью функции get
int available const; // количество свободных объектов типа T
private:
//
место для T[N] и данные, позволяющие определить, какие объекты
// извлечены из пула, а какие нет (например, список свободных
// объектов)
};
Каждый объект класса
Pool
характеризуется типом элементов и максимальным количеством объектов. Его можно использовать примерно так, как показано ниже.
Pool<Small_buffer,10> sb_pool;
Pool<Status_indicator,200> indicator_pool;
Small_buffer* p = sb_pool.get;
// ...
sb_pool.free(p);
Гарантировать, что пул никогда не исчерпается, — задача программиста. Точный смысл слова “гарантировать” зависит от приложения. В некоторых системах программист должен написать специальный код, например функцию
get
, которая никогда не будет вызываться, если объектов в пуле больше нет. В других системах программист может проверить результат работы функции
get
и сделать какие-то корректировки, если результат равен нулю. Характерным примером второго подхода является телефонная система, разработанная для одновременной обработки более 100 тыс. звонков. Для каждого звонка выделяется некий ресурс, например буфер номеронабирателя. Если система исчерпывает количество номеронабирателей (например, функция
dial_buffer_pool.get
возвращает
0
), то она запрещает создавать новые соединения (и может прервать несколько существующих соединений, для того чтобы освободить память). В этом случае потенциальный абонент может вновь попытаться установить соединение чуть позднее.
Естественно, наш шаблонный класс
Pool
представляет собой всего лишь один из вариантов общей идеи о пуле. Например, если ограничения на использование памяти не такие строгие, можем определить пулы, в которых количество элементов определяется конструктором, и даже пулы, количество элементов в которых может впоследствии изменяться, если нам потребуется больше объектов, чем было указано вначале.
25.3.4. Пример стека
Стек — это структура данных, из которой можно брать порции памяти и освобождать последнюю занятую порцию. Используя темно-серый цвет для размещенного объекта и светло-серый для места, готового для размещения объекта, мы можем проиллюстрировать пул следующим образом.
Как показано на рисунке, этот стек “растет” вправо. Стек объектов можно было бы определить как пул.
template<class T, int N> class Stack { // стек объектов типа T
// ...
};
Однако в большинстве систем необходимо выделять память для объектов разных размеров. В стеке это можно сделать, а в пуле нет, поэтому мы покажем определение стека, из которого можно брать “сырую” память для объектов, имеющих разные размеры.