들어가며

Garbage Collection 즉 GC 는 메모리 관리 방법 중 하나이며 JVM에서 메모리를 관리하는 방법입니다.

말 그래도 쓰레기를 수집하는 기능이며 쓰레기는 실제 쓰레기를 뜻하는게 아니라 개발자가 동적으로 할당한 메모리 영역 중 더 이상 쓰이지 않는 영역을 말합니다.

가비지 컬렉션은 그러한 영역을 자동으로 찾아내어 해제하는 기능을 합니다.

그러면 가비지 컬렉션은 어떻게 더 이상 쓰이지 않는 영역을 탐지하는 알고리즘이 어떤 것이 있는지 확인해 보겠습니다.

알고리즘

GC는 작동 방식에 따라 크게 두 가지로 분류 가능합니다. ₂₎

참조 횟수 카운팅 GC ( Reference Counting Garbage Collection )
추적 기반 GC ( Tracing Garbage Collection )

참조 횟수 카운팅 GC ( Reference Counting Garbage Collection )

Reference Counting GC는 GC의 초기 알고리즘으로 Gabrage 를 발견하는 것에 초점이 맞추어져 있습니다. 어느 한 메모리가 다른 메모리를 얼마나 많이 참조하는지 횟수를 세어서 메모리 접근 가능과 불가능을 나누는 방식입니다.

예를 들어 A 메모리가 B 메모리를 참조하면 B 메모리의 참조 횟수를 1을 더하고, A 메모리가 B 메모리 참조를 중단하면 B 메모리 참조 횟수를 1을 뺍니다.

만약 1을 뺐을 때, 참조 횟수가 0이 되면 해당 메모리에 아무도 접근을 못 하는 것이므로 해당 메모리를 해제합니다.

장점

다른 GC 알고리즘에 비해 구현이 매우 간단한 편입니다.

또한 참조횟수가 0이 되자마자 소멸한다는 장점도 있습니다.

단점

크게 두 가지 단점이 존재합니다.

오버헤드

참조 횟수를 변경하도록 구현을 하는데 이러한 부분이 프로그램을 느리게 만듭니다. 참조 횟수를 + 하는 부분 보다 - 를 하는 부분에서 정수 감소, 조건문, 함수 호출 등이 실행될 수 있어서 대입이 빈번히 일어나는 곳에서는 성능이 좋지 않습니다. 또한 캐시 효율이 낮아질 수도 있습니다.
무한 참조 ( Cyclic Reference )

메모리들이 서로 참조하는 형상입니다. 예를 들면 다음과 같습니다. 메모리 A가 메모리 B를 가리키고, 메모리 B가 메모리 A를 가리키면 두 메모리의 참조 횟수는 모두 1입니다. 하지만 만약 다른 메모리에서도 메모리 A나 B에 접근 가능한 루트가 없다고 하면 둘 다 GC에 의해 해제되어야 합니다. 그러나 메모리 A와 B 모두 서로를 참조하고 있어, 참조 횟수가 0이 아니기 때문에 해제가 불가능해져 그대로 메모리 누수가 발생합니다.

추적 기반 GC ( Tracing Garbage Collection )

가장 많이 사용되는 GC 기법입니다. Tracing 즉 추적이라는 단어의 뜻처럼 프로그램 실행 중 특정 타이밍에 현재 할당된 모든 메모리를 조사하여 현재 접근 가능한지 불가능한지 분류한 뒤, 접근이 불가능한 메모리를 쓰레기라고 간주하여 해제시키는 방식입니다. ₁₎

이 방식을 사용하면 Reference Counting GC의 단점인 오버헤드 이슈와 순환 참조 이슈를 어느 정도 해결이 가능합니다.

메모리 조사의 시작점이 있어야 할 텐데, 항상 접근 가능한 메모리를 root라고 합니다. 이 메모리 부터 검사를 시작해서 참조하는 다른 메모리를 확인하는 행위를 반복하여 접근이 가능한 메모리이거나 불가능한 메모리인지 분류합니다.

추적 기반 GC 알고리즘은 총 5가지의 알고리즘을 조사하였으며 목록은 다음과 같습니다.

Mark-Sweep Algorithm
Mark-Sweep-Compact Algorithm
Tri-color Marking Algorithm ( Incremental GC )
Copying Algorithm ( Incremental GC )
Generational Algorithm ( Incremental GC )

이 중에서 먼저 위에 위에 있는 2가지의 알고리즘에 대해 알아 보도록 하겠습니다.

Mark-Sweep Algorithm

Mark-Sweep Algorithm 은 이름의 해석 그대로 메모리를 Mark(마킹) 후, Sweep(해제)하는 방식입니다.

마킹이 안 된 메모리는 전부 해제한 후 살아남은 객체의 마킹 정보를 초기화합니다.

Marking 정보는 각 객체의 Header 에 Flag 나 별도의 BitmapTable 등을 사용하여 저장합니다.

이 방식대로 수행하면 접근이 가능하거나 불가능한 메모리를 완벽하게 분류해서 해제하는 것이 가능합니다.

하지만 프로그램 실행 도중 메모리가 변경되면 마킹을 다시 해야 하기 때문에 프로그램을 통째로 정지(stop-the-world)시켜야 합니다.

이러한 이유 때문에 Mark-Sweep 방식은 프로그램 실행 도중 잠깐 멈추는 시간이 생겨, 실시간으로 빠르게 동작해야 하는 프로그램에서는 뚝뚝 끊기는 큰 단점이 발생합니다.

Mark-Sweep-Compact Algorithm

위의 Mark-Sweep 그림을 보면 해제 과정 후 메모리 상태가 중간중간 비워져 있는 상태를 확인할 수 있습니다. GC가 수행되면서 제거된 메모리들이 있던 곳이며 이렇게 조각난 상태를 Fragmentation(단편화)라고 하는데, 이 문제를 해결하기 위해 만들어진 알고리즘 입니다.

단편화는 메모리의 빈 부분들을 합쳐보면 충분히 많은 메모리가 있음에도 불구하고 새로운 객체를 할당할 수 없는 상황이 생깁니다. 또한 새로운 객체를 할당하기 위해 메모리 상의 빈 공간을 뒤지는 과정 자체가 성능에 악영향을 미치기 때문에 프로그램도 느려질 수 있습니다.

그래서 Compact 단계에서는 빈 공간을 없애고, 사용되는 메모리들을 연속적으로 붙여줍니다.

Mark-Sweep-Compact img

하지만 이러한 Compact 단계 자체와 그 후에 메모리의 참조 관계를 다시 설정해주는 등의 부가적인 오버헤드가 발생합니다.

점진적 GC ( Incremental GC )

위의 2가지 추적 기반 GC ( Tracing Garbage Collection )을 소개하였는데 해당 알고리즘들은 문제점들이 있었습니다. 이러한 문제점을 해결하기 위해 나온 것이 Incremental 점진적 GC 입니다.

위의 방식들처럼 마킹과 해제를 한 번에 하지 않고, 여러 번에 걸쳐서 수행하는 방식입니다. 이 방법을 사용하면 프로그램을 통째로 정지하는 것에 비해 마킹과 해제를 하는 한 싸이클에 걸리는 시간은 더 오래 걸릴 수 있지만, 한번 GC를 수행할 때 프로그램이 정지하는 시간을 줄일 수 있습니다.

위에서 설명한 Mark-Sweep 알고리즘에서도 점진적 GC를 어느정도 적용할 수 있습니다. 해제 단계에서 접근이 불가능하다고 판단된 메모리는 절대 다시 접근 가능해질 수 없기 때문에 해당 메모리의 해제는 언제 해도 상관없으므로 여러 번에 걸쳐서 수행해도 됩니다. 문제는 탐색 단계인데, 마킹을 점진적으로 하려면 Tri-color Marking(삼색 기법)등의 방법을 추가로 사용해야 합니다.

그러면 Tri-color Marking 알고리즘을 포함한 나머지 2개의 알고리즘도 확인해 보겠습니다.

Tri-color Marking Algorithm ( Incremental GC )
Copying Algorithm ( Incremental GC )
Generational Algorithm ( Incremental GC )

Tri-color Marking Algorithm

기존에는 접근/불가능이라는 2가지의 색으로만 마킹을 했다면 Tri-color Marking (삼색 기법)는 3가지의 색으로 마킹을 하는 것 입니다.

3가지의 색은 아래와 같이 구분합니다.

흰색 : 접근 가능한지 알 수 없는 메모리
회색 : 접근 가능하지만 해당 메모리에서 참조하는 메모리의 마킹을 하지 않은 경우
검은색 : 접근 가능하며 해당 메모리가 참조하는 메모리의 마킹도 끝난 경우

Tri-color Marking 의 3가지 색으로 구분하기 위한 탐색 방법은 다음과 같습니다.

root 메모리 조사
흰색인 메모리를 발견하면 회색으로 마킹
root메모리를 모두 마킹했으면 회색으로 마킹된 메모리 탐색
해당 메모리가 참조하는 모든 메모리를 회색으로 마킹
(4)번 작업이 끝나면 처음 회색이었던 메모리를 검은색으로 변경

위 작업들이 끝난 후 만약 회색으로 마킹된 메모리가 존재하지 않으면 모두 흰색이나 검은색이므로 모든 메모리의 접근 가능 여부를 결정합니다.

이런 방식을 이용하면 임의로 GC를 중단해도 다음번에는 회색인 메모리부터 조사하면 되므로 여러 번에 걸쳐 GC를 수행할 수 있습니다.

하지만 마킹을 하는 도중에 메모리 참조가 수정되면 잘못 마킹이 되는 경우가 발생할 수 있습니다.

위와 같은 문제를 해결하기 위해 read-barrier나 write-barrier를 사용하여 root 메모리를 읽거나 쓰는 것에 제약을 둡니다.

대부분의 경우 write 보다 read 행위가 더 자주 일어나므로 write-barrier가 주로 사용됩니다.

Copying Algorithm

Copying Algorithm 은 Mark-Sweep 알고리즘에서 나타나는 단편화 문제를 해결하기 위해 제시된 방법이며 Mark(마킹)을 하지 않고 아예 메모리를 옮겨버립니다.

Heap 영역을 활동하는 공간(Active)과 활동하지 않는 공간(InActive), 즉 두 개의 같은 크기의 공간으로 나누어 활동하는 공간에만 객체를 할당하는 방식입니다. 만약 활동하는 공간에서 GC를 수행하여 살아남은 객체를 사용하지 않는 공간으로 복사하고 두 공간을 서로 바꿉니다.

위 그림으로 예를 들면, 두 개의 메모리를 A, B라고 했을 때

처음에는 모든 메모리를 A에 할당합니다.
A가 가득 차는 등으로 인해 GC가 실행되면 프로그램은 잠시 일시중단 상태가 되고, A에서 살아남은 메모리가 모두 B로 복사됩니다.
A는 쓰레기 객체들만 존재하므로 A메모리를 비워버립니다.
그 다음 과정에서는 B에 메모리를 할당하다가 또 다시 GC가 실행되면 A로 복사합니다.

이후 (1)부터 (4)까지의 과정을 반복합니다.

해당 알고리즘의 장점으로는 새로운 공간에 단편화 없이, 연속된 메모리 공간에 차곡차곡 재배열이 되기에 캐시 효율이 높아집니다. 두 번째 장점으로는 처음부터 아예 메모리를 할당해두고 시작하기 때문에 Heap 영역의 메모리 할당을 Stack처럼 빠르게 할 수 있습니다.

하지만 단점으로는 처음부터 메모리를 잡아두고 시작하다 보니 메모리 공간을 많이 사용하게 됩니다. 두 번째로는 Copying이라는 작업의 오버헤드가 존재하며, 복사하는 과정에서 메모리의 주소가 바뀌므로 포인터를 이용한 접근을 포기하거나, 메모리의 주소가 바뀔 때마다 모든 메모리의 주소를 갱신해야 한다는 단점이 존재합니다. 세 번째는 프로그램의 일시 중단 현상도 존재합니다.

Generational Algorithm

객체의 라이프 사이클을 자세히 살펴보니, 한 가지 특이한 현상이 있습니다. 객체에 메모리를 할당 후, 해당 객체가 사용하지 않는 쓰레기가 될 때까지 걸리는 시간을 추적했을 때, 대부분의 객체는 잠시 사용되고 금세 버려지며, 반대로 오래 살아남아 쓰이는 경우는 "그리 많지 않다"라는 것을 파악하였습니다.

이러한 현상을 토대로 아래 두 가지 가정 (Weak Generational Hypothesis)을 전제 삼아 만들어진 방식이 해당 알고리즘입니다.

대부분의 할당된 객체는 오랫동안 참조되지 않는다.
오래된 객체에서 젊은 객체로의 참조는 거의 없다.

상대적으로 크기가 작은 New(Young) 영역에 할당하고, New(Young) 영역에서 기준 시간 이상으로 오래 살아남은 객체가 있다면 Old 영역으로 이동시켜 말 그대로 세대를 구분하는 방법입니다.

이 세대를 나누는 기준은 구현 방식마다 다른데 Stack 영역을 New(Young) 영역으로 쓸 수도 있고, Heap영역에 임의로 할당해서 쓸 수도 있지만, 대부분의 경우 Heap 영역을 사용합니다.

위의 그림을 보면, 객체는 New(Young) 세대에 할당되고 GC가 수행될 때마다 살아남은 객체에 Age를 기록합니다.

이 Age 역활은 해당 객체가 몇 번 살아남았는지 기록하는 것이며, 특정 임계값을 넘어서게 되면 Old Generation으로 복사하는 작업을 진행합니다. ( Promotion )

해당 알고리즘의 장점으로는 대부분의 객체는 New(Young) 에서 살다가 쓰레기가 되기 때문에 Old로의 복사 작업을 최소화시킬 수 있습니다. 두 번째로는 상대적으로 작은 영역만 추적하면 적은 시간과 비용으로 짧은 시간 안에 쓰레기 메모리를 확보할 수 있게 됩니다. 세 번째로는 Copying 작업이 이루어지며 Compact 작업도 수행되기 때문에 단편화 문제도 해결될 수 있습니다.

정리

참조 횟수 카운팅 GC ( Reference Counting Garbage Collection )의 장점으로는 구현이 쉽고추적, 참조 횟수가 0이 되면 즉시 소멸한다는 장점이 있지만 단점으로는 오버헤드가 많고, 무한 참조가 발생합니다. 그래서 추적 기반 GC ( Tracing Garbage Collection )를 사용하여 참조 횟수 카운팅 GC의 단점을 극복하였습니다.

Mark-Sweep 은 탐색 후 해제하는 작업을 진행하였습니다. 하지만 메모리 단편화라는 단점이 있습니다.
Mark-Sweep-Compact 은 탐색 후 해제한 뒤 메모리 단편화를 해결하기 위해서 메모리의 빈 공간을 없애고 연속적으로 붙여주는 작업을 진행하였습니다. 하지만 단편화를 해결하기 위해서 오버헤드가 많이 일어나는 등 단점등이 있습니다.
Tri-color Marking은 3가지의 색으로 구분하여 탐색하는 시간을 줄였습니다.
Copying은 해제를 할 때 복사하여 남은 쓰레기 객체를 해제하여 단편화를 해결하였습니다. 하지만 메모리를 2배를 설정해야 한다는 단점이 있습니다.
Generational 은 앞서 설명한 모든 알고리즘 기법을 사용하여 가장 효율적인 방법으로 GC를 진행하고 있습니다.

결론

현재 GC 알고리즘은 대부분 점진적 GC를 사용하고 있으며 어떠한 이유로 새로운 알고리즘이 탄생하였는지 확인하였습니다.

위의 내용에는 없지만 Major-GC, Minor-GC로 나눠서 GC를 수행할 수 있고 Cheney's Algorithm을 접목하여 단편화를 줄일 수도 있는 등 여러 모로 이점이 많습니다.

SSARTEL-10th / JPTS_bookstudy

GC 알고리즘 정복하기 #18

👍 문제

✈️ 선정 배경

📺 관련 챕터 및 레퍼런스

🐳 비고