Программирование

Каждый раз, выполняя этот цикл, мы создаем два объекта класса Node, причем в процессе их создания возникает и удаляется объект класса Message. Такой фрагмент кода вполне типичен для структур данных, используемых для ввода данных, поступающих от какого-то устройства. Глядя на этот код, можно предположить, что каждый раз при выполнении цикла мы тратим 2*sizeof(Node) байтов памяти (плюс расходы свободной памяти). К сожалению, нет никаких гарантий, что наши затраты памяти ограничатся ожидаемыми и желательными 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;

  // ...

}