Основы объектно-ориентированного программирования - Бертран Мейер

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

Алгоритм сжатия памяти возвращает неиспользуемые участки памяти операционной системе, работая с наименьшими временными затратами. Он разбивает память на 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.

Алгоритм параллельной сборки мусора представлен в [Dijkstra 1978]. Проблемы производительности подобных алгоритмов рассматривал [Cohen 1984]. Сборка мусора поколений представлена в [Ungar 1984].

Механизм сборки мусора ISE's среды, описанный в конце этой лекции, был создан Рафаэлем Манфреди (Raphael Manfredi) и усовершенствован Ксавьером Ле Вурч (Xavier Le Vourch) и Фабрис Францески (Fabrice Franceschi) (чей технический отчет служил основой данного здесь описания).

Упражнения

У9.1 Модели создания объектов

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

Вы можете описать эту модель как последовательность о1, о2, о3,..., где оi либо 1, (что показывает выделение памяти одному объекту), либо (-n), показывающее восстановление n единиц памяти.

У9.2 Какой уровень утилизации?

Подход на уровне компонентов, если программировать на языке типа Pascal или C, где операционная система предоставляет dispose или free, может напрямую использовать эти операции вместо создания своего списка свободной памяти для каждого типа структур данных. Рассмотрите плюсы и минусы двух подходов.

У9.3 Совместное использование стека достижимых элементов

(Это упражнение подразумевает знакомство с результатами лекции 18) Перепишите компонент available, задающий стек достижимых элементов при подходе на уровне компонентов. Единственный стек должен совместно использоваться всеми связными списками одного и того же типа. (Указание: используйте функцию once.)

У9.4 Совместное использование

(Это упражнение подразумевает, что вы выполнили предыдущее и прочитали все лекции, включая лекцию 18) Можно ли сделать available стек разделяемым всеми связными списками произвольных типов?

Лекция 10. Универсализация

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