GC 알고리즘

reference counting algorithm

count를 관리하여 reference count가 0이되면 그때그때 garbage collection을 수행하는것이다.object에 reference 가되면 reference count는 1이 증가하고 reference가 사라지면 1이 감소하는 식으로 동작한다. 그런데 이 reference 관계가 간접적이라 하더라도 참조하고 있는 모든 object에 대해 연쇄적으로 reference count가 변경된다 이reference count가 0 이될때마다 garbage collection이 발생하기 때문에 자연스럽게 Pause Time이 분산되어 실시간 작업에도 거의 영향을 주지 않는 장점이 있다. 그러나 reference의 변경이나 garbage collection의 결과에 따라 각 object마다 reference count를 변경해 주어야하기 때문에 이에 대한 관리 비용이 상당하다 또한 Garbage collecition이 연쇄적으로 일어 날수 있다는 것도 문제가 될 수 있다. 하지만 무엇보다 이 reference counting algorithm 문제는 memory leak의 가능성이 농후하다는데 있다 reference count가 0이 되어야 garbage collection이 될것인데 순환 참조의 구조에서는 regerence count가 0이 될 가능성이 희박하다 그렇기 때문에 garbage 가 되어도 heap 에서 사라지지 않게 되어 memory leak 을 유발할 가능성이 커지게 된다

mark-and-sweep algorithm

reference에 따라 object마다 count를 하는 방식대신, root set에서 시작하는 reference의 관계를 추적하는 방식을 사용한다. 이러한 방식은 garbage를 detection하는데 있어 상당히 효과적이기 때문에 이후의 garbage collection에서 detection은 대부분 이 algorithm을 사용하고 있다.

mark-and-sweep algorithm은 mark phase와 sweep phase로 나뉘어 진다. mark phase는 gabage object를 구별핸재는 단계로 root set 에서 reference 관계가 있는 object에 marking하는 방식으로 수행된다.marking 을 위해서는 여러가지 방법이 있는데 주로 object header에 flag 나 별도의 btimap table등을 사용한다

이 mark-and-sweep algorithm은 reference관계까 정확하게 파악될 뿐만 아니라 reference의 관계의 변경 시에 부가적인 작업을 하지 않기 때문에 속도가 향상된다는 장점이 있다. 그러나 garbage collection 과정 중에는 heap의 사용이 제한된다. 그것은 작업의 정확성과 meomry corruption을 방지 하기 위함인데 이 경우 프로그램이 잠깐 멈추는 현상이 발생한다 또하나의 문제는 바로 fragementation이 발생 할수 있다는 것이다.

mark-and-compaction algorithm

make-and-sweep algorithm의 fragmentation이라는 약점을 국복하고자 sweep 대신 compaction을 포함한 것이다.

이 algorithm은 mark phase와 compaction phase로 구성되어 있다. compaction이란 작업은 말 그대로 live object를 연속된 메모리 공간에 차곡차곡 적재하는 것을 의미하며 보통 하위 address로 compaction을 수행한다 compaction에는 여러가지 방식이 있는데 arbitrary 방식, linear방식, sliding 방식 등이 있다. 이중 arbitrary방식은 순서가 보장되지 않는 방식이다. linear방식은 reference의 순서대로 정렬된 compaction이다 그리고 sliding 방식은 할당된 순서대로 정렬되는 방식이다.

compaction을 원활하게 하기 위해 handle과 같은 자료구조를 사용할 수도 있다. handle에는 객체의 논리적인 주소와 실제 주소가 들어가 있다. mark phase에서는 live object의 handel에 marking한다. compaction phase에서는 일단 marking 된 정보를 바탕으로 garbage object를 sweep 한 후 heap의 한 쪽 방향으로 live object를 이동시킨다. 이동하는 방법은 sliding compaction의 방법을 사용한다. 그 이후 이동한 새로운 주소로 모든 reference를 변경하는 작업을 수행한다

fragmentation의 방지에 초점이 맞추어져 있기 때문에 메모리 공간의 효율성이 가장 큰 장점이다.그러나 compaction 작업 이후에 모든 reference를 업데이트 하는 작업은 경우에 따라서 모든 object를 access하는등의 부가적인 overhead가 수반 될 수도 있다. 또한 mark phase와 compaction phase는 모두 suspend 현상이 발생한다는 단점이 있다

copying algorithm

heap 을 active영역과 inactive 영역으로 나누어서 사요한느 특징을 가지고 있다. 이중 active영역에만 object를 할당 받을 수 있고 active영역이 꽉 차게 되어 더이상 allocation이 불가능하게 되면 garbage collection이 수행된다.

garbage collection이 수행되면 모든 프로그램은 일단 suspend 상태가 된다. 그리고 live object를 inactive영역으로 copy하는 작업을 수행한다. object를 copy할때 각각의 reference 정보도 같이 변경된다.

이렇게 작업이 끝나면 active영역에는 garbage object만 남아 있게 되고 inactive 영역에는 live object만이 남아 있게 된더. 그런데 inactive영역에 object를 copy 할 때는 한쪽 방향에서부터 차곡차곡 적재를 하기 때문에 마치 compaction을 수행한 것처럼 정렬이 된 상태가 된다 이렇게 garbage collection이 완료되는 시점에서 active 영역은 모두 freememory가 되고 active 영역과 inactive 영역은 서로 바뀌게 된다. 이를 scavenge라고 한다.

fragmantation의 방지에는 효과적이기는 하지만 전첼 heap의 절반 정도를 사용하지 못한다는 단점이 존재한다. 또한 suspend현상과 copy에 대한 overhead는 필요악이라 할 수 있을 것이다.

generational algorithm

copy algorithm의 연장선상에 있다. heap을 active, inactive로 나누는 것이 아니라 age 별로 몇개의 sub heap으로 나눈다. object는 youngest generation sub heap 에 할당되고 그 곳에서 성숙하게 되면 그 다음 age에 해당하는 sub heap으로 올라가 결국 oldest generation sub heap 까지 promotion하는 방식으로 동작한. age가 임계값을 넘엇 다른 generation으로 copy되는 것을 promotino이라고 한다.

무엇보다 이 algorithm의 장점은 각 sub heap에서 각각 적절한 algorithm을 적용 할수 있다는 것이다 이러한 장점으로 인해 hosspotjvm이나 ibm jvm에서도 generational algorithm을 사용하고 있다

train algorithm

Heap을 작은 Memory Block으로 나누어 Single Block 단위로, Mar Phase와 Copy Phase로 구성된 Garbage Collection을 수행한다.이러한 특징때문에 이 algorithm은 incremental algorithm이라고도 한다.

garbage collection을 수행하는 단위가 single block 인 만큼 전체 heap의 suspend가 아닌 collection 중인 memtory block만 suspend가 발생한다 다시 말해 suspend를 분산시켜 전체적인 pause time을 줄이자는 아이디어인 것이다.

heap을 tran으로 구성한다 이 train은 car라고 불리는 fixed size의 memory block을 묶어 놓은 체인이다. train은 필요에 따라 car를 추가 할수도 있고 하나의 train이 추가 될 수도 있다. 그리고 각 memory block은 car외부에서의 참조를 기억하는 remember set이라는 장치가 있다. 이러한 구조 때문에 train algorithm이라는 명칭을 사용하게 되었다.

remember set은 train algorithme이 single block 단위로 garbage collection을 한다는 의미에서 상당히 중요하다 copy나 compaction을 통해 objectr가 이동을 하게 되면 당연히 그 주소가 변경될 것이고 이를 참조하는 object들도 따라서 reference가 변겨이 되어야한다. 그런데 obejct가 이동을 하게 되면 당연히 그 주소가 변경될 것이고 이를 참조하는 object들도 따라서 reference가 변경이 되어야 한다. 그런데 object는 자신이 참조하는 refence는 가지고 있지만, 누가 나를 참조하고 있는지에 대한 정보는 가지고 있지 못하다. 그렇기 때문에 이동한 object를 누가 참조하고 있는지를 알기 위해서는 , 최악의 경우 모든 root set과 object의 reference를 모두찾아 다녀야 하는 경우가 발생한다. 이경우 suspend의 분산 효과는 현저히 떨어진다.

remember set은 이러한 일을 방지하는 효과가 있다. remember set을 구성하기 위해서는 write barrier라는 장치를 동반하게 된다. wite barrierㅇ는 간단한 코드로 되어 있는 instruction의 set, 즉 작은 이벤트 프로그램 또는 트리거 정도로 이해할 수 있다. 보통 write barrier는 reference 관계를 맺을때 대상 object가 같은 car에 있지 않을 경우 대상 object의 car에 있는 remember set에 기록하는 식으로 구성되어 있다

adaptive algorithm

지금까지 설명한 것과는 달리 특정 collection방법을 지칭하는 것은 아니다. heap의 현재 상황을 모니터링하여 적절한 algorithm을 선택 적용하는 것 또는 heap sizing을 자동화하는 일련의 방법을 의미한다. 이것은 hotspot jvm의 ergonomics 기능 또는 adaptive optino이나 ibm jvm의 tilting 기능 등으로 구현이 되고 있다.

Creative Commons License
GC 알고리즘 by Voyager of Linux is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Post a comment

You may use the following HTML:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">