Cheney算法,最初由C.J. Cheney在1970年ACM论文中描述,它是计算机软件系统中追踪垃圾回收的一种“停止并复制”方法[1]。在这种方案中,堆被划分成相等的两半,在任何时刻都只有其中一个在使用中。进行垃圾回收的方式为,通过将存活对象从一个半空间(semispace)即“自”空间(from-space),复制到另一个半空间即“至”空间(to-space),它接着成为新堆,而整个旧堆一次性丢弃。
Cheney算法收回如下项目:
一旦所有的“至”空间引用都已经检查并更新,垃圾回收完成。
算法不需要栈并只需要在“自”空间和“至”空间外部的两个指针:到在“至”空间中空闲空间开始处的指针,和到在“自”空间中需要检查的下一个字的指针。在这两个指针之间的数据,代表它仍需要做的工作。
转发指针(昵称“破碎的心”),只在垃圾回收进程中使用;在到已经处在“至”空间的对象(因此在“自”空间中有一个转发指针)的一个引用被找到的时候,通过更新其指针来匹配转发指针,这个引用就可以简单而快速的更新。
由于这种策略要穷尽所有的存活引用,和在所引用对象中的所有的引用,它被称为“广度优先”列表复制垃圾回收方案。
initialize() = tospace = N/2 fromspace = 0 allocPtr = fromspace scanPtr = whatever -- only used during collection
allocate(n) = If allocPtr + n > fromspace + tospace collect() EndIf If allocPtr + n > fromspace + tospace fail “insufficient memory” EndIf o = allocPtr allocPtr = allocPtr + n return o
collect() = swap(fromspace, tospace) allocPtr = tospace scanPtr = tospace -- 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)
Cheney算法基于了“半空间”(semispace)垃圾回收器,这是在它一年之前由R.R. Fenichel和J.C. Yochelson发表的[2]。