[JVM] GC의 객체회수과정은 어떻게 일어나는가? - 마크-스윕, 마크-카피, 마크-컴팩트

https://dev-dx2d2y-log.tistory.com/163

[Java] JVM 끝까지 파헤치기 독서 #5 - 가비지 컬렉터의 알고리즘 이론

가비지컬렉션은 '도달 가능성 분석 알고리즘'을 따른다. 이의 세부적인 구현방식은 GC에 따라서, 가상머신에 따라서 차이가 있다. 앞으로 몇 개의 게시글에서 이 가상 머신의 GC 알고리즘에 대해 알아보기로한다.

 

상세이론은 리처드 존스(Richard Jones) 등의 <The Garbage Collection Handbook> (2nd edition, Chapman and Hall/CRC, 2023)의 2~4장을 참조하면된다.

---

세대 단위 컬렉션 이론

현재 상용 가상 머신들이 주로 채택하는 가비지 컬렉터는 이 이론에서 기초하였다. 다음 두 가지 가정에 기초한다.

 

1. 약한 세대 가설 (weak generational hypothesis): 대다수 객체는 일찍 죽는다.

2. 강한 세대 가설 (strong generational hypothesis): 가비지 컬렉션 과정에서 살아남은 횟수가 많은 객체일수록 더 오래 살아남을 확률이 크다.

 

위 두 가지 가정에 기초하여

자바힙을 몇 가지 영역으로 나누고 객체들을 GC에서 살아남은 횟수(나이)에 따라서 각기 다른 영역에 할당하는 것이다. 그래서 GC에서 살아남은 횟수가 많은 객체들은 GC를 동작시켜 그 영역을 회수하는 빈도를 줄이도록하는 것이 가장 기본적인 세대 단위 컬렉션 이론이다. 가상 머신의 메모리에도 한계가 있으므로 이렇게 동작시키면 GC에 드는 시간도 줄고 메모리 공간도 효율적으로 이용할 수 있다.

 

이렇게 세대를 구분하여 힙을 관리하면 힙을 최소한 두 개로 나눠지게된다. 바로 신세대(핫스팟 가상머신에서 ParNewGeneration 이 가비지컬렉터)와 구세대(DefNewGeneration)로 나눠지게되고, GC를 한 번에 한 개, 또는 여러 세대에서 작동시킬 수 있다.

 

모든 세대에서 적용되는 전체GC, 힙의 일부만 회수하는 부분 GC로 이루어지며, 신세대만을 가비지컬렉션의 대상으로 삼는 마이너 GC, 구세대만을 대상으로 삼는 메이저GC, 신세대전체와 구세대 일부를 대상으로 삼는 혼합GC가 있다.

 

흔히 자바의 GC 알고리즘으로 나오는 마크-스윕(mark-sweep: 표시 후 쓸기), 마크-카피(mark-copy: 표시 후 복사), 마크-컴팩트(mark-compact: 표시 후 모으기) 등은 모두 이 이론에 기초한 것이다.

---

뒤엉킨 참조에서 나온 세 번째 가정

힙을 몇 가지 세대로 나누고 각 세대마다 GC를 동작시킨다는 것. 좋아보인다.

 

하지만 신세대에 있는 객체를 구세대에서만 참조하고 있다면? 그럴 때에는 고정된 GC 루트들 뿐 아니라 구세대 객체까지 모두 뒤져야한다. 반대도 마찬가지(이지만 구세대에서만 작동하는 가비지컬렉터는 거의없다.). 이렇게 전체세대를 모두 뒤진다면야 성능면에서 큰 부담이 될 것이고, 그래서 세 번째 가정을 하나 추가해야한다.

 

3. 세대 간 참조 가설(intergenerational reference hypothesis): 세대 간 참조의 개수는 같은 세대 안에서의 참조보다 훨씬 적다.

 

만약 신세대 객체가 구세대 객체와 참조관계를 가지고 있다면, 구세대 객체는 잘 죽지 않으므로 (2번째 가정) 가비지컬렉션을 거쳐도 얼마안가 신세대 객체도 구세대 객체로 올라갈 것이다. 그러면 신세대 객체와 구세대 객체가 같은 구세대 객체가 되었으므로 세대 간 참조가 사라진다.

 

이는 '경험적 추론'으로, 이론상으로는 세대 간 참조의 수가 1000개가되고, 세대 안의 참조가 10개가 될 수는 있지만, JVM환경에서 그런 일이 발생하는 경우는 거의 없었다는 경험 아래 세워진 가정이다.

 

위 가정에 따르면 세대 간 참조의 수는 아주 적기 때문에 구세대를 모두 훑기보다는

구세대 영역을 여러 작은 부분들로 나누고, 세대 간 참조가 발생하는 부분을 기록한다. 이 때 기록은 '기억집합'이라는 전역 데이터 구조를 만들어 구세대 어느 부분에서 세대 간 참조가 발생했는지 기록한다.

 

이후 마이너GC가 수행되면 기억집합에 기록된 세대 간 참조를 수행하는 구세대 영역의 부분들이 GC루트에 추가된다. 런타임에 해야할 일은 늘어나지만, 구세대 전체를 훑는 비용보다는 싸다.

---

마크-스윕 알고리즘

현대 프로그래밍 언어의 기초를 닦은 리스프의 창시자 존 맥카시가 1960년에 제안한 최초이자 가장 기본적인 가비지컬렉션 알고리즘이다. 이름처럼 회수할 객체를 모두 표시(mark)하고 이를 일괄적으로 쓸기(sweep)를 통해 메모리를 회수하는 두 단계로 나뉘어져 진행한다.

회수할 객체를 찾는 것은 GC루트를 하나 잡아서 도달 가능성 분석 알고리즘을 통해 회수해야할 객체를 찾아내고, 세대 단위 컬렉션 이론으로 부분GC를 수행할 경우 신세대 영역과 '기억집합'을 통해 세대 간 참조가 일어나는 구세대 객체들을 GC루트로 잡고 도달 가능성 알고리즘을 수행한다.

 

마크-스윕의 탄생배경에서 알 수 있듯이 현대 가비지컬렉션 알고리즘들은 대부분 이를 기초로한다. 이 마크-스윕 알고리즘의 단점을 보완하는 방법으로 발전했다. 마크-스윕 알고리즘의 단점은 크게 두 가지가 있는데..

 

1. 실행효율이 일정하지 않다.

힙메모리에 객체가 많아질수록 그 객체들을 하나하나 확인하고, 또 그 중에서 많은 부분이 회수대상이라면 그 회수대상들을 하나하나 표시하고 회수하는 일에 부하가 생기기 마련이다. 객체가 많을수록 효율이 떨어진다.

 

2. 메모리 파편화가 심하다.

처음에는 연속적으로 객체를 저장했지만 GC가 계속 수행되고나면 죽은 객체들의 자리가 비어버린 불연속적인 메모리 구조가 생긴다. 파편화가 극심한 경우 프로그램이 큰 객체를 저장하기 위한 연속적인 메모리 공간을 찾기 어려워지고, 결국에는 가비지컬렉션이 한 번 더 일어나게된다.

---

회수할 객체가 많더라도 효율적으로 회수하자 - 마크-카피 알고리즘

카피 알고리즘이라고도한다.

마크-카피 알고리즘은 가용메모리공간을 두 개로 나눈다. 한 쪽이 꽉 차면 죽은 객체들은 지워버리고 생존한 객체들만 다른 한 쪽에 복사하고 기존 블럭은 일괄적으로 청소한다.

 

대다수가 살아남는다면 메모리 복사에 상당한 시간이 소요되겠지만, 대다수가 회수된다면 소수의 객체만 복사하면되므로 성능문제가 크지 않다. 또한 복사 후 새로운 메모리 공간에 연속적으로 객체를 저장하면되므로 메모리 파편화 문제에서도 벗어난다.

 

IBM에서의 연구에 따르면 신세대 객체 중 98%가 첫 번째 GC에서 삭제된다. 즉, 대다수의 객체는 회수되므로 성능문제가 그리 큰 편이 아니며, 현재 상용 자바 가상 머신 대부분은 이 알고리즘을 사용한다.

 

다만 단점도 있는데, 가용메모리를 절반으로 줄였으므로 메모리 누수가 있다는 편이다.

---

위의 IBM 연구에서 신세대 객체 중 98%가 첫 번째 GC에서 삭제된다고했는데, 이를 역으로 생각해보면 굳이 신세대용 메모리 영역을 1:1로 나누지 않아도된다.

 

굳이 IBM 연구 때문이 아니라, 핫스팟 자바 가상머신은 신세대를 하나의 큰 에덴 공간과 두 개의 작은 생존자 공간으로 나눈다. 메모리를 할당할 때에는 에덴과 하나의 생존자 공간만을 사용한다.

이후 가비지컬렉션이 시작되면 에덴에서 살아남은 객체들과 생존자공간에 있던 객체들을 나머지 한 쪽에 생존자 공간으로 이동시키고 에덴과 기존 생존자 공간을 비우며 가비지컬렉션을 수행한다. 생존자영역에서 일정 횟수 이상 가비지컬렉션에서 살아남으면 구세대로 이동한다.

 

이렇게하면 대다수가 삭제되는 신세대 객체들의 특성을 잘 반영하면서 메모리를 효율적으로 사용할 수 있다. 일반적으로 신세대 공간에서 에덴과 생존자공간의 비율은 8:1. 나머지 10%는 빈 공간이다. 위에서 말했듯이 신세대 객체가 98% 회수된다고는하나 10% 넘게 살아남는 일이 일어나지 않는다고 단정지을 수는 없다. 이러한 특이케이스에 대처하기 위해 만들어진 10%의 빈공간이 마련되어있다.

 

이는 '메모리 할당 보증'이라는 매커니즘으로, 마이너GC에서 생존자를 생존자 구역에서 전부 수용하지 못할 경우, 다른 메모리 영역을 활용해 메모리를 할당하는 것을 말한다. (핸들 승격)

 

이를 '아펠 스타일 컬렉션'이라고 칭한다.

---

구세대에서는 어떻게? - 마크-컴팩트 알고리즘

많은 객체들이 회수되는 신세대에서는 마크-카피 알고리즘이 괜찮은 선택이지만, 많은 객체들이 회수되지 않는 구세대에서는 적합하지 않은 선택이다.

 

구세대 객체들은 마크-컴팩트 알고리즘을 사용한다. 표시까지는 마크-스윕과 동일하지만, 마크-스윕 알고리즘에서는 마크된 객체의 메모리를 회수하는 방식으로 진행했지만, 마크-컴팩트 알고리즘에서는 생존한 모든 객체를 한쪽 메모리 끝으로 옮긴다음 나머지 공간을 한꺼번에 비운다.

 

이렇게되면 연속적인 메모리공간을 얻을 수 있어 파편화 문제에서 벗어나게된다. 구세대 영역에서는 많은 부분들이 회수대상이 아니므로 마크-스윕 알고리즘의 문제점에서도 어느정도 벗어나게된다.

 

다만 문제는 '객체를 한쪽 메모리 끝으로 옮긴다'라는 것인데, 이렇게되면 메모리를 옮길 뿐 아니라 그 메모리를 참조하던 모든 곳에 들어가서 참조값을 수정해야한다.

 

https://dev-dx2d2y-log.tistory.com/150

[Java] JVM 밑바닥까지 파헤치기 독서 #3 - 자바는 어떻게 객체를 불러오는가?

핫스팟에서 사용되는 다이렉트 포인터 방식을 예시로 들면, 힙 메모리에 저장된 공간의 메모리가 변했으므로 스택 지역변수 테이블에서 해당 객체를 참조 중인 모든 참조변수를 찾아가 참조값을 바꿔야한다.

 

신세대 영역에서는 대부분의 객체가 사라지다보니 마크-카피 알고리즘을 사용해서 메모리 주소가 바뀌더라도 큰 문제가 없었지만, 대다수의 객체가 생존하는 구세대 영역에서는 또 하나의 문제가 발생하게된 것이다. 또한 메모리를 이동시키고 참조를 갱신하는 과정은 애플리케이션을 중단한 상태에서 진행되야하므로 (옮기다가 신세대 영역에서 객체가 날아오면 섞이니까) 신중히 고려해야한다.

 

그렇다고 메모리 이동을 하지 않으면 결국 다시 마크-스윕 알고리즘의 문제점으로 돌아가게된다. 결국에는 메모리 이동을 하지 않아 생기는 메모리 파편화로 인한 메모리 공간을 읽어오는데 걸리는 소요시간의 증가와, 메모리 이동을 통해서 일어나는 스레드 정지, 참조값을 하나하나 바꾸기 등의 문제에서 저울질해야한다. 가비지컬렉터 시 '일시정지시간'을 기준으로하면 마크-스윕이, 전체 프로그램의 '처리량'을 기준으로하면 마크-컴팩트 알고리즘이 더 좋다.

 

따라서 가상 머신의 구현자들은 모두 이 두 개의 특징에서 고민해야한다. 같은 핫스팟 가상머신에 속하지만 패러렐-올드 컬렉터는 마크-컴팩트 알고리즘을, CMS 컬렉터는 마크-스윕 알고리즘을 사용하는 것이 이를 증명한다.

 

 

다만 이 둘의 장점을 섞은 해법도 있다. 기본을 마크-스윕 알고리즘을 실행하다가 파편화가 객체 할당에 영향을 줄 정도로 심해지면 마크-컴팩트 알고리즘을 활용해 연속된 공간을 확보하는 방안으로 주로 사용된다. CMS가 마크-스윕을 기초로하지만 위 방식을 사용한다.