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

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

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

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

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

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

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

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

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

initialize() =
    tospace   = N/2
    fromspace = 0
    allocPtr  = fromspace
    scanPtr   = whatever -- only used during collection

allocate(n) =
    If allocPtr + n > fromspace + N/2
        collect()
    EndIf
    If allocPtr + n > fromspace + N/2
        fail “insufficient memory”
    EndIf
    o = allocPtr
    allocPtr = allocPtr + n
    return o

collect() =
    swap(fromspace, tospace)
    allocPtr = fromspace
    scanPtr = fromspace

    -- scan every root you've got
    ForEach root in the stack -- or elsewhere
        root = copy(root)
    EndForEach
    
    -- scan objects in the to-space (including objects added by this loop)
    While scanPtr < allocPtr
        ForEach reference r from o (pointed to by scanPtr)
            r = copy(r)
        EndForEach
        scanPtr = scanPtr + o.size() -- points to the next object in the to-space, if any
    EndWhile

copy(o) =
    If o has no forwarding address
        o' = allocPtr
        allocPtr = allocPtr + size(o)
        copy the contents of o to o'
        forwarding-address(o) = o'
    EndIf
    return forwarding-address(o)

Полупространство

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

Эквивалент трехцветной абстракции

Алгоритм Чейни является примером сборщика мусора с трехцветной маркировкой . Первым членом серого множества является сам стек. Объекты, на которые имеются ссылки в стеке, копируются в пространство to, содержащее элементы черного и серого наборов.

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

Когда указатель сканирования достигает указателя свободного пространства, серый набор становится пустым и алгоритм завершается.

Ссылки

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

Внешние ссылки

• Понимание среды выполнения Android (Google I/O'19) на YouTube . Android использует вариант полупространственного сборщика мусора.