[Java] Garbage Collection (GC) 알고리즘

GC의 기본적인 흐름 : Garbage 대상 식별 → 그 대상을 메모리에서 해제

들어가기 전에

---

용어 정리

stop-the-world

GC를 실행하기 위해 JVM이 애플리케이션 실행을 멈추는 상태.
이 상태가 발생하면 GC를 실행하는 스레드를 제외한 나머지 스레드는 모두 작업을 멈춘다.

GC는 stop-the-world 때문에 서비스가 중단된다는 점에서 굉장히 유의할 것이 되고,
대개의 GC 튜닝이 이 stop-the-world 시간을 줄이는 노력들에 대한 것이다.

Root Set

1. JVM Stack 내의 Local Variable Section과 Operand Stack에서의 참조
   (Java 메서드 내에서 실행하는 지역 변수 또는 파라미터에 의한 참조)
2. JVM Method Area의 Constant Pool에서 참조 (정적 변수에 의한 참조)
3. 아직 메모리에 남아 있는 Native Method로 넘겨진 Object에서 참조 (JNI에 의해 생성된 객체에 대한 참조)

Reachable Object

위 3가지의 Root Set으로 이어진 참조 사슬에 포함되어 있다면 Reachable Object

Unreachable Object

위 3가지의 Root Set으로 이어진 참조 사슬에 포함되어 있지 않다면 Unreachable Object

 

weak generational hypothesis

GC를 성공적으로 수행하는 전제조건 같은 가설. 

• 대부분의 객체는 금방 접근 불가능 상태(Unreachable)가 된다.
• 오래된 객체(→Old 영역)에서 젊은 객체(→Young 영역)으로의 참조는 아주 적게 존재한다.

 

JVM Runtime Data Area에서의 Heap 메모리 구조

위의 weak generational hypothesis의 장점을 최대한 살리기 위해 Hotspot VM에서는 Heap 영역을 아래와 같이 나눈다.

즉, 크게 Young / Old 영역으로 나눠서 위의 가설을 제대로 구현하고자 하였다.
이는 Generational Algorithm을 바탕으로 구성한 Generational Heap이라고도 부른다.
(Generational Algorithm은 뒤에 설명)

또한, Heap영역에는 new 키워드로 생성된 인스턴스 및 배열이 저장되는데, 이에 대해 GC를 수행한다는 의미이므로 GC는 Heap에서 일어난다는 것을 알 수 있다.

 

 

 

이것들을 기준으로 GC 방법들에 대해 설명할 것이다.

 

Young 영역 : Generational Algorithm

---

Young 영역에서 발생하는 GC를 Minor GC라고 한다.

Young영역 = Eden 영역 + Survivor 영역 * 2

절차

1. 새로 생성한 대부분의 객체는 Eden 영역에 위치한다. (Allocation)
2. Eden 영역에서 GC가 한 번 발생한 후 살아남은 객체는 Survivor 영역 중 하나로 이동된다.
3. Eden 영역에서 GC가 발생하면 이미 살아남은 객체가 존재하는 Survivor 영역으로 객체가 계속 쌓인다.
4. 하나의 Survivor 영역이 가득 차게 되면 그 중에서 살아남은 객체를 다른 Survivor 영역으로 이동한다. 그리고 가득 찬 Survivor 영역은 아무 데이터도 없는 상태로 된다.
5. 이 과정을 반복하다가 계속해서 살아남아 있는 객체는 Old 영역으로 이동하게 된다. (Promotion)

두 Survivor 영역에 모두 데이터가 존재하거나, 두 영역 모두 사용량이 0이라면 시스템이 정상적인 상황이 아닌 것을 의미한다.

Young → Old (Promotion) 의 기준과 과정

Old영역으로 넘어가는 기준과 과정은 아래와 같다.

• GC가 수행될 때마다 살아남은 Object에는 Age를 기록한다.
• Hotspot VM에서 이 Age의 임계값의 기본값은 31이다.
  (Object Header에 Age를 기록하는 부분이 있고 6bits로 되어 있어서, 이걸로 표현할 수 있는 수치가 32라서 그렇다.)
• 이 임계값을 넘어가게 되면 Old Generation으로 Copy하는 작업을 수행한다.

Old영역으로 넘어가서 Survivor영역이 비게 되면 Compaction작업을 수행한다.

 

 

Old 영역에서 Young 영역을 참조하고 있는 경우를 구분하려면?

살아남았는지의 기준은 Reachable한지를 보는 것이다.
Root Set으로부터 참조가 가능하면 Reachable로 구분할 수 있지만, Old 영역의 객체가 Young 영역을 참조하고 있는 경우가 적게라도 존재할 수 있다.

이렇게 Old 영역에 있는 객체가 Young 영역의 객체를 참조하는 경우가 있을 때 해당 Young 영역의 객체가 사라지는 것을 막기 위한 장치가 필요하다.

이를 위해 Old 영역에는 512바이트의 chunk로 되어 있는 card table을 두고,
Old 영역에 있는 객체가 Young 영역의 객체를 참조할 때마다 표시해둔다.

Young 영역의 GC를 실행할 때는 Old 영역에 있는 모든 객체의 참조를 확인할 필요 없이, 이 card table만 뒤져서 GC 대상인지 식별하면 되는 것이다.

이 card table은 Minor GC를 빠르게 할 수 있도록 하는 장치인 write barrier를 사용하여 관리한다.
이로 인해 약간의 오버헤드가 발생하지만 전반적인 GC 시간은 줄어들게 된다.

 

Old 영역

---

Old 영역에서 발생하는 GC를 Major GC라고 한다.
Permanent 영역에서 발생하는 GC도 Major GC의 횟수에 포함한다.

Old 영역은 기본적으로 데이터가 가득 차면 GC를 실행한다. 방식에 따라서 처리 절차가 달라지므로 모두 살펴볼 필요가 있다.

주로 Old 영역에 대한 GC를 어떻게 수행하느냐에 따라 GC 알고리즘을 나누는 경향이 있으므로,
이 절에서 일반적인 GC 알고리즘의 명칭과 함께 알아보자.

 

Serial GC

---

Young 영역은 그대로 Generational Algorithm을 사용한다.

Old 영역에는 mark-sweep-compaction를 사용하는데, 절차는 아래와 같다.

1. Old 영역에 살아있는 객체 식별 (mark)
2. heap의 앞부분부터 확인하여 살아있는 것만 남기고 삭제 (sweep)
3. 살아남은 각 객체들이 연속된 형태로 존재하도록 힙의 가장 앞부분부터 채워서
   객체가 존재하는 부분과 존재하지 않는 부분으로 나눔 (compaction)

이 방법은 메모리가 적고 CPU 코어도 적은(1개인) 상황에 적합하다.
자원이 극히 적은 상황에 선택하는 방법이므로, 실제 운영하는 서버에 그냥 쓰게된다면 심각한 성능 저하를 불러온다.
일반적으로 절대 안쓰는 GC 방법이라고 보면 된다.

 

Parallel GC (Throughput GC)

---

Young 영역에는 Generational, Old 영역에는 mark-sweep-compaction을 수행하는 것이 Serial GC와 같지만,
Parallel GC는 GC를 처리하는 스레드가 여러개라는 차이가 있다.

Serial GC vs Parallel GC

그러므로 Parallel GC는 메모리가 충분하고 코어의 개수가 많을 때 사용하면 Serial GC보다 빠르게 객체를 처리할 수 있다.

Throughput GC라고도 부른다.

 

Parallel Old GC

---

Young 영역은 위의 방법들과 마찬가지의 방법이고,
병렬 스레드가 mark-summary-compaction 방법으로 Old 영역에 대한 GC를 수행한다.

절차

1. mark
   
   • Old Generation을 Region이라는 논리적인 단위로 균일하게 나눔
   • Region이 구분되면 스레드들은 각자 Region 별로 살아있는(Live / Reachable) 객체를 식별(표시)
2. summary
   • Region 단위로 작업 수행
   • Region 통계 정보를 바탕으로 각 Region의 Reachable object의 밀도를 평가한 후 Dense prefix를 설정해 GC 수행 범위를 정한다.
   • 이를 통해 Compaction 범위를 줄여 GC에 소요되는 시간을 줄인다.
   • Dense prefix 설정 후 Compaction 대상이 되는 Region의 First live object의 주소를 찾아 저장한다.
3. compaction
   • 모든 Thread가 각 Region을 할당 받아 Compaction 수행

 

Concurrent Mark & Sweep (CMS) GC

---

• Low pause collector
• Concurrent collector
• stop-the-world를 최소화 하기 위한 알고리즘
  (mark와 sweep을 애플리케이션 수행과 동시(병렬)로 처리할 수 있어서)

 

절차

stop-the-world가 일어나는 단계

1. Initial Mark
   • 클래스 로더(GC root)에서 가장 가까운 객체 중 살아 있는 객체만 찾는다.
   • 싱글 스레드로 처리한다.
   • 잠깐 찾으면 되므로 stop-the-world 상태가 매우 짧아진다.
2. Concurrent Mark
   • Initial Mark 단계에서 살아남은 객체(Root 객체)의 참조를 따라가면서 계속해서 살아있는(Reachable) 객체를 찾는다.
   • 싱글 스레드만 찾아나가는 데에 사용되고, GC 스레드 외의 애플리케이션 스레드는 그대로 동작한다
   • 따라서 stop-the-world 상태가 발생하지 않는다.
3. Remark
   • Concurrent Mark를 수행하는 동안 객체의 참조가 끊기거나, 새롭게 생긴 객체가 없는지 다시 한번 확인한다.
   • 멀티 스레드로 처리
   • stop-the-world 발생
4. Concurrent Sweep
   • 그 외의 살아있지 않는 객체들을 Sweep하는 단계이다.
   • 최종적으로 compaction은 없다.

 

장점

stop-the-world 시간이 매우 짧다. 

단점

그만큼 자원 (메모리, CPU)를 더 많이 사용하고, Compaction 단계가 없어 Old 영역의 크기가 충분하지 않거나 크기에 비해 조각난 메모리가 많을 경우 오히려 stop-the-world 시간이 늘어날 수 있다.

 

compaction 단계를 메모리 단편화가 너무 심해져 더 이상 메모리 사용이 어려울 때 추가하여 수행하면 좀 더 효율적이다.

 

발생 가능한 문제

단편화 문제

해결하기 위해 Free list를 사용하여 Young Generation에서 Promotion된 Object와 크기가 비슷한 Free space를 탐색하는 방법 고안하였으나 이 방법은 Young Generation의 부담만 가중시킨다.

Floating Garbage 문제

단계 중간에 Promotion이 되면 되자마자 (Remark 단계에 걸려) Garbage로 잡혀갈 수(...) 있다. 

 

G1 (Garbage First) GC

---

• Low pause collector
• Concurrent collector
• 4GB 이상의 heap 메모리, stop-the-world 시간이 0.5초 정도 필요한 상황에 사용
  (큰 메모리, 낮은 멈춤 시간)
• CMS Compact 단편화 문제 해결
• stop-the-world 시간 설정 가능 (대략 XX:MaxGCPauseMillis=N 과 같은 방법으로)
• Heap 영역을 동일한 크기의 영역으로 나누어 사용한다.
  • 즉, 물리적인 Generation 구분 (Young / Old / Perm) 을 없애고
    전체 heap을 1MB ~ 32MB 단위의 Region으로 재편성
  • 나누어진 영역 안에 Eden, Survivor, Old 구역도 동일한 크기로 나누어지는 것은 아니다.
  • heap 전체는 영역이고, heap 안에 나누어진 Young이나 Old는 구역으로 부른다.
  • 이러한 구역의 개수는 약 2000개 정도
  • GC 후 살아 있는 객체를 바탕으로 Young, Old 구역을 유연하게 나눈다.

이런 식으로 몰아놓지 않고 별도로 이 구역은 Eden! Survivor! Old! 라고 생각하는 것

그 대신에 G1 GC에는 다른 개념의 영역을 도입한다.

Humongous

• 이 영역은 구역 크기의 1/2 이상의 크기를 가진 객체를 저장하는 영역
• 이 영역은 GC 최적화가 되어 있지 않으므로, 큰 객체를 사용하는 애플리케이션은 G1 사용이 부적절하다.

Available/Unused

• 아직 사용하지 않는 구역

 

Allocation, Promotion 절차

1. 몇 개의 구역을 Eden 구역으로 지정 (새로운 객체가 할당되도록)
2. 이 구역에 객체가 생성, 저장
3. 이 구역이 가득차면 GC 수행
4. GC 수행 후 살아남은 객체를 Survivor 구역으로 이동시킨다
5. 1~4를 반복하다 오래 살아남은 객체는 Old 영역으로 이동시킨다

 

GC 절차

1. Initial Mark
   • Old 객체가 참조하는 Survivor 구역의 객체를 mark
   • stop-the-world 발생
2. Root Region Scan
   • Initial Mark에서 체크된 구역 스캔 (Minor GC 전에 완료되어야 함)
3. Concurrent Mark
   • heap 전체에서 살아있는 객체 mark
   • 구역 중 살아있는 객체가 없는 경우, 구역을 아예 삭제
   • 일부 stop-the-world 발생
4. Remark
   • heap에서 살아있는 객체 체크 완료 단계
   • stop-the-world 발생
5. Cleanup
   • 살아있는 객체가 작은 구역(미 사용 객체가 많은 구역)부터 제거
   • 제거 후 비어있는 구역을 Free list(여유 목록)에 추가
   • 일부 stop-the-world 발생
6. Copy
   • GC 대상 구역에서 살아있는 객체를 새로운 구역에 복사해 모은다
   • stop-the-world 상태 발생

 

초기에 쓰였던 아이디어인 Reference Counting Algorithm에 대해서도 보너스로 알아보자

Reference Counting Algorithm

---

Garbage의 Detection에 초점이 맞추어진 초기 Algorithm이다.
각 Object마다 Reference Count를 관리하여 Reference Count가 0이 되면 GC를 수행한다.

위 그림에서 a와 b는 각각 100, 99의 값을 갖는 Integer Object로 선언되어 있다.
각 Integer Object는 Referece Count가 1로 설정되어 있다.

이 상태에서 b = a로 변경하게 되면 a가 참조하고 있던 100의 값을 갖는 Integer Object는 참조가 없어지기 때문에 Reference Count가 0으로 감소하게 되고 GC가 수행된다.

장점

이 방식은 Reference Count가 0이 될 때마다 GC가 발생하기 때문에 Pause Time이 분산되어 실시간 작업에도 거의 영향을 주지 않고 즉시 메모리에서 해제된다.

단점

• 각 Object마다 Reference Count를 변경해 주어야 한다.
• 참조를 많이 하고 있는 Object의 Reference Count가 0이 될 경우 연쇄적으로 GC가 발생할 수 있는 문제가 있다.
• Reference Count의 관리 비용도 크다.
• Linked List와 같은 순환 참조 구조에서 Memory Leak이 발생할 가능성도 크다.

 

 

References

---

• https://www.slipp.net/wiki/pages/viewpage.action?pageId=30770388
• https://preamtree.tistory.com/118
• http://d2.naver.com/helloworld/1329
• https://medium.com/@joongwon/jvm-garbage-collection-algorithms-3869b7b0aa6f