[Algorithm][Garbage Collection] (3) GC 알고리즘 - Tracing Garbage Collection(추적 기반) : Mark-Sweep, Mark-Sweep-Compact, Tri-color Marking

지난 2편에 이어

 

Garbage Collection(이하 GC, 가비지 컬렉션)의 알고리즘 중

 

Tracing GC(추적 기반)에 대해 알아본다.

 

 

Tracing GC에서는

 

아래 알고리즘들에 대해 작성할 예정인데,

 

꽤나 많은 양이 예상되므로

 

두 편으로 글을 나눠 쓰려고 한다.

 

 

- Mark-Sweep Algorithm

 

- Mark-Sweep-Compact Algorithm

 

- Tri-color Marking Algorithm (Incremental GC)

 

- Copying Algorithm (Incremental GC)

 

- Generational Algorithm (Incremental GC)

 

 

이 글에서는 Reference Counting GC를 보완하며 만들어진

 

Tracing GC의 원조격 알고리즘이라 할 수 있는

 

Mark-Sweep에 대해 알아보고,

 

 

Mark-Sweep의 단점을 보완한

 

Mark-Sweep-Compact,

 

Incremental GC(점진적 GC)에 속하는

 

Tri-color Marking Algorithm에 대해 알아본다.

 

---

 

Tracing Garbage Collection

개념

가장 많이 사용되는 GC 기법으로,

 

대부분 경우 GC에 대해 누군가 물어본다면

 

이 방식일 가능성이 높다.

 

 

Tracing, 즉, "추적"이라는 단어의 뜻처럼

 

프로그램 실행 중 특정 타이밍에

 

현재 할당된 모든 메모리를 조사하여

 

그것이 현재 접근 가능한지 불가능한지 분류한 뒤,

 

접근이 불가능한 메모리를 "쓰레기"라고 간주하여 해제시키는 방식이다.

 

 

이 방식을 사용하면 2편에서 소개한

 

Reference Counting GC(참조 횟수 카운팅)의 단점인

 

오버헤드 이슈와 순환 참조 이슈를 어느 정도 해결 가능하다.

 

 

그럼 메모리 조사의 시작점이 있어야 할 텐데,

 

항상 접근 가능한 메모리를 root라고 한다.

 

 

이 root 메모리부터 검사를 시작해서

 

root 메모리가 참조하는 다른 메모리, 다른 메모리가 참조하는 또 다른 메모리 등

 

메모리가 참조하는 메모리를 확인하는 행위를 반복하여

 

접근 가능 or 불가능한 메모리를 분류한다.

 

 

이 root 메모리에 대해서는 Naver D2 블로그에서 작성한

 

Java Reference와 GC 글을 참고하면 좋다.

 

 

(root 메모리에 대해서 추후 글을 작성할 예정)

 

Mark-Sweep Algorithm

위에서 설명한 Tracing GC를 그대로 구현하는 방법 중

 

가장 단순한 방식으로,

 

Tracing GC의 원조격 되는 알고리즘이다.

 

 

알고리즘의 이름의 해석 그대로,

 

메모리 Mark(마킹) 후, Sweep(해제)하는 방식이다.

 

 

아래 그림과 함께 좀 더 자세히 풀어써보자면,

 

 

프로그램 실행 중 적당한 타이밍에 GC를 실행시켜

 

접근 가능한 메모리에는 Mark(마킹)를 하고

 

Mark(마킹)가 안 된 메모리는 전부 Sweep(해제) 한 후,

 

살아남은 객체의 Mark(마킹) 정보를 초기화한다.

 

 

(Marking 정보는 각 객체의 Header에 Flag나

 

별도의 BitmapTable 등을 사용하여 저장)

 

 

출처) https://medium.com/@joongwon/jvm-garbage-collection-algorithms-3869b7b0aa6f

 

 

이 방식대로 수행하면

 

접근이 가능한 혹은 불가능한 메모리를

 

완벽하게 분류해서 해제하는 것이 가능하다.

 

 

하지만 프로그램 실행 도중 메모리가 변경되면

 

마킹을 다시 해야 하기 때문에

 

프로그램을 통째로 정지('stop-the-world')시켜야 한다.

 

 

이 이유 때문에 Mark-Sweep 방식은

 

프로그램 실행 도중 잠깐 멈추는 시간이 생겨,

 

실시간으로 빠르게 동작해야 하는 프로그램에서는

 

뚝뚝 끊기는 큰 단점이 발생한다.

 

 

그래서 이 단점을 개선하기 위해

 

한 번에 처리하는 방식 대신,

 

조금씩 조금씩 수집을 하는 Incremental(점진적) GC 방식이나,

 

 

객체의 사용 시간을 계산하여 영역 별로 나누어 수집하는

 

Generational(세대별) GC 방식이 탄생하게 된다.

 

Mark-Sweep-Compact Algorithm

먼저 Incremental GC 방식을 알아보기 전에!

 

 

위의 Mark-Sweep 그림을 다시 보면,

 

Sweep 과정 후 메모리 상태가 중간중간 비워져 있는 이상한 상태를 볼 수 있다.

 

 

바로 GC가 수행되며 제거된 "쓰레기" 메모리들이 있던 곳이다.

 

 

이렇게 메모리가 조각난 상태를 Fragmentation(단편화)라고 하는데,

 

이 문제를 해결하기 위해 만들어진 알고리즘이다.

 

 

그럼 Fragmentation을 왜 해결해야 할까?

 

 

메모리의 빈 부분들을 합쳐보면

 

충분히 많은 빈 메모리가 있음에도 불구하고

 

새로운 객체를 할당할 수 없는 상황이 생기기 때문이다.

 

 

또한 새로운 객체를 할당하기 위해

 

메모리 상의 빈 공간을 뒤지는 과정 자체가 성능에 악영향을 미치기 때문에

 

결국 프로그램도 느려질 수 있다.

 

 

그래서 이름만 봐도 어느 정도 유추가 가능한

 

아래 그림처럼 Compact(압축) 단계가 하나 추가되었다.

 

출처) https://medium.com/@joongwon/jvm-garbage-collection-algorithms-3869b7b0aa6f

 

이 Compact 단계에서는

 

빈 공간들을 없애고, 사용되는 메모리들을 연속적으로 붙여준다.

 

 

하지만 이러한 Compact 단계 자체와

 

그 후에 메모리의 참조 관계를 다시 설정해주는 등의

 

부가적인 오버헤드가 또다시 발생한다.

 

Incremental GC

위와 같은 문제점을 해결하기 위해 나온 방식이

 

Incremental(점진적) GC다.

 

 

위의 방식들처럼 Mark(마킹)와 Sweep(해제)을

 

한 번에 하지 않고, 여러 번에 걸쳐서 수행하는 방식이다.

 

 

이 방법을 사용하면,

 

프로그램을 통째로 정지하는 것에 비해

 

마킹과 해제를 하는 한 cycle에 걸리는 시간은 더 오래 걸릴 수 있지만,

 

한번 GC를 수행할 때 프로그램이 정지하는 시간은 줄일 수 있다.

 

 

Mark-Sweep 방식에도

 

이러한 Incremental GC 방식을 어느 정도 적용이 가능하다.

 

 

Sweep 단계에서 접근이 불가능하다고 판단된 메모리는

 

절대 다시 접근 가능해질 수 없기 때문에,

 

해당 메모리의 해제는 언제 해도 상관없으므로

 

여러 번에 걸쳐서 수행해도 된다.

 

 

문제는 Mark 단계인데,

 

마킹을 점진적으로 하려면 Tri-color Marking(삼색 기법) 등의

 

방법을 추가로 사용해야 한다.

 

Tri-color Marking

Tri-color Marking(삼색 기법)은 말 그대로,

 

기존에는 접근 가능/불가능이라는 2가지의 색으로만 마킹을 했다면

 

아래 3가지의 색으로 마킹을 하는 것이다.

 

 

(1) 흰색 : 접근 가능한지 알 수 없는 메모리

 

(2) 회색 : 접근 가능하지만 해당 메모리에서 참조하는 메모리의 마킹을 하지 않은 경우

 

(3) 검은색 : 접근 가능하며 해당 메모리가 참조하는 메모리의 마킹도 끝난 경우

 

 

 

마킹하는 순서는 아래와 같다.

 

 

(a) root 메모리 조사

 

(b) 흰색인 메모리를 발견하면 회색으로 마킹

 

(c) root 메모리를 모두 마킹했으면 회색으로 마킹된 메모리 조사

 

(d) 해당 메모리가 참조하는 모든 메모리를 회색으로 마킹

 

(e) (d) 작업이 끝나면 처음 회색이었던 메모리를 검은색으로 바꿈

 

 

위 작업들이 끝난 후,

 

만약 회색으로 마킹된 메모리가 존재하지 않으면

 

모두 흰색이나 검은색일 것이므로,

 

모든 메모리의 접근 가능 여부가 결정된다.

 

 

이런 방식을 이용하면 임의로 GC를 중단하여도

 

다음번에는 회색인 메모리부터 다시 조사하면 되므로

 

여러 번에 걸쳐 GC를 수행 가능하다.

 

 

 

하지만 아래의 예시처럼,

 

마킹을 하는 도중에 메모리 참조가 수정이 되면

 

잘못 마킹되는 일이 발생할 수 있다.

 

 

(가정) root가 A 메모리를,

 

A 메모리가 B 메모리를 참조하며,

 

A 메모리 외에는 B 메모리로 접근 가능한 메모리가 없고

 

흰색으로 마킹된 상태인 C 메모리가 존재한다고 하자.

 

 

(실행) GC를 수행하여 A, B 메모리가 검은색으로 마킹되고

 

GC가 정지했다고 가정하면,

 

이후 다시 실행될 GC에서 수행해야 할 해제 작업 전에

 

A 메모리가 B 메모리에 대한 참조를 제거하고

 

C 메모리를 참조하게 수정되었다고 하자.

 

 

(결과) 그러면 B 메모리는 이제 접근이 불가능하지만 검은색이고,

 

C 메모리는 접근 가능한데 흰색인 상태가 된다.

 

 

 

위와 같은 문제를 해결하기 위해

 

보통 read-barrier나 write-barrier를 사용하여

 

root 메모리에 읽거나 쓰는 것에 제약을 둔다.

 

 

대부분의 경우 write 행위보다 read 행위가

 

더 자주 일어나므로 write-barrier가 사용된다.

 

 

write-barrier에 대해 간단히 설명하자면,

 

애플리케이션에서 참조를 대입하거나 rewrite 할 때,

 

해당 참조를 별도로 기록하는 처리이다.

 

 

위의 예시를 다시 가져와보면,

 

A 메모리의 참조가 C 메모리가 되도록 write 된 것이므로

 

C 메모리의 마킹을 회색으로 바꾸면 된다.

 

 

그러면 B 메모리는 당장 해제되지는 않아도,

 

적어도 C 메모리가 해제되는 일은 없앨 수 있다.

 

---

 

다음 글에서는

 

Copying Algorithm과,

 

 

현재의 많은 프로그래밍 언어가 사용 중인

 

Generational GC에 대해 알아본다.

 

 

끝!