기본적으로 가비지 컬렉터를 C에 쓰고 싶습니다. 아마도 마크 앤 스위프 알고리즘이나 일반적인 변형 중 하나를 사용하고 싶습니다. 이상적으로, 인터페이스는 다음과 같은 라인을 따라 일 것이다 :플랫폼 독립적 인 가비지 컬렉터를 구현하는 방법은 무엇입니까?
(1) gc_alloc() 메모리를 할당
(2) gc_realloc() 메모리를 재할
(3) gc_run() 가비지 콜렉터를 실행.
Boehm이 개발 한 libgc 쓰레기 수거 라이브러리를 살펴 보았습니다. 하지만 플랫폼에 독립적이지는 않습니다. 방금 다양한 시스템에 포팅되었습니다. 시스템 의존적 인 코드를 포함하지 않는 가비지 컬렉터를 구현하고 싶습니다. 속도는 큰 호가 아닙니다.
제안 사항? 그들이있을 때, 비트 -
불행하게도, 그것은 트랩 비트를 가지고 C 표준의 엄격한 읽기 (unsigned char 제외) 모든 종류의 수 있습니다 C.에서 진정으로 플랫폼에 독립적 인 가비지 컬렉터를 만들기 위해 정말 불가능 잘못된 값, 시스템에서 예외 신호 (예 : 정의되지 않은 동작)가 발생합니다. 포인터에 대해 할당 된 블록을 검사 할 때 특정 메모리 블록에 합법적 인 포인터 값이 들어 있는지 여부를 판단 할 방법이 없으며, 값을 보자 마자 바로 잡아낼 수 있습니다.
int로 포인터를 검사해도 도움이되지 않습니다. 포인터와 호환되는 표현을 사용하려면 int 유형이 필요하지 않습니다. intptr_t은 최신 컴파일러에서만 사용 가능하며 표현도 호환되어야한다고 생각하지 않습니다. int에는 트랩 비트가있을 수 있습니다.
또한 포인터의 정렬 요구 사항을 알지 못합니다. 포인터에 정렬 요구 사항이없는 플랫폼 (즉, 모든 바이트에서 시작할 수 있음)에서는 적절한 바이트 유형 인 memcpy을 모든 바이트에서 중지하고 결과를 검사해야합니다. 오, 그리고 다른 포인터 유형도 다른 표현을 가질 수 있으며, 또한 피할 수없는 것입니다.
하지만 더 큰 문제는 루트 집합을 찾는 것입니다. Bohem GC와 다른 사람들은 정적 데이터뿐만 아니라 스택을 스캔하여 루트 집합에 들어갈 포인터를 찾습니다. OS의 메모리 레이아웃에 대한 지식 없이는 불가능합니다. 따라서 사용자가 루트 집합의 멤버를 명시 적으로 표시해야 할 필요가 있습니다.이 집합은 가비지 수집기의 포인트를 무효화합니다. 명시 적으로 부여됩니다
그래서, 짧은에, 당신은 당신이 할 수 원칙적으로 진정한 휴대용 C.에서 GC를 할 수 없습니다 사용자가
void *의 엄격void *와 호환 표현이 가정 (다른 malloc ations에서 포인터를 합리적으로 즉, < 및 > 일을) 정렬 가정 intptr_t 사용할 수 또는 가정합니다.memcpy 포인터를 건너 뛸 수 있습니다 또한 잠재적 인 포인터의 수를 줄이려고 조사 할 것입니다.이러한 가정을하면 보수적 인 마크 스윕 할당자가 가능해야합니다. 할당이있는 위치에 대한 정보를 보유하고 포인터에 대해 할당 된 블록에서 가능한 모든 정렬 된 포인터 위치를 검사하려면 이진 트리를 사용하십시오. 그러나 명시 적으로 루트 집합을 제공해야 할 필요가 없으므로이 모든 것을 무의미하게 만들 것입니다. 특정 정의되지 않은 개체 집합을 건너 뛸 수 있다는 점을 제외하고는 malloc 및 free이 다시 반복됩니다. 정확히 GC가 제공해야하는 것은 아니지만, 예를 들어 가상 머신의 일부와 같은 장소를 가질 수 있다고 가정합니다.이 경우 루트 세트는 가상 시스템에서 사용할 수있는 정보에서 파생됩니다.
이 모든 것은 오직 보수적 인 GC에만 적용됩니다. 즉, 맹목적으로 작동하여 데이터가있는 위치에서 포인터를 검색합니다. VM에서 작업하는 경우 훨씬 쉽습니다. 포인터를 찾을 수있는 위치를 명시 적으로 나열한 VM의 모든 할당에 대해 통일 된 데이터 유형을 작성할 수 있습니다. 이와 더불어 명시적인 루트 집합을 사용하면 비 보존 GC를 만들 수 있습니다. 이것은 VM 또는 인터프리터를 구축하기에 충분해야합니다.
+1 멋진 답변, 감사합니다. 한 가지 질문 : "C 표준을 엄격하게 읽으면 모든 유형이 허용됩니다 ** (C 제외) ** ..."--- "C 제외"는 무엇을 의미합니까? –
와우, 의미없는 '서명되지 않은 문자'- 어떻게 된 일입니까? :) – bdonlan
걱정할 필요가 없습니다! :-) –
마크 앤 스위프 알고리즘의 경우 실제로 루트 세트에서 도달 할 수있는 개체를 계산해야합니다. (이걸 파고 나서 얼마 전이었습니다 ...)
이것은 GC 관리 객체에 대한 별도의 객체 그래프로 관리 할 수 있습니다.이 작업은 GC 관리 객체에 대한 별도의 객체 그래프로 관리 할 수 있습니다. 관리 오브젝트를 할당하거나 수정할 때마다 그래프로 나타납니다. 관리 객체에 대한 참조 계산을 추가하면 스택 참조에서 직접 도달 할 수있는 객체를 쉽게 계산할 수 있습니다.
이것이 진정한 가비지 컬렉터인지 여부는 논쟁의 여지가 있지만 플랫폼에 독립적으로 작성하는 것이 가능해야합니다.
간단한 의사는 내가 참조 카운팅 및 그래프 관리는 무엇을 의미하는 표시합니다 :
some_object * pObject = gc_alloc(sizeof(some_object));
some_container * pContainer = gc_alloc(sizeof(some_container));
pContainer->pObject = pObject;
/* let the GC know that pContainer has a reference to pObject */
gc_object_reference(pContainer, pObject);
/* a new block of some kind */
{
/* let the GC know we have a new reference for pObject */
some_object * pReference = gc_reference(pObject);
/* do stuff */
...
/* let the GC know that this reference is no longer used */
gc_left_scope(pReference);
}
gc_left_scope(pObject);
gc_run(); /* should not be able to recycle anything, since there still is a live
* reference to pContainer, and that has a reference to pObject
*/
순수 C가 같은 스택에 액세스를 제공하지 않기 때문에 당신은, 플랫폼 독립적 인 GC 뿌리를 찾고 스택을 걸을 수 없다 완전한. –
@bdonlan : 좋은 지적, 이전 질문 중 일부를 끝내고 가장 좋은 대답을 받아 들였습니다. –
@ 스티브가 맞아야합니다. 그러나 자신의 스택 (또는 다른 GC 근원)을 대체 할 수 있다면 - 예. VM/통역사에서 - 가능해야합니다. – delnan