Введение
Алгоритм Чейни, впервые описанный в 1970 году в статье ACM Чейни, является методом «остановка и копирование» для трассировки сборки мусора в компьютерных программных системах. В этой схеме куча разделена на две равные половины, только одна из которых используется в любой момент времени. Сбор мусора выполняется путем копирования живых объектов из одного полупространства (исходного полупространства) в другое (целевое полупространство), которое затем становится новой кучей. Затем вся старая куча целиком отбрасывается. Это улучшение по сравнению с предыдущей техникой «остановка и копирование». Алгоритм Чейни восстанавливает элементы следующим образом: ссылки на объекты в стеке. Ссылки на объекты в стеке проверяются. Для каждой ссылки на объект, указывающей на объект в исходном полупространстве, выполняется одно из двух следующих действий: если объект еще не был перемещен в целевое полупространство, это делается путем создания идентичной копии в целевом полупространстве, а затем замены версии в исходном полупространстве переадресующим указателем на копию в целевом полупространстве. Затем обновляется ссылка на объект, чтобы она указывала на новую версию в целевом полупространстве. Если объект уже перемещен в целевое полупространство, просто обновляется ссылка с переадресующего указателя в исходном полупространстве. Объекты в целевом полупространстве. Сборщик мусора просматривает все ссылки на объекты в объектах, которые были перенесены в целевое полупространство, и выполняет одно из двух вышеуказанных действий для ссылаемых объектов. После того как все ссылки в целевом полупространстве проверены и обновлены, сбор мусора завершен. Алгоритму не требуется стек и только два указателя вне исходного и целевого полупространств: указатель на начало свободного пространства в целевом полупространстве и указатель на следующее слово в целевом полупространстве, которое необходимо исследовать. Данные между этими двумя указателями представляют собой оставшуюся работу (эти объекты считаются «серыми» в трехцветной терминологии, см. далее). Переадресующий указатель (иногда называемый «разбитым сердцем») используется только во время процесса сборки мусора; когда обнаруживается ссылка на объект, уже находящийся в целевом полупространстве (и, следовательно, имеющий переадресующий указатель в исходном полупространстве), ссылку можно быстро обновить, просто изменив ее указатель в соответствии с переадресующим указателем. Поскольку стратегия заключается в исчерпании всех живых ссылок, а затем всех ссылок в ссылаемых объектах, эта схема известна как схема копирования сборки мусора с обходом в ширину.
Object references on the stack. Object references on the stack are checked. One of the two following actions is taken for each object reference that points to an object in from space:
If the object has not yet been moved to the to space, this is done by creating an identical copy in the to space, and then replacing the from space version with a forwarding pointer to the to space copy. Then update the object reference to refer to the new version in to space. If the object has already been moved to the to space, simply update the reference from the forwarding pointer in from space. Objects in the to space. The garbage collector examines all object references in the objects that have been migrated to the to space, and performs one of the above two actions on the referenced objects. Once all to space references have been examined and updated, garbage collection is complete. The algorithm needs no stack and only two pointers outside of the from space and to space: a pointer to the beginning of free space in the to space, and a pointer to the next word in to space that needs to be examined. The data between the two pointers represents work remaining for it to do (those objects are gray in the tri color terminology, see later). The forwarding pointer (sometimes called a "broken heart") is used only during the garbage collection process; when a reference to an object already in to space (thus having a forwarding pointer in from space) is found, the reference can be updated quickly simply by updating its pointer to match the forwarding pointer. Because the strategy is to exhaust all live references, and then all references in referenced objects, this is known as a breadth first list copying garbage collection scheme.
Полупространство
Чейни основал свою работу на сборщике мусора для полупространства, который был опубликован годом ранее Р. Р. Феничелем и Дж. К. Йохельсоном.
Эквивалентность трехцветной абстракции
Алгоритм Чейни — пример трехцветного маркировочного сборщика мусора. Первый элемент серого множества — это сам стек. Объекты, на которые есть ссылки в стеке, копируются в пространство to, которое содержит элементы черного и серого множеств. Алгоритм перемещает любые белые объекты (эквивалентные объектам в пространстве from без перенаправляющих указателей) в серое множество, копируя их в пространство to. Объекты, находящиеся между указателем сканирования и указателем свободного пространства в области пространства to, являются элементами серого множества, которые еще предстоит просканировать. Объекты ниже указателя сканирования принадлежат черному множеству. Объекты перемещаются в черное множество простым перемещением указателя сканирования над ними. Когда указатель сканирования достигает указателя свободного пространства, серое множество становится пустым, и алгоритм завершается.