Tri-Color Incremental Updating GC: Необходимо ли сканировать каждый стек дважды?

Позвольте мне дать вам краткое введение в трехцветный GC (если кто-то прочитает его, который никогда не слышал об этом); если вам все равно, пропустите его и перейдите к проблеме.

Как работает Tri-Color GC

В трехцветном GC объект имеет один из трех возможных цветов; белый, серый и черный. Трехцветный GC можно описать следующим образом:

Все объекты изначально белые.
Все объекты достижимы, потому что глобальная переменная или переменная стека ссылаются на нее ( "корневые объекты" ) окрашены в серый цвет.
Мы берем любой серый объект, находим все ссылки на белые объекты и окрашиваем эти белые объекты в серый цвет. Затем мы окрашиваем сам объект в черный цвет.
Мы продолжаем на шаге 3, пока у нас есть серые объекты.
Если у нас нет серых объектов, все остальные объекты либо белые, либо черные.
Все черные объекты, как оказалось, были доступны и должны оставаться в живых. Все белые объекты недоступны и могут быть удалены.

Пока это не слишком сложно... по крайней мере, если GC - это StW (Stop the World), то есть он приостанавливает все потоки при сборе мусора. Если он является параллельным, трехцветный GC имеет инвариант, который должен всегда оставаться истинным:

Черный объект не должен ссылаться на белый объект!

Это выполняется автоматически для StW GC, так как каждый объект, который окрашен в черный цвет, был рассмотрен ранее, и все белые объекты, на которые он указывал, были окрашены в серый цвет, поэтому черный объект может ссылаться только на другие черные объекты или серые объекты.

Если потоки не приостановлены, потоки могут выполнять код, который нарушит этот инвариант. Существует несколько способов предотвратить это:

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

Поскольку обращения к чтению гораздо более распространены, чем записи с доступом к записи, хотя вторая возможность включает в себя большее время обработки при ударе барьера, она называется реже и такая привилегированная. GC, работающий подобным образом, называется "инкрементным обновлением GC".

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

Я имею в виду здесь инкрементное обновление GC, которое использует вариант 2: всякий раз, когда код пытается сделать черный объект указывать на белый объект, он сразу же окрашивает объект в серый цвет. Таким образом, этот объект не будет пропущен в цикле сбора.

Проблема

Так много о трехцветных GC. Но есть одна вещь, которую я не понимаю о трехцветных GC. Предположим, что у нас есть объект A, на который ссылается стек, и сам относится к объекту B.

stack -> A.ref -> B

Теперь GC запускает цикл, останавливает поток, просматривает стек и видит A как доступный напрямую, окрашивая серый. Как только это будет сделано при сканировании всего стека, он снова отключит поток и начнет обработку на шаге (3). Прежде чем он начнет что-либо делать, он выгружается (может случиться), и поток снова запускается и выполняет следующий код:

localRef = A.ref; // localRef points to B
A.ref = NULL;     // Now only the stack points to B
sleep(10000);     // Sleep for the whole GC cycle

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

Вопрос

Правильно ли, что трехцветный GC должен дважды проверять стек каждого потока? Как только в самом начале, чтобы идентифицировать корневые объекты (получая цвет серый) и снова, перед удалением белых объектов, поскольку на них может ссылаться стек, хотя ни один другой объект не ссылается на них больше. Нет описания алгоритма, который я видел до сих пор, упоминал о сканировании стека дважды. Они все только говорили, что при одновременном использовании важно, чтобы инвариант был применен во все времена, иначе достижимые объекты пропущены. Но, насколько я вижу, этого недостаточно. Стек должен рассматриваться как один большой объект, и как только он сканируется, "стек черный", и каждое обновление ref для стека должно вызвать цвет серого объекта.

Если это действительно так, использование инкрементного обновления может быть более сложным, чем я изначально думал и имеет некоторые недостатки в производительности, так как изменения в стеке являются наиболее частыми.

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

Библиография:

Сбор мусора: алгоритмы автоматического управления динамической памятью: обязательная книга по сборке мусора.

Ответ 2

Томас, очевидно, имеет лучший ответ. Тем не менее, я просто собираюсь добавить здесь небольшую заметку.

Корневые узлы можно концептуально рассматривать как черные узлы, потому что любой объект, на который ссылается корень node, должен быть серым или черным.

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