garbage collection:reference counting and mark-and-sweep
Min Lee
쓰이죠..
http://blogs.msdn.com/b/abhinaba/archive/2009/01/25/back-to-basic-series-on-dynamic-memory-management.aspx
를 통해서 살펴봤습니다..
--
OS와는 좀 무관하지만, garbage collection (GC) 을 살펴봅시다. 기초적인 두가
지 방식이 있습니다. reference counting방식과 mark-and-sweep입니다. 먼저 간
단하게 object-reference graph를 생각해봅시다. 그리고 여기에는 root라고 할수
있는 reference들이 주어집니다. 이 root들은 register, global, static, local
등에서 모아질수 있겠습니다. 즉 접근의 시작점이 되는 reference들의 모임이라
고 할수 있습니다. 이 root로부터 그래프를 따라 접근가능한 object들은 현재 사
용중이라고 볼수 있고 그외에는 reference를 잃은 object라고 할수 있겠네요. 가
장 간단한 mark-and-sweep은 간단합니다. 주기적으로 또는 메모리가 부족할때 이
러한 root들로부터 recursive하게 object를을 mark해서 사용중임을 표시하고
mark되지 않은 object들은 모두 수거하는거죠. root를 모으는것은 런타임이 해줘
야하겠습니다. 좋은점은 프로그램의 보통실행시의 부담이 없다는것과 cyclic
reference를 처리한다는점. 하지만 예기치 않은 GC실행시에 부담으로 실해중에
pause가 생긴다거나, 메모리를 거의 다 뒤져야한다는점, 메모리 사용량이 많으면
thrashing할수 있다는 점등의 단점이 있습니다. (물론 이에 대한 대안들이 있긴
하겠지만..TODO) 또한 스택오버플로의 문제가 있습니다. 스택의 높이가
reference chain의 최장길이와 같아지기 때문이죠. 물론 iteration으로 바꾸어서
overflow를 체크할수는 있지만, 근본 문제가 해결되지는 않습니다. 이를 위해 여
러가지 방법이 쓰이는데, TODO 다른 문제점인 pause가 생기는 단점을 극복하기
위해서, generational GC등이 나옵니다. 이 optimization은 몇가지 관측에 기반
하는데, 대부분의 object가 빨리 죽는다거나 한번 GC cycle에서 살아남으면 그
다음에도 보통 살아남는다는 것이죠. object가 GC cycle에서 죽지않고 살아남을
수록 다음 세대로 옮겨가면서 GC대상에서 제외해나가는 방식입니다. 따라서 낮은
세대일수록 자주 GC의 대상이 되도록 합니다.
반면 전혀 다른 방식인 reference counting GC는 object마다 자신을 가리키는
reference 즉 포인터의 수를 세는 값을 가지고 이값이 0이 되면 수거하는 방식입
니다. object가 즉시 사라지는 장점이 있는 반면, space overhead가 있을수 있
고, 자신을 가리키거나하는 등의 cyclic reference의 경우에는 object를 지우지
못한다는것, (따라서 주기적으로 mark-and-sweep등의 알고리즘을 또 써줘야합니
다), 그리고 포인터 조작때마다 overhead가 있다는것, 그리고 멀티코어등의 환경
에서 reference update에 lock을 써야하기때문에 오버헤드가 있다는점등의 단점
이 있습니다. 한가지 optimization은 stack에서의 포인터에 대한 reference를 제
외하고, refcount가 0이 되어도 즉시 수거하지 않고 기다리다가 주기적으로
stack들을 살펴봐서 stack에도 reference가 없을때에 수거하는것이죠. common
case에 해당하는 stack에서의 reference에 대한 부담을 제거하는것입니다. 또한
space에 대해서도 1byte정도의 refcnt만을 쓰고, refcnt가 꽉 찬 경우에는 주기
적으로 특수하게 취급할수도 있겠죠.
이 둘은 상호보완적으로 쓰이는듯합니다. 그외에도 여러 이슈가 있는데, 예를들
어 런타임의 지원이 없을때 object들이 가지고 있는 포인터를 어떻게 찾아내는지
도 문제가 됩니다.TODO