Хотя GC GC GC, болел, но после стольких лет развития GC GC GCO на GC голанга много улучшился и стал очень хорошим.
Вот вехи алгоритма Golang GC:
- v1.1 STW
- v1.3 Пометка STW, параллельная развертка
- v1.5 Метод трехцветной маркировки
- v1.8 hybrid write barrier
Существует три классических алгоритма GC:引用计数(reference counting),标记-清扫(mark & sweep),复制收集(Copy and Collection).
Алгоритм GC Golang в основном основан на标记-清扫(mark and sweep)алгоритм, и на его основе внесены улучшения. Поэтому я в основном представлю здесь алгоритм маркировки и подметания.Вы можете сами рассказать Baidu о подсчете ссылок, копировании и сборе.
Алгоритм маркировки и развертки
В этом алгоритме есть два основных шага:
- Отметить фазу
- Фаза развертки
Первый шаг - найти свернутый объект, а затем сделать это. На втором шаге отзывающийся объект восстановлен.
Операция очень простая, но есть одна вещь, на которую стоит обратить внимание: при выполнении алгоритма маркировки и развертки программу нужно поставить на паузу! которыйstop the world.
То есть где программа за это время застрянет. Поэтому в переводе на китайский卡顿.
Давайте посмотрим на схему:
Маркер запуска, программа останавливается. Отношения между программами и объектами в это время следующие:
Затем начните маркировку, процесс находит все достижимые объекты и отмечает их. Как показано ниже:
После маркировки завершен, затем начните очищать не помеченные:
Потом мусор убрали, и стало как на картинке ниже.
Наконец, прекратите паузу и дайте программе продолжить работу. Затем этот процесс повторяется в цикле, пока не завершится жизненный цикл процесса.
Что не так с алгоритмом Mark And Sweep?
Хотя алгоритм Mark And Sweep очень прост, все же есть некоторые проблемы:
- STW, останови мир, пусть программа приостановится, и программа зависнет.
- Маркеры должны сканировать всю кучу
- Очистка данных приведет к фрагментации кучи
Самая важная проблема здесь заключается в том, что алгоритм пометки и очистки приостановит всю программу.
Как Go решает эту проблему?
Метод трехцветной одновременной маркировки
Давайте сначала посмотрим на общий процесс трехцветного метода маркировки Голанга.
Первое: объекты, созданные программой, отмечены белым цветом.
gc start: сканировать все доступные объекты, отмеченные серым цветом
Найдите указанный объект из серого объекта и отметьте его как серый, а сам серый объект пометьте как черный
Мониторинг объектов для модификаций памяти и продолжайте предыдущий шаг, пока объект серых не будет существовать
В этот момент gc перерабатывает белый объект.
Наконец, сделайте все черные объекты белыми и повторите весь описанный выше процесс.
Ну, общий поток таков, давайте вернемся к предыдущему вопросу: как Go решает проблему stutter (stw, stop the world) в алгоритме Mark and Swee (Mark and Swee)?
Как gc и пользовательская логика работают параллельно?
STW (STOP The World) Эксплуатация алгоритма отметки и развертки заключается в том, что время выполнения замораживает все потоки, что означает, что пользовательская логика приостановлена. Таким образом, все объекты не будут изменены, и это абсолютно безопасно сканировать в это время.
Go如何减短这个过程呢？标记-清除(mark and sweep)算法包含两部分逻辑：标记和清除。
我们知道Golang三色标记法中最后只剩下的黑白两种对象，黑色对象是程序恢复后接着使用的对象，如果不碰触黑色对象，只清除白色的对象，肯定不会影响程序逻辑。 так:清除操作和用户逻辑可以并发。
Операция маркировки и пользовательская логика также параллельны.Логика пользователя часто генерирует объекты или изменяет ссылку на объект, так как же маркировка и пользовательская логика могут быть параллельными?
Когда процесс генерирует новый объект, как работает GC? Не будет грязно?
Давайте посмотрим на рисунок ниже В этом состоянии: программа процесса создала новый объект, и мы представляем, что он станет таким:
Но это заведомо неправильно, так как по шагам метода трехцветной маркировки вновь сгенерированный объект А в конце будет очищен, что повлияет на логику программы.
Чтобы решить эту проблему, Golang представил写屏障этот механизм.
Барьер записи: операция записи до барьера сначала воспринимается другими компонентами системы по сравнению с операцией записи после нее.
С точки зрения непрофессионала: в процессе работы gc можно отслеживать изменение памяти объекта и объект может быть перемаркирован. (на самом деле тоже супер короткий stw, потом пометка объекта)
В приведенном выше случае新生成的对象，一律都标位灰色！То есть картина ниже:
Итак, как же работает Golang, когда ссылка на серый или черный объект меняется на белый объект?
Глядя на изображение ниже, черный объект относится к белому объекту, который когда-то был отмечен.
В это время срабатывает механизм барьера записи, поступает сигнал на ГХ, ГХ повторно сканирует объект и помечает его серым цветом.
Следовательно, после запуска gc, независимо от того, создан ли объект или изменена ссылка на объект, он сначала станет серым.
использованная литература:
- Сборщик мусора в реальном времени Golang в теории и на практике
- Golang's realtime garbage collector
- Анатомия сборки мусора Голанга