Трехцветное инкрементальное обновление GC: нужно ли сканировать каждый стек дважды?

Question

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

Как работает трехцветный GC

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

1. Все объекты изначально белые.

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

3. Мы берем любой серый объект, находим все ссылки на белые объекты и окрашиваем эти белые объекты в серый цвет. Затем мы окрашиваем сам объект в черный цвет.

4. Мы продолжаем на шаге 3, пока у нас есть серые объекты.

5. Если у нас больше нет серых объектов, все оставшиеся объекты будут белыми или черными.

6. Доказано, что все черные объекты достижимы и должны остаться в живых. Все белые объекты недоступны и могут быть удалены.

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

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

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

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

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

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

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

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

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

Эта проблема

Так много о трехцветных 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, поэтому это не мусор.

Вопрос

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

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

Answer 1

Немного терминологии:

Позвольте мне дать несколько имен, чтобы пояснения были понятнее.

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

В трехцветном инкрементном или параллельном GC существует три типа переменных:

• истинные корни, которые всегда доступны (регистры процессора, глобальные переменные);
• быстрые переменные, которые сканируются способом остановки мира;
• медленные переменные, которые обрабатываются с цветами. Медленные переменные - это поля в цветных объектах.

"Истинные корни" и "быстрые переменные" в дальнейшем будут все вместе называться корнями.

Потоки приложения называются мутаторами, потому что они изменяют содержимое переменных.

При инкрементном или одновременном GC паузы GC происходят регулярно. Мир остановлен (мутаторы приостановлены), а корни отсканированы. Это сканирование показывает ряд ссылок на цветные объекты. Цвета объекта корректируются соответствующим образом (такие белые объекты сделаны серыми).

Когда GC является инкрементным, происходит некоторое сканирование объекта: некоторые серые объекты сканируются (и закрашиваются черным цветом) с серыми объектами, на которые имеются ссылки. Эта активность ("маркировка") сохраняется в течение некоторого времени, но не обязательно, пока есть серые объекты. В какой-то момент маркировка останавливается и мир пробуждается. GC называется "инкрементным", потому что цикл GC выполняется небольшими приращениями, чередующимися с мутаторной активностью.

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

Корни не должны быть защищены барьером доступа, так как они сканируются с остановленным миром. Фаза GC mark заканчивается, когда одновременно выполняются следующие условия:

• корни только что отсканированы;
• все объекты либо черные, либо белые, но не серые.

поэтому такая ситуация может возникнуть только во время паузы. В этот момент начинается фаза развертки, во время которой белые объекты высвобождаются. Развертка может выполняться постепенно или одновременно; объекты, созданные во время развертки, немедленно окрашиваются в черный цвет. Когда развертка завершена, может наступить новая фаза метки GC: все объекты (которые в этот момент все черные) перекрашиваются в белый цвет (это делается атомарно, просто изменяя способ интерпретации цветовых битов).

Переменная классификация:

С учетом сказанного, теперь я могу ответить на ваш вопрос. С приведенным выше описанием возникает вопрос: каковы корни? Это на самом деле до реализации; Есть несколько возможностей и компромиссов.

Истинные корни всегда должны быть отсканированы; Истинные корни - это содержимое регистра ЦП и глобальные переменные. Обратите внимание, что стеки не являются истинными корнями; указатель кадра текущего стека.

Поскольку к быстрым переменным доступ осуществляется без барьеров, принято, чтобы стековые кадры были быстрыми переменными (т.е. также корнями). Это связано с тем, что, хотя доступ для записи является редким для всей системы, он довольно часто встречается в локальных переменных. Было измерено (в некоторых программах на Лиспе), что около 99% записей (от значения указателя) имеют локальную переменную в качестве цели.

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

С другой стороны, у вас может не быть быстрой переменной вообще, и нет корня, кроме истинных корней. Затем кадры стека обрабатываются как объекты, каждый из которых имеет свой собственный цвет. Паузы тогда минимальны (простой снимок дюжины регистров), но барьеры должны использоваться даже для доступа к локальным переменным. Это дорого, но имеет ряд преимуществ:

• Жесткие гарантии на время паузы могут быть сделаны. Это трудно, если фреймы стека являются корнями, потому что каждый новый поток имеет свой собственный стек, поэтому общий размер корней может возрасти до произвольной величины при запуске новых потоков. Если корнями являются только регистры ЦП и глобальные переменные (в обычных случаях не более нескольких десятков, а их число известно во время компиляции), то паузы могут быть очень короткими.
• Это позволяет динамически распределять кадры стека в куче. Это необходимо, если вы играете с сопрограммами и продолжениями, как в схеме call/cc примитивный. В таком случае кадры больше не обрабатываются как чистый "стек". Для правильной обработки продолжений в языке, поддерживающем GC, в основном требуется, чтобы функциональные кадры выделялись динамически.

Можно сделать стековые фреймы некорневыми, сохранив молодое поколение в качестве root. Гарантии на время паузы все еще могут быть сделаны (в зависимости от размера молодого поколения, который является фиксированным), и некоторые хитрости могут быть применены, чтобы убедиться, что кадры стека находятся в молодом поколении, когда их функция активна. Это может обеспечить беспрепятственный доступ к локальным переменным. Ничто из этого не является бесплатным, но его можно сделать достаточно эффективным для большинства целей.

Еще один концептуальный взгляд:

Другой способ просмотра обработки корня заключается в следующем: корни - это переменные, для которых правило триколора (без черно-белого указателя) не поддерживается постоянно; эти переменные могут быть изменены без ограничений. Но их нужно регулярно приводить в порядок, останавливая мир и просматривая их.

На практике мутаторы участвуют в гонках с GC. Мутаторы создают новые объекты и указывают на них; каждая пауза создает новые серые объекты. В параллельном или инкрементальном GC, если вы позволите мутаторам слишком долго играть с корнями, то каждая пауза может создавать большую партию новых серых объектов. В худшем случае ГХ не может сканировать объекты достаточно быстро, чтобы не отставать от скорости создания серых объектов. Это проблема, потому что белые объекты могут быть освобождены только во время фазы развертки, которая достигается только в том случае, если в какой-то момент ГХ может завершить свою маркировку. Обычная стратегия реализации для инкрементального GC состоит в том, чтобы сканировать серые объекты во время каждой паузы на общий размер, который пропорционален общему размеру корней. Таким образом, время паузы остается ограниченным общим размером корней, и если коэффициент пропорциональности хорошо сбалансирован, то можно гарантировать, что GC в конечном итоге прекратит работу в фазе маркировки и войдет в фазу подметания.

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

Список используемой литературы:

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

Answer 2

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

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

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