Алгоритм Чейни - Cheneys algorithm

Алгоритм Чейни, впервые описанный в 1970 г. ACM статья К.Дж.Чейни, является остановить и скопировать метод отслеживание сборки мусора в компьютерных программных системах. На этой схеме куча делится на две равные половины, только одна из которых используется одновременно. Сборка мусора выполняется путем копирования живых объектов из одного полупространства (исходное пространство) в другое (пространство-в), которое затем становится новой кучей. Затем вся старая куча выбрасывается целиком. Это усовершенствование предыдущей техники остановки и копирования.[нужна цитата ]

Алгоритм Чейни восстанавливает предметы следующим образом:

  • Ссылки на объекты в стеке. Проверяются ссылки на объекты в стеке. Одно из двух следующих действий выполняется для каждой ссылки на объект, которая указывает на объект из пространства:
    • Если объект еще не был перемещен в пространство в пространство, это делается путем создания идентичной копии в пространстве в пространстве с последующей заменой версии из пространства указателем пересылки на копию в пространство. Затем обновите ссылку на объект, чтобы она ссылалась на новую версию в to-space.
    • Если объект уже был перемещен в пространство, просто обновите ссылку из указателя пересылки в исходном пространстве.
  • Объекты в космическом пространстве. Сборщик мусора проверяет все ссылки на объекты в объектах, которые были перенесены в космос, и выполняет одно из двух действий над объектами, на которые есть ссылка.

После того, как все ссылки на пространство были изучены и обновлены, сборка мусора завершена.

Алгоритму не нужен стек и только два указателя за пределами из-пространства и в-пространство: указатель на начало свободного пространства в пространстве-за и указатель на следующее слово в пространстве-за-пространство, которое необходимо проверить. . По этой причине его иногда называют «двухпальцевым» сборщиком - ему нужны только «два пальца», указывающие в пространство, чтобы отслеживать его состояние. Данные между двумя пальцами представляют собой работу, которую ему предстоит сделать.

Указатель пересылки (иногда называемый «разбитым сердцем») используется только во время процесса сборки мусора; когда найдена ссылка на объект, уже находящийся в to-space (таким образом, имеющий указатель пересылки в from-space), ссылку можно быстро обновить, просто обновив ее указатель для соответствия указателю пересылки.

Поскольку стратегия состоит в том, чтобы исчерпать все активные ссылки, а затем все ссылки в ссылочных объектах, это известно как в ширину список копирует схему сборки мусора.

Пример алгоритма

initialize () = tospace = N / 2 fromspace = 0 allocPtr = fromspace scanPtr = любой - используется только во время сбора
allocate (n) = Если allocPtr + n> fromspace + tospace collect () EndIf Если allocPtr + n> fromspace + tospace fail «недостаточно памяти» EndIf o = allocPtr allocPtr = allocPtr + n return o
collect () = swap (fromspace, tospace) allocPtr = tospace scanPtr = tospace - сканировать каждый корень, у вас есть ForEach root в стеке - или где-либо еще root = copy (root) EndForEach - сканировать объекты в to-space (включая объекты, добавленные этим циклом) Пока scanPtr 
copy (o) = Если o не имеет адреса пересылки o '= allocPtr allocPtr = allocPtr + size (o) скопировать содержимое o в o' адрес-пересылки (o) = o 'EndIf return-адрес-пересылка (o)
Полупространство












Чейни основывал свою работу на полупространство сборщик мусора, опубликованный годом ранее Р. Р. Фенихелем и Дж. К. Йохельсоном.
Эквивалентность трехцветной абстракции












Алгоритм Чейни является примером трехцветная маркировка уборщик мусора. Первый член серого набора - это сам стек. Объекты, указанные в стеке, копируются в пространство, которое содержит элементы черного и серого наборов.
Алгоритм перемещает любые белые объекты (эквивалентные объектам в исходном пространстве без указателей пересылки) в серый набор, копируя их в пространство. Объекты, которые находятся между указателем сканирования и указателем свободного пространства в области перемещения, являются членами серого набора, которые еще предстоит сканировать. Объекты под указателем сканирования относятся к черному набору. Объекты перемещаются в черный набор простым наведением на них указателя сканирования.
Когда указатель сканирования достигает указателя свободного пространства, серый набор становится пустым, и алгоритм завершается.
Рекомендации












  • Чейни, Си-Джей (ноябрь 1970 г.). «Нерекурсивный алгоритм сжатия списка». Коммуникации ACM. 13 (11): 677–678. Дои:10.1145/362790.362798.
  • Fenichel, R.R .; Йохельсон, Джером К. (1969). «Сборщик мусора LISP для компьютерных систем с виртуальной памятью». Коммуникации ACM. 12 (11): 611–612. Дои:10.1145/363269.363280.
  • Байерс, Рик (2007). «Алгоритмы сборки мусора» (PDF). Алгоритмы сборки мусора. 12 (11): 3–4.
  • Руководство на Университет Мэриленда, Колледж-Парк