[JVM] 참조 카운팅 알고리즘과 파이썬의 순환 검출 알고리즘에 대해서

가비지 컬렉션에 대해서 배울 때, 객체가 '죽었는지' 여부를 판단하기 위해서는 그 판단 기준이 필요하다.

이 '죽었는지'는 프로그램 코드에서 어떠한 방식으로도 객체가 다시 사용될 수 없는, 즉 아무 변수도 해당 객체를 참조하지 않아 더이상 해당 객체에 접근할 수 없다는 뜻이다.

---

죽었는가? - 참조 카운팅 알고리즘 (기본)

이 '죽었는지' 판단하는 알고리즘 중에 하나가 바로 참조 카운팅 알고리즘.

대략적인 순서는 이렇다.

1. 객체를 가리키는 참조 카운터(reference counter)를 추가하고, 참조하는 곳이 하나씩 늘어날 때마다 참조 카운터의 값을 1씩 증가시킨다.

2. 참조하는 곳이 하나 사라질 때마다 카운터 값을 1씩 감소시킨다.

3. 카운터 값이 0이 되면 객체는 사용될 수 없다 ==> 가비지 컬렉션의 대상이 된다.

 

위의 예시에서는 객체A가 가비지컬렉션의 대상이된다.

 

즉, 가장 기초적인 참조 카운팅 알고리즘은 객체가 자신을 참조하는 객체들의 수를 가지고 있으며, 그 값이 0이되면 가비지 컬렉션의 대상이 된다. 약간의 메모리를 추가로 사용하게되지만 원리와 판단이 간단하다. 그래서 MS COM, 파이썬, 러스트, 스퀄(Squirrel) 등의 언어에서 참조 카운팅 알고리즘을을 사용하여 메모리를 관리한다.

---

순환참조문제

단순한 참조 카운팅 알고리즘에서 주로 발생하는 문제는 순환참조 문제다.

 

만일 위와 같은 상황이 벌어졌다면?

실제로는 어디서나 참조될 수 없는 여러 객체들이 서로를 참조 중이라면 기본적인 참조 카운팅 알고리즘을 사용하는 경우에는 해당 객체들에 접근할 방법이 없더라도 메모리를 회수할 방법이 없다.

 

위의 경우에는 정상적이라면 객체A와 객체B는 그 어디에서도 참조될 수 없으므로 GC 대상이 되어야하지만 참조 카운팅 알고리즘을 사용 중이라면 GC의 대상이 되지 않는다. 왜냐하면 참조 카운터 값이 1이니까.

 

그래서 순수한 참조 카운팅 알고리즘만 있다면 순환참조문제에서 벗어날 수 없다.

 

class ReferenceCountingGC {
    public Object instance = null;

    public static void testGC(){
        ReferenceCountingGC objA = new ReferenceCountingGC();
        ReferenceCountingGC objB = new ReferenceCountingGC();

        objA.instance = objB;
        objB.instance = objA;

        objA = null;
        objB = null;

        System.gc();
    }
}

이를 자바로 표현하면 이렇게된다.

objA의 인스턴스 instance 는 objB를 참조하고, objB의 인스턴스 instance는 objA를 참조한다. 그래서 objA와 objB의 값을 null로 바꿔 참조를 해제시키더라도 각각의 인스턴스 변수들이 서로의 객체를 참조 중이므로 가비지컬렉션을 작동시키더라도 메모리 회수가 진행되지 않을 것이다.

 

물론 자바는 참조 카운팅 알고리즘을 사용하지 않는 언어이기 때문에 위와같은 상황에서도 메모리 회수는 잘 이루어진다.

---

그럼 어떻게?

대표적으로 참조카운팅 알고리즘을 사용해 GC를 작동시키는 언어가 파이썬.

그렇다면 파이썬은 어떻게 순환참조에서 벗어날까?

 

파이썬은 가비지컬렉터를 하나 더 사용한다.

하나는 참조카운팅 알고리즘을 사용하는 가비지컬렉터, 다른 하나는 '순환검출' 가비지컬렉터.

 

파이썬 표준 인터프리터인 CPython 기준으로

파이썬은 자바와 달리 모든 것이 객체기 때문에 다른 객체를 담을 수 있는 객체를 '컨테이너 객체'(클래스부터 리스트, 딕셔너리 등..)라고하며, 이 컨테이너 객체가 GC의 검사 대상이된다.

 

컨테이너 객체들은 각자의 세대가 나뉘는데,

- 0세대 (가장 최근에 생성되었으며 GC가 실행되지 않은 객체)

- 1세대 (0세대 중 GC 실행 후 삭제되지 않은 객체)

- 2세대

로 분리되며, GC를 동작시키면 대부분 0세대를, 가끔 1세대를, 아주가끔 2세대에서 GC를 돌린다.

 

GC가 돌아갈 때

첫 번째로 GC는 GC 대상이되는 각 컨테이너 객체들마다 참조 카운트 필드(gc)에 추가적인 참조 카운트필드(gc_ref)를 추가하고, gc_ref를 gc와 같은 값을 가지도록 초기화시킨다.

이후 GC는 각 컨테이너 객체를 순회하며 해당 컨테이너 객체가 참조하는 다른 객체들의 gc_ref값을 하나씩 줄여나간다.

 

최종적으로 모든 컨테이너 객체를 순회했다면 메모리 회수의 대상이 되지 않는 컨테이너 객체는 gc_ref 값이 0 이상이다. 왜냐하면 동시에 GC의 대상이된 객체들이외에도 외부(다른 세대의 컨테이너 객체들, 스택이나 전역변수 등)에서 그 컨테이너 객체를 참조 중일테니까.

 

만약, 다른 세대의 컨테이너 객체들, 스택, 전역변수에서도 접근할 수 없다면, 그러니까 현재 GC의 대상이된 컨테이너 객체들 간에서만 참조할 수 있다면 gc_ref 값이 0이 될 것이고, 그러면 그 어디에서도 해당 객체에 접근할 수 없다는 뜻이고 결국 GC 대상이될 것이다. 이렇게 순환참조를 잡아내는 것이다.

 

 

모든 컨테이너 객체에 대해서 GC와 순환검출을 조사하면 좋겠지만 그렇기엔 메모리가 한정되어있기도해서 세대를 구분하고 그에 맞춰서 GC의 빈도수를 다르게하는 편이다.

 

 

위 블로그는 아래 게시글과 GPT 내용의 일부를 포함하여 작성되었습니다.

내용오류에 대한 지적은 환영입니다.

https://hajinnote.tistory.com/132

파이썬 가비지 컬렉터

https://www.gdsanadevlog.com/planguages/python/about-python-cpython-%EC%9D%98-garbage-collection-%EC%9D%80-%EC%96%B4%EB%96%BB%EA%B2%8C-%EB%8F%99%EC%9E%91%ED%95%98%EB%8A%94%EA%B0%80/

[Python] – “CPython 의 Garbage Collection 은 어떻게 동작하는가?" - GdsanaDevLog.com