Об автоматическом управлении памятью

Что такое "сбор мусора"?    Об эффективности алгоритмов сбора мусора

Для знатоков старого Паскаля можно сказать, что автоматическое управление памятью ("сбор мусора") — это механизм, исключающий необходимость (и даже запрещающий) использовать оператор DISPOSE старого Паскаля: зарезервированные на куче (посредством NEW) блоки памяти будут автоматически утилизованы системой, когда на них больше не будет ни прямых, ни косвенных ссылок из программы (т.е. на практике достаточно — но не обязательно — присвавить NIL указателям, ссылающимся на данные, которые больше не нужны). Этим исключаются два больших класса весьма опасных ошибок: висячие указатели (dangling pointers) и утечки памяти (memory leaks). Если такие ошибки не приводят сразу к краху программы (segment violation и т.п.), то они могут нарушать систему безопасности вычислительной системы, или в расчетах приводить к неверным ответам, распознать которые может быть нелегко. Такие ошибки очень трудно искать в больших программах с существенно динамическими структурами данных.

Автоматическое управление памятью впервые возникло в функциональном языке Лисп (начало 60-х гг.), т.к. в такого рода языках оно является принципиальным требованиям. Затем оно стало широко использоваться и в других интерпретируемых средах. В компилируемом процедурном языке, построенном на процедурной основе, АУП впервые было реализовано в Системе Оберон Н.Вирта и Ю.Гуткнехта, и системы этого семейства — в т.ч. Компонентный Паскаль — до сих пор остаются уникальными в этом отношении.

В системах процедурного программирования старого типа (фортран, старый Паскаль, включая Турбо- и Дельфи-вариации, С, С++ ...) устроить АУП невозможно по принципиальным причинам: для его реализации необходимо распространить механизмы строгой статической типизации на указательные переменные, и в числе прочего запретить адресную арифметику (что немыслимо, скажем, в C).

С другой стороны, специалисты признают, что именно автоматическое управление памятью (а не широко обсуждаемые средства объектно-ориентированного программирования) является главной причиной резкого повышения программистской производительности при работе с такими "динамическими" языками как Java, Perl, python, и т.п., и основной технической причиной быстрого практического успеха последних. Однако для задач, в которых велик чисто вычислительный компонент, подобные интерпретируемые системы мало пригодны вследствие недостаточной эффективности.

Что такое "сбор мусора"?

Термин "сбор мусора" является метафорой, которую можно объяснить следующим образом. Предположим, что мы вычисляем сумму трех чисел 1+2+100, хранящихся в трех ячейках памяти. Предположим, что вычисления проводятся таким образом, что для результата каждой арифметической операции выделяется новая ячейка памяти. (Это необходимо, если, например, вычисления проводятся с очень большими числами, и величина результата и размер блока памяти, необходимого для его хранения, заранее неизвестен. Такая ситуация постоянно возникает, например, в символических вычислениях — как и во всех алгоритмах с "динамическими структурами данных", размер которых невозможно предсказать заранее.) Получающаяся картинка такова:

То есть сложение 1 + 2 + 100 пройдет в два шага, причем промежуточное значение 3 после вычисления окончательного результата уже нигде использовано не будет, — с точки зрения алгоритма это уже бесполезный "мусор". Нужно как-то распознать, что показанная розовым цветом ячейка могла бы быть повторно использована под другой промежуточный результат. Алгоритмы такого распознавания и называются "сбором мусора".

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

Нарастающая сложность современных алгоритмов и программ диктует необходимость использования динамических структур данных, работать с которыми невозможно без автоматического управления памятью. Более того, даже в задачах, где конечный результат может быть представлен в виде алгоритма с относительно простыми статическими структурами данных, использование механизма АУП может весьма радикально облегчить алгоритмическое экспериментирование, т.к. окончательная структура данных может быть заранее неизвестна, и поиск алгоритма превращается в пресловутую "погоню за двумя зайцами". В этом смысле свобода алгоритмического экспериментирования без необходимости заботиться об управлении памятью подобна выходу в комплексную плоскость при решении алгебраических уравнений 3-го и 4-го порядка, где при извлечении корней на промежуточных шагах могут возникнуть комплексные числа даже при чисто вещественных ответах.

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

Об эффективности алгоритмов сбора мусора

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

Во-первых, языки Оберон/Компонентный Паскаль спроектированы так, что программы, не использующие динамических структур данных, полностью нечувствительны к наличию этого механизма, т.к. он включается только при использовании псевдо-процедуры NEW (размещение массива или записи на куче), либо при явном вызове (в Блэкбоксе это процедура Services.Collect). Сам же сбор мусора встроен в систему на самом глубоком уровне, в качестве "примитива", что позволило сделать соответствующие алгоритмы простыми и эффективными.

Второй момент состоит в том, что в компилируемых процедурных языках отношение объема вычислений на каждый вызов NEW обычно гораздо больше, чем в функциональных языках типа Лисп: нередко именно из опыта работы с Лиспом и другими интерпретируемыми языками, медленными и без учета расходов на управление памятью, обычно и выводят мнение о неэффективности этого механизма. Это мнение перестает быть справедливым для программ на Обероне/Компонентном Паскале, где накладные расходы на сбор мусора редко становятся существенными.

Проблемы могут возникнуть в двух случаях.
Во-первых, когда размер виртуальной памяти, используемой Блэкбоксом с нашими программами, становится слишком велик, и операционная система начинает выгружать страницы виртуальной памяти из физической на диск (swapping). В этом случае следует чаще форсировать в программе сбор мусора, чтобы предотвратить рост кучи за пределы некоторого приемлемого минимума.
Во-вторых, это задачи "реального времени", где необходимо добиться гарантированного времени реакции вычислительной системы на внешние сигналы. Здесь неконтролируемое включение механизма сбора мусора нежелательно. Но эта область приложений весьма специфична и требует особого внимания и особых методов.