Книга: Основы объектно-ориентированного программирования

Сборка мусора

Наиболее общей и полностью удовлетворительной техникой является лишь автоматическая сборка мусора или просто сборка мусора.

Механизм сборки мусора

Сборщик мусора (garbage collector) - это функция исполнительной системы (runtime system) языка программирования. Сборщик мусора выполняет обнаружение и утилизацию недостижимых объектов, не нуждаясь в управлении приложением, хотя приложение может иметь в своем распоряжении различные средства контроля работы сборщика.

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

Требования к сборщику мусора

Сборщик мусора, несомненно, должен быть корректным, удовлетворяя двум требованиям:

Свойства сборщика мусора

Качественность: каждый собираемый объект должен быть недостижимым.

Полнота: каждый недостижимый объект должен быть собран.

Качественность - абсолютное требование: лучше не собирать мусор, чем выбрасывать нужный объект. Нужна полная уверенность в том, что управлению памятью можно слепо доверять. Фактически надо забыть о нем почти навсегда, будучи уверенным, что кто-то как-то убирает беспорядок в вашей программе, также как кто-то как-то убирает мусор в вашем офисе, когда вас нет, но не убирает при этом ваши книги, компьютер и семейные фотографии со стола.

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

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

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

Действительная проблема лежит в структуре языка, а не в технологии компиляции или культурных традициях. Язык С++, следуя С, слабо типизирован; он предоставляет возможность преобразования типа, благодаря которой на объект одного типа можно ссылаться как на сущность другого типа. Конструкция:

(OTHER_TYPE) x

означает, что теперь x рассматривается как сущность типа OTHER_TYPE, связанного или несвязанного с истинным типом x. Хорошие книги по С++ предостерегают приложения от применения подобных конструкций. Но разработчикам компилятора деваться некуда, - они обязаны реализовать язык в соответствии с его определением. Теперь представьте следующий сценарий. Ссылка на объект какого-либо полезного типа, скажем NUCLEAR_SUBMARINE, временно приведена к типу integer. Сборщик мусора, работающий в этот момент, не видит ссылки, а видит только целое типа integer. Не находя других ссылок на объект, сборщик утилизирует подлодку. Когда, через некоторое время программа выполнит обратное преобразование целого в ссылку типа NUCLEAR_SUBMARINE, будет уже поздно, - подлодка уничтожена.

Для решения этой проблемы предлагались разные методы. Широкого применения они не получили из-за накладываемых ограничений. Язык Java может рассматриваться как язык семейства C++, в котором введены существенные ограничения на систему типов, вплоть до удаления множественного наследования и универсализации, чтобы сделать, наконец, возможной сборку мусора в мире программ, основанных на С.

При тщательно спроектированной системе типов, конечно, можно сочетать мощь множественного наследования и универсализации с безопасностью типов и поддержкой эффективной сборки мусора.

Основа сборки мусора

Рассмотрим работу сборщика мусора.

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

Как и в случае с подсчетом ссылок, объекты включают дополнительное поле, используемое здесь для пометки. Но требуемая для этого поля память незначительна, - достаточно одного бита для каждого объекта. Как будет видно при изучении динамического связывания, реализация ОО-возможностей требует, чтобы объект имел дополнительную внутреннюю информацию (например, тип). Эта информация обычно занимает одно или два слова в каждом объекте. Бит пометки может быть частью служебного слова, и не будет занимать дополнительную память.

Сборка по принципу "все-или-ничего"

Когда нужно приводить в действие сборщик мусора?

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

Эта техника может быть названа "все-или-ничего". Преимущество ее в том, что она не вызывает перегрузки пока достаточно памяти. Когда программа выходит за пределы достижимых ресурсов, в наказание вызывается сборщик мусора.

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

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

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

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

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

Конечно, временные потери должны быть не только постоянными, но и небольшими. Если приложение без сборщика мусора - заяц, никто не согласится заменить его черепахой. Хороший сборщик мусора должен обеспечивать задержку, не превышающую 5-15%. Хотя некоторые скажут, что и это неприемлемо, я знаю совсем немного приложений, которым нужны меньшие издержки. Необходимо учитывать также, что в отсутствии сборщика мусора потребуется ручная утилизация, также не обходящаяся без издержек. Несмотря на все издержки, сборка мусора необходима.

В ходе обсуждения выявлены две дополнительные проблемы эффективности работы сборщика мусора: производительность глобальная (overall performance) и в стартстопном режиме (incrementality).

Продвинутый (Advanced) подход к сборке мусора

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

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

collection_off
collection_on
collect_now

Вызов первой прекращает циклическую работу по сборке мусора до особого распоряжения; второй - включает сборщик, восстанавливая нормальное состояние работы; третьей - заставляет сборщик немедленно выполнить полный цикл работы. Пусть некоторая система содержит критический по времени выполнения раздел, в котором не должно быть никаких непредсказуемых временных задержек. В этом случае разработчик может вызвать collection_off в начале этого раздела и collection_on в его конце; в любой другой точке, где приложение работает вхолостую (например, во время ввода или вывода), можно запустить collect_now.

Более продвинутая техника, используемая в большинстве современных сборщиков мусора, известна как сборка мусора поколений (generation scavenging). Она исходит из следующего наблюдения: чем больше циклов сборки мусора объект пережил, тем больше вероятность, что он доживет до следующего цикла или всегда будет достижимым. Отсюда принцип работы сборщика мусора: "старые объекты оставляй нетронутыми". Сборщику полезна любая информация, позволяющая сканировать определенные категории объектов реже, чем остальные. Сборка мусора поколений обнаруживает объекты, существующие более чем определенное количество циклов. Такие объекты получают статус постоянной должности (tenuring) по аналогии с механизмом, защищающим экземпляры класса реальной жизни PROFESSOR, прошедших несколько циклов переизбрания и получивших, наконец, постоянную позицию. Объекты-долгожители будут рассматриваться отдельным сборщиком, работающим реже, чем сборщик "молодых" объектов.

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

Алгоритмы параллельной сборки мусора

Для получения полного решения проблемы работы в стартстопном режиме крайне привлекательно выделить сборщику мусора отдельный поток выполнения, конечно, при условии поддержки многозадачности операционной системой. Этот прием известен, как сборка мусора "на лету" (on-the fly) или параллельная.

Во время сборки мусора на лету выполнение ОО-системы использует два отдельных потока (часто соответствующих двум отдельным процессам операционной системы): приложение и сборщик. Только приложение выделяет память объектам с помощью инструкций создания; только сборщик освобождает память с помощью reclaim операций.

Сборщик будет работать непрерывно, повторяя фазу пометки и следом фазу чистки для обнаружения и удаления недостижимых объектов.

Отдельные потоки не обязательно должны быть отдельными процессами. Они могут быть, во избежание дополнительных расходов на переключение между процессами или даже потоками, плоскими сопрограммами. (Подробнее сопрограммы будут рассмотрены в лекции 12 курса "Основы объектно-ориентированного проектирования", рассматривающей "параллелизм")

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

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

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

"Какой тип аппаратного обеспечения наиболее пригоден для объектной технологии?" -

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

Оглавление книги