Триколор Возрастающее Обновление GC: это должно просканировать каждый стек дважды?
Позвольте мне дать Вам краткое введение в триколор GC (в случае, если кто-то читает его, кто никогда не слышал о нем); если Вы не заботитесь, пропустите его и переход к проблеме.
Как триколор работы GC
В триколоре GC объект имеет один из трех возможных цветов; белый, серый и черный. Триколор GC может быть описан следующим образом:
Все объекты являются первоначально белыми.
Все объекты, достижимые, потому что глобальная переменная или переменная стека относятся к нему ("корневые объекты"), окрашены в серый.
Мы берем любой серый объект, находим все ссылки, которые он имеет к белым объектам, и окрасьте те белые объекты в серый. Затем мы окрашиваем сам объект черным.
Мы продолжаем на шаге 3, пока у нас есть серые объекты.
Если у нас нет серых объектов еще, все остающиеся объекты являются или белыми или черными.
Весь черный приют объектов, доказанный быть достижимым и, должен остаться в живых. Все белые объекты недостижимы и могут быть удалены.
До сих пор это не слишком сложно …, по крайней мере, если GC будет StW (Остановите Мир), то означание его приостановит все потоки при сборе мусора. Если это параллельно, триколор, GC имеет инвариант, который должен сохраняться в любом случае:
Черный объект не должен относиться к белому объекту!
Это сохраняется автоматически для StW GC, так как каждый объект, который окрашен в черный, был исследован ранее и все белые объекты, на которые он указывал, были окрашены в серый, таким образом черный объект может только относиться к другим черным объектам или серым объектам.
Если бы потоки не приостанавливаются, потоки могут выполнить код, который повредил бы этот инвариант. Существует несколько путей, как предотвратить это:
Получите весь доступ для чтения к указателям и посмотрите, если этот доступ для чтения сделан к белому объекту. Если это, окрасьте тот объектный серый сразу. Если касательно к этому объекту будет теперь присвоен черному объекту, то он не будет иметь значения, объект является серым и не белым больше (эта реализация использует барьер чтения),
Получите весь доступ для записи к указателям и посмотрите, если назначенный объект является белым, и объект, которому он присвоен, является черным. Если так, окрасьте белый объектный серый. Это, более очевидно, способ сделать вещи, но также и требуется немного большее количество времени обработки (эта реализация использует барьер записи),
Так как доступ для чтения намного более распространен, чем доступ для записи, даже при том, что вторая возможность включает больше времени обработки, когда барьер поражен, это называют менее часто и такой привилегированный. GC, работающий как этот, называют "возрастающим обновлением GC".
Существует альтернатива обоим методам, названным SatB (Снимок вначале). Эти немного отличающиеся работы изменения, рассматривая то, что не действительно необходимо поддержать инвариант в любом случае, так как не имеет значения, если черный объект относится к белому пока GC, знают, что этот белый объект раньше был и все еще доступен во время текущего цикла GC (или потому что существуют все еще серые объекты, относящиеся к этому белому объекту также, или потому что касательно к этому белому объекту помещается на явный стек, который также рассматривает GC, когда это исчерпывает серые объекты). Коллекторы SatB используются чаще на практике, потому что у них есть некоторые преимущества, но по моему скромному мнению их более трудно реализовать.
Я отсылаю здесь к возрастающему обновлению GC, который использует различные 2: Каждый раз, когда код пытается высказать черное объектное мнение к белому объекту, он сразу окрашивает объектный серый. Тем путем этот объект не будет пропущен в цикле сбора.
Проблема
Так о триколоре GCs. Но существует одна вещь, я не понимаю о триколоре GCs. Давайте предположим, что у нас есть объект A, который упомянут стеком, и оно относится к объекту B.
stack -> A.ref -> B
Теперь GC запускает цикл, останавливает поток, сканирует стек и видит как непосредственно доступный, окрашивая серый. После того как это сделано со сканированием целого стека, это не приостанавливает поток снова и начинает обрабатывать на шаге (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 не изменился, это все еще бело. Не относится к B больше, поэтому при обработке "серого" A B не изменит свой цвет, и A станет черным. В конце цикла B является все еще белым и является похожим на мусор. Однако localRef относится к B, таким образом это не мусор.
Вопрос
Действительно ли я прав, что триколор GC должен просканировать стопку каждого потока дважды? Однажды в самом начале, чтобы определить корневые объекты (получение цветного серого) и снова прежде, чем удалить белые объекты, поскольку на них мог бы сослаться стек, даже при том, что никакой другой объект не относится к ним больше. Никакое описание алгоритма, который я видел до сих пор, ничего не упомянуло о сканировании стека дважды. Они все только сказали, что при параллельном использовании важно, чтобы инвариант был осуществлен во все время, в других отношениях достижимые объекты пропущены. Но насколько я вижу, это недостаточно. Стек нужно рассмотреть как единственный большой объект и когда-то просканировать, "стек является черным", и каждый касательно обновления стека должен заставить объект быть окрашенным в серый.
Если это действительно имеет место, использование возрастающего обновления может быть более хитрым, чем я первоначально думал и имею некоторые недостатки производительности, так как изменения стека являются самыми частыми всех.
1 ответ
Немного терминологии:
Позвольте мне дать несколько имен, чтобы объяснения были более ясными.
Переменная - это любой слот для данных, который может содержать указатель и может изменяться со временем. Сюда входят глобальные переменные, локальные переменные, регистры ЦП и поля в выделенных объектах.
В трехцветном инкрементном или параллельном сборщике мусора есть три типа переменных:
- истинные корни , которые всегда доступны (регистры ЦП, глобальные переменные);
- быстрые переменные , которые сканируются в режиме остановки мира,
- медленные переменные , которые обрабатываются с помощью цветов. Медленные переменные - это поля в цветных объектах.
«Истинные корни» и «быстрые переменные» в дальнейшем будут вместе называться корнями .
Потоки приложений называются мутаторами , потому что они изменяют содержимое переменных.
При инкрементальном или параллельном сборке мусора паузы сборщика мусора происходят регулярно. Остановка мира (пауза мутаторов) и сканирование корней. Это сканирование показывает ряд ссылок на цветные объекты. Соответственно настраиваются цвета объектов (такие белые объекты становятся серыми).
Когда GC является инкрементальным , происходит сканирование некоторых объектов: некоторые серые объекты сканируются (и окрашиваются в черный цвет), белые объекты, на которые ссылаются, становятся серыми. Эта активность («маркировка») сохраняется в течение некоторого времени, но не обязательно до тех пор, пока есть серые объекты. В какой-то момент маркировка прекращается, и мир пробуждается. Сборщик мусора называется «инкрементным», потому что цикл сборщика мусора выполняется небольшими приращениями, чередующимися с активностью мутатора.
В параллельном GC сканирование серых объектов происходит одновременно с активностью мутатора. Затем мир пробуждается, как только просканированы корни. При параллельном сборке мусора барьеры доступа довольно сложно реализовать, поскольку они должны обрабатывать одновременный доступ из потока сборщика мусора; но на концептуальном уровне это не сильно отличается от инкрементного сборщика мусора. Параллельный сборщик мусора можно рассматривать как оптимизацию по сравнению с инкрементным сборщиком мусора, который использует преимущества наличия нескольких ядер ЦП (параллельный сборщик мусора имеет небольшое преимущество перед инкрементным сборщиком мусора, когда имеется только одно ядро).
Корни не обязательно должны быть защищены барьером доступа, так как они сканируются с остановленным миром. Фаза метки GC заканчивается, когда одновременно выполняются следующие условия:
- корни только что отсканированы;
- все объекты либо черные, либо белые, но не серые.
, поэтому такая ситуация может возникнуть только во время паузы. В этот момент начинается фаза развертки, во время которой освобождаются белые объекты. Развертка может выполняться поэтапно или одновременно; объекты, созданные во время развертки, сразу окрашиваются в черный цвет.Когда развертка завершена, может иметь место новая фаза метки GC: все объекты (которые в этот момент все черные) перекрашиваются в белый цвет (это делается атомарно, просто изменяя способ интерпретации битов цвета).
Классификация переменных:
Теперь я могу ответить на ваш вопрос. С приведенным выше описанием возникает вопрос: каковы корни? На самом деле это зависит от реализации; есть несколько возможностей и компромиссов.
Истинные корни всегда нужно сканировать; Истинные корни - это содержимое регистров ЦП и глобальные переменные. Обратите внимание, что стеки являются не истинными корнями; только текущий указатель кадра стека.
Поскольку доступ к быстрым переменным осуществляется без препятствий, принято делать фреймы стека быстрыми переменными (то есть корнями). Это связано с тем, что, хотя доступ для записи редко встречается в масштабах всей системы, он довольно часто встречается в локальных переменных. Было измерено (в некоторых программах на Лиспе), что около 99% операций записи (значения указателя) имеют локальную переменную в качестве цели.
Быстрые переменные часто расширяются еще дальше, в случае GC поколений: «молодое поколение» состоит в специальной области выделения для новых объектов, ограниченной по длине и сканируемой как быстрые переменные. Яркая сторона быстрых переменных - это быстрый доступ (отсюда и название); Обратной стороной является то, что все эти быстрые переменные можно сканировать только во время паузы (мир остановлен). Существует компромисс между размером быстрых переменных, который часто приводит к ограничению размера молодого поколения.Более крупное молодое поколение способствует средней производительности (за счет уменьшения количества барьеров доступа) за счет более длительных пауз.
С другой стороны, у вас может вообще не быть быстрой переменной и не иметь корня, кроме истинных корней. Затем кадры стека обрабатываются как объекты, каждый из которых имеет свой цвет. При этом паузы минимальны (всего лишь снимок десятка регистров).но барьеры необходимо использовать даже для доступа к локальным переменным. Это дорого, но имеет некоторые преимущества:
- Могут быть предоставлены жесткие гарантии времени паузы. Это сложно, если кадры стека являются корнями, потому что каждый новый поток имеет свой собственный стек, поэтому общий размер корня может увеличиваться до произвольных значений при запуске новых потоков. Если только регистры ЦП и глобальные переменные (в типичных случаях не более нескольких десятков, и их количество известно во время компиляции) являются корнями, то паузы можно делать очень короткими.
- Это позволяет динамически выделять кадры стека в куче. Это необходимо, если вы играете с сопрограммами и продолжениями, как с примитивом Scheme
call / cc. В таком случае фреймы больше не обрабатываются как чистый «стек». Правильная обработка продолжений на языке, поддерживающем сборщик мусора, в основном требует, чтобы функциональные фреймы распределялись динамически.
Можно сделать кадры стека некорневыми, сохранив молодое поколение как корневое. По-прежнему можно гарантировать время паузы (в зависимости от размера молодого поколения, который является фиксированным), и можно применить некоторые хитрости, чтобы убедиться, что кадры стека находятся в молодом поколении, когда их функция активна. Это может обеспечить беспрепятственный доступ к локальным переменным. На самом деле все это не является бесплатным, но его можно сделать достаточно эффективным для большинства целей.
Другой концептуальный взгляд:
Другой способ просмотра обработки корневого каталога заключается в следующем: корни - это переменные, для которых правило трехцветности (отсутствие указателя от черного к белому) не поддерживается постоянно; эти переменные могут изменяться без ограничений.Но их нужно регулярно приводить в порядок, останавливая мир и просматривая их.
На практике мутаторы конкурируют с GC. Мутаторы создают новые объекты и указывают на них; каждая пауза создает новые серые объекты. Если в параллельном или инкрементном сборке мусора вы позволяете мутаторам слишком долго играть с корнями, то каждая пауза может создавать большую партию новых серых объектов. В худшем случае GC не может сканировать объекты достаточно быстро, чтобы не отставать от скорости создания серых объектов. Это проблема, потому что белые объекты могут быть освобождены только во время фазы развертки, которая достигается только в том случае, если в какой-то момент GC может завершить свою маркировку. Обычная стратегия реализации инкрементного сборщика мусора - сканировать серые объекты во время каждой паузы на предмет общего размера, который пропорционален общему размеру корней. Таким образом, время паузы остается ограниченным общим размером корней, и если коэффициент пропорциональности хорошо сбалансирован, то можно гарантировать, что сборщик мусора в конечном итоге завершит фазу маркировки и войдет в фазу развертки.
В параллельном GC все немного сложнее, потому что мутаторы свободно перемещаются в дикой природе. Возможная реализация могла бы сделать небольшую инкрементную маркировку, пока мир все еще остановлен.
Библиография:
Сборка мусора: алгоритмы автоматического динамического управления памятью : книга по сборке мусора, которую необходимо прочитать.