가비지 수집 추적

Tracing garbage collection

컴퓨터 프로그래밍에서 가비지 수집 추적은 특정 "루트" 개체로부터 참조 체인으로 어떤 개체에 도달할 수 있는지 추적하여 할당을 해제해야 하는 개체("쓰레기 수집")를 결정하고 나머지는 "쓰레기"로 간주하여 수집하는 것으로 구성되는 자동 메모리 관리의 한 형태다.추적 가비지 수집은 가장 일반적인 유형의 가비지 수집으로, "쓰레기 수집"은 참조 수량과 같은 다른 방법이 아니라 가비지 수집을 추적하는 것을 의미할 정도로 많이, 구현에 사용되는 알고리즘이 많이 있다.

물체의 도달 가능성

비공식적으로, 객체는 직접 또는 다른 도달 가능한 객체의 참조를 통해 프로그램의 적어도 하나의 변수에 의해 참조되는 경우 도달할 수 있다.더 정확히 말하면, 물체는 오직 두 가지 방법으로만 도달할 수 있다.

  1. 고유한 뿌리 집합: 도달할 수 있다고 가정되는 개체.일반적으로 이러한 개체에는 통화 스택의 어느 곳에서든 참조되는 모든 개체(즉, 현재 호출되고 있는 함수의 모든 로컬 변수와 매개 변수)와 전역 변수가 포함된다.
  2. 도달할 수 있는 물체에서 참조되는 모든 것은 그 자체로 도달할 수 있다; 더 공식적으로, 도달할 수 있는 것은 전이성 폐쇄다.

프로그램이 물체를 사용하는 마지막 시간이 해당 물체가 환경 범위 밖으로 떨어지기 훨씬 전일 수 있는 한 "쓰레기"의 도달 가능성 정의는 최적이 아니다.때때로 구문론적 쓰레기, 프로그램이 도달할 수 없는 물체, 그리고 의미론적 쓰레기, 프로그램이 실제로 다시는 사용하지 않을 물체 사이에 구별된다.예를 들면 다음과 같다.

오브젝트 x = 새로운 푸(); 오브젝트 y = 새로운 바(); x = 새로운 쿠우시(); /* 이 시점에서, 우리는 Foo 물체가 * 원래 x에 할당되지 않음 * 접근: 그것은 통사적 쓰레기다. */  /* 다음 블록에서 의미론적 쓰레기가 될 수 있다. * 하지만 x.check_something이 돌아올 때까지는 알 수 없다. * 어떤 값 -- 만약 그것이 조금이라도 돌아온다면. */ 만일 (x.check_something()) {     x.do_something(y); } 시스템.퇴장하다(0);

의미론적 가비지를 정확하게 식별하는 문제는 부분적으로 해독이 가능한 것으로 쉽게 나타날 수 있다: 개체 X를 할당하고 임의 입력 프로그램 P를 실행하며, P가 완료되는 경우에만 의미론적 가비지 수집기를 사용하여 중지 문제를 해결하는 프로그램이다.비록 의미론적 쓰레기 감지를 위한 보수적인 경험적 접근방식이 여전히 활발한 연구 영역으로 남아있지만, 본질적으로 모든 실제적인 쓰레기 수집가들은 통사적 쓰레기에 초점을 맞추고 있다.[citation needed]

이 접근법의 또 다른 복잡성은 참조 유형과 박스화되지 않은 값 유형을 모두 가진 언어에서 가비지 수집기가 어떤 스택의 변수나 객체의 필드가 정규 값이고 어떤 변수가 참조인지 구별할 수 있어야 한다는 것이다. 메모리에서는 정수와 참조가 유사하게 보일 수 있다.그러면 쓰레기 수거업자는 원소를 참조로 취급하고 그 원소를 따를 것인지, 아니면 원시적인 값인지 알 필요가 있다.한 가지 일반적인 해결책은 태그가 붙은 포인터의 사용이다.

강하고 약한 참조 자료

가비지 수집기는 루트 집합에서 직접 또는 간접적으로 이들을 가리키는 참조가 없는 개체만 회수할 수 있다.그러나 일부 프로그램에는 약한 참조가 필요하며, 이는 개체가 존재하는 한 사용할 수 있어야 하지만 수명이 연장되어서는 안 된다.약한 참고문헌에 대한 논의에서 보통 참고문헌은 강한 참고문헌으로 불리기도 한다.객체에 대한 일부 약한 참조가 남아 있더라도 강력한(즉, 일반적인) 참조가 없는 경우 해당 객체는 쓰레기 수집 대상이 된다.

약한 참조는 단순히 쓰레기 수집가가 신경쓰지 않는 물체에 대한 어떤 포인터만이 아니다.이 용어는 일반적으로 객체가 안전한 값에 도달하기 때문에(일반적으로) 객체가 사라진 후에도 안전하게 사용할 수 있는 특수 참조 객체의 적절하게 관리되는 범주를 위해 예약된다.null가비지 수집기에 알려지지 않은 안전하지 않은 참조는 단순히 물체가 이전에 있었던 주소를 계속 참조함으로써 매달려 있을 것이다.이것은 약한 언급이 아니다.

일부 구현에서는 취약한 참조가 하위 범주로 나뉜다.예를 들어, 자바 가상 머신은 세 가지 형태의 약한 참조, 즉 소프트 레퍼런스,[1] 팬텀 레퍼런스,[2] 정기적인 약한 레퍼런스를 제공한다.[3]부드럽게 참조되는 개체는 가비지 수집기가 프로그램 메모리가 부족하다고 판단하는 경우에만 회수할 수 있다.소프트 레퍼런스나 일반적인 약한 레퍼런스와는 달리 팬텀 레퍼런스는 자신이 참조하는 객체에 대한 액세스를 제공하지 않는다.대신 팬텀 참조는 참조된 객체가 팬텀에 도달할 수 있게 되었을 때 가비지 수집기가 프로그램을 통지할 수 있도록 하는 메커니즘이다.물체는 여전히 메모리에 있고 팬텀 참조에 의해 참조되지만 최종 결정자가 이미 실행된 경우 팬텀에 도달할 수 있다.비슷하게, 마이크로소프트.NET는 약한 참조의 두 가지 하위 범주,[4] 즉 긴 취약 참조(트랙 부활)와 짧은 취약 참조를 제공한다.

약한 컬렉션

추적 기능이 약한 데이터 구조도 설계할 수 있다.예를 들어, 약한 해시 테이블이 유용하다.일반 해시 테이블처럼 약한 해시 테이블은 개체 쌍 간의 연관성을 유지하며, 여기서 각 쌍은 키와 값으로 이해된다.그러나 해시 테이블은 실제로 이들 객체에 대해 강한 참조를 유지하지 않는다.특수 동작은 키나 값 또는 둘 다 가비지가 될 때 발생한다: 해시 테이블 항목이 자연적으로 삭제된다.해시 테이블과 같이 약한 키(값 참조는 보통, 강한 참조)만 있거나 약한 값(키 참조는 강한 참조)만 있는 추가 정비가 존재한다.

약한 해시 테이블은 프로그램의 어떤 물체도 더 이상 언급되지 않을 경우(연관 해시 테이블 제외) 여전히 쓰레기가 될 수 있도록 개체 간의 연결을 유지하는 데 중요하다.

그러한 목적을 위해 정규 해시 테이블을 사용하면 "논리적 메모리 누수"로 이어질 수 있다. 즉, 프로그램이 필요하지 않고 사용하지 않을 수 있는 도달 가능한 데이터의 축적이다.

기본 알고리즘

추적 수집기는 작업 메모리 세트를 추적하기 때문에 그렇게 불린다.이 쓰레기 수집가들은 주기적으로 수집을 한다.메모리 관리자가 할당 요청을 충족할 수 있는 여유 메모리가 충분하지 않을 때 사이클이 트리거되는 것이 일반적이다.그러나 사이클은 종종 돌연변이가 직접 요청하거나 시간 스케줄에 따라 실행될 수 있다.원래의 방법은 전체 메모리 세트를 여러 번 만지는 순진한 마크 앤 스윕을 포함한다.

네이브 마크 앤 스위프

8개의 물체가 들어 있는 힙에 작용하는 순진한 마크 앤 스윕.화살표는 객체 참조를 나타낸다.원은 물체 자체를 나타낸다.개체 #1, #2, #3, #4, #6은 루트 집합에서 강하게 참조된다.한편, #5, #7, #8 물체는 루트 집합으로부터 직접 또는 간접적으로 강하게 참조되지 않으므로, 쓰레기라고 할 수 있다.

순진한 마크앤스위프 방식에서 메모리의 각 물체는 가비지 수집용으로만 예약된 플래그(일반적으로 단일 비트)를 가지고 있다.이 플래그는 수집 주기 동안만 제외하고 항상 지워진다.

첫 번째 단계는 전체 '뿌리 집합'을 나무로 가로지르며, 뿌리가 가리키는 각 개체를 '사용 중'으로 표시하는 마크 단계다.이러한 물체가 가리키는 등의 모든 물체도 표시되므로 루트 세트를 통해 도달할 수 있는 모든 물체가 표시된다.

두 번째 단계인 스위프 단계에서는 모든 메모리가 처음부터 끝까지 스캔되어 모든 자유 블록 또는 사용된 블록을 검사한다. '사용 중'으로 표시되지 않은 블록은 어떤 루트로도 도달할 수 없으며, 그 메모리는 자유롭다.사용 중으로 표시된 객체의 경우, 사용 중 플래그가 지워져 다음 사이클을 준비한다.

이 방법에는 몇 가지 단점이 있는데, 가장 주목할 만한 점은 수집하는 동안 전체 시스템을 중지해야 한다는 것이다. 작업 세트의 돌연변이는 허용되지 않는다.이로 인해 프로그램이 주기적으로(일반적으로 예측 불가능하게) '동결'되어 일부 실시간 및 시간에 중요한 애플리케이션이 불가능해질 수 있다.또한 전체 작동 메모리를 검사해야 하며, 대부분은 두 번 검사해야 하며, 이는 페이징된 메모리 시스템에 잠재적으로 문제를 일으킬 수 있다.

삼색 표시

8개의 객체가 있는 힙의 3색 표시 예제.흰색, 회색, 검은색 물체는 각각 연회색, 노란색, 파란색으로 표현된다.

이러한 성능 문제 때문에 대부분의 현대적인 추적 쓰레기 수집기는 삼색 표시 추상화의 일부 변형을 구현하지만, 단순한 수집기(표시와 줍기 등)는 이러한 추상화를 명시적으로 하지 않는 경우가 많다.삼색 마킹은 아래 설명된 대로 작동한다.

흰색, 검은색, 회색 세트가 생성된다.

  • 화이트 세트 또는 사형 선고 세트는 그들의 기억을 재활용하기 위한 후보 물체들의 집합이다.
  • 검정색 세트는 흰색 세트에 있는 물체에 대한 발신 참조가 없으며 뿌리로부터 도달할 수 있는 물체 집합이다.검은색 세트에 있는 물체는 수집 대상이 아니다.
  • 회색 세트는 뿌리에서 도달할 수 있는 모든 물체를 포함하지만 "흰색" 물체에 대한 참조는 아직 스캔되지 않았다.뿌리부터 닿을 수 있는 것으로 알려져 있어 쓰레기 수거가 불가능하고 스캔을 한 뒤 블랙 세트에 들어가게 된다.

많은 알고리즘에서, 처음에 검은색 세트는 비어있는 것으로 시작하고, 회색 세트는 루트에서 직접 참조되는 객체들의 집합이며, 흰색 세트는 다른 모든 객체를 포함한다.기억 속에 있는 모든 물체는 항상 정확히 세 세트 중 하나에 있다.알고리즘은 다음과 같이 진행된다.

  1. 회색 세트에서 개체를 선택하고 검은색 세트로 이동하십시오.
  2. 참조하는 각 흰색 개체를 회색 세트로 이동하십시오.이것은 이 물체나 그것이 참조하는 어떤 물체도 가비지 수집될 수 없음을 보장한다.
  3. 회색 세트가 비워질 때까지 마지막 두 단계를 반복하십시오.

회색 세트가 비어 있으면 스캔이 완료된다. 검은색 물체는 뿌리에서 닿을 수 있는 반면 흰색 물체는 그렇지 않고 가비지를 수집할 수 있다.

뿌리에서 즉시 도달할 수 없는 모든 물체는 흰색 세트에 추가되고 물체는 흰색에서 회색, 회색에서 검은색으로만 이동할 수 있으므로 알고리즘은 중요한 불변성(검은색 물체는 흰색 물체를 참조하지 않음)을 보존한다.이렇게 하면 회색 세트가 비었을 때 흰색 객체가 해제될 수 있다.이것을 삼색 불변제라고 한다.알고리즘의 일부 변동은 이 불변성을 보존하지 않지만 모든 중요한 특성이 보유하는 수정된 형식을 사용한다.

3색 방법은 중요한 장점이 있다. 즉, 상당 기간 시스템을 중단하지 않고 "즉시" 수행할 수 있다.이것은 물체가 할당되는 대로 표시하고 돌연변이 중에 다양한 세트를 유지함으로써 이루어진다.이 시스템은 세트의 크기를 모니터링함으로써 필요에 따라 쓰레기 수거를 정기적으로 수행할 수 있다.또한 각 사이클에서 전체 작업 세트를 만질 필요가 없다.

구현 전략

이동 대 비이동

일단 도달할 수 없는 세트가 결정되면, 쓰레기 수집기는 단순히 도달할 수 없는 물체를 방출하고 다른 모든 것을 그대로 두거나, 도달 가능한 물체의 일부 또는 전부를 새로운 메모리 영역으로 복사하여 필요에 따라 그 물체에 대한 모든 참조를 업데이트할 수 있다.이를 각각 "움직이지 않는" 및 "움직이는" (또는 "비작동" 및 "작동") 쓰레기 수집기라고 한다.

처음에 이동 알고리즘은 각 사이클마다 훨씬 더 많은 작업이 필요한 것처럼 보이기 때문에 움직이지 않는 알고리즘에 비해 비효율적으로 보일 수 있다.그러나 이동 알고리즘은 가비지 수집 주기 자체와 프로그램 실행 중에 다음과 같은 몇 가지 성능상의 이점을 제공한다.

  • 죽은 물체에 의해 해방된 공간을 되찾기 위해 추가적인 작업이 필요하지 않다. 도달 가능한 물체가 이동된 전체 메모리 영역은 자유 공간으로 간주될 수 있다.이와는 대조적으로, 이동하지 않는 GC는 접속할 수 없는 각 물체를 방문하여 점유한 메모리를 사용할 수 있다는 것을 기록해야 한다.
  • 마찬가지로, 새로운 물체는 매우 빨리 할당될 수 있다.일반적으로 이동하는 GC에 의해 메모리의 큰 인접 영역이 제공되기 때문에, '자유 메모리' 포인터를 증가시키는 것만으로 새로운 개체를 할당할 수 있다.이동하지 않는 전략은 시간이 흐른 후 심하게 조각난 힙으로 이어질 수 있으며, 새 개체를 할당하기 위해 사용 가능한 소형 메모리 블록의 "무료 목록"을 값비싼 상담을 필요로 한다.
  • 적절한 통과 순서(예: 목록 조합의 경우 cdr-first)가 사용되는 경우, 개체는 메모리에서 참조하는 개체와 매우 가깝게 이동될 수 있으므로 동일한 캐시 라인 또는 가상 메모리 페이지에 위치할 가능성이 높아진다.이는 이러한 참조를 통해 이러한 객체에 대한 접근 속도를 현저하게 높일 수 있다.

움직이는 가비지 수집기의 한 가지 단점은 가비지 수집 환경에서 관리되는 참조를 통해서만 접근을 허용하고 포인터 산술은 허용하지 않는다는 것이다.이는 가비지 수집기가 그 물체를 움직이면 물체에 대한 어떤 포인터도 무효가 되기 때문이다(그 포인터들은 매달려 있는 포인터들이 된다).네이티브 코드와의 상호운용성을 위해, 가비지 수집기는 객체 내용을 가비지 수집 메모리 영역 밖의 위치에 복사해야 한다.다른 접근방식은 객체를 메모리에 고정시켜 가비지 수집기가 객체를 이동하지 못하게 하고 메모리를 네이티브 포인터와 직접 공유(그리고 포인터 산술도 허용할 수 있음)[5]하는 것이다.

복사 대 마크 앤 스윗 대 마크 앤 스윗 대 마크 앤 스윗

수집기는 움직이는지 움직이지 않는지 간에 차이가 있을 뿐만 아니라 수집 주기 동안 흰색, 회색 및 검은색 객체 세트를 처리하는 방법에 따라 분류할 수 있다.

가장 직접적인 접근법은 1969년으로 거슬러 올라가는 반공간 수집기다.이 움직이는 수집기에서 메모리는 동일한 크기의 "공간으로부터"와 "공간까지"로 분할된다.처음에 객체는 가득 차서 수집 주기가 트리거될 때까지 "공간"에 할당된다.사이클이 시작될 때, "공간으로"는 "공간으로부터"가 되고, 그 반대도 "공간으로부터"가 된다.루트 집합에서 도달할 수 있는 객체는 "공간에서 공간까지" 복사된다.이 물체들은 차례로 스캔되고, 그들이 가리키는 모든 물체들은 "공간으로" 복사된다, 도달 가능한 모든 물체들이 "공간으로" 복사될 때까지.프로그램이 계속 실행되면 새 개체는 다시 한 번 가득 차서 프로세스가 반복될 때까지 "공간으로" 할당된다.

이 방식은 매우 간단하지만 객체 할당에는 하나의 반공간만 사용되기 때문에 메모리 사용량은 다른 알고리즘에 비해 2배 높다.이 기술은 또한 스톱 앤드 카피로도 알려져 있다.체니 부통령의 알고리즘은 세미 스페이스 컬렉터(semi-space collector)의 개선이다.

마크 앤 스위프 가비지 수집기는 흰색인지 검정색인지 기록할 수 있는 각 물체를 약간 또는 두 개씩 보관한다.회색 세트는 별도의 목록으로 유지되거나 다른 비트를 사용한다.수집 주기("표시" 단계) 동안 참조 트리가 통과되면 이러한 비트는 수집기에 의해 조작된다.기억 영역의 마지막 "스위프"는 흰 물체를 자유롭게 한다.마크와 스위프 전략은 일단 사형 집단이 결정되면 이동 또는 이동하지 않는 수집 전략을 추구할 수 있다는 장점이 있다.이 전략의 선택은 가용 메모리가 허용하는 대로 런타임에 이루어질 수 있다.목록/추가 비트 때문에 모든 물체가 작은 숨겨진 메모리 비용을 가지고 있기 때문에 소량씩 "빌로잉"하는 단점이 있다.수집기가 할당을 처리할 경우 할당 데이터 구조에서 사용되지 않은 비트를 잠재적으로 사용할 수 있기 때문에 이 문제는 다소 완화될 수 있다.또는 이 "숨겨진 메모리"는 Tagged 포인터를 사용하여 메모리 비용을 CPU 시간과 교환함으로써 제거할 수 있다.그러나 마크와 스윕은 애당초 외부 할당자와 쉽게 협력하는 유일한 전략이다.

마크 앤 스윕과 같이 가비지 수집기를 스위프하지 않는 표시는 흰색인지 검정색인지 기록하기 위해 각 개체와 함께 약간 유지되며, 회색 세트는 별도의 목록으로 유지되거나 다른 비트를 사용한다.여기에는 두 가지 주요한 차이점이 있다.첫째, 흑백은 마크나 스위프 컬렉터와는 다른 것을 의미한다."표시 및 스위프하지 않음" 수집기에서, 도달할 수 있는 모든 물체는 항상 검은색이다.물체는 할당될 때 검은색으로 표시되며, 도달할 수 없게 되더라도 검은색으로 유지된다.흰색 개체는 사용되지 않는 메모리이며 할당될 수 있다.둘째, 흑백 비트의 해석이 변할 수 있다.처음에 흑백 비트는 (0=흰색, 1=검은색)을 가질 수 있다.할당 작업에서 사용 가능한(흰색) 메모리를 찾지 못하면 모든 객체가 사용됨(검은색)으로 표시됨을 의미한다.그런 다음 검은색/흰색 비트의 감각이 반전된다(예: 0=검은색, 1=흰색).모든 것이 하얗게 된다.이것은 도달할 수 있는 물체가 검은색이라는 불변성을 순간적으로 깨뜨리지만, 다시 검은색으로 표시하기 위해 즉시 완전한 표시 단계가 뒤따른다.일단 이것이 끝나면, 도달할 수 없는 모든 기억은 하얀색이다."스위프" 단계는 필요하지 않다.

마크와 스윕 안 함 전략은 할당자와 수집기 사이의 협력이 필요하지만 할당 포인터당 1비트(어쨌든 대부분의 할당 알고리즘이 필요로 함)만 요구하기 때문에 믿을 수 없을 정도로 공간 효율적이다.그러나 대부분의 경우 메모리의 많은 부분이 잘못 검정색으로 표시되고(사용됨) 메모리 사용량이 적은 시간에는 시스템에 리소스를 반환하기 어렵기 때문에(다른 할당자, 스레드 또는 프로세스에 의해 사용됨) 이러한 상승은 다소 완화된다.

따라서 마크와 스윕하지 않는 전략은 마크와 스윕의 기복과 스톱과 카피 전략 사이의 절충안으로 볼 수 있다.

General GC(Ephemeral GC)

많은 프로그램에서 가장 최근에 만들어진 개체도 빨리 도달할 수 없게 될 가능성이 가장 높은 개체(유아 사망률 또는 세대 가설로 알려져 있음)라는 것이 경험적으로 관찰되었다.세대 GC(일명 후 삭제 GC)는 물체를 세대로 나누고, 대부분의 사이클에서 일부 세대의 물체만 초기 흰색(콘솔된) 세트에 배치한다.더욱이, 런타임 시스템은 참조의 작성과 덮어쓰기를 관찰함으로써 참조가 세대를 가로지르는 시기에 대한 지식을 유지한다.가비지 수집기가 실행될 때, 초기 흰색 세트의 일부 물체가 전체 참조 트리를 통과하지 않고도 연결할 수 없다는 것을 증명하기 위해 이 지식을 사용할 수 있을 것이다.세대 가설이 유지된다면, 이것은 여전히 도달할 수 없는 대부분의 물체를 회수하면서 훨씬 더 빠른 수집 주기를 초래한다.

이 개념을 구현하기 위해, 많은 세대 쓰레기 수집가들은 개체 연령에 따라 별도의 기억 영역을 사용한다.영역이 가득 차면 그 안에 있는 물체는 구세대(들)의 참조를 루트로 사용하여 추적된다.이것은 대개 세대에 있는 대부분의 개체들이 (가설에 의해) 수집되어 새로운 개체들을 할당하는 데 사용될 수 있게 한다.컬렉션이 많은 객체를 수집하지 않는 경우(예를 들어 프로그램이 유지하고자 하는 새 객체의 많은 컬렉션을 계산했기 때문에 가설이 유지되지 않는 경우), 오래된 메모리 영역에서 참조되는 생존 객체의 일부 또는 전부를 다음으로 높은 영역으로 승격하고, 그러면 전체 영역을 덮어쓸 수 있다.새 물건으로 장식하다이 기법은 한 번에 한 지역만 쓰레기 수거가 일반적으로 필요한 것이기 때문에 매우 빠른 증분 쓰레기 수거를 허용한다.

운가르의 고전적인 세대 청소부에게는 두 세대가 있다.'새로운 공간'이라 불리는 최연소 세대를 새로운 물체가 만들어지는 커다란 '에덴'과 과거의 생존 공간, 미래의 생존 공간 두 개의 작은 '생존 공간'으로 나뉜다.새로운 공간에서 객체를 참조할 수 있는 구세대 객체는 "기억 세트"에 보관된다.각각의 스캐빈지에서, 새로운 공간에 있는 물체들은 기억된 세트의 뿌리로부터 추적되어 미래의 생존자 공간으로 복사된다.미래의 생존공간이 메워지면 맞지 않는 물체는 낡은 공간으로 승격되는데, 이를 '테닝(tenering)'이라고 한다.스캐빈저 끝에는 미래의 생존공간에 일부 물체가 상주하며 에덴과 과거의 생존공간은 텅 비어 있다.그런 다음 미래의 생존자 공간과 과거의 생존자 공간이 교환되고 프로그램은 에덴의 객체를 할당하면서 계속된다.운가르의 원래 체계에서 에덴은 각각의 생존 공간보다 5배나 크다.

세대별 쓰레기 수거는 경험적 접근법이며, 접속할 수 없는 일부 물체는 각 사이클마다 매립되지 않을 수 있다.따라서 사용 가능한 모든 공간을 회수하기 위해 전체 표시를 수행하고 가비지 수집을 스위프하거나 복사해야 하는 경우가 있을 수 있다.사실, 최신 프로그래밍 언어(Java 및 와 같은)를 위한 런타임 시스템.NET Framework)는 일반적으로 지금까지 설명한 다양한 전략의 일부를 혼합하여 사용한다. 예를 들어, 대부분의 수집 주기는 몇 세대에 대해서만 볼 수 있는 반면 때로는 마크 앤 스윕을 수행하기도 하며, 단편화를 방지하기 위해 전체 복사를 수행하는 경우는 더 드물다."최소 주기"와 "주요 주기"라는 용어는 이러한 서로 다른 수준의 수집기 공격성을 설명하기 위해 사용되기도 한다.

세계 정지 대 증분 대 동시

단순 중지-세상 쓰레기 수집기는 수집 주기를 실행하기 위해 프로그램의 실행을 완전히 중지하여 수집기가 실행되는 동안 새 개체가 할당되지 않고 개체가 갑자기 연결되지 않도록 보장한다.

이는 수집 주기가 실행되는 동안 프로그램이 유용한 작업을 수행할 수 없다는 단점을 가지고 있다(때로는 "당혹적인 일시 중지"라고도 함).[6]따라서 쓰레기 수거는 주로 비연동 프로그램에 적합하다.구현이 간단하면서도 점진적인 쓰레기 수거 속도보다 빠르다는 게 장점이다.

증분 및 동시 쓰레기 수집기는 그들의 작업을 주 프로그램의 활동과 상호 연계시킴으로써 이러한 혼란을 줄이기 위해 설계된다.증분적 가비지 수집기는 각 단계 사이에 프로그램 실행이 허용되고 때로는 일부 단계 동안 가비지 수집 주기를 개별 단계로 수행한다.동시 가비지 수집기는 프로그램의 실행 스택이 스캔될 때를 제외하고는 프로그램 실행을 전혀 중지하지 않는다.그러나 증분 단계의 합계는 하나의 일괄 처리 가비지 수집 패스를 완료하는 데 더 오랜 시간이 걸리기 때문에 이러한 가비지 수집기는 총 처리량을 낮출 수 있다.

주 프로그램이 가비지 수집기를 방해하지 않도록 하기 위해, 그리고 그 반대의 경우를 위해 이러한 기법으로 세심한 설계가 필요하다. 예를 들어, 프로그램이 새로운 객체를 할당해야 할 때, 런타임 시스템은 수집 주기가 완료될 때까지 가비지 수집기에게 가비지 수집기를 일시 중단해야 하거나, 또는 어떤 식으로든 가비지 수집기에게 가비지 수집기가 존재한다는 사실을 통지해야 할 수 있다.새롭고 손이 닿을 수 있는 물체

정밀한 대 보수적이고 내부적인 포인터

일부 수집기는 물체의 모든 포인터(참조)를 정확하게 식별할 수 있다. 이러한 포인터(참조)는 정밀(정확하거나 정확한) 수집기라고 하며, 그 반대는 보수적이거나 부분적으로 보수적인 수집기라고 한다.보수적인 수집가들은 만약 그것이 포인터로 해석되어 할당된 객체를 가리킬 경우 메모리의 비트 패턴이 포인터가 될 수 있다고 가정한다.보수적인 수집기는 잘못된 긍정을 발생시킬 수 있으며, 이때 잘못된 포인터 식별으로 인해 사용되지 않은 메모리가 해제되지 않는다.프로그램이 포인터로서 쉽게 잘못 식별될 수 있는 많은 데이터를 처리하지 않는 한, 이것은 실제로 항상 문제가 되는 것은 아니다.잘못된 긍정은 유효 메모리 주소의 범위가 64비트 값 범위의 극히 일부인 경향이 있기 때문에 일반적으로 32비트 시스템보다 64비트 시스템에서 덜 문제가 된다.따라서 임의의 64비트 패턴은 유효한 포인터를 모방할 가능성이 낮다.예를 들어 XOR 연결 목록을 사용하는 것과 같이 포인터가 "숨겨져 있는" 경우에도 잘못된 음성이 발생할 수 있다.정밀한 수집기의 실용성 여부는 대개 해당 프로그래밍 언어의 유형 안전 속성에 따라 달라진다.보수적인 쓰레기 수집가가 필요한 예로는 C언어가 있는데, C언어는 타이프(비보이드) 포인터를 타입이 아닌(Void) 포인터로 주조할 수 있으며, 그 반대의 경우도 마찬가지다.

관련 문제는 개체 내의 필드에 대한 내부 포인터 또는 포인터와 관련이 있다.언어의 의미론이 내부 포인터를 허용한다면, 동일한 물체의 일부를 언급할 수 있는 많은 다른 주소가 있을 수 있으며, 이것은 물체가 쓰레기인지 아닌지를 결정하는 것을 복잡하게 만든다.예를 들어, C++ 언어는 다중 상속이 기본 객체에 다른 주소를 갖는 포인터를 유발할 수 있다.촘촘히 최적화된 프로그램에서는 개체 자체에 대한 해당 포인터가 레지스터에서 덮어쓰여졌을 수 있으므로, 그러한 내부 포인터를 스캔할 필요가 있다.

퍼포먼스

대기 시간과 처리량 모두 가비지 수집기의 추적 성능은 구현, 작업량 및 환경에 따라 크게 달라진다.특히 임베디드 시스템 등 메모리 제약이 심한 환경에서 순진하게 구현하거나 사용하면 다른 방법에 비해 성능이 매우 떨어지는 반면 메모리가 풍부한 환경에서 정교한 구현과 사용은 우수한 성능을 얻을 수 있다.[citation needed]

처리량 측면에서, 그 성격에 따라 추적하려면 일부 암묵적인 런타임 오버헤드가 필요하지만, 어떤 경우에는 할당 또는 수집당 하나의 지침보다 더 낮은 상각 비용이 극히 낮아서 스택 할당을 능가하는 경우도 있다.[7]수동 메모리 관리는 메모리의 명시적 자유화로 인한 오버헤드가 필요하며, 참조 카운트는 기준 카운트의 증감 및 감소로부터 오버헤드가 발생하며, 카운트가 오버플로 또는 0으로 떨어졌는지 점검한다.[citation needed]

대기 시간 측면에서 단순 정지 쓰레기 수집기는 임의의 시간에 발생할 수 있고 임의의 시간이 걸릴 수 있는 가비지 수집을 위한 프로그램 실행을 일시 중지하여 실시간 컴퓨팅, 특히 임베디드 시스템, 인터렉티브 사용에 적합하지 않거나 지연 시간이 낮은 다른 상황을 우선시한다.그러나 증분형 쓰레기 수집기는 하드 실시간 보증을 제공할 수 있으며, 개인용 컴퓨터와 같이 유휴 시간이 빈번하고 여유 메모리가 충분한 시스템에서는 쓰레기 수집을 유휴 시간으로 예약할 수 있으며 대화형 성능에 최소한의 영향을 미칠 수 있다.수동 메모리 관리(C++와 같이)와 레퍼런스 카운팅은 대형 데이터 구조와 그 모든 자식들을 할당 해제할 경우 임의로 장시간 일시 정지하는 유사한 문제를 가지고 있지만, 이러한 문제는 가비지 수집에 의존하지 않고 정해진 시간에만 발생한다.[citation needed]

수동 힙 할당
  • 충분한 크기의 베스트/퍼스트핏 블록을 찾다
  • 무료 목록 유지 관리
쓰레기 수거
  • 도달할 수 있는 물체를 찾다
  • 이동 수집기를 위해 도달할 수 있는 개체를 복사하다.
  • 증분 수집기의 읽기/쓰기 장벽
  • 이동하지 않는 수집기에 대한 베스트/퍼스트핏 블록 및 자유 목록 유지 관리 검색

두 사건은 상황에 따라 행동이 달라지기 때문에 직접 비교하기는 어렵다.예를 들어, 쓰레기 수거 시스템의 최선의 경우, 할당은 포인터를 증가시킬 뿐이지만, 수동 힙 할당의 경우, 할당자는 특정 크기의 프리랜서를 유지하며, 할당은 포인터를 따라야만 한다.그러나 이러한 크기 분리는 일반적으로 외부 단편화를 크게 일으키며, 이는 캐시 거동에 악영향을 미칠 수 있다.가비지 수집 언어로 메모리 할당은 단순히 포인터를 증가시키는 것이 아니라 장면 뒤의 힙 할당을 사용하여 구현될 수 있으므로 위에 열거된 성능 장점이 반드시 이 경우에 적용되는 것은 아니다.가장 눈에 띄는 임베디드 시스템인 일부 상황에서는 메모리 풀을 미리 할당하고 할당/할당하기 위해 사용자 정의 경량화된 체계를 사용함으로써 가비지 수집과 힙 관리 오버헤드를 모두 방지할 수 있다.[8]

쓰기 장벽의 오버헤드는 데이터를 한 번만 구성하고 변경하지 않는 기능형 프로그램보다 기존 데이터 구조에 포인터를 자주 쓰는 명령형 프로그램에서 더 두드러질 가능성이 높다.

쓰레기 수거의 일부 발전은 성능 문제에 대한 반응으로 이해될 수 있다.초기 수집가들은 세계의 수집가들을 멈추게 했지만, 이 접근방식의 성능은 인터랙티브 애플리케이션에서 주의를 산만하게 했다.증분 수집은 이러한 중단을 피했지만 장벽의 필요성 때문에 효율성이 저하되는 비용을 부담했다.세대 수집 기법은 성능을 높이기 위해 정지 세계 수집기와 증분 수집기 둘 다와 함께 사용된다. 단점은 일부 쓰레기는 정상보다 더 오래 검출되지 않는다는 것이다.

결정론

  • 가비지 수집을 추적하는 것은 객체 최종화의 시기에 결정론적이지 않다.쓰레기 수거 대상이 되는 물체는 대개 결국 청소되지만 언제(또는 설사) 그런 일이 일어날지는 장담할 수 없다.네트워크 연결 닫기, 장치 해제 또는 파일 닫기 등 외부에서 볼 수 있는 프로그램 동작이 릴리스인 비메모리 리소스에 개체가 묶여 있을 때 프로그램 정확성에 대한 문제다.이와 관련하여 결정론을 제공하는 한 가지 쓰레기 수거 기법은 참조 계수다.
  • 가비지 수집은 처리 중인 알고리즘과 상관없는 프로그램의 실행에 일시 중단을 잠재적으로 도입함으로써 실행 시간에 비결정적인 영향을 미칠 수 있다.가비지 수집을 추적할 때 새 개체를 할당하라는 요청은 때때로 빠르게 반환될 수 있으며 다른 경우에는 긴 가비지 수집 주기가 트리거될 수 있다.참조 계수에서, 일반적으로 객체의 할당이 빠른 반면, 참조의 감소는 비결정론적이다. 왜냐하면 참조가 0에 도달할 수 있기 때문에, 해당 객체가 보유하고 있는 다른 객체의 참조 카운트를 감소시키는 재귀가 발생할 수 있기 때문이다.

실시간 가비지 수집

가비지 수집은 일반적으로 비결정론적이지만, 하드 실시간 시스템에서는 사용이 가능하다.실시간 가비지 수집기는 최악의 경우에도 일정 수의 계산 리소스를 돌연변이 쓰레드에 전용할 수 있도록 보장해야 한다.실시간 가비지 수집기에 부과되는 제약조건은 대개 작업 기반 또는 시간 기반이다.시간 기반 제약조건은 다음과 같다: 지속시간 T의 각 시간 기간 내에 최소 Tm 시간 동안 돌연변이 스레드가 실행되도록 허용해야 한다.작업 기반 분석의 경우 일반적으로 MMU(최소 돌연변이 이용률)[9]는 가비지 수집 알고리즘의 실시간 제약조건으로 사용된다.

JVM을 위한 하드 실시간 가비지 수집의 첫 번째 구현 중 하나는 IBM WebSphere Real Time의 일부로 상용 구현이 가능한 Metronome 알고리즘에 기초하였다.[10][11]또 다른 하드 실시간 가비지 수집 알고리즘은 IBM의 J9 JVM에서 이용할 수 있는 Staccato로, 대형 멀티프로세서 아키텍처에도 확장성을 제공하는 동시에, 메트로놈과 다른 알고리즘에 비해 다양한 장점을 가지고 있으며, 반대로 전문화된 하드웨어가 필요하다.[12]

참고 항목

참조

  1. ^ "Class SoftReference<T>". Java™ Platform Standard Ed. 7. Oracle. Retrieved 25 May 2013.
  2. ^ "Class PhantomReference<T>". Java™ Platform Standard Ed. 7. Oracle. Retrieved 25 May 2013.
  3. ^ "Class WeakReference<T>". Java™ Platform Standard Ed. 7. Oracle. Retrieved 25 May 2013.
  4. ^ "Weak References". .NET Framework 4.5. Microsoft. Retrieved 25 May 2013.
  5. ^ "Copying and Pinning". Msdn2.microsoft.com. Retrieved 9 July 2010.
  6. ^ Steele, Guy L. (September 1975). "Multiprocessing Compactifying Garbage Collection". Communications of the ACM. 18 (9): 496. doi:10.1145/361002.361005.
  7. ^ Appel, Andrew W. (17 June 1987). "Garbage collection can be faster than stack allocation". Information Processing Letters. 25 (4): 275–279. CiteSeerX 10.1.1.49.2537. doi:10.1016/0020-0190(87)90175-X.
  8. ^ "Memory allocation in embedded systems". Eros-os.org. Retrieved 29 March 2009.
  9. ^ Cheng, Perry; Blelloch, Guy E. (22 June 2001). "A parallel, real-time garbage collector" (PDF). ACM SIGPLAN Notices. 36 (5): 125–136. doi:10.1145/381694.378823.
  10. ^ "The Metronome: A Simpler Approach to Garbage Collection in Real-Time Systems" (PDF).
  11. ^ "Real-time Java, Part 4: Real-time garbage collection".
  12. ^ McCloskey, Bill; Bacon, David F.; Cheng, Perry; Grove, David (22 February 2008). "Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors" (PDF). Retrieved 11 March 2014.