Механизм сборки мусора
Приведем схему алгоритма, используемого сборщиком мусора.
Решение представляет собой не единственный алгоритм, а основано на комбинации основных алгоритмов, часть из которых используется совместно, часть - независимо друг от друга. Каждая активизация сборщика выбирает алгоритм или сочетание алгоритмов, основанных на критерии запроса необходимой памяти. Основные алгоритмы включают: сборку мусора поколений, пометку-чистку и сжатие памяти, плюс несколько других, в меньшей степени относящихся к данному обсуждению.
Идея сборки мусора поколений описана в этой лекции ранее: следует сосредоточиться на молодых объектах, - именно они с большой вероятностью могут быть недостижимыми, и собраны мусорщиком. Основное преимущество этого алгоритма в том, что он просматривает не все объекты, а только те, которые могут быть достижимы из локальных сущностей и из старых объектов, содержащих ссылки на молодые объекты. Всякий раз по завершению обработки поколения все выжившие объекты становятся старше; когда они достигают определенного возраста, они переходят на постоянную должность в другое поколение. Алгоритм ищет компромисс, устанавливающий границу переходного возраста. Ее снижение приводит к росту старых объектов, увеличение - к частой сборке мусора.
Алгоритм время от времени нуждается в выполнении полной пометки-сборки для поиска любых недостижимых объектов, пропущенных сборщиком поколений. Пометка-сборка состоит из двух шагов: пометка - рекурсивный обход и пометка достижимых объектов; чистка - полный обход памяти и сборка непомеченных объектов.
Алгоритм сжатия памяти возвращает неиспользуемые участки памяти операционной системе, работая с наименьшими временными затратами. Он разбивает память на n блоков и за n-1 циклов сжимает их.
Повышенное чувство голода и потеря аппетита (Bulimia and anorexia)
Алгоритм сжатия предохраняет от частых, дорогих по времени вызовов операционной системы - выделить или возвратить память. Вместо возвращения всех освобожденных блоков он сохраняет некоторые из них для построения небольшого резерва памяти, доступной приложению без обращения к операционной системе.
Эта техника крайне полезна для часто встречающегося класса приложений с повышенным чувством голода и потерей аппетита, у которых период кутежа с массовым созданием объектов сменяется постом, в течение которого происходит избавление от ненужных объектов; затем все повторяется.
Операции сборщика мусора
Сборщик мусора включается одной из двух требующих память операций: инструкцией создания ( create x ) или клонирования. Сборщик запускается не только, когда программе не хватает памяти: механизм может активизироваться, когда он определяет некоторые условия, за которыми последует нехватка памяти.
Если первичная память заполнена, сборщик начнет сборку мусора поколений. В большинстве случаев освободится достаточно памяти для текущих нужд. Если этого не произошло, следующий шаг - полный цикл пометки-чистки с последующим сжатием памяти. Если и в этом случае памяти не достаточно, сборщик запросит память у операционной системы.
Основные алгоритмы являются стартстопными; их время выполнения обычно составляет несколько процентов от времени выполнения приложения. Внутренняя статистика ведет учет занятой памяти и помогает определить подходящий для вызова алгоритм.
Можно настроить работу сборщика, задавая различные параметры, в частности, включение параметра speed заставит алгоритм не собирать всю доступную память с помощью механизма сжатия, а сразу использовать возможности операционной системы. Устанавливая другие параметры, можно включать механизмы: collection_off, collect_now и dispose из класса MEMORY.
Механизм управления памятью, построенный на основе всех этих методов, сделал возможным разработку и выполнение больших приложений, создающих много объектов, создающих их быстро, не заботясь об используемой памяти, поручая кому-то другому заботу о последствиях.
Ключевые концепции
[x]. Существует три основных режима создания объектов: статический, основанный на стеке, динамический. Последний характерен для ОО-языков, но встречается везде, например, в Lisp, Pascal (указатели и new), C (malloc), Ada (типы доступа).
[x]. В программах, создающих много объектов, объекты могут становиться недостижимыми. Их память теряется, приводя, в худших случаях, к сбою из-за нехватки памяти, при том что часть памяти остается неиспользованной.
[x]. Эту проблему можно игнорировать в тех случаях, когда программа почти не создает недостижимых объектов или создает всего лишь несколько объектов, общий размер которых сравним с доступной памятью.
[x]. Во всех других случаях (динамические структуры данных, ограниченные ресурсы памяти) любое решение проблемы включает два компонента: обнаружение мертвых объектов и восстановление занятой ими памяти.
[x]. Каждая из задач может быть решена на одном из трех уровней: реализации языка, разработки компонентов, приложения.
[x]. Вменять в обязанность приложения обнаружение мертвых объектов и восстановление памяти - опасно и обременительно. Эта проблема должна решаться на уровне языка.
[x]. В некоторых специальных случаях можно управлять памятью на уровне компонентов. Обнаружение выполняется компонентами, восстановление памяти - компонентами, либо средствами, реализованными на уровне языка.
[x]. Подсчет ссылок не работает для циклических структур.
[x]. Общеприменимой техникой решения проблемы является сборка мусора. Ее накладные издержки приемлемо малы в нормальных ситуациях и, благодаря алгоритмам, работающим в стартстопном режиме, невидимы в нормальных интерактивных приложениях.
[x]. Сборка мусора поколений увеличивает эффективность алгоритма, используя тот факт, что недостижимыми становятся, в первую очередь, новые объекты.
[x]. Хороший механизм управления памятью должен возвращать неиспользуемую память не только текущему приложению, но и операционной системе.
[x]. Описанная схема реальной системы управления памятью предлагает комбинацию алгоритмов и способов, позволяющих разработчикам приложений производить настройку механизмов системы, в том числе позволяя включать и отключать сборку мусора в критических разделах приложения.
Библиографические заметки
Различные модели создания объектов, обсуждаемые в начале этой лекции, поддерживаются "контурной моделью" выполнения языка программирования, которая может быть найдена в [Johnston 1971].
Информация о фиаско Лондонской службы скорой помощи получена из множества сообщений, присланных на форум Risks.