Garbage Collection의 정의와 알고리즘

출처 @Java-Latte: Garbage Collection in Java

메모리 재활용 Garbage Collection을 어떻게 정의할까?

function gc(M) = 다음 프로그램 실행에서 쭉 사용되지 않을 메모리 M의 영역들을 재활용한다그러나 미래에 가보지 않고는 어떤 메모리의 영역들이 실행될 것인지 정확하게 알 수 없다. 그래서 대략 맞는 안전한 장치를 만들어낸다. 

 

이때 이름을 통해서 메모리에 접근한다는 사실을 이용한다. M(E(x)), M(E(x)(age))그리고 현재 Env 환경이 이름에 들어있는 내용을 결정한다. 접근할 수 있는 메모리 영역은 현재 Env 환경에서 접근할 수 있는 영역과 같다. 

 

이런 과정을 통해 fun gc는 다음과 같이 정의한다. fun gc(E, M) = E (Env)에서 접근할 수 있는 부분을 제외하고 M을 재활용한다. 

 

Mark & Sweep

Garbage Collection을 수행하는 알고리즘 중 하나. 

 

Garbage Collection은 두 단계로 나뉘어 수행된다. 

첫번째 단계는 접근 불가능한 메모리 영역을 찾아내는 것이다. 

두번째 단계는 찾아낸 메모리를 모두 재활용하는 것이다.

 

Mark & Sweep 알고리즘에서는 <1> Mark 단계 <2> Sweep 단계에서 각각을 수행한다. 

 

<1> Mark 단계

접근 가능한 메모리에 표식 비트(1, true)를 남긴다. 

메모리를 탐색할 때에는 DFS(Depth-First-Search)를 수행한다. 

 

<2> Sweep 단계

접근 가능하지 않은 모든 메모리 영역을 지운다. 

 

(참고) Mark-and-Sweep: Garbage Collection Algorithm - GeeksforGeeks

Mark-and-Sweep: Garbage Collection Algorithm - GeeksforGeeks