[Java] Garbage Collection

STW(Stop The World)J

C/C++와 Java의 가장 큰 차이는 '메모리 관리의 주체' 이다. C/C++ 프로그래밍에서는 개발자가 직접 메모리 관리를 해줬다. C에서는 malloc() 계열의 함수들로 메모리 할당을, free() 함수로 메모리 해제를 해주었고, C++에서는 new 키워드를 통해 객체를 생성하고 delete 키워드를 통해 객체를 제거해주었다. 하지만 Java 프로그래밍을 하다보면 new 키워드는 사용하지만 delete 키워드를 사용하지 않는다. (Java에는 delete 키워드가 없다) 즉, 개발자가 메모리 관리를 하지 않는다는 것이다. 이는 JVM (Java Virtual Machine)속의 Garbage Collector가 사용하지 않는 객체를 제거하는 GC(Garbage Collection)을 실행하기 때문이다.

본격적으로 GC에 대해 알아보기에 앞서 STW(Stop The World)라는 것을 알아야한다. 세상을 멈춰라'라는 뜻처럼 GC를 수행하기 위해 JVM이 실행중인 어플리케이션을 멈추는 것을 말한다. 아무리 효율적인 GC 알고리즘을 사용한다고 하더라도 STW는 발생하기 때문에 GC 튜닝은 결국 STW 시간을 줄이는 것이 관건이다. STW에 대략적으로 알게되었으니 이제 본격적으로 GC에 대해서 알아보도록 하자.

Garbage Collection Algorithm

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

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

Reference Counting

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

class Main {
    public static void main(String[] args) {
        doSomething();
    }

    public static void doSomething() {
        Person person = new Person();
        Car car = new Car();
        person.setCar(car);
        car.setOwner(person);
    }
}

class Car {
    private Person owner;

    public void setOwner(Person owner) {
        this.owner = owner;
    }
}

class Person {
    private Car car;

    public void setCar(Car car) {
        this.car = car;
    }
}

+-----------+
| car       |  +---------+
| makeCar() |  | Car[1]  |  car -> Car
| main()    |  |         |
+-----------+  +---------+
   Stack           Heap

위의 코드에서 makeCar() 함수의 지역 객체 car 는 객체를 생성하는 순간 레퍼런스 카운트가 1이 된다. 그리고 함수를 벗어나면서 레퍼런스가 끊기게 되고, car 객체의 레퍼런스 카운트는 0이 된다. 이렇게 레퍼런스 카운트가 0이 되는 객체들을 제거해주는 방식을 생각해볼 수 있다. 직관적이고 간단해서 좋은 방법이라고 생각할 수 있지만 객체가 서로를 가리키는 경우 문제가 생긴다.

class Main {
    public static void main(String[] args) {
        doSomething();
    }

    public static void doSomething() {
        Person person = new Person();
        Car car = new Car();
        person.setCar(car);
        car.setOwner(person);
    }
}

class Car {
    private Person owner;

    public void setOwner(Person owner) {
        this.owner = owner;
    }
}

class Person {
    private Car car;

    public void setCar(Car car) {
        this.car = car;
    }
}

+---------------+
| setOwner()    |
| setCar()      |
| car           |                   person -> Person
| person        |    +-----------+  car    -> Car
| doSomething() |    | Person[2] |  Person -> car    -> Car
| main()        |    |   Car[2]  |  Car    -> person -> Person
+---------------+    +-----------+
      Stack               Heap

위의 코드에서는 서로가 서로를 참조하고 있다. 이런 경우 레퍼런스에 사이클이 일어나 doSomething() 함수가 끝나도 레퍼런스 카운트가 0이 되지 않는다. 따라서 레퍼런스 카운트가 0이 되면 객체를 제거하는 방식으로는 위와 같은 경우 메모리 누수(Memory Leak)이 발생한다.

Mark-and-Sweep Algorithm

다른 이름으로 Tracing Algorithm이라고도 한다. 이 방법은 이름 그대로 객체의 레퍼런스를 추적하는 방법이다. 스택의 지역 변수에서 시작해 해당 변수가 가리키고 있는 객체를 추적한다. 그리고 객체에 레퍼런스가 연결되어있다면 marked 값을 true 로 설정하는 방식이다.

+---------------+
| setOwner()    |
| setCar()      |
| car           |                      person -> Person
| person        |    +--------------+  car    -> Car
| doSomething() |    | Person[true] |  Person -> car    -> Car
| main()        |    |   Car[true]  |  Car    -> person -> Person
+---------------+    +--------------+
      Stack                Heap

만약 지역 변수로부터 레퍼런스가 끊기면 연결된 객체의 marked 값을 false 로 설정한다. 그리고 false 값을 가진 객체들만 메모리에서 해제한다.

                                        ???    -> Person
                     +---------------+  ???    -> Car
+---------------+    | Person[false] |  Person -> car    -> Car
| main()        |    |   Car[false]  |  Car    -> person -> Person
+---------------+    +---------------+
      Stack                Heap

이 때, 메모리를 해제하면서 한가지 문제가 발생한다.

+---+----------+----+------+---------+
|   | empty    |    |      | empty   |
+---+----------+----+------+---------+

힙 영역 여기 저기에 흩어진 객체들을 정리했기 때문에 메모리 사이에 빈 공간이 발생하게 된다. 이 빈 공간을 Fragmentation이라고 하는데, 이러한 Fragmentation은 메모리 총량이 충분함에도 불구하고 새로운 객체를 할당할 수 없도록 만든다. 또한 객체를 할당하기 위해 적절한 메모리 블록을 찾는 과정을 지연시키므로 어플리케이션의 성능도 떨어뜨린다는 치명적인 문제가 있다.

Mark-and-Compact Algorithm

Mark-and-Sweep Algorithm에서 Fragmentation이 생기는 치명적인 문제를 해결하기 위해 나온 알고리즘이다. Mark-and-Sweep Algorithm에 Compact 과정을 한 단계 더 거치는 알고리즘이다. 이러한 Compaction 작업을 통해 메모리 공간의 효율을 높였지만, Compaction 작업 이후 살아남은 모든 객체들의 Reference를 업데이트하는 작업이 필요하기 때문에 부가적인 Overhead가 수반된다. 위의 과정을 MSC(Marking, Sweeping, Compacting)라고 한다.

+---+----------+----+------+---------+
|   | empty    |    |      | empty   |
+---+----------+----+------+---------+

+---+----+------+--------------------+
|   |    |      | empty              |
+---+----+------+--------------------+

Copying Algorithm

Copying Algorith 역시도 Fragmentation을 해결하기 위해 제시된 또 다른 알고리즘이다. Copying Algorithm의 아이디어는 Heap을 논리적인 단위인 Active 영역과 InActive 영역으로 나누어 Active 영역에만 객체를 할당할 수 있게 하고 Active 영역이 꽉 차게 되면 GC를 수행하는 것이다. 그리고 GC가 끝난 뒤, Live Object를 Inactive 영역으로 복사하는 작업을 수행한다.

복사 작업까지 완료하게 되면 Active 영역에는 Garbage Object, Inactive 영역에는 Live Object만 남게 된다. 모든 Garbage Object를 제거하고 Active 영역과 Inactive 영역의 논리적인 구분을 바꿔주면 된다.

복사 과정에서 Live Object들을 연속된 메모리 공간에 쌓기 때문에 Fragmentation을 해결할 수 있다. 하지만 공간을 2개로 나눔으로써 전체 Heap의 절반만 사용할 수 있다는 비효율성과 복사에 대한 Overhead가 있다는 단점이 있다.

Generational Algorithm

현재 Garbage Collector가 채택하고 있는 방식이다. 해당 알고리즘은 다음의 2가지 가정을 전제로 고안되었다.

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

이러한 가설을 Weak generational hypothesis라고 하고, 이 가설을 바탕으로 Young Generation과 Old Generation이라는 영역으로 Heap을 구분했다.

                  |--------- Old ---------|
+------+----+----+-----------+-----------+
| Eden | S0 | S1 |  Tenured  | Permanent |
+------+----+----+-----------+-----------+
|----- Young ----|

eden, S0, S1은 생성된지 얼마되지 않은 오브젝트들이 쌓이는 공간이기 때문에 young generation이라고 부르며, 반대로 tenured와 permanent는 old generation이라고 부른다.

• Eden: 오브젝트가 처음 생성됐을 때 eden에 들어간다.
• Survivor 0, Survivor 1: 생성된 이후 시간이 조금 흘렀을 때 garbage가 되지 않은 오브젝트들이 eden에서 이곳으로 옮겨진다. 에덴에서 살아남은 오브젝트들이 들어간다고 해서 survivor space라고 부른다.
• Tenured: 오래 살아있을 확률이 높은 오브젝트들이 들어간다. 여기서는 거의 GC가 수행되지 않는다.
• Permanent: 프로그램이 끝날 때까지 살아있을 오브젝트들이 들어간다.

이제 실제 알고리즘이 어떻게 동작하는지 알아보자.

1. 새로운 객체가 생성되면 Eden에 할당된다.
2. Eden이 어느정도 차면 Eden에서 GC를 수행한다. (MSC)
3. 남아있는 객체들을 S0으로 옮기고 Eden을 비운다.
4. 1~3을 반복하다보면 S0가 가득 차게 되는데, GC를 수행하고 남은 객체들을 S1으로 옮기고 Eden과 S0을 비운다.
5. 1~4를 반복하다보면 S1 역시 가득 차게 된다. 이번엔 GC를 수행하고 남은 객체들을 S0으로 옮기고 Eden과 S1을 비운다.
6. 1~5 과정을 반복하면서 특정 횟수 이상 살아있는 객체가 있다면 tenured로 보내준다.

객체가 살아남아 다음 세대로 넘어가는 것을 promotion이라고 한다. 그리고 young generation에서 일어나는 GC를 minor GC라고 하고, old generation에서 일어나는 GC를 major GC라고 한다. minor GC는 자주, 빠르게 수행된다. 반대로 major GC는 가끔, 느리게 수행된다는 특징이 있다.

참고

• https://gyoogle.dev/blog/computer-language/Java/Garbage Collection.html
• https://medium.com/@joongwon/jvm-garbage-collection-algorithms-3869b7b0aa6f
• https://parksb.github.io/article/2.html