GC Algorithms

들어가며

프로그램이 실행되면 하나 이상의 객체가 생성된다.

더이상 필요하지 않게 된 객체는 어떻게 처리할까?

 

Java에서는 프로그래머가 명시적으로 메모리를 지정해 할당하거나 해제하지 않기 때문에,

Garbage Collector가 더이상 사용되지 않는 객체를 찾아서 메모리로부터 삭제해야 한다.

 

JVM이 GC 실행을 위해 application의 실행을 잠깐 멈추는 것을 'stop-the-world'라고 한다.

stop-the-world가 발생하면 GC가 실행되는 스레드를 제외한 나머지 스레드는 모두 작업을 멈춘다.

어떤 GC 알고리즘을 사용하더라도 stop-the-world가 발생하기 때문에 이 시간을 줄이기 위해 GC 튜닝이 수행되기도 한다.

 

지금부터는 어떤 방법들로 Garbage Collection 될 객체를 찾고 메모리에서 해제하는지 알아보자.

 

초기, Reference Counting Algorithm

이 알고리즘은 Garbage의 Detection, 즉 Garbage 탐지에 초점이 맞추어진 초기 알고리즘이다.

생성되는 객체마다 '참조된 횟수(Reference Count)'를 관리해 Reference Count가 0이 되면 GC를 수행한다.

 

장점

(1)  Pause Time이 분산되어 실시간 작업에 거의 영향을 주지 않는다.

(2)  Garbage는 즉시 메모리에서 해제된다.

 

단점

(1)  각 Object마다 Reference Count를 변경해 주어야 하므로 Reference Count의 관리 비용이 크다.

(2)  참조를 많이 하고 있는 Object의 Reference Count가 0이 될 경우 연쇄적으로 GC가 발생할 수 있는 문제가 있다.

(3)  Linked List와 같은 순환 참조 구조에서 Memory Leak이 발생할 가능성이 크다.

 

단점 극복을 위한 Mark-and-Sweep Algorithm

이 알고리즘은 Reference Counting Algorithm의 단점을 극복하기 위해 고안되었다고 한다.

참조된 횟수를 관리하는 Reference Counting Algorithm과는 달리,

Mark-and-Sweep Algorithm에서는 Root Set에서 시작하는 Reference의 관계를 추적한다.

이 때문에 Tracing Algorithm이라고도 한다.

 

Mark-and-Sweep 알고리즘이라는 이름에서 유츄할 수 있듯 두 Phase로 진행된다.

 

Mark Phase

Garbage 대상이 아닌 Object에 Marking하는 작업이 진행된다.

Marking을 위해 각 Object의 헤더에 Flag를 사용하거나 별도의 Bitmap Table을 사용하기도 한다.

 

Sweep Phase

Marking 정보를 활용하여 Marking되지 않은 Object를 메모리에서 해제하는 작업이 진행된다.

이 작업을 Sweep 이라고 하며, Sweep이 완료되면 살아남은 모든 Object의 Marking 정보를 초기화한다.

 

장점

(1)  Reference 관계를 파악하기 때문에 참조 관계가 변경되어도 별도의 오버헤드가 없어 속도가 향상된다.

 

단점

(1)  Marking의 정확성을 향상시키고 Memory Corruption을 방지하기 위해 GC 수행 도중에는 Heap의 사용이 제한된다.

(2)  Suspend가 발생한다.

(3)  GC 작업 이후 Garbage는 존재하던 메모리 공간에서 해제되기 때문에 마치 구멍이 뚫린 것처럼 듬성듬성한 상태가 된다.

     - 이 상태를 Fragmentation이라고 한다.

     - Heap 메모리 전체로 봤을 때에는 충분한 공간이 있는 것처럼 보이지만 메모리 할당이 불가능한 상태가 되어 예외를 발생시킬 수 있다.

 

 

Fragmentation을 해결하기 위한 방법

첫번째, Mark-and-Compact Algorithm

Mark-and-Sweep Algorithm이 가지고 있는 Fragmentation이라는 약점을 극복하기 위해 고안된 알고리즘이다.

Sweep 대신 Compact라는 용어를 사용하였지만, Sweep Phase가 사라진 것이 아니라 Compact Phase 안에 포함되어 있다.

 

Mark Phase

Mark-and-Sweep Algorithm의 Mark Phase와 동일한 작업이 수행된다.

Garbage 대상이 아닌 Object에 Marking하는 작업이 진행된다.

 

Compact Phase

Mark-and-Sweep Algorithm의 Sweep Phase와 동일한 작업이 먼저 수행된다.

Marking 정보를 활용하여 Marking되지 않은 Object를 메모리에서 해제하는 작업이 진행된다.

이후 Garbage가 사라지고 남은 빈자리들에 살아남은 Object를 연속적으로 메모리 공간에 적재하는 Compaction 작업이 수행된다.

 

장점

Compaction 작업을 통해 메모리 공간의 효율을 높일 수 있다.

 

단점

Compaction 후 살아남은 모든 Object들의 Reference를 업데이트하는 작업이 필요하기 때문에 부가적인 오버헤드가 수반된다.

 

 

두번째, Copying Algorithm

Fragmentation의 문제를 해결하기 위해 제시된 또 다른 알고리즘으로,

이 알고리즘이 발전해 현대의 Garbage Collector가 차용하는 Generational Algorithm이 된다.

 

여기서는 Heap을 Active 영역과 Inactive 영역으로 나눈다.

 

Active 영역

이 영역에만 Object를 할당할 수 있도록 한다.

Active 영역이 꽉 차면 GC를 수행한다.

 

Inactive 영역

GC가 실행되면 Live Object, 즉 필요한 Object들이 이 영역에 Copy된다.

 

Copy

Copy 작업 이후에는 Inactive 영역에 필요한 Object가, Active 영역에는 Garbage Object가 남게 된다.

여기서 Garbage Object를 메모리에서 해제하면 Active 영역은 Free Memory 상태가 된다.

Inactive 영역과 Active 영역을 서로 바꾼다.

 

Scavenge

영역을 서로 바꾸는 것을 Scavenge라고 하는데, 영역의 구분은 논리적 구분일 뿐이라는 것을 잊지 말자.

 

 

장점

Fragmentation이 생기지 않는다.

 

단점

(1)  Live Object를 옮기는 과정에서 각 Object들의 Reference를 업데이트하면서 적재시켜야 하므로 이 과정에서 오버헤드가 발생한다.

(2)  Fragmentation 방지에는 효과적이지만 전체 Heap 공간의 절반 정도 밖에 사용하지 못한다는 점이 비효율적이다.

(3)  Suspend가 발생한다.

 

HotSpot JVM에서 사용되는, Generational Algorithm

전제, Weak generational hypothesis

두 가지를 전제로 한다.

 

(1)  대부분의 객체는 오랫동안 참조되지는 않는다. 즉 금방 Garbage 대상이 된다.

(2)  오래된 객체에서 젊은 객체로의 참조는 거의 없다.

 

Young Generation

Object는 이 영역에 할당되고, GC가 수행될 때마다 살아남은 Object의 age를 기록한다.

 

Age

Object Header에 기록되는 age에는 임계값이 정해져있다.

 

Old Generation

age의 임계값을 넘어서게 된 Object들이 이 영역으로 Copy 된다.

Copy 작업이 수행되면서 자연스럽게 Compaction 작업이 수행된다.

 

장점

(1)  대부분의 객체가 Young Generation에서 살다가 Garbage가 되기 때문에 Copy 작업의 횟수를 최소화시킬 수 있다.

 

 

---

 

마치며

이 글에서 하나하나의 GC 알고리즘을 깊게 살펴보지는 않았지만,

GC 알고리즘이 어떤 점을 보완하며 바뀌었는지 그 흐름에 따라 정리해보았다.

 

application 특성에 따라 적절한 GC 알고리즘을 선택하거나 GC를 튜닝할 수 있을 때까지 계속 공부할 것이다.

 

참고링크

https://d2.naver.com/helloworld/1329

https://medium.com/@joongwon/jvm-garbage-collection-algorithms-3869b7b0aa6f