체니 알고리즘

Cheney's algorithm

1970년 C.J.의 ACM 논문에 처음 기술된 체니의 알고리즘.Cheney는 컴퓨터 소프트웨어 시스템에서 가비지 수집을 추적하는 중지 및 복사 방법입니다.이 방식에서는 히프는 2개의 동등한 반으로 분할되어 있으며, 그 중 1개만 동시에 사용되고 있습니다.가비지 컬렉션은 하나의 반스페이스(공간에서 공간)에서 다른 반스페이스(공간에서 공간)로 라이브개체를 복사하여 실행됩니다.이것이 새로운 힙이 됩니다.그런 다음 오래된 힙 전체가 한 조각으로 폐기됩니다.이것은 이전의 정지 및 복사 [citation needed]기법보다 개선된 것입니다.

Cheney의 알고리즘은 다음과 같이 아이템을 회수합니다.

  • 스택상의 오브젝트 참조.스택상의 오브젝트 참조가 체크됩니다.다음 두 가지 작업 중 하나는 공간에서 개체를 가리키는 각 개체 참조에 대해 수행됩니다.
    • 오브젝트가 아직 스페이스로 이동되지 않은 경우에는 스페이스에서 동일한 복사본을 작성한 후 스페이스에서 스페이스 복사로 전송 포인터로 바꿉니다.그런 다음 객체 참조를 업데이트하여 새 버전의 To-space의 새 버전을 참조합니다.
    • 오브젝트가 이미 스페이스로 이동되어 있는 경우는, 스페이스로부터 전달 포인터의 참조를 갱신하기만 하면 됩니다.
  • To-space 내의 객체.가비지 컬렉터는 공간으로 마이그레이션된 개체의 모든 개체 참조를 검사하고 참조된 개체에 대해 위의 두 가지 작업 중 하나를 수행합니다.

모든 공간 참조를 검사하고 업데이트하면 가비지 수집이 완료됩니다.

이 알고리즘에는 스택이 필요 없고 from-space 및 to-space 외부에 있는 두 개의 포인터(to-space의 빈 공간 시작 부분에 대한 포인터 및 검사해야 하는 to-space의 다음 단어에 대한 포인터)만 필요합니다.두 포인터 사이의 데이터는 남은 작업을 나타냅니다(이러한 오브젝트는 3색 용어로 회색입니다.나중에 참조).

전달 포인터(일명 "파손된 심장"이라고도 함)는 가비지 수집 프로세스 중에만 사용됩니다. 따라서 이미 공간에 있는 개체에 대한 참조가 발견되면 전달 포인터와 일치하도록 포인터를 업데이트하기만 하면 참조를 빠르게 업데이트할 수 있습니다.

이 전략은 모든 라이브 참조를 소진하고 다음으로 참조된 객체의 모든 참조를 소진하는 것이므로 가비지 컬렉션 방식을 복사하는 너비 우선 목록이라고 합니다.

샘플 알고리즘

initialize() = tospace = N/2 fromspace = 0 allocatePtr = fromspace scanPtr = anything -- 수집 중에만 사용됩니다.
allocate(n) = allocatePtr + n > fromspace + tospace collect() EndIf allocatePtr + n > fromspace + tospace에 실패한 경우 EndIf o = allocatePtr = allocatePtr + n을 반환합니다.
Collect())allocPtr)tospacescanPtr=tospace-스캔 검사를 수행하고 스택에서 ForEach 뿌리가 있어 모든 뿌리, 혹은 다른 곳 뿌리)copy(뿌리)EndForEach이 to-space(등의 물체 이 고리에서 추가)에 스캔 개체는 동안scanPtr<>allocPtr ForEach 참조 rfrswap(fromspace, tospace).omo (scanPtr에 의해 참조됨) r = copy(r) EndForEach scanPtr = scanPtr + o.size() -- EndWhile이 있는 경우 To-space의 다음 개체를 가리킵니다.
copy(o) = o에 포워딩 주소 o' = allocatePtr = allocatePtr + size(o)의 내용을 o' forwarding-address(o) = o'EndIf return forwarding-address(o)로 복사합니다.

반스피스

체니는 R.R.에 의해 1년 전에 출판된 반구형 쓰레기 수집기에 그의 연구를 기초했다.페니첼과 J.C.요켈슨.

삼색 추상화에 상당하는 것

체니의 알고리즘은 삼색 표시 쓰레기 수집기의 한 예이다.그레이 세트의 첫 번째 멤버는 스택 자체입니다.스택에서 참조되는 객체는 검은색 및 회색 세트의 멤버가 포함된 To-space로 복사됩니다.

알고리즘은 흰색 객체(포워딩 포인터가 없는 from-space 객체와 동일)를 to-space에 복사하여 회색 세트로 이동합니다.스캔 포인터와 공간 이동 영역의 빈 공간 포인터 사이에 있는 개체는 여전히 스캔할 회색 세트의 구성원입니다.스캔 포인터 아래의 개체는 검은색 세트에 속합니다.스캐닝 포인터를 검은색 세트로 이동하기만 하면 됩니다.

스캔 포인터가 빈 공간 포인터에 도달하면 회색 세트가 비어 알고리즘이 종료됩니다.

레퍼런스

  • Cheney, C.J. (November 1970). "A Nonrecursive List Compacting Algorithm". Communications of the ACM. 13 (11): 677–678. doi:10.1145/362790.362798. S2CID 36538112.
  • Fenichel, R.R.; Yochelson, Jerome C. (1969). "A LISP garbage-collector for virtual-memory computer systems". Communications of the ACM. 12 (11): 611–612. doi:10.1145/363269.363280. S2CID 36616954.
  • Byers, Rick (2007). "Garbage Collection Algorithms" (PDF). Garbage Collection Algorithms. 12 (11): 3–4.