Ответ 1
Немного терминологии:
Позвольте мне дать несколько имен, чтобы объяснения были более ясными.
Переменная - это любой слот для данных, который может содержать указатель и может меняться со временем. Это включает в себя глобальные переменные, локальные переменные, регистры CPU и поля в выделенных объектах.
В трехкратном инкрементальном или параллельном GC существует три типа переменных:
- истинные корни, которые всегда доступны (регистры процессора, глобальные переменные);
- быстрые переменные, которые сканируются в режиме "stop-the-world";
- медленные переменные, которые обрабатываются цветами. Медленными переменными являются поля в цветных объектах.
"Истинные корни" и "быстрые переменные" будут в дальнейшем называться корнями.
Потоки приложений называются мутаторами, потому что они изменяют содержимое переменных.
С инкрементным или параллельным GC, паузы GC происходят регулярно. Мир остановлен (мутаторы приостановлены), и корни сканируются. Это сканирование показывает ряд ссылок на цветные объекты. Соответственно корректируются цвета объектов (такие белые объекты сделаны серыми).
Когда GC является инкрементальным, происходит некоторая активность сканирования объекта: некоторые серые объекты сканируются (и окрашиваются в черный цвет), посылая ссылки на белые объекты. Эта деятельность ( "маркировка" ) сохраняется в течение некоторого времени, но не обязательно, пока существуют серые объекты. В какой-то момент маркировка прекращается, и мир пробуждается. GC называется "инкрементальным", потому что цикл GC выполняется небольшими приращениями, чередующимися с активностью мутатора.
В параллельном GC сканирование серых объектов происходит одновременно с активностью мутатора. Затем мир пробуждается, как только сканируются корни. При одновременном использовании ГК барьеры доступа являются сложным комплексом для реализации, поскольку они должны обрабатывать параллельный доступ из потока GC; но на концептуальном уровне это не сильно отличается от инкрементного GC. Параллельный GC можно рассматривать как оптимизацию по сравнению с инкрементным GC, который использует преимущества нескольких процессорных ядер (параллельный GC имеет небольшое преимущество перед инкрементным GC, когда есть только одно ядро).
Корни не должны быть защищены барьером доступа, поскольку они сканируются с остановленным миром. Фаза метки GC заканчивается, когда выполняются следующие условия:
- только что сканированные корни;
- все объекты либо черные, либо белые, но не серые.
поэтому эта ситуация может возникнуть только во время паузы. В этот момент начинается этап развертки, в течение которого белые объекты высвобождаются. Прокрутка может выполняться постепенно или одновременно; объекты, созданные во время развертки, сразу окрашиваются в черный цвет. Когда развертка закончена, может произойти новая фаза метки GC: объекты (все черные в этой точке) перекрашены в белый цвет (это делается атомарно, просто изменяя способ интерпретации цветовых битов).
Переменная классификация:
С учетом сказанного я теперь могу ответить на ваш вопрос. С приведенным выше описанием возникает вопрос: каковы корни? Это фактически до реализации; существует несколько возможностей и компромиссов.
Истинные корни всегда должны проверяться; истинными корнями являются содержимое регистра CPU и глобальные переменные. Обратите внимание, что стеки не являются истинными корнями; только текущий указатель фрейма стека.
Поскольку быстрые переменные доступны без барьеров, принято устанавливать быстрые переменные стека (т.е. корни). Это связано с тем, что в то время как записи доступа являются редкими общесистемными, они довольно распространены в локальных переменных. Было измерено (в некоторых программах Lisp), что около 99% записей (значения указателя) имеют локальную переменную в качестве цели.
Быстрые переменные часто расширяются еще дальше, в случае генерации GC: "молодое поколение" состоит в специальной области выделения для новых объектов, ограниченной по длине и проверенной как быстрые переменные. Яркой стороной быстрых переменных является быстрый доступ (отсюда и название); недостатком является то, что все эти быстрые переменные могут сканироваться только во время паузы (мир остановлен). Существует компромисс по размеру быстрых переменных, что часто приводит к ограничению размера молодого поколения. Более молодое поколение способствует повышению средней производительности (за счет сокращения числа барьеров доступа) за счет более длительных пауз.
С другой стороны, у вас может не быть быстрой переменной вообще, и нет корня, кроме истинных корней. Фреймы стека затем обрабатываются как объекты, каждый со своим цветом. Затем паузы минимальны (простой снимок десятка регистров), но барьеры должны использоваться даже для доступа к локальным переменным. Это дорого, но имеет некоторые преимущества:
- Возможны жесткие гарантии времени паузы. Это сложно, если фреймы стека являются корнями, потому что каждый новый поток имеет свой собственный стек, поэтому общий размер корней может вырасти до произвольных сумм по мере запуска новых потоков. Если только регистры CPU и глобальные переменные (не более нескольких десятков в типичных случаях и их число известно во время компиляции), являются корнями, тогда паузы могут быть очень короткими.
- Это позволяет динамически распределять фреймы стека в куче. Это необходимо, если вы играете с совместными подпрограммами и продолжениями, как с примитивом Scheme
call/cc. В таком случае фреймы больше не обрабатываются как чистый "стек". Правильная обработка продолжений на языке, ориентированном на GC, в основном требует, чтобы функциональные кадры были распределены динамически.
Можно создать фреймы стека без полномочий root, сохранив при этом молодое поколение как root. Гарантии в периоды паузы все еще можно сделать (в зависимости от размера молодого поколения, который исправлен), и некоторые приемы могут быть применены, чтобы убедиться, что кадры стека находятся в молодом поколении, когда их функция активна. Это может обеспечить безбарьерный доступ к локальным переменным. Ничто из этого не является действительно бесплатным, но его можно сделать достаточно эффективным для большинства целей.
Другой концептуальный вид:
Другим способом просмотра корневой обработки является следующее: корни - это переменные, для которых правило tricolor (без указателя "черный-белый" ) не поддерживается постоянно; эти переменные допускаются к мутации без ограничений. Но их нужно возвращать в линию регулярно, останавливая мир и просматривая их.
На практике мутаторы участвуют в гонках с GC. Мутаторы создают новые объекты и указывают на них; каждая пауза создает новые серые объекты. В параллельном или инкрементальном GC, если вы позволите мутаторам играть с корнями слишком долго, тогда каждая пауза может создать большую партию новых серых объектов. В худшем случае GC не может сканировать объекты достаточно быстро, чтобы не отставать от скорости создания серого объекта. Это проблема, потому что белые объекты могут быть выпущены только во время фазы развертки, которая достигается только в том случае, если в какой-то момент GC может завершить свою маркировку. Обычной стратегией реализации инкрементного GC является сканирование серых объектов во время каждой паузы на общий размер, который пропорционален общему размеру корней. Таким образом, время паузы остается ограниченным общим размером корней, и если коэффициент пропорциональности хорошо сбалансирован, то можно гарантировать, что GC в конечном итоге закончится, будет отмечать фазу и войти в фазу подметания.
В параллельном GC все немного сложнее, потому что мутаторы свободно перемещаются в дикой природе. Возможная реализация сделает немного инкрементной маркировки, пока мир все равно остановится.
Библиография:
Сбор мусора: алгоритмы автоматического управления динамической памятью: обязательная книга по сборке мусора.