[자바최적화] GC 알고리즘

삼색 마킹 알고리즘

실행할 때 노드의 상태를 삼색으로 표시하며 GC를 하는 알고리즘

• 흰색 (White): 초기 상태로, 아직 방문하지 않은 객체
  • GC 마킹 시작 시 모든 객체는 흰색, 최종적으로 흰색인 객체들은 도달 불가능한 객체로 판단되어 GC 대상
• 회색 (Gray): 탐색 중인 객체
  • 회색 객체는 자기 자신은 살아있지만, 자신이 참조하는 자식 객체들은 아직 방문하지 않았다는 의미
  • GC는 회색 객체의 자식 객체들을 탐색하며, 탐색이 완료되면 이 객체를 검은색으로 변경
• 검은색 (Black): 탐색이 완료된 객체
  • 검은색 객체는 자신과 자신이 참조하는 모든 객체가 살아있는 객체라는 것이 확인된 상태
  • GC는 더 이상 검은색 객체를 탐색하지 않습니다.

GC가 진행되는 동안 새로운 객체가 할당된다면?
예를 들면 탐색 완료되어 검정으로 표시된 객체에 새로운 자식 객체(흰색)이 할당된다면?
1. 쓰기 장벽: 검정 객체를 다시 회색으로 표시한다. 
2. 변경 사항을 추적하는 큐를 유지하고, 주요 단계가 완료된 후 보정 단계를 거친다. 이때 보정 단계는 STW를 동반한다.

G1 GC

영역 기반 세대별 컬렉터이며 예측 가능한 STW 시간 제공 (직접 시간 세팅)

Young-only GC

Eden 영역과 Survivor 영역을 상대로 마크-스윕 그리고 evaucation까지 모두 STW로 처리

 

Mixed GC

힙 점유율 임계값을 넘을 시 발생하는 GC

사이클중 모든 원은 stop-the-world가 발생한 것을 나타낸 것이고, 원의 크기에 따라 소요 시간이 달라짐

• 파란 원은 Minor GC(=Young GC)가 진행함에 따라 stop-the-world가 발생
  • STW가 짧게 일어남
• 주황 원은 Major GC(=Old GC, ConcurrentCycle)이 진행하면서 객체를 마킹 및 기타 과정을 하기 위해 stop-the-world가 발생
• 빨간 원은 Mixed GC를 진행함에 따라 stop-the-world가 발생 합니다.

 

1. Initial Mark: Old Region이 참조하는 Survivor Region 탐색, STW 발생

2. Root Region Scan: Survivor Region의 GC 대상 객체 스캔 작업, STW 발생 x

3. Concurrent Mark: 전체 힙 스캔, STW 발생 x

4. Remark: 최종 GC 대상 식별, STW 발생 -> 2, 3단계에서 객체 할당이 별도로 이루어졌기 때문에 잠시 멈춰서 변경사항을 모두 반영하는 단계

5. Cleanup: 애플리케이션을 멈추고(STW 발생) 살아있는 객체가 가장 적은 Region부터 수거, STW 발생. 마킹하며 Region 별 Liveness 정보를 정리하였기 때문에 가장 높은 효율의 Region부터 수거. 한번에 정리하지 않고 여러번에 나눠 수집하여 정해진 STW 시간을 맞추고자 함. 즉, G1 GC는 힙 크기가 커질수록 STW 시간이 증가할 수 있음을 의미

6. Copy: 살아남은 객체들을 새로운 Region에 Compaction하며 복사, STW 발생

 

셰넌도어 GC

 

G1 GC의 5,6 단계를 STW하지 않고 애플리케이션과 동시 진행하는 GC, G1 GC와 달리 Heap size에 영향 받지않는 STW 시간 제공(Concurrent Cleanup, Evaucation으로 아주 빠른 STW)

일반 객체와 달리, 브룩스 포인터로 객체가 이동될 때 새로운 객체를 참조하도록 표시를 함

Non-generational GC지만 특정 jdk 이상부터 generational 제공 -> 만들었던 개발자는 young은 수거될 가능성이 높을 것이라는 가정이 더이상 성립되지 않을거라고 예상했다고 한다. 그래서 non-generational으로 만들면 memory-copy가 덜 일어날거라는 설계 하에 만들어졌다고 함.

 

내용 레퍼런스 https://velog.io/@recordsbeat/Low-Pause-Shenandoah-GC

Low-Pause ! Shenandoah GC

 

GC(3) Pause Init Mark 0.771ms
GC(3) Concurrent marking 76480M->77212M(102400M) 633.213ms
GC(3) Pause Final Mark 1.821ms
GC(3) Concurrent cleanup 77224M->66592M(102400M) 3.112ms
GC(3) Concurrent evacuation 66592M->75640M(102400M) 405.312ms
GC(3) Pause Init Update Refs 0.084ms
GC(3) Concurrent update references  75700M->76424M(102400M) 354.341ms
GC(3) Pause Final Update Refs 0.409ms
GC(3) Concurrent cleanup 76244M->56620M(102400M) 12.242ms

• 마킹도 concurrent, compaction(객체 이동)도 concurrent
• 핵심 기법: Brooks-style indirection pointer + load barrier
  • 각 객체 앞/안에 “forwarding pointer(간접 포인터)”를 두고,
  • 객체 접근 시 load barrier가 항상 최신 위치로 따라가게 함
• 이 덕분에:
  • 객체를 이동시키는 동안에도 애플리케이션 스레드가 계속 돌 수 있음
  • compaction이 거의 완전히 concurrent하게 수행됨

 

1. Initial Mark: 스캔 시작점(root set) 탐색, STW 발생

2. Concurrent Mark: 전체 힙 스캔하며 reachable 오브젝트 탐색, STW 발생 x

3. Final Mark: 최종 GC 대상 식별, STW 발생 -> 2, 3단계에서 객체 할당이 별도로 이루어졌기 때문에 잠시 멈춰서 root set 재탐색. 회수 대상 집합인 Collection Set 생성

4. Concurrent Cleanup: 애플리케이션 쓰래드와 동시에 live 객체 없는 지역 제거

5. Concurrent Evacuation: 애플리케이션 쓰레드와 동시에 Collection Set에 없는 살아있는 객체 이동

6. Init Update Refs: evacuation 종료 확인, STW 발생

7. Concurrent Update References: Heap 전반에 걸쳐 concurrent evaucation 된 객체 참조 갱신.

8. Concurrent Cleanup: 참조가 없는 region 회수

 

그리고 모든 단계에서 객체가 읽히는 시점에 Load Ref Barrier가 발생, 즉 읽는 시점에 객체가 이동 중이라면 리다이렉션하여 새로운 값을 읽도록 함

 

 

ZGC

초저지연 GC 알고리즘으로 처음에 root set 탐색 외에는 모두 concurrent 하게 이루어짐

3bit의 colored pointer를 사용하여 하나의 물리메모리 주소를 3가지의 가상메모리 주소로 매핑함, 이 bit들로 객체의 현재 상태을 저장 (객체 마킹, 재배치 등등)

- mapped0

- mapped1

- remapped flag: 이동 중임을 표시

 

1. pause_mark_start: 각 스레드가 자신의 로컬 변수를 스캔하여 GC root을 모은 GC root set을 만듬. STW 발생하지만 로컬 변수가 많지 않아 매우 짧음

• mapped0, mapped1를 사이클 교대로 사용함. 이번 사이클에서 0를 사용했다면 다음 사이클은 1
• 새로운 ZPage(Relocatable Page) 생성, 살아있다고 판단한 객체는 해당 ZPage에 할당
• GC root 객체에 load barrier를 적용, 살아있는 객체라고 판단되는 객체를 mark stack에 넣음

2~4. concurrent mark

• mark stack 안에 있는 객체를 상대로 marking(coloring) 혹은 remapping
• marking: 접근 가능한 객체에 coloring를 하는 과정, zpage 안에 garbage 가 하나라도 존재하면 relocation set으로 분류

5. marking이 끝난 후 STW 발생시켜 soft, week, phantom reference 처리

6. 이전 GC 사이클에서 식별한 Relocation Set 초기화

8,9,10. relocation: coloring을 통해 참조가 끊긴 객체는 해제하고, 참조가 살아있는 객체들은 새로운 ZPage로 이동

 

void ZDriver::gc(const ZDriverRequest& request) {  
  ZDriverGCScope scope(request);

  // Phase 1: Pause Mark Start
  pause_mark_start();

  // Phase 2: Concurrent Mark
  concurrent(mark);

  // Phase 3: Pause Mark End
  while (!pause_mark_end()) {
    // Phase 3.5: Concurrent Mark Continue
    concurrent(mark_continue);
  }

  // Phase 4: Concurrent Mark Free
  concurrent(mark_free);

  // Phase 5: Concurrent Process Non-Strong References
  concurrent(process_non_strong_references);

  // Phase 6: Concurrent Reset Relocation Set
  concurrent(reset_relocation_set);

  // Phase 7: Pause Verify
  pause_verify();

  // Phase 8: Concurrent Select Relocation Set
  concurrent(select_relocation_set);

  // Phase 9: Pause Relocate Start
  pause_relocate_start();

  // Phase 10: Concurrent Relocate
  concurrent(relocate);
}

 

Remapping

Load Barrier에서 발생하는 메커니즘. 살아있는 객체를 새로운 ZPage로 옮겼으면 그 후 새로운 옮긴 주소를 바라볼 수 있도록 forwarding table에 기록한다. 이 상태를 remapped라고 한다.

Load Barrier에서는 객체가 읽힐 때 이전 주소로 참조가 들어오면 remapped flag를 확인하고 remapped된 주소를 참조하도록 한다.

remap bit = 1 이라면 최신 상태임을 뜻함

Reclaimed

이전 ZPage에 새로운 객체의 주소를 저장한 forwarding table이 할당되었으니 이제 메모리를 해제해야 한다. 이 과정을 recliamed라고 한다.

참고 https://d2.naver.com/helloworld/0128759#ch4