Boehm GC는 C 프로그램에서 어떻게 작동합니까?

Question

나는 Boehm GC를 검사했다. C/C++ 용 GC입니다.

나는 마크 앤 스위프 알고리즘을 알고 있습니다. 내가 호기심을 느끼는 이유는 전체 C 메모리에서 포인터 만 가져 오는 방법입니다. C 메모리에 대한 나의 이해는 단순한 바이트 배열이다. 그것은 가능한 포인터 또는 포인터 메모리의 값을 결정할 수 있습니까?

Answer 1

Boehm GC는 모든 것이 포인터라고 가정하는 보수적 인 수집기입니다. 즉, 힙의 주소 값을 우연히 가지고있는 정수처럼 잘못된 긍정 참조를 찾을 수 있습니다. 결과적으로 일부 블록은 비 보존적인 수집기보다 메모리에 더 오래 머무를 수 있습니다.

Boehm's page 여기에서 설명이다 :

가비지 컬렉터 변형 마크 스위프 알고리즘을 사용한다.

1. 제조 각각의 객체에 연관된 마크 비트를 갖는다 : 개념적으로는 그것을 메모리 할당의 일부로서 종종 수행 네 단계에서 대략 동작한다. 모든 표시가 비트를 지우면 모든 객체가 잠재적으로 도달 할 수 없음을 나타냅니다.
2. 마크 단계 변수의 포인터를 통해 연결할 수있는 모든 개체를 표시합니다. 종종 컬렉터는 포인터의 위치에 대한 실제 정보가 이 아니므로, 정적 데이터 영역, 스택 및 레지스터는 잠재적으로 포인터를 포함하는 것으로 봅니다. 비트 패턴은 힙 내부의 주소를 나타내며 콜렉터가 관리하는 객체는 입니다. 클라이언트 프로그램에서 콜렉터에 대해 힙 오브젝트 레이아웃 정보를 사용할 수없는 경우 에있는 힙 오브젝트는 모두 다시 액세스 할 수있는 변수가됩니다. 마찬가지로 스캔됩니다.
3. 스윕 단계 액세스 할 수없는, 따라서 표시가없는 개체에 대해 힙을 검색하고 적절한 사용 가능 목록으로 다시 반환합니다. 이 은 실제로 별개의 단계는 아닙니다. 심지어 비 증분 모드에서 이것은 일 때 일반적으로 수행됩니다. 은 빈 빈 목록을 발견하는 할당 중에 요청시에 수행됩니다. 따라서 스윕 단계는 페이지를 만지지 않을 가능성이 높습니다. 그 페이지는 어쨌든 과 접촉하지 않았을 것입니다.
4. 마무리 단계 종료에 등록 된 도달 할 수없는 개체는 콜렉터 외부에서 완료되도록 대기열에 포함됩니다.

는 또한 뵘 GC는 마크 앤 스윕 알고리즘 포인트를 시작하고있다 "뿌리"의 집합을 제공 할 필요가 있음을 알아야한다. 스택 및 레지스터는 자동으로 루트입니다. 전역 포인터를 루트로 명시 적으로 추가해야합니다.

---

편집 : 의견에 따르면, 보수적 인 수집가에 대한 일부 의견이 지적되었습니다.콜렉터에 대한 힙 포인터처럼 보이는 정수는 메모리가 해제되지 않도록 할 수 있습니다. 생각만큼 큰 문제는 아닙니다. 프로그램의 대부분의 스칼라 정수는 개수와 크기에 사용되며 상당히 작습니다 (그래서 힙 포인터처럼 보이지 않습니다). 대부분 비트 맵, 문자열, 부동 소수점 데이터 또는 그 종류의 배열을 포함하는 배열에 문제가 발생합니다. Boehm GC를 사용하면 GC_MALLOC_ATOMIC이있는 블록을 할당 할 수 있습니다.이 블록은 수집기에 포인터가 들어 있지 않음을 나타냅니다. gc_typed.h을 보면 블록의 어떤 부분에 포인터가 들어 있는지 지정할 수있는 방법을 찾을 수 있습니다.

즉 보수적 인 수집기의 근본적인 한계는 포인터를 다시 쓰는 것이 안전하지 않기 때문에 수집하는 동안 안전하게 메모리를 이동할 수 없다는 것입니다. 즉, 단편화 감소와 캐시 성능 향상과 같은 압축의 이점을 얻지 못합니다.