трехцветный алгоритм
Работа сборщика мусора go основана натрехцветный алгоритм, эта статья в основном описывает этот алгоритм.
Примечание: трехцветный алгоритм не уникален для go, он также используется в других языках программирования.
Строго говоря, официальное название этого алгоритма в Go называетсяАлгоритм трехцветной маркировки и развертки. Может работать одновременно с программами и использоватьнаписать барьер. Это означает, что когда программатор Go работает, планировщик go отвечает за планирование приложения, а сборщик мусора будет использовать несколькоgoroutinesидти на работу.
Основная идея этого алгоритма была предложена Эдсгером В. Дейкстра, Лесли Лэмпортом, А.Дж.Мартином, К.С.Шолтеном и Э.Ф.М.Стеффенсом. Впервые алгоритм был опубликован в статьеОперативная сборка мусора: упражнение в сотрудничествевыше. Первый принцип алгоритма удаления трехцветных меток заключается в том, что он сортирует объекты в куче на наборы в соответствии с их цветами.
Теперь давайте поговорим о том, что представляет каждый набор цветов.черная коллекциязаключается в том, чтобы гарантировать, что никакие указатели не указывают на белую коллекцию. нобелая коллекцияОбъектам разрешено иметь указатели на черный набор, так как это не влияет на работу сборщика мусора.серая коллекцияВ белом наборе могут быть указатели на объекты. Объекты в белом наборе являются кандидатами на сборку мусора.
Обратите внимание, что никакие объекты не могут перейти из черного набора в белый набор, что позволяет алгоритму манипулировать и очищать объекты в белом наборе. Кроме того, никакие объекты-указатели в черном наборе не могут напрямую указывать на объекты в белом наборе.
Когда начинается сборка мусора, все объекты помечаются белым цветом, затем сборщик мусора просматривает все корневые объекты и помечает их серым цветом.корневой объектЭто объект, к которому программа может напрямую обращаться, включая глобальные переменные и вещи в стеке. Большинство этих объектов зависят от исходного кода конкретной программы. После этого сборщик мусора выбирает серый объект, превращает его в черный и начинает искать, есть ли в этом объекте указатель на белый набор объектов. Это означает, что при сканировании серого объекта, поскольку на него указывает указатель другого объекта, серый объект будет помечен как черный. Если сканирование обнаружит, что у серого объекта есть один или несколько указателей, указывающих на белые объекты, оно поместит заостренные белые объекты в серый набор. Этот процесс будет продолжаться до тех пор, пока существуют серые объекты коллекции. После этого объекты в белом наборе — это объекты, к которым никто не обращался, а занимаемая ими память может быть восстановлена и использована повторно. Поэтому в этот момент мы говорим, что элементы в белом наборе удаляются сборщиком мусора.
Если в процессе сборки мусора серый объект в некоторых случаях становится недоступным, он не будет собран в этой сборке мусора, но это не значит, что он не будет собран в следующий раз!
В этом процессе запуск приложения называетсямутатор. мутатор для запуска небольшого метода под названием写屏障（write barrier）, барьер записи будет выполняться каждый раз при изменении указателя в куче. Если указатель на объект в куче изменен, что означает, что этот объект теперь доступен, барьер записи пометит его серым цветом и поместит в серый набор.
Мутатор отвечает за то, чтобы указатели, не содержащие элементов в черном наборе, указывали на элементы в белом наборе. Это делается с помощью методов барьера записи. Неспособность поддерживать это неизменяемое состояние нарушит процесс сборки мусора и, вероятно, сломает вашу программу уродливым и непреднамеренным образом.
Куча может рассматриваться как граф множества связанных объектов, как показано ниже, показывающий один процесс сборки мусора.
У нас есть три разных цвета: черный, белый и черный. При запуске алгоритма все объекты помечаются белым цветом. По мере продолжения алгоритма белый объект перемещался в один из двух других наборов цветов. Последние объекты, оставшиеся в белом наборе, будут очищены в какой-то момент в будущем.
На предыдущей диаграмме вы можете видеть белый объект E, который находится в белом наборе и имеет доступ к объекту F, E не будет доступен никаким другим объектам, потому что нет других указателей на E, что делает E мусором. лучший кандидат на переработку! Кроме того, объекты A, B и C являются корневыми объектами и всегда доступны, поэтому они не будут удалены сборщиком мусора.
Далее алгоритм обработает оставшиеся элементы серого множества, а значит, объекты A и F перейдут в черное множество. Объект A входит в черный набор, потому что он является корневым элементом, а F входит в черный набор, потому что он не указывает ни на какой другой объект, но находится в сером наборе. После того, как объект A будет удален, объект F станет недоступным и будет собран в следующем цикле обработки сборщика мусора.
Go позволяет вам сделать это, поместив в свой код Goruntime.GC()Инструкция для ручного запуска сборки мусора. Однако имейте в виду, что,runtime.GC()заблокирует вызывающую программу и может заблокировать всю программу, особенно если вы хотите запустить очень загруженную программу go с большим количеством объектов. Это происходит главным образом потому, что вы не можете заниматься сборкой мусора, когда что-то еще часто меняется, потому что это не дает сборщику мусора возможности четко идентифицировать элементы белого, черного и серого наборов. Это состояние сборки мусора также известно какпункт сбора мусора.
Вы можете найти высокоуровневый код go, связанный со сборщиком мусора, по адресу https://github.com/golang/go/blob/master/src/runtime/mgc.go. Вы можете изучить это, если хотите узнать больше об операциях сборки мусора.