и желательными 2*sizeof(Node) байтами. В действительности это маловероятно.
Представим себе простой (хотя и вполне вероятный) механизм управления памятью. Допустим также, что объект класса Message немного больше, чем объект класса Node. Эту ситуацию можно проиллюстрировать следующим образом: темно-серым цветом выделим память, занятую объектом класса Message, светло-серым — память, занятую объектами класса Node, а белым — “дыры” (т.е. неиспользуемую память).
Итак, каждый раз, проходя цикл, мы оставляем неиспользованную память (“дыру”). Эта память может составлять всего несколько байтов, но если мы не можем использовать их, то это равносильно утечке памяти, а даже малая утечка рано или поздно выводит из строя долговременные системы. Разбиение свободной памяти на многочисленные “дыры”, слишком маленькие для того, чтобы в них можно было разместить объекты, называется фрагментацией памяти (memory fragmentation). В конце концов, механизм управления свободной памятью займет все “дыры”, достаточно большие для того, чтобы разместить объекты, используемые программой, оставив только одну “дыру”, слишком маленькую и потому бесполезную. Это серьезная проблема для всех достаточно долго работающих программ, широко использующих операторы new и delete; фрагментация памяти встречается довольно часто. Она сильно увеличивает время, необходимое для выполнения оператора new, поскольку он должен выполнить поиск подходящего места для размещения объектов. Совершенно очевидно, что такое поведение для встроенной системы недопустимо. Это может также создать серьезную проблему в небрежно спроектированной невстроенной системе.
Почему ни язык, ни система не может решить эту проблему? А нельзя ли написать программу, которая вообще не создавала бы “дыр” в памяти? Сначала рассмотрим наиболее очевидное решение проблемы маленьких бесполезных “дыр” в памяти: попробуем переместить все объекты класса Node так, чтобы вся свободная память была компактной непрерывной областью, в которой можно разместить много объектов.
К сожалению, система не может этого сделать. Причина заключается в том, что код на языке С++ непосредственно ссылается на объекты, размещенные в памяти. Например, указатели n1 и n2 содержат реальные адреса ячеек памяти. Если мы переместим объекты, на которые они указывают, то эти адреса станут некорректными. Допустим, что мы (где-то) храним указатели на созданные объекты. Мы могли бы представить соответствующую часть нашей структуры данных следующим образом.
Теперь мы уплотняем память, перемещаем объекты так, чтобы неиспользуемая память стала непрерывным фрагментом.
К сожалению, переместив объекты и не обновив указатели, которые на них ссылались, мы создали путаницу. Почему же мы не обновили указатели, перемещая объекты? Мы могли бы написать такую программу, только зная детали структуры данных. В принципе система (т.е. система динамической поддержки языка С++) не знает, где хранятся указатели; иначе говоря, если у нас есть объект, то вопрос: “Какие указатели ссылаются на данный объект в данный момент?” не имеет ответа. Но даже если бы эту проблему можно было легко решить, такой подход (известный как
уплотняющая сборка мусора (compacting garbage collection)) не всегда оправдывает себя. Например, для того чтобы он хорошо работал, обычно требуется, чтобы свободной памяти было в два раза больше, чем памяти, необходимой системе для отслеживания указателей и перемещения объектов. Этой избыточной памяти во встроенной системе может не оказаться. Кроме того, от эффективного механизма уплотняющей сборки мусора трудно добиться предсказуемости.
Можно, конечно, ответить на вопрос “Где находятся указатели?” для наших структур данных и уплотнить их, но проще вообще избежать фрагментации в начале блока. В данном примере мы могли бы просто разместить оба объекта класса Node до размещения объектов класса Message.
while( ... ) {
Node* n1 = new Node;
Node* n2 = new Node;
Message* p = get_input(dev);
// ...храним информацию в узлах...
delete p;
// ...
}
Однако перестройка кода для предотвращения фрагментации в общем случае не такая простая задача. Решить ее надежно очень трудно. Часто это приводит к противоречиям с другими правилами создания хороших программ. Вследствие этого мы предпочитаем ограничивать использование свободной памяти только методами, позволяющими избежать фрагментации в начале блока. Часто предотвратить проблему проще, чем ее решить.
ПОПРОБУЙТЕ
Выполните программу, приведенную выше, и выведите на печать адреса и размеры созданных объектов, чтобы увидеть, как возникают “дыры” в памяти и возникают ли они вообще. Если у вас есть время, можете нарисовать схему памяти, подобную показанным выше, чтобы лучше представить себе, как происходит фрагментация.
25.3.2. Альтернатива универсальной свободной памяти
Итак, мы не должны провоцировать фрагментацию памяти. Что для этого необходимо сделать? Во-первых, сам по себе оператор new не может порождать фрагментацию; для того чтобы возникли “дыры”, необходим оператор delete. Следовательно, для начала запретим оператор delete. В таком случае объект, размещенный в памяти, остается там навсегда.
Если оператор delete запрещен, то оператор new становится предсказуемым; иначе говоря, все операторы new выполняются за одинаковое время? Да, это правило выполняется во всех доступных реализациях языка, но оно не гарантируется стандартом. Обычно встроенная система имеет последовательность загрузочных команд, приводящую ее в состояние готовности после включения или перезагрузки. На протяжении периода загрузки мы можем распределять память как нам угодно, вплоть до ее полного исчерпания. Итак, мы можем выполнить оператор new на этапе загрузки. В качестве альтернативы (или дополнения) можем также зарезервировать глобальную (статическую память) для использования в будущем. Из-за особенностей структуры программы глобальных данных часто лучше избегать, но иногда благоразумно использовать этот механизм для заблаговременного выделения памяти. Точные правила работы этого механизма устанавливаются стандартами программирования данной системы (см. раздел 25.6).
Существуют две структуры данных, которые особенно полезны для предсказуемого выделения памяти.
• Стеки. Стек (stack) — это структура данных, в которой можно разместить любое количество данных (не превышающее максимального размера), причем удалить можно только данные, которые были размещены последними; т.е. стек может расти и уменьшаться только на вершине. Он не вызывает фрагментации памяти, поскольку между двумя его ячейками не может быть “дыр”.
• Пулы. Пул (pool) — это коллекция объектов одинаковых размеров. Мы можем размещать объекты в пуле и удалять их из него, но не можем поместить в нем больше объектов, чем позволяет его размер. Фрагментация памяти при этом не возникает, поскольку объекты имеют одинаковые