복제 복사 컬렉션

최근 Nettles 등은 Baker의 점진적 복사 방식과는 상당히 다른 새로운 종류의 점진적 복사 컬렉션인 복제 복사(replication copying)를 고안했습니다. Baker의 수집기에서는 가비지 컬렉션이 “플립”으로 시작되어 즉시 도달 가능한 데이터를 tospace로 복사하고 fromspace를 무효화한다는 것을 상기해보세요. 그 순간부터 뮤테이터는 오직 객체의 새 버전만 볼 수 있으며, fromspace의 버전은 절대 볼 수 없습니다.

복제 복사는 이것의 거의 반대입니다. 복사가 진행되는 동안 뮤테이터는 tospace의 “복제본”이 아니라 fromspace 버전의 객체를 계속 봅니다. 복사 프로세스가 완료되면 플립이 수행되고, 그때 뮤테이터는 복제본을 보게 됩니다.

복제 복사의 일관성 문제는 Baker 스타일 복사와 매우 다릅니다. 뮤테이터는 복사 순회 중에 동일한 버전의 객체에 계속 접근하므로, 포워딩 포인터를 확인할 필요가 없습니다. 이는 읽기 장벽의 필요성을 제거합니다. 개념적으로 모든 객체가 플립이 발생할 때 한 번에 새 버전으로 “포워딩”됩니다.

반면에 이 전략은 쓰기 장벽을 필요로 하며, 쓰기 장벽은 단순히 포인터 업데이트 이상을 다뤄야 합니다. Baker의 수집기에서 뮤테이터는 오직 객체의 새 버전만 보므로, 객체에 대한 모든 쓰기는 자동으로 현재(tospace) 버전을 업데이트합니다. 하지만 복제 복사에서는 뮤테이터가 fromspace의 오래된 버전을 봅니다. 객체가 이미 tospace로 복사되었고 fromspace 버전이 뮤테이터에 의해 수정되면, 새 복제본은 잘못된(오래된) 값을 가질 수 있습니다. 뮤테이터가 보는 버전과 “동기화가 깨집니다”.

이를 피하기 위해 쓰기 장벽은 모든 업데이트를 잡아야 하며, 수집기는 플립이 발생할 때 모든 업데이트가 전파되었음을 보장해야 합니다. 즉, 객체의 오래된 버전에 대한 모든 수정이 해당하는 새 버전에 적용되어야 프로그램이 플립 후에 올바른 값을 볼 수 있습니다.

이 쓰기 장벽은 대부분의 범용 프로그래밍 언어에서는 비용이 많이 드는 것으로 보이지만, 함수형 언어나 부작용이 허용되지만 드물게 사용되는 “거의 함수형” 언어(ML 같은)에서는 그렇지 않습니다.

일관성과 보수성 재고

점진적 수집기는 뮤테이터를 수집기의 추적 순회와 조정하는 데 다른 접근법을 취할 수 있습니다. 이러한 준병렬 프로세스가 긴밀하게 조정되면 데이터 구조에 대한 뷰가 매우 정확할 수 있지만, 조정 비용이 받아들일 수 없을 수 있습니다. 긴밀하게 조정되지 않으면 오래된 정보를 사용하여 컬렉션 중에 가비지가 된 객체를 유지할 수 있습니다.

비복사 컬렉션에서의 일관성과 보수성

우리가 설명한 비복사 쓰기 장벽 알고리즘들은 효과성과 보수성의 스펙트럼에서 서로 다른 지점에 위치합니다. 시작 시점 스냅샷 알고리즘은 모든 것을 보수적으로 처리하여 효과성을 감소시킵니다. Dijkstra 등의 점진적 업데이트 알고리즘은 스냅샷 알고리즘보다는 덜 보수적이지만 Steele의 알고리즘보다는 더 보수적입니다.

Steele의 알고리즘에서는 흰색 객체에 대한 포인터가 검은색 객체에 저장될 때, 그 흰색 객체가 즉시 회색으로 칠해지지 않습니다. 대신 저장된 검은색 객체가 회색으로 되돌아가 수집기가 수행한 검게 칠하기를 “취소”합니다. 이는 저장된 필드가 다시 덮어쓰여지면 흰색 객체가 도달 불가능해질 수 있고 현재 컬렉션이 끝날 때 회수될 수 있음을 의미합니다. 대조적으로 Dijkstra의 알고리즘은 그 객체를 회색으로 칠했을 것이므로 회수하지 않을 것입니다.

이것이 사소한 차이처럼 보일 수 있지만, 중요한 시나리오를 상상하기는 쉽습니다. “스택” 객체에서 매달린 연결 리스트로 구현된 스택에 대부분의 데이터를 저장하는 프로그램을 생각해보세요. 스택 객체가 수집기의 순회에 의해 도달되어 검게 칠해진 후, 많은 객체가 스택에 푸시되고 팝되면, Dijkstra의 알고리즘은 팝된 항목을 전혀 회수하지 않을 것입니다. 스택 객체의 리스트 포인터가 리스트를 통해 진행되면서 다음 항목에 대한 포인터로 반복적으로 덮어쓰여질 때, 이전 항목이 팝될 때마다 각 항목이 회색으로 칠해질 것입니다. 반면 Steele의 알고리즘은 팝된 항목의 거의 대부분을 회수할 수 있는데, 수집기의 순회가 다시 검사하기 전에 포인터 필드가 여러 번 덮어쓰여질 수 있기 때문입니다.

이 보수성의 스펙트럼(스냅샷 알고리즘, Dijkstra의 것, Steele의 것)은 알고리즘들이 동일한 순회 알고리즘을 사용하고 프로그램의 실제 동작과 관련하여 동일한 방식으로 스케줄링될 때만 선형 순서라는 점에 주목하세요. 그리고 이는 실제로는 가능성이 낮습니다. 수집기와 뮤테이터 동작의 순서 세부 사항이 얼마나 많은 떠다니는 가비지가 유지될지를 결정합니다. 이러한 수집기 중 어느 것이든 뮤테이터에 의해 끊어지기 전에 수집기가 순회하는 경로를 통해 도달 가능한 모든 데이터를 유지할 것입니다.

이는 도달성 그래프가 기회주의적으로(opportunistically) 순회되면 이익이 될 수 있음을 시사합니다. 즉, 회색 객체의 스캔 순서를 신중하게 정하면 총 비용을 줄일 수 있습니다. 예를 들어, 곧 가비지가 될 객체에 도달하는 것을 피하기 위해 가능한 한 오래 그래프의 빠르게 변화하는 부분의 스캔을 피하는 것이 바람직할 수 있습니다.

다른 모든 것이 같다면(즉, 기회주의와 무작위 운이 없다면), 시작 시점 스냅샷은 점진적 업데이트보다 더 보수적이며(따라서 덜 효과적이며), Dijkstra의 점진적 업데이트는 Steele의 것보다 더 보수적입니다.

복사 컬렉션에서의 일관성과 보수성

Baker의 읽기 장벽 알고리즘은 위의 스펙트럼에 깔끔하게 들어맞지 않습니다. 회색 객체의 포인터가 덮어쓰여져 절대 순회되지 않을 수 있다는 점에서 시작 시점 스냅샷보다는 덜 보수적입니다. 하지만 점진적 업데이트 알고리즘보다는 더 보수적인데, 뮤테이터가 도달하는 모든 것이 회색으로 칠해지기 때문입니다. 객체는 컬렉션 중에 뮤테이터가 단순히 터치한 후에는 수집기의 관점에서 가비지가 될 수 없습니다.

Nettles 등의 복제 복사 알고리즘은 (점진적 업데이트 알고리즘처럼) 포인터가 수집기에 의해 도달되기 전에 덮어쓰여질 수 있기 때문에 도달 불가능해진 객체를 회수할 수 있습니다. 그들의 수집기는 Baker의 것보다 덜 보수적인데, 부분적으로는 더 약한 일관성 개념을 사용할 수 있기 때문입니다. 뮤테이터가 복사 단계가 완료될 때까지 tospace에서 작동하지 않기 때문에, tospace의 데이터 복사본은 점진적 복사 중에 완전히 일관될 필요가 없습니다. 뮤테이터가 fromspace 데이터 구조에 만든 변경은 결국 tospace로 전파되어야 하지만, 전체 상태는 원자적 “플립”이 수행되는 컬렉션 끝에만 일관되면 됩니다. 다른 쓰기 장벽 알고리즘처럼, 복제 복사도 기회주의적 순회 순서로부터 상당한 이익을 얻을 수 있습니다.

“급진적” 컬렉션과 기회주의적 추적

우리가 설명한 추적 알고리즘들은 대략 보수성이 감소하는 스펙트럼에 속합니다:

• 시작 시점 스냅샷 쓰기 장벽
• 검은색만 읽기 장벽
• Baker의 읽기 장벽
• Dijkstra의 쓰기 장벽
• Steele의 쓰기 장벽

이 준스펙트럼을 고려할 때 흥미로운 질문은 Steele의 알고리즘보다 덜 보수적인 것이 있을까?입니다. 즉, Steele의 것보다 더 잘 정보를 갖춘 수집기, 도달성 그래프의 변경에 더 공격적으로 대응하는 수집기를 가질 수 있을까요? 답은 예입니다. 그러한 가비지 컬렉터는 보수성을 피하기 위해 이미 수행한 순회의 일부를 다시 수행하고, 이전에 도달한 객체의 마킹을 해제할 의향이 있을 것입니다. 우리는 이것을 “급진적(radical)” 가비지 컬렉션 전략이라고 부릅니다. 언뜻 보기에 그러한 수집기는 비실용적으로 보일 수 있지만, 어떤 상황에서는 그것의 근사치가 의미가 있을 수 있습니다.

보수성 감소의 극한 경우는 도달성 그래프의 모든 변경에 완전히 대응하여, 이미 도달한 객체의 마킹을 해제하여 모든 가비지를 탐지할 수 있도록 하는 것입니다. 우리는 이것을 완전 급진적(fully radical) 수집기라고 부를 수 있습니다.

이를 수행하는 한 가지 방법은 애플리케이션의 모든 포인터 쓰기마다 실제 도달성 그래프의 전체 추적을 수행하는 것입니다. 당연히 이는 극단적인 비용 때문에 비실용적입니다. 일반적인 비점진적 수집기는 이것의 근사치로 볼 수 있습니다. 그래프는 전체 순회 동안 뮤테이터를 멈춤으로써 “순간적으로” 순회되지만, 이는 가끔만 수행됩니다.

완전 급진적 컬렉션을 달성하는 또 다른 방법은 도달성 그래프 내의 모든 종속성을 기록하고 모든 포인터 업데이트마다 종속성 데이터베이스를 업데이트하는 것입니다. 객체를 살아있게 유지하는 모든 경로가 끊어지면 객체가 가비지임을 알 수 있습니다. 다시 말하지만, 이 전략의 완전한 구현은 범용 가비지 컬렉션에는 비실용적일 것인데, 종속성 데이터베이스가 매우 클 수 있고 포인터 업데이트가 매우 비쌀 것이기 때문입니다.

하지만 이 종속성 정보의 근사치는 비교적 저렴할 수 있으며, 실제로 그것이 바로 참조 카운트입니다. 참조 카운트는 객체로의 경로 수의 보수적 근사치이며, 그러한 경로가 제거되면 참조 카운트는 보통 0이 되어 객체를 즉시 회수할 수 있게 합니다. 일부 분산 가비지 컬렉션 알고리즘도 수집기 순회의 일부 로컬 부분을 자주 재계산함으로써 다소 급진적인 컬렉션을 수행합니다.

점진적 기법 비교

수집기 설계를 비교할 때, 삼색 마킹의 추상화를 마킹-스윕이나 복사 컬렉션 같은 구체적인 추적 메커니즘과 구별하여 염두에 두는 것이 유익합니다. 읽기 또는 쓰기 장벽의 선택(그리고 정확성을 보장하기 위한 전략)은 대부분 추적 및 회수 메커니즘의 선택과 독립적입니다.

예를 들어, Brooks의 복사 수집기는 실제로 점진적 업데이트 쓰기 장벽 알고리즘인데, Brooks가 그것을 Baker 방식의 최적화로 설명했음에도 불구하고 그렇습니다. 마찬가지로 Dawson의 복사 방식은 Baker의 변형으로 제시되지만, 실제로는 점진적 업데이트 방식이며, 객체는 Dijkstra의 수집기에서처럼 fromspace, 즉 흰색으로 할당됩니다.

읽기 또는 쓰기 장벽 방식의 선택은 사용 가능한 하드웨어를 기반으로 이루어질 가능성이 높습니다. 특수 하드웨어 지원 없이는 쓰기 장벽이 효율적으로 구현하기 더 쉬운 것으로 보이는데, 힙 포인터 쓰기가 포인터 순회보다 훨씬 덜 일반적이기 때문입니다. 적절한 가상 메모리 지원이 가능하고 하드 실시간 응답이 필요하지 않다면, 페이지 단위 읽기 장벽이 바람직할 수 있습니다.

쓰기 장벽 방식 중에서 시작 시점 스냅샷 알고리즘은 점진적 업데이트 알고리즘보다 상당히 더 보수적입니다. 점진적 업데이트의 이 이점은 루트 순회의 순서를 신중하게 선택하여 증가될 수 있는데, 수집기의 작업이 뮤테이터 변경에 의해 취소되는 것을 피하기 위해 가장 안정적인 구조를 먼저 순회합니다.

점진적 업데이트 방식은 효과성을 증가시키지만 비용도 증가시킬 수 있습니다. 최악의 경우 컬렉션 중에 가비지가 되는 모든 것이 “떠다닙니다”. 즉, 너무 늦게 도달 불가능해져서 어쨌든 순회되고 유지됩니다. 새 객체가 흰색으로 할당되면(회수 대상), 점진적 업데이트 알고리즘은 최악의 경우 시작 시점 스냅샷 알고리즘보다 상당히 더 비쌀 수 있습니다. 새로 할당된 객체가 모두 떠다니며 순회를 필요로 하면서 회수되는 메모리 양은 증가하지 않을 수 있습니다.

쓰기 장벽 구현에 세심한 주의를 기울여야 합니다. Boehm, Demers, Shenker의 점진적 업데이트 알고리즘은 가상 메모리 더티 비트를 거친 페이지 단위 쓰기 장벽으로 사용합니다. 페이지의 모든 검은색 객체는 컬렉션이 끝나기 전에 페이지가 다시 더러워지면 재스캔되어야 합니다. Appel, Ellis, Li의 복사 수집기와 마찬가지로, 이 거칠기는 실시간 보장을 희생하면서 병렬성을 지원합니다. 또한 힙 쓰기와 함께 쓰기 장벽 명령어를 내보내지 않는 기성 컴파일러를 사용할 수 있게 합니다.

가비지 컬렉션에 대한 컴파일러 지원이 있는 시스템에서는 저장된 위치의 리스트를 유지하거나 작은 메모리 영역에 대해 (소프트웨어로) 더티 비트를 유지하여 스캔 비용을 줄이고 마킹 순회 업데이트에 소요되는 시간을 제한할 수 있습니다. 이는 세대별 가비지 컬렉터에서 다른 이유로 수행되어 왔습니다.

실시간 추적 컬렉션

점진적 수집기는 종종 실시간으로 설계됩니다. 즉, 프로그램 실행에 엄격하게 제한된 지연을 부과하여 프로그래머가 가비지 컬렉션된 프로그램이 실시간 데드라인을 충족할 것을 보장할 수 있도록 합니다. 실시간 애플리케이션은 산업 공정 제어기, 테스트 및 모니터링 장비, 시청각 처리, 플라이 바이 와이어 항공기 제어, 전화 교환 장비를 포함하여 많고 다양합니다. 실시간 애플리케이션은 일반적으로 하드 실시간으로 분류될 수 있는데, 계산이 엄격하게 제한된 시간 범위 내에서 완료되어야 하며, 소프트 실시간은 일부 작업이 “너무 자주”만 아니라면 때때로 스케줄을 놓치는 것이 허용됩니다.

실시간 가비지 컬렉션의 기준은 종종 특정 프로그램 작업에 작고 제한된 지연만 부과하는 것으로 명시됩니다. 예를 들어, 포인터 순회는 절대 마이크로초 이상 걸리지 않고, 작은 객체의 힙 할당은 절대 몇 마이크로초 이상 걸리지 않는 식입니다.

이러한 종류의 기준에는 두 가지 문제가 있습니다. 한 가지 문제는 “작은” 지연의 적절한 개념이 필연적으로 애플리케이션의 특성에 따라 달라진다는 것입니다. 일부 애플리케이션의 경우 1초의 상당 부분, 심지어 여러 초만큼 지연된 응답도 허용됩니다. 다른 애플리케이션의 경우 1~2밀리초의 지연은 문제가 되지 않지만, 다른 애플리케이션의 경우 몇 마이크로초 이상의 지연이 치명적일 수 있습니다. 한편으로는 음악 신디사이저 컨트롤러를 생각해보세요. 인간 자신의 부정확성이 1밀리초의 지연을 압도하여 눈에 띄지 않을 것입니다. 다른 한편으로는 대미사일 미사일을 위한 고정밀 유도 시스템을 생각해보세요.

이러한 종류의 기준의 또 다른 문제는 가장 작은 프로그램 작업을 비현실적으로 강조한다는 것입니다. 음악 키보드의 키를 누르면 컨트롤러는 수천 개의 프로그램 문을 실행해야 할 수 있습니다. 예를 들어, 어떤 음이 연주되고 있는지, 현재 튜닝을 고려할 때 해당 피치가 무엇인지, 얼마나 크게 연주할지, 주어진 피치에 대해 올바른 음색을 얻기 위해 어떤 사운드 구성 요소를 어떤 비율로 혼합할지 등을 결정해야 합니다.

따라서 대부분의 애플리케이션에서 실시간 성능에 대한 더 현실적인 요구 사항은 애플리케이션이 항상 애플리케이션과 관련된 시간 척도에서 주어진 시간 비율 동안 CPU를 사용할 수 있어야 한다는 것입니다. 당연히 관련 비율은 애플리케이션과 프로세서의 속도 모두에 따라 달라질 것입니다.

화학 공장의 공정 제어 컴퓨터의 경우, 제어 애플리케이션이 2초마다 최소 1초 동안 실행되는 것으로 충분할 수 있습니다. 컨트롤러가 2초 이내에 변경에 응답해야 하고 1초면 적절한 응답을 계산하기에 충분하기 때문입니다. 반면에 음악 신디사이저의 컨트롤러는 개별 음의 시작 지연을 눈에 띄는 임계값 이하로 유지하기 위해 2밀리초마다 0.5밀리초 동안 제어 프로그램을 실행하도록 CPU를 요구할 수 있습니다.

이러한 애플리케이션 중 어느 것이든 가비지 컬렉터가 때때로 0.25밀리초 동안 애플리케이션을 멈추더라도 올바르게 작동할 수 있습니다. 이러한 일시 정지가 너무 빈번하지 않다면, 애플리케이션의 실시간 데드라인과 관련하여 너무 짧습니다.

하지만 이러한 일시 정지가 시간적으로 군집되어 있다고 가정해보세요. 충분히 자주 발생하면 단순히 CPU 시간의 너무 큰 비율을 흡수하여 애플리케이션이 데드라인을 충족하는 능력을 파괴할 것입니다. 애플리케이션이 0.25밀리초 일시 정지 사이에 0.0625밀리초 동안만 실행되면 CPU 시간의 5분의 1 이상을 얻을 수 없습니다. 그 경우 위의 프로그램 중 어느 것도 실시간 요구 사항을 충족하지 못할 것이며, 2초 이내에만 응답하면 되는 공정 제어 시스템조차도 그렇습니다.

위에서 설명했듯이 일부 복사 수집기는 가상 메모리 보호를 사용하여 페이지 단위 스캔을 트리거하며, 이 거칠기는 실시간 보장을 존중하지 못할 수 있습니다. 최악의 경우 천 개의 요소로 된 리스트를 순회하면 천 개의 페이지가 스캔되어 상당한 가비지 컬렉션 작업을 수행하고 트랩 오버헤드도 발생할 수 있습니다. 이런 식으로 일반적으로 수천 개의 명령어가 걸리는 리스트 순회가 예기치 않게 수백만 개가 걸려 리스트를 순회하는 시간이 몇 배나 증가할 수 있습니다. 참조의 지역성이 그러한 상황을 가능성이 낮게 만들 수 있지만, 나쁜 경우의 확률은 무시할 수 없습니다.

불행히도 세밀한 점진적 수집기를 사용하는 것이 이 문제를 해결하지 못할 수 있습니다. Baker의 복사 기법을 생각해보세요. 리스트를 순회하는 시간은 리스트 요소가 tospace로 재배치를 필요로 하는지에 따라 달라집니다. 단일 포인터를 순회하는 것이 객체를 복사해야 할 수 있습니다. 이는 객체가 작고 하드웨어 지원이 가능하더라도 그 메모리 참조의 비용을 한 자릿수만큼 증가시킬 수 있습니다. 헤더, CAR 필드, CDR 필드로 구성된 Lisp cons 셀을 복사하는 것을 생각해보세요. 실제 복사를 위해 최소 3번의 메모리 읽기와 3번의 메모리 쓰기가 필요하며, 포워딩 포인터를 설치하고 자유 공간 포인터를 조정하고 아마도 이 작업을 수행하는 가비지 컬렉터 루틴으로 분기하고 돌아오기 위한 추가 명령어가 필요합니다. 그러한 경우 가비지 컬렉터 오버헤드가 CPU 시간의 90% 이상을 소비하여 사용 가능한 컴퓨팅 파워, 즉 실시간 데드라인을 충족하는 데 사용 가능하도록 보장되는 파워를 한 자릿수만큼 줄일 수 있습니다.

Baker의 원래 점진적 복사 방식에서 최악의 경우 비용은 훨씬 더 나쁜데, 모든 포인터 순회가 큰 객체의 복사를 강제할 수 있기 때문입니다. 배열은 특별히 처리되며 지연 복사됩니다. 즉, 실제로 터치될 때만 복사됩니다. Nilsen은 이 지연 복사를 모든 유형의 객체로 확장하여 최악의 경우를 줄입니다. 뮤테이터가 tospace 객체에 대한 포인터를 만나면 실제로 복사하는 대신 tospace에 객체를 위한 공간이 단순히 예약됩니다. 실제 복사는 나중에 백그라운드 스캐빈저가 tospace의 그 부분을 스캔할 때 점진적으로 발생합니다.

따라서 실시간 추적 전략을 결정할 때 어떤 종류의 보장이 필요한지, 어떤 시간 척도에서 필요한지를 결정하는 것이 중요합니다. Baker의 것이 가장 잘 알려진 점진적 알고리즘이지만, 대부분의 실시간 애플리케이션에 가장 적합하지 않을 수 있는데, 작은 시간 척도에서 성능이 매우 예측 불가능하기 때문입니다. 뮤테이터와 수집기 간의 결합이 약한 알고리즘(대부분의 쓰기 장벽 알고리즘 같은)이 더 적합할 수 있습니다. 프로그래머가 포인터 순회가 순회되는 포인터가 가비지 컬렉터에 의해 아직 도달되었는지 여부와 무관하게 항상 일정한 시간이 걸린다는 것을 알면 실시간 보장에 대해 추론하기가 더 쉬울 수 있습니다. 쓰기 장벽 알고리즘은 포인터 저장당 더 많은 작업을 필요로 하지만, 프로그램 작업당 작업은 덜 가변적이며, 대부분은 정확성을 유지하기 위해 즉시 수행될 필요가 없습니다.

불행히도 비복사 알고리즘은 시간 오버헤드가 더 예측 가능하다는 편리한 속성을 가지고 있지만, 공간 비용은 추론하기가 훨씬 더 어렵습니다. 복사 알고리즘은 일반적으로 크고 연속적인 메모리 영역을 해제하며, 모든 크기의 객체에 대한 요청은 상수 시간 스택 같은 할당 작업으로 충족될 수 있습니다. 비복사 알고리즘은 단편화의 대상입니다. 해제된 메모리가 연속적이지 않을 수 있으므로 그만큼의 메모리가 자유롭더라도 주어진 크기의 객체를 할당하지 못할 수 있습니다.

다음 섹션에서는 점진적 추적 수집기로부터 실시간 성능을 얻기 위한 기법을 논의합니다. 우리는 시스템이 순수하게 하드 실시간이라고 가정합니다. 즉, 프로그램이 데드라인 전에 반드시 완료되어야 하는 계산으로만 구성되며, 실시간 데드라인에 대한 시간 척도가 하나만 있다고 가정합니다. 그러한 시스템에서 주요 목표는 최악의 경우 성능을 가능한 한 좋게 만드는 것이며, 예상 케이스 성능의 추가 증가는 도움이 되지 않습니다. 나중에 예상 케이스 성능의 차이도 중요할 수 있는 소프트 실시간 스케줄이 있는 시스템의 트레이드오프를 간략히 논의할 것입니다. 또한 복사 알고리즘이 사용되거나 모든 객체가 균일한 크기라고 가정합니다. 이를 통해 모든 메모리 요청이 사용 가능한 모든 메모리로 충족될 수 있다고 가정하고 자유 저장소의 가능한 단편화를 무시할 수 있습니다.

루트 집합 스캔

실시간 성능의 중요한 결정 요인은 루트 집합을 스캔하는 데 필요한 시간입니다. Baker의 점진적 수집기에서 루트 집합이 업데이트되고 즉시 도달 가능한 객체가 tospace로 복사되는 것은 뮤테이터 실행에 의해 중단되지 않는 단일 원자적 작업이라는 것을 상기하세요. 이는 루트 집합의 크기에 대략 비례하는 기간의 일시 정지가 때때로 있을 것임을 의미합니다. 이 일시 정지는 정상적인 추적 증분에 대한 일시 정지보다 훨씬 클 가능성이 높으며, 실시간 보장의 주요 제한이 될 수 있습니다.

점진적 업데이트 추적 알고리즘에서 컬렉션을 종료하려고 할 때도 유사한 일시 정지가 발생합니다. 컬렉션이 완료된 것으로 간주되기 전에 루트 집합을 스캔해야 하며(Steele의 알고리즘 같은 경우 쓰기 장벽에 의해 기록된 회색 객체와 함께), 모든 도달 가능한 데이터를 원자적으로 순회하고 검게 칠해야 합니다. (이는 루트가 마지막으로 스캔된 후 루트에 포인터를 저장하여 수집기로부터 포인터가 숨겨지지 않았음을 보장합니다.) 이 작업이 실시간 범위에서 허용하는 시간 내에 완료될 수 없으면 수집기를 일시 중단하고 뮤테이터를 재개해야 하며, 전체 종료 프로세스를 나중에 다시 시도해야 합니다. 시작 시점 스냅샷 알고리즘은 경로가 수집기로부터 숨겨질 수 없기 때문에 종료 감지에 대해 어려운 문제를 제기하지 않습니다.

플립이나 종료에 필요한 작업을 제한하는 한 가지 방법은 루트 집합을 작게 유지하는 것입니다. 모든 지역 및 전역 변수를 루트 집합의 일부로 간주하는 대신, 일부 또는 전부를 힙의 객체처럼 처리할 수 있습니다. 이러한 변수에 대한 읽기 또는 쓰기는 읽기 장벽 또는 쓰기 장벽에 의해 감지되며, 따라서 수집기는 관련 정보를 점진적으로 유지할 것입니다.

루트 집합을 작게 유지하는 문제는 읽기 또는 쓰기 장벽의 비용이 그에 상응하여 증가한다는 것입니다. 더 많은 수의 변수가 읽기 또는 쓰기 장벽에 의해 보호되어 읽거나 쓸 때마다 오버헤드가 발생합니다. 한 가지 가능한 트레이드오프는 레지스터 할당 변수에 대한 읽기 또는 쓰기 장벽 비용을 피하고 필요할 때 레지스터 집합(만)을 원자적으로 스캔하는 것입니다. 하지만 스택 할당 지역 변수에 대한 작업이 너무 많으면 실행이 크게 느려질 것입니다. 그 경우 전체 스택을 대신 원자적으로 스캔할 수 있습니다. 이것이 비용이 많이 들 것처럼 들릴 수 있지만, 대부분의 실시간 프로그램은 깊거나 무제한 활성화 스택을 가지지 않으며, 비용은 프로그램의 의도된 응답 시간 척도에서 무시할 수 있을 수 있습니다. 마찬가지로 빠른 프로세서를 사용하는 작은 시스템(또는 실시간 요구 사항에 대해 비교적 큰 시간 척도를 가진)의 경우, 모든 전역 변수에 대한 읽기 또는 쓰기 장벽을 피하고 그것들도 원자적으로 스캔하는 것이 바람직할 수 있습니다. 중간 전략도 가능하며, 아마도 프로파일링 정보를 기반으로 일부 변수는 한 방식으로, 다른 변수는 다른 방식으로 처리합니다.

충분한 진행 보장

앞 섹션은 수집기가 관련 시간 척도에서 너무 많은 CPU 시간을 사용하여 프로세서가 실시간 데드라인을 충족하지 못하도록 하는 것을 방지하는 데 초점을 맞췄습니다. 반대로 수집기는 충족해야 할 자체 실시간 데드라인이 있습니다. 현재 자유 메모리가 고갈되기 전에 순회를 완료하고 더 많은 메모리를 해제해야 합니다. 그렇지 않으면 애플리케이션이 중단되고 컬렉션이 완료되어 더 많은 메모리를 해제할 때까지 기다려야 합니다.

따라서 하드 실시간 프로그램의 경우 수집기가 최악의 경우에도 자유 메모리가 고갈되기 전에 작업을 완료하기에 충분한 CPU 시간을 얻도록 보장하는 방법이 있어야 합니다. 그러한 보장을 제공하려면 최악의 경우를 정량화해야 합니다. 즉, 수집기가 수행할 것으로 예상되는 것에 대한 제한을 두어야 합니다. 추적 수집기는 살아있는 데이터를 순회해야 하므로, 이는 살아있는 데이터의 양에 제한을 두어야 합니다. 일반적으로 애플리케이션의 프로그래머는 프로그램이 순회할 특정 양 이상의 살아있는 데이터를 가지지 않도록 보장해야 하며, 수집기는 데드라인을 충족하기 위해 얼마나 빨리 작동해야 하는지 결정할 수 있습니다. 그런 다음 이것이 소비하도록 허용된 것보다 더 많은 CPU 시간을 필요로 하는지 결정할 수 있습니다. 당연히 이는 일반적으로 매개변수 설정에서 일부 트레이드오프를 허용합니다. 더 많은 메모리를 사용할 수 있으면 수집기는 일반적으로 메모리가 고갈되기 전에 완료하기 위해 CPU 시간의 더 작은 비율을 필요로 합니다.

컬렉션이 완료되기 전에 자유 메모리가 고갈되지 않도록 보장하는 일반적인 전략은 할당 클록(allocation clock)을 사용하는 것입니다. 각 할당 단위에 대해 해당하는 컬렉션 작업 단위가 수행되며, 후자의 단위는 자유 공간이 고갈되기 전에 순회가 완료되도록 보장하기에 충분히 큽니다. 이것의 가장 간단한 형태는 컬렉션 작업을 할당에 직접 연결하는 것입니다. 객체가 할당될 때마다 비례하는 양의 가비지 컬렉션 작업이 수행됩니다. 이는 프로그램이 메모리를 얼마나 빨리 사용하든 수집기가 그에 상응하여 가속화되도록 보장합니다. 실제 구현에서는 효율성을 위해 작업이 일반적으로 여러 할당에 걸쳐 다소 큰 단위로 일괄 처리됩니다.

이 섹션의 나머지 부분에서는 객체를 검은색으로 할당하는(즉, 컬렉션 대상이 아닌) 비복사 시작 시점 스냅샷 수집기로 시작하여 최소 안전 추적 속도를 계산하는 방법을 보여줍니다. 모든 객체가 균일한 크기라는 단순화 가정을 하여 할당되고 회수되는 단일 메모리 풀이 있습니다. 이 간단한 경우를 설명한 후, 다른 점진적 추적 알고리즘에 대해 안전 추적 속도가 어떻게 다른지 설명하겠습니다.

시작 시점 스냅샷 알고리즘의 경우 컬렉션 시작 시점의 모든 살아있는 데이터는 컬렉션이 끝날 때까지 순회되어야 합니다. 다른 알고리즘도 최악의 경우 이것을 수행해야 하는데, 컬렉션 중에 해제되더라도 객체를 순회해야 할 수 있기 때문입니다. 프로그래머로부터 다른 정보가 없는 경우, 수집기는 일반적으로 컬렉션 시작 시점에 최대 양의 살아있는 데이터가 실제로 살아있다고 가정해야 합니다.

컬렉션 중에 생성된 객체는 검은색으로 할당된다고 가정하므로, 즉 회수 대상이 아니므로 순회할 필요가 없습니다. 그러한 객체는 다음 가비지 컬렉션 사이클까지 무시될 것입니다.

언뜻 보기에 최대 살아있는 데이터 양이 L이고 메모리 크기가 M이면 $(M - L)$ 메모리를 할당할 수 있는 것처럼 보일 수 있습니다. 이는 이 “여유 공간”이 고갈되기 전에 L 데이터를 추적하기 위한 최소 안전 추적 속도가 $(M-L)/L$임을 의미합니다. 하지만 불행히도 떠다니는 가비지도 처리해야 합니다. 컬렉션 시작 시점에 살아있는 데이터는 컬렉션 중에 가비지가 될 수 있지만 이 가비지 컬렉션 사이클에서 회수되기에는 너무 늦습니다. 우리가 할당한 데이터도 가비지일 수 있지만, 검은색으로 할당하므로 아직 알지 못합니다. $(M-L)$ 메모리를 모두 사용하면 이 가비지 컬렉션 사이클에서 어떤 공간도 돌려받지 못할 수 있으며, 다른 컬렉션을 시도할 여유 공간이 남지 않을 것입니다. 따라서 할당해야 하는 최대 데이터는 여유 공간의 절반, 즉 $(M-L)/2$입니다. 최소 안전 추적 속도는 최대 살아있는 데이터를 순회하는 데 걸리는 시간에 그것을 할당할 수 있게 하므로, 안전 추적 속도는 $((M-L)/2)/L$, 즉 $(M-L)/2L$입니다. 이는 모든 가비지가 전체 가비지 컬렉션 사이클 동안 떠다니지만 다음 사이클에서 회수되는 최악의 경우에 충분합니다.

위에서 언급했듯이 새 객체를 검은색으로 할당하는 한 다른 점진적 추적 알고리즘의 상황은 본질적으로 동일합니다. 최악의 경우 시작 시점 스냅샷 알고리즘과 동일한 모든 객체를 유지하기 때문입니다. 최소 안전 추적 속도는 살아있는 데이터의 양에 비례하고 자유 메모리의 양에 반비례합니다. 따라서 메모리가 최대 살아있는 데이터 양에 비해 매우 커지면 0에 접근합니다.

하지만 흰색으로 할당하는 경우 상황은 상당히 나쁩니다. 흰색으로 할당할 때 우리는 새로 할당된 데이터가 단명할 것이라고 도박하고 있습니다. 따라서 현재 사이클에서 그 공간을 회수하기를 희망하며 가비지 컬렉션 대상으로 표시합니다. 이는 도달 가능한 흰색 객체를 순회해야 하며, 최악의 경우 가비지가 되기 전에 할당하는 모든 것을 순회합니다. 살아있는 데이터의 양에 제한이 있다고 가정하더라도(프로그래머가 제공), 순회 프로세스의 보수성과 뮤테이터가 포인터를 끊기 전에 수집기가 포인터를 순회할 수 있다는 사실을 고려해야 합니다.

따라서 흰색으로 할당할 때 최악의 경우 안전 순회 속도는 메모리가 매우 커져도 0에 접근하지 않습니다. 할당 속도에 접근합니다. 순회는 할당 속도를 따라잡아야 하며 최소한 조금 더 빨라야 결국 따라잡을 수 있습니다. 살아있는 데이터의 양에 비해 메모리 양을 늘리면 수익 체감 지점에 도달합니다. 항상 최소한 할당하는 만큼 빠르게 추적해야 합니다.

위의 분석은 균일한 크기의 객체에 대한 비복사 수집기에 적용됩니다. 복사 수집기에서는 복사되는 객체의 새 버전을 보유하기 위해 더 많은 메모리가 필요합니다. fromspace가 회수되기 전에 tospace가 고갈되지 않도록 보장하기 위해 최악의 경우 또 다른 L 단위의 메모리가 사용 가능해야 합니다. L이 실제로 사용 가능한 메모리 양에 비해 크면 이는 주요 공간 비용입니다. 균일하지 않은 크기의 객체에 대한 비복사 수집기에서는 단편화를 고려해야 합니다. 단편화는 효과적인 사용 가능 메모리를 줄여 제한된 메모리에서 컬렉션을 완료하기 위해 더 빠른 추적을 필요로 합니다. 최악의 경우 단편화 계산은 본질적으로 프로그램별이므로, 공간 제약으로 인해 여기서는 논의하지 않겠습니다.

최악의 경우 성능을 예상 성능과 교환

컬렉션 단계가 완료되면 수집기는 종종 덜 보수적인 순회 속도를 결정하여 컬렉션 프로세스를 늦추고 뮤테이터에 더 많은 CPU 사이클을 양보할 수 있습니다. 이는 컬렉션이 끝날 때 수집기가 실제로 얼마나 많은 살아있는 데이터가 추적되었는지 결정하고 다음 컬렉션에서 살아있을 수 있는 것에 대한 최악의 경우 추정치를 하향 수정할 수 있기 때문에 가능합니다. 이는 성능을 다소 향상시킬 수 있지만 일반적으로 극적이지는 않습니다.

또는 수집기가 최악의 경우보다 적은 작업을 수행해야 한다고 결정할 수 있을 때, 한동안 GC 활동을 완전히 피한 다음 데드라인을 충족할 수 있도록 제때에 수집기를 재활성화할 수 있습니다. 이는 읽기 또는 쓰기 장벽을 즉석에서 효율적으로 비활성화할 수 있는 경우 매력적인 옵션입니다.

논의

앞의 분석은 하드 실시간 데드라인에 대한 단일 시간 척도를 가진 상당히 단순한 실시간 성능 모델을 가정합니다. 혼합된 하드 및 소프트 데드라인이 있는 시스템이나 다양한 종류의 목표에 대해 여러 시간 척도를 가진 시스템에서는 더 복잡한 방식이 확실히 가능합니다. 예를 들어, 수집기의 드물지만 비교적 비싼 작업(루트 집합 스캔 같은)은 애플리케이션 자체의 장기 데드라인과 함께 보완적인 패턴으로 스케줄링될 수 있습니다. 이는 필요한 곳에서 엄격한 실시간 보장을 제공하면서 전반적으로 더 높은 성능을 달성할 수 있습니다.

우리는 또한 모든 메모리 요청에 사용 가능한 단일 메모리 풀이 있다는 점에서 상당히 단순한 가비지 컬렉션 모델을 가정했습니다. 크기가 크게 다른 객체가 있는 비복사 시스템에서는 그렇지 않을 것인데, 여러 작은 객체를 해제하는 것이 반드시 더 큰 객체를 할당할 수 있게 하지는 않기 때문입니다. 반면에 많은 애플리케이션의 메모리 사용은 매우 적은 수의 객체 크기에 의해 지배되는 것으로 보입니다. 실시간 컬렉션에 대한 추론은 대부분의 프로그램에 대해 처음 보기만큼 어렵지 않을 수 있습니다. 그래도 그러한 추론은 애플리케이션별로 수행되어야 합니다. 일부 프로그램의 경우 애플리케이션 수준 객체를 더 균일한 청크로 분할할 수 없다면 가능한 단편화로 인해 실시간 성능을 보장하는 데 상당한 메모리가 소요될 수 있습니다. 또 다른 가능성은 일반적으로 실시간 시스템에서 수행되는 것처럼 가장 문제가 되는 데이터 타입을 정적으로 할당하되, 대부분의 객체를 자동으로 관리하기 위해 가비지 컬렉터에 의존하는 것입니다.

합리적인 최악의 경우 메모리 사용을 가진 완전히 일반적인 실시간 가비지 컬렉션의 경우, 세밀한 복사 컬렉션이 필요한 것으로 보입니다. 위에서 언급했듯이 복사 컬렉션은 읽기 장벽을 가속화하기 위해 Lisp 머신 스타일 하드웨어 지원이 가능하더라도 최악의 경우 상당히 비쌀 수 있습니다. Nilsen과 Schmidt는 유용하게 실시간 성능을 보장할 하드웨어 지원을 설계하고 시뮬레이션했지만, 상당히 더 복잡합니다.

점진적 알고리즘 선택

점진적 전략을 선택할 때 전반적인 평균 성능과 최악의 경우 성능의 우선순위를 정하는 것이 중요합니다. “덜 보수적인” 알고리즘이 다른 것보다 더 매력적이지 않을 수 있는데, “덜 보수적인” 알고리즘이 최악의 경우에는 똑같이 보수적이기 때문입니다.

일반적인 경우에도 덜 보수적인 알고리즘이 바람직하지 않을 수 있는데, 단순히 더 느릴 수 있기 때문입니다(예: 쓰기 장벽이 더 많은 명령어를 필요로 하기 때문에). 역설적으로 이는 “덜 보수적인” 알고리즘을 실제로 더 보수적으로 만들 수 있는데, 비용이 자주 실행되지 못하게 할 수 있기 때문입니다. 더 높은 오버헤드 때문에 점진적 전략 측면에서의 감소된 보수성이 가비지가 얼마나 자주 수집되는지에 대한 더 큰 보수성을 도입할 수 있습니다.

따라서 전반적인 시스템 설계 목표는 가비지 컬렉션 알고리즘의 선택에 중요합니다. 다음 섹션에서 설명하겠지만, 세대별 기법은 하드 실시간 응답이 필요하지 않고 수집기가 일반적인 작동에서 “방해가 되지 않는” 것으로 충분한 많은 시스템에서 점진적 컬렉션의 오버헤드를 불필요하게 만듭니다. 다른 시스템의 경우 점진적 및 세대별 기법을 결합하는 것이 바람직할 수 있으며, 어떻게 결합되는지에 세심한 주의를 기울여야 합니다.

---

배경 지식 및 흥미로운 히스토리

1. 복제 복사의 혁신과 함수형 언어와의 관계

Nettles 등의 복제 복사(replication copying) 알고리즘은 1990년대 초에 제안되었으며, Baker의 접근법과는 근본적으로 다른 철학을 가지고 있습니다. 이 알고리즘이 함수형 언어에 특히 적합한 이유는 흥미롭습니다. ML이나 Haskell 같은 함수형 언어에서는 대부분의 데이터가 불변(immutable)이므로, 쓰기 작업이 매우 드뭅니다. 따라서 모든 쓰기를 추적하는 쓰기 장벽의 비용이 상대적으로 낮습니다. 반면 명령형 언어에서는 쓰기가 빈번하여 복제 복사의 쓰기 장벽이 큰 부담이 됩니다. 이는 가비지 컬렉션 알고리즘이 언어의 패러다임과 얼마나 밀접하게 연관되어 있는지를 보여주는 좋은 예입니다.

2. 실시간 가비지 컬렉션의 실제 응용 사례

문서에서 언급된 실시간 애플리케이션들은 실제로 매우 다양한 요구사항을 가지고 있습니다. 흥미로운 사례는 1980년대 후반 Texas Instruments의 Explorer Lisp Machine에서 사용된 Baker의 알고리즘입니다. 이 시스템은 특수 하드웨어로 읽기 장벽을 가속화했지만, 여전히 상당한 오버헤드가 있었습니다. 더 극단적인 예로는 1990년대 NASA의 Deep Space 1 미션에서 사용된 Remote Agent 시스템이 있는데, 이는 Lisp로 작성되었고 실시간 제약 조건 하에서 작동해야 했습니다. 이 시스템은 세심하게 조정된 가비지 컬렉션 전략을 사용하여 우주선의 자율 제어를 성공적으로 수행했습니다.

3. “급진적” 컬렉션과 참조 카운팅의 재발견

문서에서 “급진적(radical)” 컬렉션 개념이 참조 카운팅과 연결되는 부분은 가비지 컬렉션 역사의 흥미로운 순환을 보여줍니다. 참조 카운팅은 1960년대 초 가장 초기의 가비지 컬렉션 기법 중 하나였지만, 순환 참조 문제와 오버헤드 때문에 추적 기반 수집기에 밀려났습니다. 그러나 1990년대 들어 분산 시스템과 실시간 시스템의 요구가 증가하면서, 참조 카운팅의 “즉각적인 회수” 특성이 재평가되었습니다. Python과 Swift 같은 현대 언어들이 참조 카운팅을 주요 메모리 관리 전략으로 사용하는 것은 이러한 재발견의 결과입니다. 이는 기술이 단순히 선형적으로 발전하는 것이 아니라, 새로운 요구사항과 맥락에서 오래된 아이디어가 새로운 가치를 발견할 수 있음을 보여줍니다.

---