High-Performance Garbage Collection for. Memory-Constrained Envi

www.cs.umass.edu/~emery/pubs/04-15.pdf
 
(이 논문을 완벽히 이해하지도 못했지만, 어느 정도 이해한 바도 있고, 앞으로 계속 공부할 수 부분이 있기에 계속 시도할 것이다. 어려운 논문이다..)

가비지 콜렉션은 성능 문제가 가장 중요하다. c나 C++처럼 명시적인 힙 메모리 해제를 지원하지 않기 때문에, 어느 정도 시간이 되면, 자동으로 쓰이지 않은 힙 메모리에 대해서 compaction과 deallocation을 실시한다.
가비지 콜렉션은 mark -sweep이라는 방식, marking (sweep) * compaction, memory constrained copying(mc2) 이렇게 세개로 나누어진다.

또한 가비지 콜렉션 알고리즘에 따라 Mark-Sweep, Mark-Compaction, Copying, Generational collection 이렇게 4개로 카테고리로 나눌 수 있다. (nursey = young gen)

Mark-Copy 방법은 임베디드에서는 퍼포먼스가 나오지 않는다. copying 단계에서 메모리를 직접 map, unmap하는 부분에서 virtual memory를 써야 하는 부분, 콜렉터가 항상 old gen에서 복사를 함으로서, 효울성이 떨어진다는 점, 가비지 콜렉터시 pause 타임이 길다라는 단덤이 있다.

이런 단점을 최대한 줄인 MC2는 dynamic memory 정책과 table형태의 map, unmap 형태의 구조, indirect  addressing memory table을 가짐으로서, 최대한 장점을 가지려고 하고 있다. 이런 작업을 marking때 함으로서, 실제 map, unmap할 때의 시간적 소요를 최대한 줄일 수 있고, indirect이므로, 효율적으로 copy하는 복잡성을 제거할 수 있다.

Increment makring이라는 방법을 통해서, full 콜렉션시 pause 시간을 최대한 줄일 수 있다. 이는 마킹하는 작업시, young gen에서 interleaving하는 방법을 통해서, 마킹시시 큐를 가지고 작업하고, 번호를 부여하는 remembered set이라는 데이터 자료형을 가지고 작업하게 된다. 순차적으로 번호를 부여하고, 콜렉션 할 때마다 오랫동안 살아남았는지 여부를 판단할 수 있는 근거가 됨으로서, 추후 old gen으로 promotion할 때 사용할 수 있도록 되어 있다. 이 때 사용되는 메모리의 단위는 window라고 하는 메모리 단위이다..

copy과정에서는 Increment copying이라는 방법을 사용한다. 이 부분에서 좀 복잡한 개념이 나오는데, write barrier라는 것이다. 이 부분은 명확하게 들어오지 않아서, 다른 논문을 읽고, 다시 정리하면서 공부하는 게 좋을 거 같아서 일단 패쓰한다.

실제 이를 RVM, linux로 구현을 해서, GC 알고리즘을 가지고, 얼마나 performance가 좋은 지를 확인하는 결과를 보여주고 있다. 전체적으로 MC2가 효율이 좋은 결과를 보이고 있다.
PC나 서버에서는 full 콜렉션시 긴 pause타임이 별 의미가 없다. 하지만, 임베디드 시스템에서는 얼마나 효율적으로 메모르를 잘 사용하고, pause 타임이 최소화해야 하는 알고리즘이 사용될 수 있어야 한다. 바로 MC2는 이에 대해 잘 언급이 되어 있다. 짧은 pause 타임과 좋은 성능을 제공하고, 실시간적인 요구사항이 필요한 임베디드 단말기에서 동작할 수 있는 형태의 알고리즘이 결과를 내세웠다.

실제로 MC2가 가장 좋은 알고리즘이라고 하지만, 구현 복잡성이 있어서, 대부분 generation gc 알고리즘을 사용한다고 한다.

GC 알고리즘 논문을 처음으로 본 게 가장 어려운 논문이라 나에게 조금 벅찬 듯 하지만, 계속 공부하기엔 좋은 레퍼런스를 제공한 것 같다. 찾아 볼 수 있는 레퍼런스를 통해서 계속 GC공부를 할 수 있도록 노력해야 겠다!!