마크콤팩트 알고리즘

컴퓨터 과학에서 마크 컴팩트 알고리즘은 연결할 수 없는 메모리를 회수하는 데 사용되는 가비지 수집 알고리즘의 일종이다.마크-콤팩트 알고리즘은 마크-스위프 알고리즘과 체니의 복사 알고리즘의 조합으로 볼 수 있다.먼저 도달 가능한 물체가 표시된 다음, 압축 단계는 힙 영역의 시작 부분에 도달 가능한(표시된) 물체를 다시 배치한다.압축 가비지 수집은 현대의 JVM, 마이크로소프트의 공용 언어 런타임 및 Glasgow Haskell Compiler에 의해 사용된다.

알고리즘

마크-스위프 알고리즘과 같은 방식으로 힙의 라이브 객체를 표시한 후 힙이 조각조각 나곤 한다.마크 컴팩트 알고리즘의 목표는 메모리에 있는 살아있는 물체를 함께 이동시켜 조각화가 제거되도록 하는 것이다.문제는 모든 포인터를 이동 객체에 올바르게 업데이트하는 것이며, 대부분은 압축 후 새로운 메모리 주소를 갖게 된다.포인터 업데이트 처리 문제는 다른 방식으로 처리된다.

테이블 기반 압축

테이블 기반 알고리즘은 1967년 해든과 와이트에 의해 처음 설명되었다.^[1]이것은 힙에 있는 살아있는 물체의 상대적인 위치를 보존하며, 일정한 양의 오버헤드만 필요로 한다.

압축은 힙의 하단(낮은 주소)에서 상단(높은 주소)으로 진행된다.라이브(즉, 표시된) 객체가 발견되면, 해당 객체는 사용 가능한 첫 번째 낮은 주소로 이동되며, 레코드가 이전 정보의 브레이크 테이블에 추가된다.각 활성 객체에 대해, 브레이크 테이블의 레코드는 압축 전 객체의 원래 주소와 압축 후 원래 주소와 새 주소의 차이로 구성된다.브레이크 테이블은 압축 중인 힙에 저장되지만 사용되지 않은 것으로 표시된 영역에 저장된다.압축이 항상 성공하려면 힙의 최소 개체 크기가 브레이크 테이블 레코드보다 크거나 같아야 한다.

압축이 진행됨에 따라 재배치된 객체는 힙의 아래쪽을 향해 복사된다.결국 어떤 물체는 브레이크 테이블이 차지하는 공간에 복사되어야 할 것이며, 이제는 다른 곳으로 옮겨져야 한다.이러한 브레이크 테이블의 움직임(저자들이 테이블을 굴리는 것)은 이전 기록의 순서를 흐트러뜨리게 하여 컴파션이 완료된 후 브레이크 테이블을 정리해야 한다.브레이크 테이블을 정렬하는 비용은 O(n log n)이며, 여기서 n은 알고리즘의 마크 단계에서 발견된 라이브 객체의 수입니다.

마지막으로, 브레이크 테이블 재배치 레코드는 재배치된 객체 내부의 포인터 필드를 조정하는 데 사용된다.활선 객체는 총 가동 시간 O(n log n) 동안 O(log n) 시간 내에 크기가 n인 소트된 구분 테이블에서 조회할 수 있는 포인터를 검사한다.그런 다음 포인터는 재배치 표에 지정된 양으로 조정한다.

LISP2 알고리즘

O(n log n) 복잡성을 피하기 위해 LISP2 알고리즘은 힙을 통한 3가지 패스를 사용한다.또한 힙 오브젝트에는 가비지 컬렉션 외부에서 사용되지 않는 별도의 포워딩 포인터 슬롯이 있어야 한다.

표준 마킹 후 알고리즘은 다음 3회 패스한다.

1. 라이브 객체의 전달 위치를 계산하십시오.
   • 사용 가능한 실시간 포인터를 추적하고 힙 시작 시 두 포인터를 모두 초기화하십시오.
   • 라이브 포인터가 라이브 개체를 가리킬 경우 해당 개체의 포워딩 포인터를 현재 자유 포인터로 업데이트하고 개체의 크기에 따라 자유 포인터를 늘리십시오.
   • 라이브 포인터를 다음 개체로 이동
   • 라이브 포인터가 힙 끝에 도달하면 종료.
2. 모든 포인터 업데이트
   • 각 라이브 객체에 대해 해당 객체가 가리키는 포워딩 포인터에 따라 포인터를 업데이트하십시오.
3. 객체 이동
   • 각 라이브 객체에 대해 해당 데이터를 전달 위치로 이동하십시오.

이 알고리즘은 힙의 크기에 O(n)이다. 테이블 기반 접근법보다 복잡성이 더 높지만 테이블 기반 접근법의 n은 LISP2 알고리즘처럼 전체 힙 공간의 크기가 아니라 사용된 공간의 크기일 뿐이다.그러나 LISP2 알고리즘은 구현이 더 간단하다.

참고 항목

• 데드코드 제거

참조