JVM 시리즈 - 가비지 컬렉션 알고리즘
가비지 컬렉션 알고리즘
객체의 생사를 판별하는 기준으로 가비지 컬렉션 알고리즘은 ‘참조 카운팅 GC’와 ‘추적 GC(도달 가능성 분석 알고리즘 사용)’로 나눌 수 있다. 각 방법에 대해서는 앞선 글에서 설명했으니 넘어가겠다. 현대 주류 자바 가상 머신은 추적 GC 알고리즘을 사용한다.
세대 단위 컬렉션 이론
현재 상용 가상 머신들이 채택한 가비지 컬렉터는 대부분 세대 단위 컬렉션 이론을 활용한다. 이는 2 가지 과정에 뿌리를 두고 있다.
- 약한 세대 가설 : 대다수 객체는 일찍 죽는다.
- 강한 세대 가설 : 가비지 컬렉션 과정에서 살아남은 횟수가 늘어날수록 더 오래 살 가능성이 커진다.
이 가설을 바탕으로 설계를 했다면, 자바 힙을 몇 개의 영여긍로 나누고 객체들을 생존 횟수(나이)에 따라서 각기 다른 영역에 할당한다. 이렇게 여러 영역으로 나누면 가비지 컬렉터는 선택적으로 영역에 대해서 회수가 가능하다. 뿐만 아니라, 각 영역에 담긴 객체들의 특성에 따라서 마크-스윕, 마크-카피, 마크-컴팩트 등의 가비지 컬렉션 알고리즘을 구분해 적용할 수도 있다.
세대 단위 컬렉션 이론의 맹점
객체들은 단독으로 존재하지 않는다. 경우에 따라서는 다른 세대에 존재하는 객체들을 참조하는 상황이 벌어질 수도 있다. 신세대를 가비지 컬렉션하고 싶어도, 신세대지만 구세대에 속하는 객체가 참조 중일 수 있다. 따라서 살아남을 객체를 찾으려면 구세대 객체까지 모두 탐색해야 한다.
이는 확실히 성능상 부담이 될 것이고, 이를 방지하기 위해서는 또 다른 가설을 세워야 한다.
- 세대 간 참조 가설 : 세대 간 참조의 개수는 같은 세대 안에서의 참조보다 훨씬 적다.
만약 신세대 객체가 구세대 객체와 참조 관계에 있다면, 신세대 객체는 구세대 객체 덕에 살아남을 것이고, 구세대로 승격될 것이다. 따라서 어느 순간에는 세대 간 참조는 자연스럽게 사라진다. 그런데 이를 위해서 항상 구세대 전체에 참조가 있는지 확인하는 것은 낭비다. 이를 막기 위해서 신세대에 기억 집합이라는 전역 데이터 구조를 두고, 그 구조를 통해 구세대를 여러 조각으로 나눈 뒤, 어느 조각에 세대 간 참조가 있는지 기록해 관리하기만 하면 된다. 이 기록을 통해서 마이너 GC 가 일어나는 상황에서 살릴 객체군을 찾을 수 있다.
마크-스윕 알고리즘
마크 스윕은 1960 년에 제안된 가장 기본적인 가비지 컬렉션 알고리즘이다. 작업을 표시와 쓸기 두 단계로 나눠 진행하는 것이다. 회수할 객체를 표시하고, 쓸어서 회수하는 것이다. 이 알고리즘은 2가지 단점이 있다.
- 실행 효율이 일정하지 않다. 힙에 다양한 객체가 있고 대부분이 회수 대상이라면 표시하는 것과 회수하는 것이 모두 비용이 많이 드는 작업이된다. 즉, 객체가 많아질수록 작업 효율이 좋지 않다.
- 메모리 파편화가 심하다. 쓸고 지나간 자리에는 불연속적인 메모리 파편이 만들어진다.
마크-카피 알고리즘
마크-스윕 알고리즘에서 발생할 수 있는 1번 문제를 해결하기 위해 만들어진 알고리즘이다. 가용 메모리를 똑같은 크기의 2 블록으로 나누고, 한 번에 한 블록만 사용한다. 한쪽 블록이 꽉 차면 살아남은 객체들만 다른 블록에 복사하고 기존 블록을 한 번에 청소한다.
복사에 비용이 들지만, 메모리 파편화 문제가 해결된다. 단점은 가용 메모리가 절반 뿐이라는 것이다. 오늘날 상용 가상 머신 대부분은 이 알고리즘을 활용한다. IMB 의 연구 결과에 따르면 신세대 객체 중 98% 가 첫 번째 가비지 컬렉션에서 제거된다. 이 특성을 반영한 전략인 아펠 스타일 컬렉션이 존재한다. 이는 1:1:8(s1 : s2 : 에덴) 로 메모리를 나누는 전략이다.
객체는 s1, s2 중 하나와 에덴에 생성되고, 가비지 컬렉션의 결과로 살아남은 객체만이 다른 쪽 생존 공간으로 복사된다. 즉, 전체 메모리 중 90% 를 활용하고, 대부분의 객체가 회수되기에 살아남은 객체는 10% 의 공간으로 복사가 된다. 물론, 살아남는 객체가 10% 이상일 가능성이 있기에 이를 대처하기 위해서 만약 살아남은 객체가 10% 이상이라면 생존자 공간 뿐 아니라, 구세대 영역도 활용할 수 있도록 했다.
이 전략은 대부분의 신세대 가상 머신에서 채택됐다.
마크-컴팩트 알고리즘
마크-카피 알고리즘은 살아남는 객체가 많을 수록 복사 효율이 좋지 않기에, 구세대에서 사용하기에는 적합하지 않다. 구세대 객체들의 생존 특성을 감안한 알고리즘이 마크-컴팩트 알고리즘이다.
출처: sympony-solutions
가비지 컬렉션 후 살아남은 객체를 이동시키는 것이다. 객체의 이동에는 장단점이 있다. 객체 이동은 애플리케이션을 멈추는 행위지만, 메모리 읽기의 효율을 증가시킨다. 따라서 처리량에 중점을 뒀다먼, 마크 컴팩트 알고리즘을 사용하는 것이 좋고, 지연 시간을 줄이기 위해서는 마크-스윕 알고리즘을 사용한다고 이해할 수 있을 것이다.