[CS] GC 알고리즘

GC는 heap 영역에서 발생하며, 더 이상 참조되지 않고 있는 객체를 알아서 해제해주는 작업을 말한다.

GC 메모리 해제 과정

1. Marking

사용하는지 하지 않는지 ( 참조 or not ) 체크 → 모든 오브젝트 스캔 → 시간 소모 많음

2. Normal Deletion

참조되지 않는 객체를 제거 → 메모리를 반환. 메모리 할당기는 반환되어 비어진 블럭의 참조 위치를 저장해 두었다고 새로운 오브젝트가 선언되면 할당되도록 합니다.

3. Compacting

퍼포먼스 향상 위해 참조x 객체 제거 → 남은 객체 묶기 → 공간 생성 → 메모리 할당 빠름

Generational Garbage Collection 배경

모든 객체 mark, compact하는건 비효율

→ 시간이 갈수록 적은 객체만 남는다 ( Weak Generational Hypothesis 기반한 그래프로 알수있음 )

Weak Generational Hypothesis

자바는 young (신규) / old ( 오래됬냐? ) 영역으로 메모리 분리

Generational Gabage Collection

GC Collection

1. #Young 영역(Yong Generation 영역)
2. 새롭게 생성한 객체의 대부분이 여기에 위치합니다. 이 영역에서 객체가 사라질때 Minor GC 가 발생한다고 말합니다.
3. #Old 영역(Old Generation 영역)
4. 접근 불가능 상태로 되지 않아 Young 영역에서 살아남은 객체가 여기로 복사됩니다. 대부분 Young 영역보다 크게 할당하며, 크기가 큰 만큼 Young 영역보다 GC는 적게 발생합니다. 이 영역에서 객체가 사라질 때 Major GC(혹은 Full GC) 가 발생한다고 말합니다.
5. #Permanet 영역
6. Method Area라고도 합니다. JVM이 클래스들과 메소드들을 설명하기 위해 필요한 메타데이터들을 포함하고 있습니다. JDK8부터는 PermGen은 Metaspace로 교체됩니다.

Generational Garbage Collection 과정

1. 새로운 객체 할당되면 Eden space에 저장
2. Eden space 꽉차면 minor garbage collection이 시작
3. 참조되는 객체들은 첫 번째 survivor(S0)로 이동되어지고, 비 참조 객체는 Eden space가 clear 될 때 반환
4. 다음 minor GC → eden space에서 비참조 객체 삭제 → 참조객체는 두번째 survivor space로 이동 → 최근 minor GC에서 첫번째 survivor space로 이동한 객체들 s1으로 이동 → s0, eden 공간 clear
5. 다음 minor GC 반복 → survivor space들은 switch → eden, s1 clear
6. minor GC 후 aged 오브젝트들이 일정한 age threshold(문지방)을 넘게 되면 그들은 young generation에서 old로 promotion 되어집니다.
7. minor GC → 객체들이 old generation으로 이동 ( young에서 promotion해서 old로 이동 )
8. major GC가 old Generation에 시행되고, old Generation은 Clear 되고, 공간이 Compact 되어집니다.

GC 알고리즘

1. Serial GC

싱글 스레드로 동작하며, Mark - Sweep - Compact 로 진행된다

• GC를 수행하는 동안 다른 스레드들은 작업을 모두 멈추게 하는 STOP THE WORLD 발생
• 단일 스레드가 GC수행 하므로, 시간 소요가 많아서 잘 사용되지 않음

Serial GC

2. Parallel GC

멀티 스레드로 동작하며, Mark - Sweep - Compact 로 진행된다

• Young 영역에서 일어나는 Minor GC를 멀티스레드로 처리해 STOP THE WORLD 시간 단축
• Java 7, 8의 기본 GC 알고리즘

Parallel GC

3. Parallel Old GC

멀티 스레드로 동작하며, Parallel GC와는 다르게 Old영역에서도 멀티로 처리한다 Young영역에서는 Mark - Sweep - Compact 로 진행된다 Old 영역 Mark - Summary - Compact 로 진행된다

• Young, Old 영역에서 일어나는 GC를 멀티스레드로 처리해 STOP THE WORLD 시간 단축
• Old 영역 GC 과정
  • Mark : Old 영역을 region별로 나누고 region별 자주 참조되는 객체들을 식별(mark)한다
  • Summary : region별 통계정보로 살아남은 객체들의 밀도가 높은 부분이 어디까지인지 dense prefix를 정한다 ( dense prefix를 기준으로 compact 영역을 줄인다. )
  • Compact : destination과 source로 나누어, 살아남은 객체는 destination으로 이동시키고 참조되지 않는 객체는 제거한다.

4. CMS(Concurrent Mark Sweep) GC

low-latency GC 라고도 불리며, stop the world로 어플리케이션이 멈추는 현상을 줄이고자 나온 GC 알고리즘이다.

• Young 영역에 대한 GC는 Parallel GC와 동일하다.
• heap 메모리를 region이라는 일정한 부분으로 나누어 메모리를 관리한다.
  • heap을 균등하게 region으로 나누고 각 region을 논리적으로 구분(Eden region인지, Survivor region인지, Old region인지)하여 객체를 할당한다
• GC는 stop the world 속도가 짧으므로 응답 속도가 중요한 어플리케이션의 경우 사용된다.
• 다른 GC보다 CPU,메모리 소모가 많고, Compaction 단계가 없다 ⇒ 조각난 메모리가 많으면 STOP THE WORLD의 시간 증가 → 사용 중지 됨

CMS(Concurrent Mark Sweep) GC

1. Initial mark : GC의 root가 참조하는 객체만 마킹한다(stop the world 발생)
2. Concurrent mark : 참조하는 객체를 따라가며 지속적으로 마킹한다(stop the world 없이 발생, 마킹하는 스레드 외 다른 스레드들도 작업 가능)
3. Remark : Concurrent mark 과정에서 변경된 사항이 없는지 다시 한 번 마킹을 진행한다(stop the world 발생)
4. Concurrent Sweep : unreachable 객체를 제거한다(stop the world 없이 발생)

5. G1 GC

G1 GC

• Java 9의 기본 GC 알고리즘이다. 현재 GC 알고리즘들 중 stop the world 시간이 가장 짧다
• G1 GC에서는 Eden, Survivor, Old region에 더하여 Humongous와 Available/Unused라는 2가지 region을 추가하였다.
• Humongous는 region 크기의 50%를 초과하는 객체를 저장하는 region을 의미하고, Available/Unused는 사용되지 않은 region을 의미한다.
• heap 전체에 대한 탐색을 진행하지 않고 부분적으로(region 단위) 탐색하여 garbage가 많은 region에 우선적으로 GC를 수행한다. compaction 과정에서도 heap 메모리 전체에 대해 compaction을 진행하지 않고 region 내에서 compaction이 이루어지므로 전체적으로 GC에 소요되는 시간이 감소한다.

1) G1 GC Minor GC

특정 region에 객체를 할당하다가 해당 region이 꽉 차면 다른 region에 객체를 할당하고 꽉찬 region에 대해 Minor GC가 수행된다.

이때, G1 GC는 각 region을 추적하고 있으므로 garbage가 많은 지역을 찾아 Mark and Sweep 을 진행한다.

Eden region에서 GC가 수행되면 살아남은 객체를 식별(mark) 하고 메모리를 회수(sweep) 한다.

그리고 살아남은 객체들을 다른 region으로 이동시킨다.

이동된 region이 Available/Unused 지역이면 해당 지역은 Survivor region이 되고, Eden region은 Available/Unused 지역이 된다.

Minor GC 발생 시

• Eden -> Available/Unused
• Available/Unused -> Survivor

2) G1 GC Major GC

시스템이 운영되다가 객체가 너무 많아 빠르게 sweep이 불가능할 때 Major GC(Full GC)가 수행된다.

기존의 GC 알고리즘은 모든 Heap 영역에서 수행되어 시간이 오래 소요되었다.

하지만 G1 GC는 어느 영역에 garbage가 많은지 알고 있으므로 GC를 수행할 지역을 조합하여 해당 region에 대해서만 GC를 수행한다.

이러한 작업은 Concurrent하게 발생하여 애플리케이션의 지연도 최소화 가능하다.

G1 GC가 다른 GC 알고리즘들에 비해 자주 호출될 것이나, 작은 규모의 메모리 정리 작업이고 concurrent하게 수행 가능하므로 어플리케이션이 크게 지연되지 않는다.

또한 garbage가 많은 region에 대해서 정리를 하므로 훨씬 효율적이다.

참조

https://velog.io/@guswlsapdlf/Java-GC-알고리즘