Как работает трехцветный алгоритм сборщика мусора

Что проверяют

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

Как отвечать

Объекты кучи делятся на три множества:

• белые: ещё не найдены, кандидаты на удаление;
• серые: найдены, но их указатели ещё не просмотрены;
• чёрные: найдены, и все их ссылки уже обработаны.

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

Главное свойство схемы: работу можно прерывать и продолжать, пока программа меняет указатели. Опасность одна: программа запишет ссылку на белый объект в чёрный и удалит последнюю ссылку на него из серого. Тогда живой объект будет освобождён. Инвариант звучит так: чёрный объект не должен указывать на белый. Держит его барьер записи. В Go это гибридный барьер (сочетание вставочного и удаляющего), который избавил от повторного сканирования стеков в конце разметки.

Цикл сборки в Go: короткая остановка мира на включение барьера, конкурентная разметка, короткая остановка на её завершение, затем ленивая очистка в фоне. Объекты, созданные во время разметки, сразу считаются чёрными. Фоновая разметка забирает около четверти GOMAXPROCS, а горутины, которые активно аллоцируют, принудительно помогают ей (mark assist). Частоту запусков задают GOGC (по умолчанию 100) и мягкий лимит GOMEMLIMIT.

Где спотыкаются

Описывают алгоритм как «пометили и удалили» и не упоминают барьер записи. Без него конкурентная разметка некорректна, а это главный вопрос интервьюера.

Говорят, что сборщик Go поколенческий или перемещающий. Он непоколенческий и объекты не двигает, поэтому указатели остаются стабильными.

Считают, что пауз нет совсем. Остановки мира есть, просто обычно укладываются в доли миллисекунды, а основная цена сборки уходит в процессорное время и в mark assist, который замедляет аллоцирующие горутины.