마크 콤팩트 알고리즘

컴퓨터 과학에서 마크 콤팩트 알고리즘은 도달 불가능한 메모리를 회수하는 데 사용되는 가비지 수집 알고리즘의 일종입니다.마크 콤팩트 알고리즘은 마크 스위프 알고리즘과 체니의 복사 알고리즘의 조합으로 간주할 수 있다.먼저 도달 가능한 객체가 마킹되고 압축 스텝은 도달 가능한(마킹된) 객체를 힙 영역의 선두로 재배치합니다.압축 가비지 컬렉션은 최신 JVM, 마이크로소프트 공통 언어 런타임 및 글래스고 해스켈 컴파일러에서 사용됩니다.

알고리즘

마크 스위프 알고리즘과 같은 방법으로 힙 내의 라이브오브젝트에 마크를 붙이면 힙이 fragment화되는 경우가 많습니다.마크 콤팩트 알고리즘의 목적은 메모리 내의 라이브 오브젝트를 함께 이동시켜 단편화를 제거하는 것입니다.문제는 이동된 개체에 대한 모든 포인터를 올바르게 업데이트하는 것입니다. 대부분의 포인터는 압축 후 새 메모리 주소를 가집니다.포인터 업데이트 처리 문제는 다양한 방법으로 처리됩니다.

테이블 기반 압축

테이블 기반 알고리즘은 1967년 ^[1]Haddon과 Waite에 의해 처음 설명되었습니다.따라서 힙에서 활성 개체의 상대적 위치가 유지되고 일정한 양의 오버헤드만 필요합니다.

압축은 힙의 맨 아래(낮은 주소)에서 맨 위(높은 주소)로 진행됩니다.라이브(마킹 완료) 오브젝트가 발견되면 해당 오브젝트는 사용 가능한 첫 번째 로우주소로 이동하고 재배치 정보의 브레이크테이블에 레코드가 추가됩니다.각 활성 객체에 대해 브레이크 테이블의 레코드는 압축 전 객체의 원래 주소와 압축 후 원래 주소와 새 주소 간의 차이로 구성됩니다.브레이크 테이블은 압축 중인 힙에 저장되지만 미사용으로 표시된 영역에 저장됩니다.압축이 항상 성공하려면 힙의 최소 개체 크기가 브레이크 테이블 레코드보다 크거나 같아야 합니다.

압축이 진행됨에 따라 재배치된 개체는 힙의 맨 아래쪽으로 복사됩니다.최종적으로 오브젝트를 브레이크테이블이 점유하는 공간으로 복사해야 합니다.이 경우 오브젝트는 다른 곳으로 재배치해야 합니다.이러한 브레이크 테이블 이동(저작자에 의해 테이블 롤링)으로 인해 재배치 레코드가 무질서해지고 압축이 완료된 후 브레이크 테이블을 정렬해야 합니다.브레이크 테이블의 정렬 비용은 O(n log n)입니다.여기서 n은 알고리즘의 마크 단계에서 검출된 활성 객체의 수입니다.

마지막으로 브레이크 테이블 재배치 레코드는 재배치된 객체 내의 포인터 필드를 조정하기 위해 사용됩니다.라이브 오브젝트는 포인터를 검사합니다.브레이크 테이블이 정렬되어 있는 경우 O(log n)시간 내에 크기n의 정렬된 브레이크테이블에서 총 실행시간 O(n log n) 동안 조회할 수 있습니다.그런 다음 재배치 테이블에 지정된 양만큼 포인터가 조정됩니다.

LISP 2 알고리즘

O(n log n)의 복잡성을 피하기 위해 LISP 2 알고리즘은 3개의 다른 경로로 힙을 통과합니다.또한 힙 개체에는 가비지 컬렉션 외부에서 사용되지 않는 별도의 전달 포인터 슬롯이 있어야 합니다.

표준 마킹 후 알고리즘은 다음 3가지 경로로 진행됩니다.

1. 라이브 개체의 전달 위치를 계산합니다.
   • 빈 포인터와 라이브 포인터를 추적하여 힙의 시작까지 모두 초기화합니다.
   • 라이브 포인터가 라이브 객체를 가리키고 있는 경우 해당 객체의 전달 포인터를 현재 빈 포인터로 업데이트하고 객체의 크기에 따라 빈 포인터를 늘립니다.
   • 라이브 포인터를 다음 개체로 이동합니다.
   • 라이브 포인터가 힙의 끝에 도달하면 종료됩니다.
2. 모든 포인터 업데이트
   • 각 활성 개체에 대해 포인터가 가리키는 개체의 전달 포인터에 따라 포인터를 업데이트합니다.
3. 오브젝트 이동
   • 각 활성 개체에 대해 해당 데이터를 전달 위치로 이동합니다.

이 알고리즘은 히프 사이즈에서는 O(n)입니다.테이블 베이스의 어프로치보다 복잡도가 높지만 테이블 베이스의 어프로치의 n은 사용된 공간의 크기일 뿐 LISP2 알고리즘과 같은 힙공간 전체가 아닙니다.다만, LISP2 알고리즘의 실장은 간단합니다.

「 」를 참조해 주세요.

• 데드 코드 제거

레퍼런스