Cheney算法

Cheney算法,最初由C.J. Cheney在1970年ACM論文中描述,它是計算機軟體系統中追蹤垃圾回收的一種「停止並複製」方法[1]。在這種方案中,被劃分成相等的兩半,在任何時刻都只有其中一個在使用中。進行垃圾回收的方式為,通過將存活對象從一個半空間(semispace)即「自」空間(from-space),複製到另一個半空間即「至」空間(to-space),它接著成為新堆,而整個舊堆一次性丟棄。

簡介

Cheney算法收回如下項目:

  • 在棧上的對象引用。檢查在棧上的對象引用,對指向在「自」空間中對象的每個對象引用,選用下列兩個動作之一:
    • 如果這個對象仍未移動到「至」空間,則通過在「至」空間中創建完全相同的復件來移動它,並將這個「自」空間版本,替換為到「至」空間版本的轉發指針(forwarding pointer)。接著更新對象引用,來提及在「至」空間中的新版本。
    • 如果這個對象已經被移動到「至」空間,則簡單的從「自」空間中的轉發指針更新這個引用。
  • 在「至」空間中的對象。垃圾回收器檢查已經遷移到「至」空間的對象內所有對象引用,並在所引用的對象上進行上述兩個動作。

一旦所有的「至」空間引用都已經檢查並更新,垃圾回收完成。

算法不需要棧並只需要在「自」空間和「至」空間外部的兩個指針:到在「至」空間中空閒空間開始處的指針,和到在「自」空間中需要檢查的下一個字的指針。在這兩個指針之間的數據,代表它仍需要做的工作。

轉發指針(暱稱「破碎的心」),只在垃圾回收進程中使用;在到已經處在「至」空間的對象(因此在「自」空間中有一個轉發指針)的一個引用被找到的時候,通過更新其指針來匹配轉發指針,這個引用就可以簡單而快速的更新。

由於這種策略要窮盡所有的存活引用,和在所引用對象中的所有的引用,它被稱為「廣度優先」列表複製垃圾回收方案。

算法偽碼

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]

引用

  1. ^ Cheney, C.J. A Nonrecursive List Compacting Algorithm. Communications of the ACM. November 1970, 13 (11): 677–678 [2022-11-09]. S2CID 36538112. doi:10.1145/362790.362798. (原始內容存檔於2022-11-09). 
  2. ^ Fenichel, R.R.; Yochelson, Jerome C. A LISP garbage-collector for virtual-memory computer systems. Communications of the ACM. 1969, 12 (11): 611–612 [2022-11-09]. S2CID 36616954. doi:10.1145/363269.363280. (原始內容存檔於2020-05-28).