Concurrent Mark & Sweep GC와 한계
CMS 수집기는 Stop The World(STW) 시간을 최대한 줄이기 위해 설계된 올드 영역 (테뉴어드) 전용 수집기이다.
기존의 GC들과 병렬 수집기는 일단 Application을 멈춰 두고, Mark And Sweep방식으로 단순하게 객체들의 루트들을 탐색했다. DFS 방식으로 루트에서 부터 의존 객체들을 파고들며, 계속해서 죽은 객체들과 살아있는 객체들을 구분하고, 메모리를 수거했다.
왼쪽에 세로로 있는 배열이 Root 객체들의 목록이고, 거기서 부터 타고 타고 들어가는 것이다.
CMS는 Concurrent Mark & Sweep의 약자로, 최대한 STW 시간을 줄이고, Application가 작동중에 수거한다. (그래서 동시성 Mark & Sweep) CMS는 아래와 같은 방법을 통해 STW를 줄일 수 었었다.
- Tri-Color Marking을 사용하고, (Mark 방식)
- 수행 단계를 세분화 해서 STW 시간을 최대한 줄였다.
Java 9 부터는 기본적으로 G1 GC가 기본 GC이다. (Garbage First GC)
CMS는 그 이전에 사용되던 GC로 꽤나 위상이 높았었다. STW를 최대한 줄이기 위한 병렬 GC 이후에 사용되던 GC였으나, 이제는 G1 GC와 비교 대상으로써 알면 좋은 불쌍한 아이가 되었다. 이제, CMS가 STW를 줄인 방식 2가지를 알아보고, 한계점을 알아보자!
1. Tri-Color Marking (삼색 마킹)
삼색 마킹은 위대하고 고결한 Dijkstra 님께서 논문을 통해 증명한 알고리즘으로, 동시성 알고리즘과 GC의 정확성을 친히 증명하셨다. 삼색 마킹은 매우 효과적이기 때문에 CMS에서만 사용하는 것이 아니라, 최신 GC들에서 많이 사용한다고 한다.
삼색 마킹은 "검정색", "흰색", "회색"의 3가지 색을 활용하며 Marking하고, 일반적인 Mark & Sweep 보다 좀 더 복잡한 과정을 거쳐 Marking한다.
1.1 삼색 마킹의 작동방식
이제 작동 방식을 알아보자. 헷갈렸었는데, 그림을 보니까 쉽다.
- GC 루트를 "회색"으로 마킹한다. 이 "회색" 노드들은 탐색의 시작점이 된다.
- 다른 객체들은 모두 "흰색"으로 표시한다.
- 이제, 마킹을 담당하는 마킹 스레드가
임의의 회색 노드로 이동한다. - DFS로 탐색하는데,
흰색인 자식 노드가 있는 회색 노드를 만나게 된다면 그 자식 노드들을 모두 "회색"으로 표시한 뒤, 해당 노드를 "검은색"으로 표시한다.
그러니까, 자식이 있는 흰색 노드를 새로운 루트 삼아 하위에 있는 자식 노드들을 탐색하는데, 그 자식들도 새로운 루트가 될 수 있으므로 (탐색 시작 지점이 될 수 있으므로) 회색으로 표시하는 것 같다. 그리고, 표시를 완료했다는 의미로 검은색을 칠하는 것 같다. - 회색 노드가 하나도 남지 않을 때까지 이 과정을 되풀이한다!
6.1 색칠이 끝난 시점에 "검은색"인 노드는 Reachable한 노드이므로, 살아남게 된다.
6.2 아직도 흰색인 노드는 Unreachable 한 노드이므로, 수집 대상이 된다!
1.2 동시 수집기에 삼색 마킹을 적용했을 떄의 단점
(관심 없으면 패스해도 된다. 사소한 문제라고 한다.)
동시 수집기들은 보통 Snapshot at the Beginning (SATB) 기법을 적극 활용한다. 이 기법은 수집 사이클을 시작하는 시점에 스냅샷을 찍고, 이때 할당된 객체들이 Live 객체라고 간주하는 것이다.
삼색 알고리즘이 이런 SATB 기법을 활용하는 GC와 쓰일 때, 사소한 담점이 몇개 있다.
이미 어떤 객체를 검은 색으로 색칠하고, 하위 객체를 회색으로 색칠했는데, 그 하위에 새로운 객체가 만들어져서 흰색이 되는 경우이다. 이 경우, 실제로는 Reachable한데, 흰색이기 때문에 단단히 오해를 사서 수집당해 버릴 수 있다.
이러한 실행 중인 Application 스레드의 변경으로 인한 Live 객체 수집을 막기 위해서 여러 방법을 시도해볼 수 있다.
- 쓰기 배리어 : 객체가 추가되는 경우 상위 노드를 검은색에서 회색으로 바꾼다. 이로써 한번 더 확인하게 만든다.
- 삼색 불번의 법칙 (동시 마킹 중에는 검은 노드가 흰색 노드를 가리킬 수 없다)을 어길 수도 있는 변경사항들을 큐와 같은 자료구조에 모아둔 다음 확인한다.
이러한 방법들로 CMS와 삼색 마킹을 함께 사용했을 때의 단점을 보완해볼 수 있다.
2. Concurrent Mark & Sweep GC
분량 조절 실패 + 이동해야 해서 CMS GC는 2편에서 ㅋ