가비지 수집기를 구현하는 방법은 무엇입니까?
누구든지 가비지 수집을 구현하는 방법에 대한 좋은 소스를 알려줄 수 있습니까? 나는 lisp와 같은 통역 언어를 만들고 있습니다. 현재 참조 계산을 사용하지만 물론 순환 종속 개체를 해제하는 데 실패합니다.
나는 마크와 스윕, 삼색 마킹, 이동 및 비 움직임, 증분 및 정지 세계에 대해 읽어 왔지만 ... 개체를 세트로 깔끔하게 분리하여 유지하는 가장 좋은 방법이 무엇인지 모르겠습니다. 최소한의 개체 메모리 오버 헤드 또는 점진적으로 작업하는 방법.
참조 계산을 사용하여 순환 참조 감지를 사용하는 일부 언어를 읽었습니다. Boehm과 같이 무료로 구할 수있는 수집가를 사용할 수 있다는 것을 알고 있지만 직접 수행하는 방법을 배우고 싶습니다.
저와 같은 주제에 대한 경험이없는 사람들을위한 일종의 튜토리얼이나 도움이있는 온라인 자료에 감사드립니다.
누구든지 가비지 수집을 구현하는 방법에 대한 좋은 소스를 알려줄 수 있습니까?
가비지 컬렉션에 대한 고급 자료가 많이 있습니다. 쓰레기 수집 핸드북은 중대하다. 그러나 나는 귀중한 기본적인 입문 정보가 거의 없다는 것을 알았 기 때문에 그것에 관한 기사를 썼습니다. 마크 스윕 가비지 수집기 프로토 타이핑은 F #으로 작성된 최소 마크 스윕 GC를 설명합니다. 매우 동시 가비지 콜렉터는 더 진보 된 동시 수집기를 설명합니다. HLVM 은 스레딩을 처리하는 stop-the-world 수집기를 포함하는 내가 작성한 가상 머신입니다.
가비지 수집기를 구현하는 가장 간단한 방법은 다음과 같습니다.
전역 루트를 대조 할 수 있는지 확인하십시오. 힙에 대한 참조를 포함하는 로컬 및 글로벌 변수입니다. 로컬 변수의 경우 범위 기간 동안 섀도우 스택에 푸시합니다.
힙을 순회 할 수 있는지 확인하십시오. 예를 들어 힙의 모든 값은 해당 객체의
Visit모든 참조를 반환 하는 메서드를 구현하는 객체입니다.할당 된 모든 값의 집합을 유지합니다.
할당 된
malloc모든 값 집합에 포인터를 호출 하고 삽입하여 할당합니다.할당 된 모든 값의 총 크기가 할당량을 초과하면 표시를 시작한 다음 단계를 스윕합니다. 이는 도달 가능한 모든 값 세트를 누적하는 힙을 재귀 적으로 순회합니다.
할당 된 값에서 도달 가능한 값을 뺀 세트 차이는 도달 할 수없는 값의 집합입니다.
free할당 된 값 집합에서 호출 및 제거를 반복 합니다.할당량을 모든 할당 된 값의 총 크기의 두 배로 설정합니다.
다음 페이지를 확인하십시오. 많은 링크가 있습니다. http://lua-users.org/wiki/GarbageCollection
delnan이 제안한대로, 저는 매우 순진한 stop-the-world 3 색 마크 및 스윕 알고리즘으로 시작했습니다. 링크 된 목록 노드를 만들어서 세트에 객체를 유지했지만 각 객체에 많은 데이터를 추가합니다 (가상 포인터, 노드에 대한 두 포인터, 색상을 유지하는 하나의 열거 형). 완벽하게 작동합니다. valgrind에서는 메모리가 손실되지 않습니다. :) 여기에서 재활용을위한 무료 목록을 추가하거나, 세계를 중지하는 것이 편리한시기를 감지하는 일종의 것, 증분 접근 방식 또는 특수 할당자를 추가하려고 할 수 있습니다. 조각화 또는 다른 것을 피하십시오. 이러한 작업을 수행하는 방법이나 수행 할 작업에 대한 정보 나 조언을 찾을 수있는 곳을 알려 주시면 (답변 된 질문에 대해 언급 할 수 있는지 여부는 모르겠습니다) 매우 감사하겠습니다. 그동안 Lua의 GC를 확인하겠습니다.
약 400 SLOC에서 C로 Cheney 스타일 복사 가비지 수집기 를 구현했습니다 . 나는 정적으로 형식화 된 언어를 위해 그것을했다. 놀랍게도 더 어려운 부분은 실제로 어떤 것이 포인터이고 어떤 것이 아닌지 정보를 전달하는 것이었다. 동적으로 입력되는 언어에서는 이미 어떤 형태의 태깅 체계를 사용해야하므로이 작업이 더 쉬울 것입니다.
또한 가비지 컬렉션에 대한 표준 책의 새 버전이 나옵니다. Jones, Hosking, Moss의 "가비지 컬렉션 핸드북 : 자동 메모리 관리 기술"이 있습니다. (Amazon UK 사이트에는 2011 년 8 월 19 일이 나와 있습니다.)
내가 아직 언급하지 않은 한 가지는 메모리 핸들의 사용입니다. 각 개체 참조가 해당 개체의 실제 주소를 포함하는 구조에 대한 포인터 인 경우 메모리를 두 배로 늘릴 필요가 없습니다 (Cheney 스타일 복사 알고리즘에서 필요). 메모리 객체에 핸들을 사용하면 특정 루틴이 약간 느려집니다 (객체를 이동할 수있는 일이 발생할 때마다 객체의 메모리 주소를 다시 읽어야 함). 가비지 수집이 예측 가능한 시간에만 발생하는 단일 스레드 시스템의 경우 별로 문제가되지 않으며 특별한 컴파일러 지원이 필요하지 않습니다 (다중 스레드 GC 시스템은 핸들을 사용하든 직접 포인터를 사용하든 컴파일러에서 생성 한 메타 데이터를 요구할 가능성이 높습니다).
핸들을 사용하고 라이브 핸들에 하나의 연결 목록을 사용하는 경우 (재 할당이 필요한 데드 핸들에 대한 연결 목록을 보관하는 데 동일한 저장소를 사용할 수 있음) 각 핸들에 대한 마스터 레코드를 표시 한 후 핸들 목록을 진행할 수 있습니다. , 할당 순서대로 해당 핸들에서 참조하는 블록을 힙의 시작 부분에 복사합니다. 핸들이 순서대로 복사되기 때문에 두 번째 힙 영역을 사용할 필요가 없습니다. 또한 일부 힙 상단 포인터를 추적하여 세대를 지원할 수 있습니다. 메모리를 압축 할 때는 마지막 GC 이후 추가 된 항목을 압축하여 시작하십시오. 충분한 공간이 확보되지 않으면 마지막 레벨 1 GC 이후 추가 된 항목을 압축하십시오. 충분한 공간이 확보되지 않으면 모든 것을 압축하십시오. 마킹 단계는 아마도 모든 세대의 물건에 작용해야 할 것입니다.
실제로 핸들 기반 접근 방식을 사용하면 모든 세대의 항목을 표시하는 경우 원하는 경우 각 GC의 컴퓨팅이 각 세대에서 해제 할 수있는 공간을 전달할 수 있습니다. Gen2에있는 개체의 절반이 죽은 경우 Gen1 수집 빈도를 줄이기 위해 Gen2 수집을 수행하는 것이 좋습니다.
Lisp에서 가비지 컬렉션 구현
LISP 구축 | http://www.lwh.jp/lisp/
Arcadia | https://github.com/kimtg/arcadia
Read Memory Management : Algorithms and Implementations in C / C ++ . 시작하기에 좋은 곳입니다.
포스트 스크립트 인터프리터를 위해 비슷한 작업을하고 있습니다. 내 질문을 통해 더 많은 정보. 나는 간단한 마크 스윕 알고리즘이 시작하기에 좋은 곳이라는 Delnan의 의견에 동의합니다. 모든 컨테이너에 대해 설정 표시, 확인 표시, 지우기 표시 및 반복자를위한 함수가 필요합니다. 한 가지 쉬운 최적화는 새 개체를 할당 할 때마다 표시를 지우고 스윕 중에 표시를 지우는 것입니다. 그렇지 않으면 설정을 시작하기 전에 마크를 지우려면 전체 패스가 필요합니다.
참조 URL : https://stackoverflow.com/questions/6866531/how-to-implement-a-garbage-collector
'Program Tip' 카테고리의 다른 글
| 열거 형 케이스 '…'은 '…'유형의 멤버가 아닙니다. (0) | 2021.01.10 |
|---|---|
| 마이크로 서비스 : 외래 키 관계를 처리하는 방법 (0) | 2021.01.08 |
| 하나 (단일) 문자 최상위 도메인 이름을 가질 수 있습니까? (0) | 2021.01.08 |
| Flask-POST 오류 405 메서드가 허용되지 않음 (0) | 2021.01.08 |
| 대소 문자를 구분하지 않고 JavaScript 속성에 액세스 하시겠습니까? (0) | 2021.01.08 |