Go언어의 가비지컬렉션 알고리즘

Go언어의 가비지 컬렉션 알고리즘의 핵심이 삼색알고림에 대해 알아보려고 합니다.

먼저 삼색알고리즘에 사용하는 정의 부터 알아 보겠습니다.

흰색 집합: 프로그램에서 더 이상 접근 할 수 없어 가비지 컬렉션이 되는 대상입니다.

검은색 집합: 프로그램이 사용 하고 있으며 흰색 집합의 오브젝트를 가리키는 포인터가 확식히 없는 오브젝트의 집합입니다.

회색 집합: 프로그램이 현재 사용하고 있지만 흰색 오브젝트를 가리키고 있어 검사 과정이 필요한 집합입니다.

Point 검은 색에서 흰색 집합으로 연결 되지 않아 흰색 집합의 오브젝트를 제거 할 수 있습니다.

삼색 알고리즘 Process

initial

    모든 오브젝트가 흰색인 상태

Process

    Step 1

        루트 오브젝트를 방문해서 탐색을 한 후 회색 집합으로 이동 시킨다.

        Root 오브젝트란 스택에 있거나 전역변수와 같이 애플리케이션에서 직접 접근할 수 있는 오브젝트

    Step 2

        회색 오브젝트를 하나씩 뽑아서 검은색으로 바꾸고, 그 오브젝트가 흰색 집합에 있는 오브젝트를 가리키는 포인터가 있는지 탐색 한다.

        흰색 오브젝트를 가르키는 포인터가 있다면 그 흰색 오브젝트를 회색 집합에 넣는다.

terminate

    회색 집합에 오브젝트가 남지 않았을 때 흰색 집합을 비운다.

    비워진 흰색 집합의 오브젝트는 가비지컬렉션이 됐다고 표현한다.

다음은 삼색 알고리즘을 사용해서 가비지 컬렉터가 작동하는 것을 설명 하겠습니다.

표시 후 쓸어 담기 알고리즘(mark -and -sweep algorithm)을 사용하여 가비지 컬렉트를 하는데 이 알고리즘은 프로그램 실행을 잠시 멈추고 프로그램의 힙에서 접급 가능한 오브젝트를 모두 방문한뒤 삼색 알고리즘을 통해 표시를 해두는 간단한 알고리즘입니다.

이 알고리즘은 구현이 간단하지만 단점으로 프로그램에 지연이 발생합니다.

Golang의 가비지 컬렉터는 이를 동시성 프로그래밍으로 처리하지만 컬렉터가 동시에 실행하는 동안에 포인터가 변할 수 있으므로 구현이 까다롭습니다.

이것에 대한 해결책으로 삼색 알고리즘의 불변성으르 유지 하는 것입니다. 새로운 오브젝트를 만나며 이를 회색 집합에 넣으면 회색 집합의 오브젝트가 검정색 집합으로 변하면서 흰색 집합에 있는 오브젝트가 회색으로 변한다는 것을 이용합니다(삼색 알고리즘의 Step2)

이상으로 가비지 컬렉션에 대한 설명을 마치고 다음 포스팅에 unsafe에 대해 포스팅 하겠습니다.