Немного терминологии:
Позвольте мне дать несколько имен, чтобы объяснения были понятнее.
A переменная - это любой слот для данных, который может содержать указатель и со временем меняться. Это включает в себя глобальные переменные, локальные переменные, регистры процессора и поля в выделенных объектах.
В трехцветном инкрементном или параллельном GC существует три типа переменных:
- истинные корни , которые всегда доступны (регистры ЦП, глобальные переменные);
- быстрые переменные , которые сканируются способом остановки мира;
- медленные переменные , которые обрабатываются цветами. Медленные переменные - это поля в цветных объектах.
«Истинные корни» и «быстрые переменные» далее будут вместе называться корнями .
Потоки приложения называются мутаторами , потому что они изменяют содержимое переменных.
При инкрементном или одновременном GC паузы GC происходят регулярно. Мир остановлен (мутаторы приостановлены), а корни отсканированы. Это сканирование показывает ряд ссылок на цветные объекты. Цвета объекта корректируются соответствующим образом (такие белые объекты сделаны серыми).
Когда ГХ имеет значение с шагом , происходит некоторое сканирование объекта: некоторые серые объекты сканируются (и окрашиваются в черный цвет), и серые объекты упоминаются как белые. Эта деятельность («маркировка») сохраняется в течение некоторого времени, но не обязательно, пока есть серые объекты. В какой-то момент маркировка останавливается, и мир пробуждается. GC называется «инкрементным», потому что цикл GC выполняется с небольшими приращениями, чередующимися с мутаторной активностью.
В одновременном GC сканирование серых объектов происходит одновременно с мутаторной активностью. Мир тогда пробуждается, как только корни были отсканированы. При параллельном GC барьеры доступа являются сложным для реализации, поскольку они должны обрабатывать параллельный доступ из потока GC; но на концептуальном уровне это не очень отличается от инкрементального GC. Параллельный GC можно рассматривать как оптимизацию по сравнению с инкрементным GC, в котором используется наличие нескольких ядер ЦП (параллельный GC имеет небольшое преимущество по сравнению с инкрементным GC, когда имеется только одно ядро).
Корни не должны быть защищены барьером доступа, так как они сканируются с остановленным миром. Фаза GC mark заканчивается, когда одновременно выполняются следующие условия:
- корни только что отсканированы;
- все объекты черного или белого цвета, но не серые.
поэтому такая ситуация может возникнуть только во время паузы. В этот момент начинается фаза развертки, во время которой белые объекты высвобождаются. Развертка может выполняться постепенно или одновременно; объекты, созданные во время развертки, немедленно окрашиваются в черный цвет. Когда развертка завершена, может наступить новая фаза метки GC: все объекты (которые в этот момент все черные) перекрашиваются в белый цвет (это делается атомарно, просто изменяя способ интерпретации цветовых битов).
Переменная классификация:
С учетом сказанного, теперь я могу ответить на ваш вопрос. С приведенным выше описанием возникает вопрос: каковы корни? Это на самом деле до реализации; Есть несколько возможностей и компромиссов.
Истинные корни всегда должны быть отсканированы; Истинные корни - это содержимое регистра ЦП и глобальные переменные. Обратите внимание, что стеки не истинные корни; только текущий указатель фрейма стека.
Поскольку к быстрым переменным обращаются без барьеров, принято делать фреймы стека быстрыми переменными (то есть также корнями). Это связано с тем, что, хотя доступ для записи является редким для всей системы, он довольно часто встречается в локальных переменных. Было измерено (в некоторых программах на Лиспе), что около 99% записей (от значения указателя) имеют локальную переменную в качестве цели.
Быстрые переменные часто расширяются еще больше, в случае GC поколения: «молодое поколение» состоит в специальной области выделения для новых объектов, ограниченной по длине и сканируемой как быстрые переменные.Яркой стороной быстрых переменных является быстрый доступ (отсюда и название);Недостатком является то, что все эти быстрые переменные можно сканировать только во время паузы (мир остановлен).Существует компромисс между размером быстрых переменных, который часто приводит к ограничению размера молодого поколения.Подрастающее молодое поколение повышает среднюю производительность (сокращая количество барьеров доступа) за счет более длительных пауз.
С другой стороны, у вас может не быть быстрой переменной вообще, и нет корня, а есть истинные корни,Кадры стека затем обрабатываются как объекты, каждый из которых имеет свой собственный цвет.Паузы тогда минимальны (простой снимок дюжины регистров), но барьеры должны использоваться даже для доступа к локальным переменным.Это дорого, но имеет некоторые преимущества:
- Могут быть сделаны жесткие гарантии на время паузы.Это сложно, если кадры стека являются корнями, потому что каждый новый поток имеет свой собственный стек, поэтому общий размер корней может возрасти до произвольной величины при запуске новых потоков.Если корнями являются только регистры ЦП и глобальные переменные (не более нескольких десятков в типичных случаях, и их число известно во время компиляции), то паузы могут быть очень короткими.
- Это позволяет динамически распределятьскладывать кадры в кучу.Это необходимо, если вы играете с сопрограммами и продолжениями, как примитив
call/cc Схемы.В таком случае кадры больше не обрабатываются как чистый «стек».Для правильной обработки продолжений в языке, поддерживающем GC, требуется, чтобы функциональные кадры выделялись динамически.
Можно сделать стековые кадры некорневыми, сохранив молодое поколение в качестве корневого.Гарантии времени паузы все еще могут быть сделаны (в зависимости от размера молодого поколения, который фиксирован), и некоторые хитрости могут быть применены, чтобы убедиться, что кадры стека находятся в молодом поколении, когда их функция активна.Это может обеспечить беспрепятственный доступ к локальным переменным.Ничто из этого на самом деле не является бесплатным, но его можно сделать достаточно эффективным для большинства целей.
Другой концептуальный обзор:
Другой способ просмотра обработки корня заключается в следующем: корни - это переменные, для которых правило триколора (без черно-белого указателя) не поддерживается постоянно;эти переменные могут быть изменены без ограничений.Но их нужно регулярно приводить в порядок, останавливая мир и сканируя их.
На практике мутаторы участвуют в гонках с GC.Мутаторы создают новые объекты и указывают на них;каждая пауза создает новые серые объекты.В параллельном или инкрементальном GC, если вы позволите мутаторам слишком долго играть с корнями, то каждая пауза может создавать большую партию новых серых объектов.В худшем случае ГХ не может сканировать объекты достаточно быстро, чтобы не отставать от скорости создания серых объектов.Это проблема, потому что белые объекты могут быть освобождены только во время фазы развертки, которая достигается только в том случае, если в какой-то момент ГХ может завершить свою маркировку.Обычная стратегия реализации для инкрементального GC состоит в том, чтобы сканировать серые объекты, во время каждой паузы, на общий размер, который пропорционален общему размеру корней.Таким образом, время паузы остается ограниченным общим размером корней, и если коэффициент пропорциональности хорошо сбалансирован, то можно гарантировать, что GC в конечном итоге прекратит помечать фазу и войдет в фазу подметания.
В параллельном GCвсе немного сложнее, потому что мутаторы свободно бродят в дикой природе.Возможная реализация могла бы сделать небольшую добавочную разметку, пока мир все еще остановлен.
Библиография:
Сборка мусора: алгоритмы для автоматического динамического управления памятью: обязательная к прочтению книга по сбору мусора.