[JVM] Garbage Collection Algorithms

13 min readJan 26, 2019

Java 코드를 작성함에 있어서 JVM에 대해 이해를 하고 작성하는 것은 중요하다. Android를 개발할 때도 Android 플랫폼 특성에 대해 이해가 중요하듯이 Java 코드가 실행되는 환경에 대해 이해가 부족하다면 잘못된 코드를 작성할 확률이 높아지거나 문제가 발생했을 때 대처하는 방식에 있어서 차이점이 생긴다. 그렇기에 우리는 우리가 작성한 코드가 실행되는 환경에 대한 적절한 이해가 필요하다. Java 언어가 세대를 거치며 많은 발전을 거듭해온 것처럼 JVM도 많은 발전을 이뤄왔고 Garbage Collector 또한 많은 발전을 이뤄왔다.

Garbage Collector가 동작하는 방식을 이해하기 전에 내부 Algorithm을 이해한다면 Garbage Collector의 동작을 더 이해하기 쉬울 거라 생각한다. Garbage Collector들이 어떠한 Algorithm들을 채택해왔고 발전해왔는지 살펴보자.

우선 각 Algorithm을 살펴보기에 앞서 어떤 Object를 Garbage로 볼 것이냐에 대한 이해가 글을 읽는 데 도움이 될 것이다. Garbage Collector는 객체를 Reachable과 Unreachable의 상태로 구분한다. 구분하는 방법은 Root set 과의 관계로 판단한다. Root Set으로부터 어떤 식으로든 Reference 관계가 있다면 Reachable Object라고 판단하고 Root Set으로부터 참조하는 Reference 관계가 없다면 Unreachable Object라고 판단한다. Root Set을 간단하게 설명하면 객체들 간에 참조 사슬의 시작점이라고 보면 된다.

Root Set은 아래의 세 가지 형태로 나뉜다.

1. JVM Stack 내의 Local Variable Section과 Operand Stack에서의 참조 (Java 메서드 내에서 실행하는 지역 변수 또는 파라미터에 의한 참조)
2. JVM Method Area의 Constant Pool에서 참조 (정적 변수에 의한 참조)
3. 아직 메모리에 남아 있는 Native Method로 넘겨진 Object에서 참조 (JNI에 의해 생성된 객체에 대한 참조)

위 세 가지 형태의 Root Set으로부터 이어진 참조 사슬에 포함되어 있으면 Reachable Object이고 그렇지 않은 것은 Unreachable Object이다. Reachability에 대한 자세한 내용은 Java Reference와 GC를 읽어보는 걸 추천한다.

Garbage Collection의 기본 알고리즘의 흐름은 다음과 같다.

Garbage 대상을 식별하고 -> 식별된 대상을 메모리에서 해제한다.

말은 참 쉽다. 하지만 저 짧은 문장에 많은 최적화 기술들이 녹아들어 있기 때문에 파고들어볼 만한 가치가 있다. 여기서 다룰 Algorithm은 총 5개이며 다음과 같다.

Reference Counting Algorithm
Mark-and-Sweep Alogrithm
Mark-and-Compact Algorithm
Copying Algorithm
Generational Algorithm

Reference Counting Algorithm

Garbage의 Detection에 초점이 맞추어진 초기 Algorithm이다. 각 Object마다 Reference Count를 관리하여 Reference Count가 0이 되면 GC를 수행한다.

위 그림에서 a와 b는 각각 100, 99의 값을 갖는 Integer Object로 선언되어 있다. 각 Integer Object는 Referece Count가 1로 설정되어 있다. 이 상태에서 b = a로 변경하게 되면 a가 참조하고 있던 100의 값을 갖는 Integer Object는 참조가 없어지기 때문에 Reference Count가 0으로 감소하게 되고 GC가 수행된다.

이 방식은 Reference Count가 0이 될 때마다 GC가 발생하기 때문에 Pause Time이 분산되어 실시간 작업에도 거의 영향을 주지 않고 즉시 메모리에서 해제된다는 장점이 있으나 각 Object마다 Reference Count를 변경해 주어야 하고 참조를 많이 하고 있는 Object의 Reference Count가 0이 될 경우 연쇄적으로 GC가 발생할 수 있는 문제가 있고 Reference Count의 관리 비용도 크다. 또한 Linked List와 같은 순환 참조 구조에서 Memory Leak이 발생할 가능성도 크다.

위와 같은 순환 참조 구조에서 a로부터의 참조가 끊어졌다 해도 다른 노드로부터의 참조가 남아 있기 때문에 Reference Count가 0이 되지 않게 되고 그로 인해 Garbage 대상이 되지 않아 Memory Leak으로 이어지게 된다.

Mark-and-Sweep Algorithm

Reference Counting Algorithm의 단점을 극복하기 위해 나온 Algorithm이다. 이 방식은 Garbage Detection은 Root Set에서 시작하는 Reference의 관계를 추적한다. 그래서 Tracing Algorithm이라고도 하며 이름에서 유추할 수 있듯이 Mark Phase와 Sweep Phase로 나뉘게 된다.

Mark Phase에서는 Garbage 대상이 아닌 살아남아야 할 Object에 Marking 하는 방식으로 수행되며 Marking을 위해 각 Object의 Object Header에 Flag나 별도의 BitmapTable 등을 사용한다. Mark Phase가 끝나면 곧바로 Sweep Phase로 진입하는데 이 단계에서는 Marking 정보를 활용하여 Marking 되지 않은 Object를 지우는 작업을 한다. 그리고 Sweep이 완료되면 살아남은 모든 Object의 Marking 정보를 초기화 한다.

위 그림에서 Before는 GC가 일어나기 전의 상황이고 이후 Sweep Phase를 거치게 되면 Marking 되지 않은 Object들이 지워지게 된다. Sweep이 완료되면 살아남은 모든 Object들의 Marking 정보는 초기화된다. Mark-and-Sweep은 Reference 관계를 정확하게 파악하고 Reference 관계의 변경 시에 별도의 Overhead가 없어 속도가 향상되기는 하나 GC가 수행되는 도중 Mark 작업의 정확성과 Memory Corruption을 방지하기 위해 Heap의 사용이 제한되기 때문에 Suspend 현상이 발생한다.

그리고 그림에서 볼 수 있듯이 GC 이후에 제거된 Garbage가 존재하던 메모리 공간이 듬성듬성한 상태가 되어 Heap 메모리 전체로 봤을 때 충분한 공간이 있는 것처럼 보이지만 메모리 할당이 불가능한 상태가 되어 OutOfMemoryException이 발생할 수 있다. 위와 같이 메모리가 조각난 상황을 Fragmentation이라고 한다.

Fragmentation은 메모리의 총량은 충분함에도 불구하고 새로운 Object를 할당할 수 없는 상황을 유발하고 Object를 할당하기 위해 적절한 메모리 블록을 찾는 과정을 지연시키기 때문에 애플리케이션의 성능에도 영향을 끼친다. 우리가 컴퓨터의 성능을 개선하기 위해 디스크 조각 모음을 했던 시절을 떠올려보면 이해가 쉬울 것 같다.

Mark-and-Compact Algorithm

Mark-and-Sweep Algorithm이 가지고 있는 Fragmentation이라는 약점을 극복하기 위해 나온 Algorithm이다. Sweep 대신 Compact이라는 용어를 사용하였지만 Sweep이 사라진 것은 아니고 Compact Phase 안에 포함되어 있다. 아래 그림은 Mark, Sweep, Compact의 과정을 잘 나타내고 있다.

Mark와 Sweep의 단계는 이전 Mark-and-Sweep Algorithm과 동일하나 Compact 과정을 한 단계 더 거치게 된다. 그림에서 볼 수 있듯이 Compaction 작업은 Sweep 이후 Garbage였던 Object들이 사라지고 남은 빈자리들을 살아남은 Object들로 연속된 메모리 공간에 차곡차곡 적재하는 것을 의미한다. Compaction 작업을 통해 메모리 공간의 효율을 높일 수 있다. 하지만 Compaction 작업 이후 살아남은 모든 Object들의 Reference를 업데이트하는 작업이 필요하기 때문에 부가적인 Overhead가 수반된다.

Copying Algorithm

Copying Algorithm도 Fragmentation의 문제를 해결하기 위해 제시된 또 다른 방법이다. 현대의 Garbage Collector가 차용하고 있는 Generational Algorithm이 Copying Algorithm을 발전시킨 형태이다. Copying Algorithm의 기본 아이디어는 Heap을 Active 영역과 InActive 영역으로 나누어 Active 영역에만 Object를 할당할 수 있게 하고 Active 영역이 꽉 차게 되면 GC를 수행한다는 것이다. GC를 수행하면 Suspend 상태가 되고 살아남은 Live Object를 Inactive 영역으로 Copy 하는 작업을 수행한다. Copy 하는 동안 프로그램이 Suspend 상태가 되기 때문에 Stop-the-Coyping이라고도 부른다.

Copy 작업을 완료하면 Active 영역에는 Garbage Object만 남게 되고 Inactive 영역에는 Live Object만 남게 된다. 이후 Garbage Object를 제거하게 되면 Active 영역은 Free Memory 상태가 되고 Active 영역과 Inactive 영역이 서로 바뀌게 된다. 이를 Scavenge이라고 하며 Active 영역과 Inactive 영역은 물리적인 구분이 아니라 논리적인 구분일 뿐이다.

그림을 보면 Region A, Region B이라고 표기하였는데 Active, Inactive는 개념적인 구분일 뿐이기 때문에 단순히 Heap 영역을 반으로 나누어 한쪽에만 Object를 할당한다고 이해하면 된다. 앞에서 Copying Algorithm도 Fragmentation 문제를 해결하기 위해 고안되었다고 하였다. Fragmentation 문제를 해결하기 위해 Copy 할 때 Live Object를 옮기는 과정에서 각 Object들의 Reference를 업데이트하면서 연속된 메모리 공간에 차곡차곡 적재시킨다.

Copying Algorithm은 Fragmentation 방지에는 효과적이지만 전체 Heap의 절반 정도밖에 사용하지 못한다는 공간 활용의 비효율성, Suspend 현상, Copy에 대한 Overhead가 존재한다는 단점이 있다.

Generational Algorithm

Copying Algorithm을 사용하면서 대부분의 프로그램에서 생성되는 대다수의 Object들이 생성된 지 얼마 되지 않아 Garbage가 되는 짧은 수명을 가지고 있다는 것과 수명이 긴 몇 개의 Object는 반드시 가지고 있다는 경험적 체득을 통해 고안된 Algorithm이다. 이 Algorithm은 아래의 두 가지 가정을 전제로 만들어졌다.

대부분의 할당된 객체는 오랫동안 참조되지 않으며 즉 금방 Garbage 대상이 된다.
오래된 객체에서 젊은 객체로의 참조는 거의 없다.

위와 같은 가설을 Weak generational hypothesis라고 한다. 이 가설을 바탕으로 Young Generation과 Old Generation이라는 영역으로 Heap을 구분 지었다.

위의 그림은 Young Generation과 Old Generation의 두 개의 Sub Heap으로 나뉜 것을 표현한 것이다. Object는 Young Generation에 할당되고 GC가 수행될 때마다 살아남은 Object에 Age를 기록한다. HotSpot JVM에서 이 Age의 임곗값의 기본값은 31이다(Object Header에 Age를 기록하는 부분이 있고 6 Bit로 되어 있기 때문에 6 Bits로 표현할 수 있는 수치가 32라서 그렇다). 그냥 몇 번 살아남았는지를 기록하는 것이라고 보면 되며 특정 임곗값을 넘어서게 되면 Old Generation으로 Copy 하는 작업을 수행한다. 이를 Promotion이라고 하며 대부분의 객체는 Young Generation에서 살다가 Garbage가 되기 때문에 Copy 작업의 횟수를 최소화시킬 수 있다. 또한 Old Generation으로 Copy 하며 Compaction 작업이 이루어진다. 우리가 주로 사용하고 있는 HotSpot JVM이 Generational Algorithm을 바탕으로 다음과 같이 Generational Heap을 구성하고 있다.

HotSpot JVM에서 제공하는 Garbage Collector들을 보면 Young Generation과 Old Generation에서 어떠한 Algorithm으로 GC를 수행하는지 명시되어 있으므로 각 Garbage Collector가 취하는 GC 전략에 대해 이해할 수 있을 것이다.

Reference

Java Performance Fundamental (김한도 지음)
https://plumbr.io/handbook/garbage-collection-algorithms
https://www.oracle.com/technetwork/java/javase/tech/memorymanagement-whitepaper-1-150020.pdf

마치며

HotSpot JVM의 Garbage Collection에 대해 설명한 훌륭한 글들이 많이 있습니다. 그중 하나로 Java Garbage Collection 을 읽어보는 걸 추천하며 위에서 소개한 내용들을 이해했다면 Garbage Collector들이 각 영역별로 채택하고 있는 Algorithm과 동작 방식에 대해 이해하는 데 도움이 될 것이라 생각합니다.