Теория и практика Java: Краткая история развития технологии утилизации памяти

Как работает технология утилизации памяти?

Java, возможно, и является самым распространённым языком программирования, основанным на технологии утилизации памяти, но ни в коем случае не первым. Утилизация памяти была неотъемлемой частью многих языков программирования, включая Lisp, Smalltalk, Eiffel, Haskell, ML, Scheme и Modula-3 и используется с начала 1960-х годов. В этом выпуске Теория и практика Java Брайан Гетц описывает самые распространенные методы сборки мусора. В ближайшие несколько месяцев он рассмотрит стратегии сборки мусора, используемые виртуальной машиной Java 1.4, влияние различных стратегий сборки мусора на производительность, а также то, как способствовать (а равно и как помешать) сборщику мусора в достижении наивысшей производительности.

Брайан Гетц, главный консультант, Quiotix

Брайан Гетц (Brian Goetz) - консультант по ПО и последние 15 лет работал профессиональными разработчиком ПО. Сейчас он является главным консультантом в фирме Quiotix, занимающейся разработкой ПО и консалтингом и находящейся в Лос-Альтос, Калифорния. Следите за публикациями Брайана в популярных промышленных изданиях. Вы можете связаться с Брайаном по адресу brian@quiotix.com



02.03.2007

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

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

Возможности и варианты выбора

Версия 1.3 инструментального пакета JDK включает три разных стратегии сборки мусора; версия 1.4.1 JDK включает их шесть и более дюжины параметров командной строки для конфигурации и тонкой настройки сборки мусора. Как они различаются? Почему их нужно так много?

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


Как же работает сборка мусора?

Существует несколько основных стратегий для сборки мусора: подсчет ссылок, маркирование-зачистка, маркирование-сжатие и копирование. Кроме того, некоторые алгоритмы могут делать свою работу по шагам (всю динамическую память не нужно обрабатывать сразу, что приводит к более коротким паузам на сбор мусора), а некоторые могут быть запущены, во время выполнения пользовательской программы (одновременные сборщики). Иные должны производить всю сборку сразу, в то время как пользовательская программа временно приостановлена (так называемые отключающие сборщики). И, наконец, существуют гибридные сборщики такие как сборщик по поколениям, который используется в пакете JDK 1.2 и последующих. Здесь используются различные алгоритмы сборки мусора на различных участках динамической памяти.

При оценке алгоритма сборки мусора мы можем руководствоваться любым или всеми из перечисленных ниже критериев:

  • Время пауз. Останавливает ли сборщик мусора работу приложения для сборки мусора? На какое время? Могут ли паузы быть ограничены по времени?
  • Предсказуемость пауз. Можно ли запланировать паузы для сборки мусора таким образом, чтобы это было удобно для пользовательской программы, а не для сборщика мусора?
  • Потребление ресурсов процессора. Какой процент всего доступного времени ЦП тратится на сборку мусора?
  • Отпечаток памяти. Многие алгоритмы сбора мусора требуют разделить динамическую память на отдельные области, некоторые из которых могут быть недоступны пользовательской программе в определённые периоды времени. Это значит, что реальный размер динамической памяти может быть в несколько раз больше, чем максимальная часть динамической памяти, занимаемая пользовательской программой.
  • Взаимодействие с виртуальной памятью. В системах с ограниченной физической памятью полная сборка мусора может вызывать страничные ошибки и подгружать нерезидентные страницы в память, чтобы проверить их в процессе сборки мусора. Так как затраты на страничную ошибку, желательно, чтобы сборщик мусора должным образом отслеживал локальность ссылок.
  • Взаимодействие с кэш-памятью. Даже в системах, в которых вся динамическая память целиком может поместиться в основной памяти, что верно практически для всех приложений Java, сборка мусора будет часто давать эффект удаления из кэша данных, используемых пользовательской программой, вызывая потери производительности для пользовательской программы.
  • Влияние на локальность программы. В то время, как некоторые считают, что работа сборщика мусора заключается только в регенерации недоступной памяти, другие уверены, что сборка мусора должна стараться улучшить локальность ссылок пользовательской программы. Сжимая и копируя, сборщики перемещают объекты во время сборки, что потенциально может улучшить локализацию.
  • Влияние на шаге компиляции и выполнения. Некоторые алгоритмы сборки мусора требуют существенной поддержки со стороны компилятора и среды выполнения, такого как обновление подсчета ссылок всякий раз, когда происходит присвоение значения указателю. Это создает как работу для компилятора, который должен генерировать эти подсчитывающие инструкции, так и дополнительную избыточность для среды выполнения, которая должна эти дополнительные инструкции исполнять. Как эти требования влияют на производительность? Вмешиваются ли они в оптимизацию, выполненную во время компиляции?

Независимо от выбранного алгоритма динамика развития технических и программных средств сделала утилизацию мусора гораздо более удобной. Экспериментальные исследования в 70-ых и 80-ых годах показали, что сбор мусора занимает от 25 до 40 процентов рабочего времени в больших программах, написанных на языке Лисп. Хотя сборка мусора пока не стала совершенно невидимой, она прошла долгий путь развития.


Основные алгоритмы

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

Подсчёт ссылок

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

Многие библиотечные классы ANSI C++, как например string, используют подсчёт ссылок, чтобы обеспечить появление сборки мусора. Перезагружая оператор присваивания и используя детерминированное завершение процедур, которое установлено областями действия в языке C++, программы на C++ могут использовать класс string так, будто он был собран в мусор. Подсчёт ссылок прост, хорошо позволяет проводить пошаговый сбор мусора и поддерживать хорошую локальность ссылок, но он редко используется в серийных сборщиках мусора по нескольким причинам, как то неспособность восстанавливать недоступные циклические структуры (объекты, которые прямо или косвенно ссылаются друг на друга, как циклически связанный список или древовидная схема, которая содержит обратные ссылки на родительский узел).

Трассирующие сборщики мусора

Ни один из стандартных сборщиков мусора в инструментальном пакете JDK не использует подсчёт ссылок; вместо этого используется одна из форм трассирующего сборщика. Трассирующий сборщик останавливает приложение (хоть это и не нужно на весь период сборки мусора) и начинают трассировать объекты, начиная с корневого набора, и проходят по всем ссылкам, пока все доступные объекты не будут проверены. Корни могут быть найдены в регистрах программ, в локальных (стековых) переменных, в стеке каждого из потоков и в статических переменных.

Маркирующе-зачищающие сборщики мусора

Наиболее простая форма трассирующего сборщика мусора, впервые предложенная создателем языка Lisp Джоном Маккарти в 1960г., - это маркирующе-зачищающий сборщик, в котором среда выполнения останавливается, и сборщик посещает каждый живой узел, начиная с корней, и маркирует каждый посещённый узел. Когда не существует больше не отслеженных ссылок, сборка мусора завершена, и затем динамическая память зачищается (то есть каждый объект динамической памяти проверяется), а любой непомеченный объект регенерируется как мусор и возвращается в список свободной памяти. Рисунок 1 иллюстрирует, как выглядит динамическая память до сборки мусора. Закрашенные блоки являются мусором, потому что они недоступны пользовательской программе:

Рисунок 1. Доступные и недоступные объекты
Доступные и недоступные объекты

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

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

Копирующие сборщики мусора

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

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

Уплотнение динамической памяти

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

Листинг 1. Беззатратное распределение ячеек памяти при работе копирующего сборщика мусора
void *malloc(int n) { 
    if (heapTop - heapStart < n)
        doGarbageCollection();

    void *wasStart = heapStart;
    heapStart += n;
    return wasStart;
}

Разработчики, которые использовали сложные схемы управления памятью для языков, не использующих сборщики мусора, могли бы сильно удивиться тому, насколько незатратным может быть распределение памяти - простое добавление ссылки - в копирующем сборщике мусора. Это может быть одной из причин распространённого мнения, что распределение объектов связанно с затратами, в более ранних версиях виртуальной машины Java не использовались копирующие сборщики мусора, и разработчики все еще подспудно считают, что затраты на распределение такие же, как в других языках, типа C, тогда как на самом деле они могут быть значительно меньше в исполняемой среде Java. Но не только издержки на распределение памяти меньше, но также для объектов, которые превратились в мусор до начала следующего цикла сборки, затраты на освобождение памяти равны нулю, так как утилизируемый объект не будет ни проверяться, ни копироваться.

Маркирующе-сжимающие сборщики мусора

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


Итак, какой выбрать?

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

Сборка мусора по поколениям оказалась очень эффективной, хотя она потребовала несколько дополнительных требований по регистрации в среде выполнения. В выпуске Теории и практики Java, который выйдет в следующем месяце, мы рассмотрим, как сборка мусора по поколениям работает и как она используется виртуальной машиной 1.4.1 JVM. Кроме того, остановимся на том, какие еще возможности по сборке мусора предлагает JVM 1.4.1. В выпуске, который следует за этим, мы проанализируем, как влияет сборка мусора на работу системы, в том числе попытаемся развенчать несколько мифов, связанных с управлением памятью.

Ресурсы

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=199687
ArticleTitle=Теория и практика Java: Краткая история развития технологии утилизации памяти
publish-date=03022007