GC (Garbage Collection)의 알고리즘

GC의 정의

GC는 Garbage Collector의 약자로 힙 영역에서 사용하지 않는 객체들을 제거하는 작업을 총칭한다. 이 객체를 제거하는 작업이 필요한 이유는 자바는 개발자가 메모리를 직접 해제해줄 수 없는 언어이기 때문이다. 따라서 객체를 사용하고 제거하는 기능이 필요하게 된다. 

 

GC의 동작방식

GC의 동작방식을 정리하면 다음과 같다.

 

1. GC의 동작방식은 가장 간단한 Serial GC 방식으로 설명한다.
2. GC는 Minor GC, Major GC로 구분한다.
3. Minor GC는 young한 영역에, Major GC는 old한 영역에서 일어난다.
4. GC를 수행할 때는 GC를 수행하는 스레드 이외의 스레드는 모두 정지한다.
5. Minor GC는 Eden 영역이 가득 차면 시작한다.
6. Eden 영역에서 참조가 남아있는 객체를 마킹하고 survivor 영역으로 복사한다. 그리고 Eden 영역을 지운다.
7. survivor 영역도 가득차면 다른 survivor 영역에 복사하고 비운다. 이를 반복하다보면 계속해서 살아남는 객체는 old영역으로 이동하게 된다.
8. Major GC는 old 영역에서 일어난다. Minor GC와는 반대로 삭제되어야 하는 객체를 마킹하고 지운다.
9. 이때 메모리는 단편화 된 상태이므로 한 군데에 모아주어야 하는데 메모리를 한군데에 모아주는 것을 Compaction이라 하며 Compact라고 한다. 이를 Mark-Sweep-Compact 알고리즘이라 한다.
10. 이것이 중요한 이유는 GC는 수행시 시스템이 멈추기 때문에 의도치 않은 장애의 원인이 될 수 있다.

 

이러한 동작 방식을 더 잘 이해하기 위해서는 GC가 채용하는 알고리즘을 알아보면 된다. 

 

GC의 알고리즘

GC 알고리즘의 중요 목적은 무엇일까? 

 

바로 어떻게 하면 불필요한 Object들을 선별 하는가 그리고 GC가 동작하는 동안 프로그램이 중단되는 시간을 어떻게 줄일것인가 이렇게 두개로 나눠 생각할 수 있다. 

 

불필요한 Object를 발견하고 해당 메모리 주소를 되찾는 방법에는 세가지 알고리즘이 있다.

 

1) Mark and Sweep 알고리즘

Mark : 필요한 Object를 표시한다. 이러한 작업을 하기 위해 Garbage Collection Root라고 불리는 특별한 Object를 계속 추적한다. GC Root는 현재 실행 되고 있는 메서드에 지역변수가 될 수도 있고 혹은 로드된 클래스의 static 변수일 수도 있다. Mark and Sweep 알고리즘 동안 GC는 모든 GC Root 그래프를 돌아다니면서 필요한 Object를 발견하기 위해 노력한다.

 

GC Root 그래프

위의 그림은 GC Root 그래프이다. 보라색으로 표시된건 참조되어 있는 Object이고 빨간색으로 표시되어 있는 것은 특정 시기에 참조 되어있지만 현재는 범위를 벗어나 참조되지 않는 Object들이다. 

 

Sweep : 그래프를 돌고 난 후 마크되지 않은(참조 되지 않은 Object) 메모리에서 지우고 해당 메모리 공간을 되찾는다. 만약 GC가 작동 할 때 프로그램을 중단시키지 않으면 Object를 관리할 때 새로운 Object가 생성 될지도 모른다. 해당 Object는 현재 GC가 동작하고 있는 Object들과 서로 연결되지 않을 가능성이 높고 그로인해 GC는 생성된 Object의 주소값을 지울 것이다. 

 

2) Mark-Sweep-Compact 알고리즘

그림은 GC가 실행되기 전과 후의 힙메모리 영역을 나타낸 것이다. GC가 동작한 후 힙 메모리는 새로운 공간들을 얻은 것을 알 수 있다. 해당 공간에는 새로운 Object가 할당될 수 있다. 하지만 보다시피 메모리 공간이 조각조각 나있다(위의 동작방식에서 설명한 단편화 된 상태). 그렇기 때문에 새로운 Object를 할당할 때 남아있는 각각 조각마다 해당 Object 크기를 담아낼 수 없는 경우가 발생할 것이다. 이 경우 JVM은 메모리를 할당할 수 없어서 OutOfMemmoryError를 발생시킨다. 그렇기 때문에 우리는 Mark-Sweep-Compact 알고리즘을 같이 사용한다. 

 

Mark-Sweep-Compact 알고리즘을 사용하면 아래와 같이 조각난 공간을 합쳐준다.

 

3) Mark and Copy 알고리즘

 

Mark-Sweep-Compact 알고리즘같이 사용하고 있는 메모리 주소값은 새로 할당하는 알고리즘이다. Mark and Copy 알고리즘은 위와 같이 GC를 하기전 두가지 메모리 공간을 사용한다. A는 메모리안에 사용된 공간과 사용되지 않는 공간이 존재한다. 하지만 B는 완전히 비어있다. GC가 실행될 때 다음과 같이 두가지 단계를 수행한다.

 

1. Mark된 Object를 모두 A메모리에서 지운다. 
2. 이 후, Mark Object를 B에 다시 재할당한다. 

위의 단계는 Object가 Mark되는 것과 동시에 동작할 수 있고 이렇게 하면 프로그램이 GC에 의해 중단되는 시간을 줄여준다.